C++
std :: vector

Invoering

Opmerkingen

Een std :: vector initialiseren

Een std::vector kan op verschillende manieren worden geïnitialiseerd terwijl deze wordt gedeclareerd:

std::vector<int> v{ 1, 2, 3 };  // v becomes {1, 2, 3}

// Different from std::vector<int> v(3, 6)
std::vector<int> v{ 3, 6 };     // v becomes {3, 6}

// Different from std::vector<int> v{3, 6} in C++11
std::vector<int> v(3, 6);  // v becomes {6, 6, 6}

std::vector<int> v(4);     // v becomes {0, 0, 0, 0}

Een vector kan op verschillende manieren vanuit een andere container worden geïnitialiseerd:

Kopieer constructie (alleen van een andere vector), die gegevens van v2 kopieert:

std::vector<int> v(v2);
std::vector<int> v = v2;

std::vector<int> v(std::move(v2));
std::vector<int> v = std::move(v2);

Iterator (bereik) kopie-constructie, die elementen kopieert naar v :

// from another vector
std::vector<int> v(v2.begin(), v2.begin() + 3); // v becomes {v2[0], v2[1], v2[2]}

// from an array
int z[] = { 1, 2, 3, 4 };
std::vector<int> v(z, z + 3);                   // v becomes {1, 2, 3}

// from a list
std::list<int> list1{ 1, 2, 3 };
std::vector<int> v(list1.begin(), list1.end()); // v becomes {1, 2, 3}

// from another vector
std::vector<int> v(std::make_move_iterator(v2.begin()),
                   std::make_move_iterator(v2.end());

// from a list
std::list<int> list1{ 1, 2, 3 };
std::vector<int> v(std::make_move_iterator(list1.begin()),
                   std::make_move_iterator(list1.end()));

Met behulp van de member assign() member-functie kan een std::vector na de constructie opnieuw worden geïnitialiseerd:

v.assign(4, 100);                      // v becomes {100, 100, 100, 100}

v.assign(v2.begin(), v2.begin() + 3);  // v becomes {v2[0], v2[1], v2[2]}

int z[] = { 1, 2, 3, 4 };
v.assign(z + 1, z + 4);                // v becomes {2, 3, 4}

Elementen invoegen

Een element toevoegen aan het einde van een vector (door kopiëren / verplaatsen):

struct Point {
  double x, y;
  Point(double x, double y) : x(x), y(y) {}
};
std::vector<Point> v;
Point p(10.0, 2.0);
v.push_back(p);  // p is copied into the vector.

std::vector<Point> v;
v.emplace_back(10.0, 2.0); // The arguments are passed to the constructor of the
                           // given type (here Point). The object is constructed
                           // in the vector, avoiding a copy.

Merk op dat std::vector geen hebben push_front() lid functie te wijten aan de prestaties te verbeteren. Als u aan het begin een element toevoegt, worden alle bestaande elementen in de vector verplaatst. Als u vaak elementen aan het begin van uw container wilt invoegen, kunt u in plaats daarvan std::list of std::deque gebruiken.

Een element invoegen op elke positie van een vector:

std::vector<int> v{ 1, 2, 3 };
v.insert(v.begin(), 9);          // v now contains {9, 1, 2, 3}

std::vector<int> v{ 1, 2, 3 };
v.emplace(v.begin()+1, 9);     // v now contains {1, 9, 2, 3}

Een andere vector invoegen op elke positie van de vector:

std::vector<int> v(4);      // contains: 0, 0, 0, 0
std::vector<int> v2(2, 10); // contains: 10, 10
v.insert(v.begin()+2, v2.begin(), v2.end()); // contains: 0, 0, 10, 10, 0, 0

Een array invoegen op elke positie van een vector:

std::vector<int> v(4); // contains: 0, 0, 0, 0
int a [] = {1, 2, 3}; // contains: 1, 2, 3
v.insert(v.begin()+1, a, a+sizeof(a)/sizeof(a[0])); // contains: 0, 1, 2, 3, 0, 0, 0

Gebruik reserve() voordat u meerdere elementen invoegt als de resulterende vectorgrootte vooraf bekend is om meerdere herallocaties te voorkomen (zie vectorgrootte en capaciteit ):

std::vector<int> v;
v.reserve(100);
for(int i = 0; i < 100; ++i)
    v.emplace_back(i);

Maak in dit geval niet de fout om resize() aan te roepen, anders maakt u per ongeluk een vector met 200 elementen waarvan alleen de laatste honderd de waarde hebben die u bedoelde.

Iterating Over std :: vector

U kunt op verschillende manieren over een std::vector itereren. Voor elk van de volgende secties is v als volgt gedefinieerd:

std::vector<int> v;

Terugkerend in de voorwaartse richting

// Range based for
for(const auto& value: v) {
    std::cout << value << "\n";
}

// Using a for loop with iterator
for(auto it = std::begin(v); it != std::end(v); ++it) {
    std::cout << *it << "\n";
}

// Using for_each algorithm, using a function or functor:
void fun(int const& value) {
    std::cout << value << "\n";
}

std::for_each(std::begin(v), std::end(v), fun);

// Using for_each algorithm. Using a lambda:
std::for_each(std::begin(v), std::end(v), [](int const& value) {
    std::cout << value << "\n";
});

// Using a for loop with iterator
for(std::vector<int>::iterator it = std::begin(v); it != std::end(v); ++it) {
    std::cout << *it << "\n";
}

// Using a for loop with index
for(std::size_t i = 0; i < v.size(); ++i) {
    std::cout << v[i] << "\n";
}

Itererend in omgekeerde richting

// There is no standard way to use range based for for this.
// See below for alternatives.

// Using for_each algorithm
// Note: Using a lambda for clarity. But a function or functor will work
std::for_each(std::rbegin(v), std::rend(v), [](auto const& value) {
    std::cout << value << "\n";
});

// Using a for loop with iterator
for(auto rit = std::rbegin(v); rit != std::rend(v); ++rit) {
    std::cout << *rit << "\n";
}

// Using a for loop with index
for(std::size_t i = 0; i < v.size(); ++i) {
    std::cout << v[v.size() - 1 - i] << "\n";
}

Hoewel er geen ingebouwde manier is om het bereik te gebruiken om iteratie terug te draaien; het is relatief eenvoudig om dit op te lossen. Het bereik dat is gebaseerd op gebruik begin() en end() om iterators te krijgen en dit dus te simuleren met een wrapperobject, kan de gewenste resultaten bereiken.

template<class C>
struct ReverseRange {
  C c; // could be a reference or a copy, if the original was a temporary
  ReverseRange(C&& cin): c(std::forward<C>(cin)) {}
  ReverseRange(ReverseRange&&)=default;
  ReverseRange& operator=(ReverseRange&&)=delete;
  auto begin() const {return std::rbegin(c);}
  auto end()   const {return std::rend(c);}
};
// C is meant to be deduced, and perfect forwarded into
template<class C>
ReverseRange<C> make_ReverseRange(C&& c) {return {std::forward<C>(c)};}

int main() {
    std::vector<int> v { 1,2,3,4};
    for(auto const& value: make_ReverseRange(v)) {
        std::cout << value << "\n";
    }
}

Const-elementen afdwingen

Omdat C ++ 11 de cbegin() en cend() methoden kunt u een constante iterator verkrijgen van een vector, zelfs wanneer de vector niet-const. Met een constante iterator kunt u de inhoud van de vector lezen, maar niet wijzigen, wat handig is om const-correctheid af te dwingen:

// forward iteration
for (auto pos = v.cbegin(); pos != v.cend(); ++pos) {
   // type of pos is vector<T>::const_iterator
   // *pos = 5; // Compile error - can't write via const iterator
}

// reverse iteration
for (auto pos = v.crbegin(); pos != v.crend(); ++pos) {
   // type of pos is vector<T>::const_iterator
   // *pos = 5; // Compile error - can't write via const iterator
}

// expects Functor::operand()(T&) 
for_each(v.begin(), v.end(), Functor());

// expects Functor::operand()(const T&)
for_each(v.cbegin(), v.cend(), Functor())

for (auto const& e : std::as_const(v)) {
  std::cout << e << '\n';
}

Dit is eenvoudig te implementeren in eerdere versies van C ++:

template <class T>
constexpr std::add_const_t<T>& as_const(T& t) noexcept {
  return t;
}

Een opmerking over efficiëntie

Aangezien de klasse std::vector in feite een klasse is die een dynamisch toegewezen aaneengesloten array beheert, is hetzelfde principe dat hier wordt uitgelegd van toepassing op C ++ vectoren. Toegang tot de inhoud van de vector via een index is veel efficiënter bij het volgen van het rij-hoofdorde-principe. Natuurlijk plaatst elke toegang tot de vector ook zijn managementinhoud in de cache, maar zoals vele malen besproken (met name hier en hier ), het verschil in prestaties voor iteratie over een std::vector vergelijking met een onbewerkte array is te verwaarlozen. Hetzelfde efficiëntieprincipe voor onbewerkte arrays in C is dus ook van toepassing op C ++ s std::vector .

Toegang tot elementen

Er zijn twee primaire manieren om toegang te krijgen tot elementen in een std::vector

• op index gebaseerde toegang
• iterators

Op index gebaseerde toegang:

Dit kan worden gedaan met de subscript-operator [] of met de lidfunctie at() .

Beide retourneren een verwijzing naar het element op de respectieve positie in de std::vector (tenzij het een vector<bool> ), zodat het zowel kan worden gelezen als gewijzigd (als de vector niet const ).

[] en at() verschillen in zoverre dat [] niet gegarandeerd is dat er grenzen worden gecontroleerd, terwijl at() doet. Toegang krijgen tot elementen waarbij index < 0 of index >= size een ongedefinieerd gedrag is voor [] , terwijl at() een uitzondering std::out_of_range .

Opmerking: de onderstaande voorbeelden gebruiken C ++ 11-stijl initialisatie voor de duidelijkheid, maar de operatoren kunnen met alle versies worden gebruikt (tenzij gemarkeerd C ++ 11).

std::vector<int> v{ 1, 2, 3 };

// using []
int a = v[1];    // a is 2
v[1] = 4;        // v now contains { 1, 4, 3 }

// using at()
int b = v.at(2); // b is 3
v.at(2) = 5;     // v now contains { 1, 4, 5 }
int c = v.at(3); // throws std::out_of_range exception

Omdat de methode at() grenzen controleert en uitzonderingen kan genereren, is deze langzamer dan [] . Dit maakt de voorkeurscode [] waar de semantiek van de bewerking garandeert dat de index binnen de perken is. In elk geval worden toegangen tot elementen van vectoren in constante tijd uitgevoerd. Dat betekent dat toegang tot het eerste element van de vector dezelfde kosten (in de tijd) heeft voor toegang tot het tweede element, het derde element enzovoort.

Overweeg bijvoorbeeld deze lus

for (std::size_t i = 0; i < v.size(); ++i) {
    v[i] = 1;
}

Hier weten we dat de indexvariabele i altijd binnen de perken is, dus het zou zonde zijn van CPU-cycli om te controleren of i binnen de perken zit voor elke aanroep van operator[] .

De functies voor front() en back() maken eenvoudige referentietoegang mogelijk tot respectievelijk het eerste en laatste element van de vector. Deze posities worden vaak gebruikt en de speciale accessors kunnen beter leesbaar zijn dan hun alternatieven met [] :

std::vector<int> v{ 4, 5, 6 }; // In pre-C++11 this is more verbose

int a = v.front();   // a is 4, v.front() is equivalent to v[0]
v.front() = 3;       // v now contains {3, 5, 6}
int b = v.back();    // b is 6, v.back() is equivalent to v[v.size() - 1]
v.back() = 7;        // v now contains {3, 5, 7}

Opmerking : het is ongedefinieerd gedrag om front() of back() op een lege vector aan te roepen. U moet controleren of de container niet leeg is met behulp van de functie empty() (die controleert of de container leeg is) voordat u front() of back() . Een eenvoudig voorbeeld van het gebruik van 'empty ()' om te testen op een lege vector volgt:

int main ()
{
  std::vector<int> v;
  int sum (0);

  for (int i=1;i<=10;i++) v.push_back(i);//create and initialize the vector

  while (!v.empty())//loop through until the vector tests to be empty
  {
     sum += v.back();//keep a running total
     v.pop_back();//pop out the element which removes it from the vector
  }

  std::cout << "total: " << sum << '\n';//output the total to the user

  return 0;
}

In het bovenstaande voorbeeld wordt een vector gemaakt met een reeks getallen van 1 tot 10. Vervolgens worden de elementen van de vector eruit getrokken totdat de vector leeg is (met 'empty ()') om ongedefinieerd gedrag te voorkomen. Vervolgens wordt de som van de getallen in de vector berekend en aan de gebruiker weergegeven.

std::vector<int> v{ 1, 2, 3, 4 }; // v contains {1, 2, 3, 4}
int* p = v.data(); // p points to 1
*p = 4;            // v now contains {4, 2, 3, 4}
++p;               // p points to 2
*p = 3;            // v now contains {4, 3, 3, 4}
p[1] = 2;          // v now contains {4, 3, 2, 4}
*(p + 2) = 1;      // v now contains {4, 3, 2, 1}

std::vector<int> v(4);
int* ptr = &(v.front()); // or &v[0]

iterators:

Iterators worden in meer detail uitgelegd in het voorbeeld "Iterating over std::vector " en het artikel Iterators . Kortom, ze werken op dezelfde manier als verwijzingen naar de elementen van de vector:

std::vector<int> v{ 4, 5, 6 };

auto it = v.begin();
int i = *it;        // i is 4
++it; 
i = *it;            // i is 5
*it = 6;            // v contains { 4, 6, 6 }
auto e = v.end();   // e points to the element after the end of v. It can be 
                    // used to check whether an iterator reached the end of the vector:
++it; 
it == v.end();      // false, it points to the element at position 2 (with value 6)
++it;
it == v.end();      // true

Het is in overeenstemming met de standaard die een std::vector<T> 's iteratoren eigenlijk T* s, maar de meeste standaard bibliotheken doen dit niet. Als u dit niet doet, verbetert dit zowel foutmeldingen, vangt niet-draagbare code en kan het worden gebruikt om iterators te voorzien van debug-controles in builds die niet zijn vrijgegeven. Vervolgens wordt de release van de klasse rond de onderliggende aanwijzer geoptimaliseerd.

U kunt een verwijzing of een aanwijzer naar een element van een vector behouden voor indirecte toegang. Deze verwijzingen of verwijzingen naar elementen in de vector blijven stabiel en de toegang blijft gedefinieerd, tenzij u elementen toevoegt / verwijdert bij of vóór het element in de vector of u ervoor zorgt dat de vector verandert. Dit is hetzelfde als de regel voor het ongeldig maken van iterators.

std::vector<int> v{ 1, 2, 3 };
int* p = v.data() + 1;     // p points to 2
v.insert(v.begin(), 0);    // p is now invalid, accessing *p is a undefined behavior.
p = v.data() + 1;          // p points to 1
v.reserve(10);             // p is now invalid, accessing *p is a undefined behavior.
p = v.data() + 1;          // p points to 1
v.erase(v.begin());        // p is now invalid, accessing *p is a undefined behavior.

Std :: vector gebruiken als een C-array

Er zijn verschillende manieren om een std::vector als een C-array te gebruiken (bijvoorbeeld voor compatibiliteit met C-bibliotheken). Dit is mogelijk omdat de elementen in een vector aaneengesloten worden opgeslagen.

std::vector<int> v{ 1, 2, 3 };
int* p = v.data();

Vóór C ++ 11 zou u het adres van het eerste element van de vector nemen om een equivalente pointer te krijgen, als de vector niet leeg is, zijn deze beide methoden uitwisselbaar:

int* p = &v[0];      // combine subscript operator and 0 literal

int* p = &v.front(); // explicitly reference the first element

Opmerking: Als de vector leeg is, zijn v[0] en v.front() niet gedefinieerd en kunnen niet worden gebruikt.

push_back bij het opslaan van het basisadres van de gegevens van de vector rekening mee dat veel bewerkingen (zoals push_back , resize , etc.) de locatie van het gegevensgeheugen van de vector kunnen wijzigen, waardoor eerdere gegevenswijzers ongeldig worden . Bijvoorbeeld:

std::vector<int> v;
int* p = v.data();
v.resize(42);      // internal memory location changed; value of p is now invalid

Iterator / aanwijzer ongeldig

Iterators en pointers die naar een std::vector wijzen, kunnen ongeldig worden, maar alleen bij bepaalde bewerkingen. Het gebruik van ongeldige iterators / pointers leidt tot ongedefinieerd gedrag.

Bewerkingen die iterators / pointers ongeldig maken, zijn onder meer:

• Elke invoegbewerking die de capacity van de vector wijzigt, maakt alle iterators / pointers ongeldig:

  vector<int> v(5); // Vector has a size of 5; capacity is unknown.
  int *p1 = &v[0];
  v.push_back(2);   // p1 may have been invalidated, since the capacity was unknown.
  
  v.reserve(20);    // Capacity is now at least 20.
  int *p2 = &v[0];
  v.push_back(4);   // p2 is *not* invalidated, since the size of `v` is now 7.
  v.insert(v.end(), 30, 9); // Inserts 30 elements at the end. The size exceeds the
                            // requested capacity of 20, so `p2` is (probably) invalidated.
  int *p3 = &v[0];
  v.reserve(v.capacity() + 20); // Capacity exceeded, thus `p3` is invalid.
  

auto old_cap = v.capacity();
v.shrink_to_fit();
if(old_cap != v.capacity())
    // Iterators were invalidated.

• Elke invoegbewerking, die de capaciteit niet verhoogt, maakt iterators / aanwijzers die naar elementen op de invoegpositie wijzen en passeren nog steeds ongeldig. Dit geldt ook voor het end iterator:

  vector<int> v(5);
  v.reserve(20);                 // Capacity is at least 20.
  int *p1 = &v[0];
  int *p2 = &v[3];
  v.insert(v.begin() + 2, 5, 0); // `p2` is invalidated, but since the capacity
                                 // did not change, `p1` remains valid.
  int *p3 = &v[v.size() - 1];
  v.push_back(10); // The capacity did not change, so `p3` and `p1` remain valid.
  

• Elke verwijderingsbewerking maakt iterators / pointers ongeldig die naar de verwijderde elementen en naar alle elementen voorbij de verwijderde elementen wijzen. Dit geldt ook voor het end iterator:

  vector<int> v(10);
  int *p1 = &v[0];
  int *p2 = &v[5];
  v.erase(v.begin() + 3, v.end()); // `p2` is invalid, but `p1` remains valid.
  

• operator= (kopiëren, verplaatsen of anderszins) en clear() maakt alle iterators / verwijzingen naar de vector ongeldig.

Elementen verwijderen

Het laatste element verwijderen:

std::vector<int> v{ 1, 2, 3 };
v.pop_back();                           // v becomes {1, 2}

Alle elementen verwijderen:

std::vector<int> v{ 1, 2, 3 };
v.clear();                              // v becomes an empty vector

Element verwijderen op index:

std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
v.erase(v.begin() + 3);                 // v becomes {1, 2, 3, 5, 6}

Opmerking: voor een vector een element verwijdert dat niet het laatste element is, moeten alle elementen voorbij het verwijderde element worden gekopieerd of verplaatst om het gat te vullen, zie de opmerking hieronder en std :: lijst .

Alle elementen in een bereik verwijderen:

std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
v.erase(v.begin() + 1, v.begin() + 5);  // v becomes {1, 6}

Opmerking: De bovenstaande methoden veranderen niet de capaciteit van de vector, alleen de grootte. Zie Vectorgrootte en capaciteit .

De erase , die een reeks elementen verwijdert, wordt vaak gebruikt als onderdeel van het wis-verwijder- idioom. Dat wil zeggen, eerste std::remove verplaatst enkele elementen naar het einde van de vector en erase deze dan te erase . Dit is een relatief inefficiënte bewerking voor alle indices die kleiner zijn dan de laatste index van de vector omdat alle elementen na de gewiste segmenten naar nieuwe posities moeten worden verplaatst. Zie std :: list voor snelheidskritieke toepassingen die efficiënte verwijdering van willekeurige elementen in een container vereisen.

Elementen verwijderen op waarde:

std::vector<int> v{ 1, 1, 2, 2, 3, 3 };
int value_to_remove = 2;
v.erase(std::remove(v.begin(), v.end(), value_to_remove), v.end()); // v becomes {1, 1, 3, 3}

Elementen verwijderen op voorwaarde:

// std::remove_if needs a function, that takes a vector element as argument and returns true, 
// if the element shall be removed
bool _predicate(const int& element) {
    return (element > 3); // This will cause all elements to be deleted that are larger than 3
}
...
std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
v.erase(std::remove_if(v.begin(), v.end(), _predicate), v.end()); // v becomes {1, 2, 3}

Elementen verwijderen door lambda, zonder extra predicaatfunctie te creëren

std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
v.erase(std::remove_if(v.begin(), v.end(),
     [](auto& element){return element > 3;} ), v.end()
);

Elementen op voorwaarde uit een lus verwijderen:

std::vector<int> v{ 1, 2, 3, 4, 5, 6 };
std::vector<int>::iterator it = v.begin();
while (it != v.end()) {
    if (condition)
        it = v.erase(it); // after erasing, 'it' will be set to the next element in v
    else
        ++it;             // manually set 'it' to the next element in v
}

Hoewel het belangrijk is om it niet te verhogen in het geval van een verwijdering, moet u overwegen een andere methode te gebruiken wanneer u vervolgens herhaaldelijk in een lus wist. Overweeg remove_if voor een efficiëntere manier.

Elementen verwijderen op voorwaarde uit een omgekeerde lus:

std::vector<int> v{ -1, 0, 1, 2, 3, 4, 5, 6 };
typedef std::vector<int>::reverse_iterator rev_itr;
rev_itr it = v.rbegin();

while (it != v.rend()) { // after the loop only '0' will be in v
    int value = *it;
    if (value) {
        ++it;
        // See explanation below for the following line.
        it = rev_itr(v.erase(it.base()));
    } else
        ++it;
}

Let op enkele punten voor de voorgaande lus:

• Bij een omgekeerde iterator it wijzen op een element, waarbij de werkwijze base geeft reguliere (niet-omgekeerde) iterator wijst naar hetzelfde element.

• vector::erase(iterator) wist het element waarnaar een iterator verwijst en retourneert een iterator naar het element dat het gegeven element volgde.

• reverse_iterator::reverse_iterator(iterator) construeert een reverse iterator van een iterator.

Zet geheel, de lijn it = rev_itr(v.erase(it.base())) zegt: neem de omgekeerde iterator it hebben v wis aangewezen element door zijn regelmatige iterator; Neem de verkregen repeater, construct een omgekeerde iterator ervan, en toewijzen aan de keerzijde iterator it .

Het verwijderen van alle elementen met v.clear() maakt geen geheugen vrij ( capacity() van de vector blijft ongewijzigd). Om ruimte vrij te maken, gebruik:

std::vector<int>().swap(v);

v.shrink_to_fit();

De shrink_to_fit kan niet garanderen dat er echt ruimte wordt shrink_to_fit , maar de meeste huidige implementaties wel.

Een element zoeken in std :: vector

De functie std::find , gedefinieerd in de kop <algorithm> , kan worden gebruikt om een element in een std::vector .

std::find gebruikt de operator== om elementen voor gelijkheid te vergelijken. Het retourneert een iterator naar het eerste element in het bereik dat gelijk is aan de waarde.

Als het betreffende element niet wordt gevonden, retourneert std::find std::vector::end (of std::vector::cend als de vector const ).

static const int arr[] = {5, 4, 3, 2, 1};
std::vector<int> v (arr, arr + sizeof(arr) / sizeof(arr[0]) );

std::vector<int>::iterator it = std::find(v.begin(), v.end(), 4);
std::vector<int>::difference_type index = std::distance(v.begin(), it);
// `it` points to the second element of the vector, `index` is 1

std::vector<int>::iterator missing = std::find(v.begin(), v.end(), 10);
std::vector<int>::difference_type index_missing = std::distance(v.begin(), missing);
// `missing` is v.end(), `index_missing` is 5 (ie. size of the vector)

std::vector<int> v { 5, 4, 3, 2, 1 };

auto it = std::find(v.begin(), v.end(), 4);
auto index = std::distance(v.begin(), it);
// `it` points to the second element of the vector, `index` is 1

auto missing = std::find(v.begin(), v.end(), 10);
auto index_missing = std::distance(v.begin(), missing);
// `missing` is v.end(), `index_missing` is 5 (ie. size of the vector)

Als u veel zoekopdrachten in een grote vector moet uitvoeren, kunt u overwegen de vector eerst te sorteren voordat u het binary_search algoritme gebruikt.

Om het eerste element in een vector te vinden dat aan een voorwaarde voldoet, kan std::find_if worden gebruikt. Naast de twee parameters die aan std::find , accepteert std::find_if een derde argument dat een functieobject of functiepointer is naar een predikaatfunctie. Het predicaat moet een element uit de container als argument accepteren en een waarde teruggeven die converteerbaar is naar bool , zonder de container te wijzigen:

bool isEven(int val) {
    return (val % 2 == 0); 
}

struct moreThan {
    moreThan(int limit) : _limit(limit) {}
    
    bool operator()(int val) {
        return val > _limit;
    }
    
    int _limit;
};

static const int arr[] = {1, 3, 7, 8};
std::vector<int> v (arr, arr + sizeof(arr) / sizeof(arr[0]) );
    
std::vector<int>::iterator it = std::find_if(v.begin(), v.end(), isEven);
// `it` points to 8, the first even element

std::vector<int>::iterator missing = std::find_if(v.begin(), v.end(), moreThan(10));
// `missing` is v.end(), as no element is greater than 10

// find the first value that is even
std::vector<int> v = {1, 3, 7, 8};
auto it = std::find_if(v.begin(), v.end(), [](int val){return val % 2 == 0;});
// `it` points to 8, the first even element

auto missing = std::find_if(v.begin(), v.end(), [](int val){return val > 10;});
// `missing` is v.end(), as no element is greater than 10

Een array converteren naar std :: vector

Een array kan eenvoudig worden omgezet in een std::vector met std::begin en std::end :

int values[5] = { 1, 2, 3, 4, 5 }; // source array

std::vector<int> v(std::begin(values), std::end(values)); // copy array to new vector

for(auto &x: v)
    std::cout << x << " ";
std::cout << std::endl;

int main(int argc, char* argv[]) {
    // convert main arguments into a vector of strings.
    std::vector<std::string>  args(argv, argv + argc);
}

Een C ++ 11 initializer_list <> kan ook worden gebruikt om de vector in één keer te initialiseren

initializer_list<int> arr = { 1,2,3,4,5 };
vector<int> vec1 {arr};

for (auto & i : vec1)
    cout << i << endl;

vector : De uitzondering voor zoveel, zoveel regels

De standaard (paragraaf 23.3.7) specificeert dat een specialisatie van vector<bool> wordt verschaft, die de ruimte optimaliseert door de bool in te pakken, zodat elk slechts één bit in beslag neemt. Omdat bits niet adresseerbaar zijn in C ++, betekent dit dat verschillende vereisten voor vector niet op vector<bool> :

• De opgeslagen gegevens hoeven niet aaneengesloten te zijn, dus een vector<bool> kan niet worden doorgegeven aan een C API die een bool array verwacht.
• at() , operator [] en dereferencing van iterators retourneren geen verwijzing naar bool . In plaats daarvan retourneren ze een proxy-object dat (imperfect) een verwijzing naar een bool simuleert door de toewijzingsoperators te overbelasten. De volgende code is bijvoorbeeld mogelijk niet geldig voor std::vector<bool> , omdat het verwijderen van een iterator geen verwijzing retourneert:

std::vector<bool> v = {true, false};
for (auto &b: v) { } // error

Evenzo kunnen functies die een bool& argument verwachten niet worden gebruikt met het resultaat van operator [] of at() toegepast op vector<bool> , of met het resultaat van het verwijderen van de iterator:

  void f(bool& b);
  f(v[0]);             // error
  f(*v.begin());       // error

De implementatie van std::vector<bool> is afhankelijk van zowel de compiler als de architectuur. De specialisatie wordt geïmplementeerd door n Booleans in het laagst adresseerbare gedeelte van het geheugen te verpakken. Hier is n de grootte in bits van het laagst adresseerbare geheugen. In de meeste moderne systemen is dit 1 byte of 8 bits. Dit betekent dat één byte 8 Booleaanse waarden kan opslaan. Dit is een verbetering ten opzichte van de traditionele implementatie waarbij 1 Booleaanse waarde wordt opgeslagen in 1 byte geheugen.

Opmerking: het onderstaande voorbeeld toont mogelijke bitgewijze waarden van afzonderlijke bytes in een traditionele versus geoptimaliseerde vector<bool> . Dit zal niet altijd in alle architecturen gelden. Het is echter een goede manier om de optimalisatie te visualiseren. In de onderstaande voorbeelden wordt een byte weergegeven als [x, x, x, x, x, x, x, x].

Traditionele std::vector<char> 8 Booleaanse waarden:

std::vector<char> trad_vect = {true, false, false, false, true, false, true, true};

Bitgewijze weergave:

[0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], 
[0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,1]

Gespecialiseerde std::vector<bool> 8 Booleaanse waarden:

std::vector<bool> optimized_vect = {true, false, false, false, true, false, true, true};

Bitgewijze weergave:

[1,0,0,0,1,0,1,1]

Merk in het bovenstaande voorbeeld op dat in de traditionele versie van std::vector<bool> , 8 Booleaanse waarden 8 bytes geheugen innemen, terwijl ze in de geoptimaliseerde versie van std::vector<bool> slechts 1 byte gebruiken van geheugen. Dit is een aanzienlijke verbetering van het geheugengebruik. Als u een vector<bool> moet doorgeven aan een API in C-stijl, moet u mogelijk de waarden naar een array kopiëren of een betere manier vinden om de API te gebruiken als geheugen en prestaties gevaar lopen.

Vectorgrootte en capaciteit

Vector grootte is gewoon het aantal elementen in de vector:

1. Stroomvector maat is opgevraagd door size() lid functie. Gemak empty() functie geeft true terug als grootte 0 is:

   vector<int> v = { 1, 2, 3 }; // size is 3
   const vector<int>::size_type size = v.size();
   cout << size << endl; // prints 3
   cout << boolalpha << v.empty() << endl; // prints false
   

2. Standaard geconstrueerde vector begint met een grootte van 0:

   vector<int> v; // size is 0
   cout << v.size() << endl; // prints 0
   

3. Het toevoegen van N elementen aan vector vergroot de grootte met N (bijv. Door push_back() , insert() of resize() functies).

4. Als u N elementen uit de vector verwijdert, neemt de grootte af met N (bijv. Door pop_back() , erase() of clear() functies).

5. Vector heeft een implementatiespecifieke bovenlimiet voor de grootte, maar het is waarschijnlijk dat het RAM-geheugen vol raakt voordat het wordt bereikt:

   vector<int> v;
   const vector<int>::size_type max_size = v.max_size();
   cout << max_size << endl; // prints some large number
   v.resize( max_size ); // probably won't work
   v.push_back( 1 ); // definitely won't work
   

Veelgemaakte fout: grootte is niet noodzakelijk (of zelfs meestal) int :

// !!!bad!!!evil!!!
vector<int> v_bad( N, 1 ); // constructs large N size vector
for( int i = 0; i < v_bad.size(); ++i ) { // size is not supposed to be int!
    do_something( v_bad[i] );
}

Vectorcapaciteit verschilt van grootte . Hoewel de grootte eenvoudig is hoeveel elementen de vector momenteel heeft, is de capaciteit voor hoeveel elementen het geheugen is toegewezen / gereserveerd. Dat is handig, omdat te frequente (her) toewijzingen van te grote formaten duur kunnen zijn.

1. Huidige vector capaciteit wordt opgevraagd door capacity() lid functie. Capaciteit is altijd groter of gelijk aan grootte :

   vector<int> v = { 1, 2, 3 }; // size is 3, capacity is >= 3
   const vector<int>::size_type capacity = v.capacity();
   cout << capacity << endl; // prints number >= 3
   

2. U kunt capaciteit handmatig reserveren via reserve( N ) functie (het verandert de vectorcapaciteit in N ):

   // !!!bad!!!evil!!!
   vector<int> v_bad;
   for( int i = 0; i < 10000; ++i ) {
       v_bad.push_back( i ); // possibly lot of reallocations
   }
   
   // good
   vector<int> v_good;
   v_good.reserve( 10000 ); // good! only one allocation
   for( int i = 0; i < 10000; ++i ) {
       v_good.push_back( i ); // no allocations needed anymore
   }
   

3. U kunt verzoeken om de overtollige capaciteit vrij te geven door shrink_to_fit() (maar de implementatie hoeft u niet te gehoorzamen). Dit is handig om het gebruikte geheugen te behouden:

   vector<int> v = { 1, 2, 3, 4, 5 }; // size is 5, assume capacity is 6
   v.shrink_to_fit(); // capacity is 5 (or possibly still 6)
   cout << boolalpha << v.capacity() == v.size() << endl; // prints likely true (but possibly false)
   

Vector beheert de capaciteit gedeeltelijk automatisch, wanneer u elementen toevoegt, kan het besluiten om te groeien. Implementers gebruiken graag 2 of 1,5 voor de groeifactor (gulden snede zou de ideale waarde zijn - maar is onpraktisch vanwege het rationele aantal). Aan de andere kant krimpt vector meestal niet automatisch. Bijvoorbeeld:

vector<int> v; // capacity is possibly (but not guaranteed) to be 0
v.push_back( 1 ); // capacity is some starter value, likely 1
v.clear(); // size is 0 but capacity is still same as before!

v = { 1, 2, 3, 4 }; // size is 4, and lets assume capacity is 4.
v.push_back( 5 ); // capacity grows - let's assume it grows to 6 (1.5 factor)
v.push_back( 6 ); // no change in capacity
v.push_back( 7 ); // capacity grows - let's assume it grows to 9 (1.5 factor)
// and so on
v.pop_back(); v.pop_back(); v.pop_back(); v.pop_back(); // capacity stays the same

Vectoren samenvoegen

Een std::vector kan aan een andere worden toegevoegd met behulp van de lidfunctie insert() :

std::vector<int> a = {0, 1, 2, 3, 4};
std::vector<int> b = {5, 6, 7, 8, 9};

a.insert(a.end(), b.begin(), b.end());

Deze oplossing mislukt echter als u probeert een vector aan zichzelf toe te voegen, omdat de standaard opgeeft dat iterators die worden gegeven aan insert() niet uit hetzelfde bereik moeten komen als de elementen van het ontvangerobject.

a.insert(std::end(a), std::begin(b), std::end(b));

Als de volgorde van de elementen in de ontvangende vector er niet toe doet, kan het overwegen van het aantal elementen in elke vector onnodige kopieerbewerkingen voorkomen:

if (b.size() < a.size())
  a.insert(a.end(), b.begin(), b.end());
else
  b.insert(b.end(), a.begin(), a.end());

De capaciteit van een vector verminderen

Een std::vector verhoogt automatisch de capaciteit bij het inbrengen indien nodig, maar vermindert nooit de capaciteit na verwijdering van het element.

// Initialize a vector with 100 elements
std::vector<int> v(100);

// The vector's capacity is always at least as large as its size
auto const old_capacity = v.capacity();
// old_capacity >= 100

// Remove half of the elements
v.erase(v.begin() + 50, v.end());  // Reduces the size from 100 to 50 (v.size() == 50),
                                   // but not the capacity (v.capacity() == old_capacity)

Om de capaciteit te verminderen, kunnen we de inhoud van een vector naar een nieuwe tijdelijke vector kopiëren. De nieuwe vector heeft de minimale capaciteit die nodig is om alle elementen van de originele vector op te slaan. Als de verkleining van de originele vector aanzienlijk was, dan is de capaciteitsvermindering voor de nieuwe vector waarschijnlijk aanzienlijk. We kunnen dan de originele vector verwisselen met de tijdelijke om de geminimaliseerde capaciteit te behouden:

std::vector<int>(v).swap(v);

v.shrink_to_fit();

Een gesorteerde vector gebruiken om snel elementen op te zoeken

De kop <algorithm> biedt een aantal handige functies voor het werken met gesorteerde vectoren.

Een belangrijke voorwaarde voor het werken met gesorteerde vectoren is dat de opgeslagen waarden vergelijkbaar zijn met < .

Een ongesorteerde vector kan worden gesorteerd met de functie std::sort() :

std::vector<int> v;
// add some code here to fill v with some elements
std::sort(v.begin(), v.end());

Gesorteerde vectoren maken efficiënt zoeken van elementen mogelijk met behulp van de functie std::lower_bound() . In tegenstelling tot std::find() voert dit een efficiënte binaire zoekopdracht uit op de vector. Het nadeel is dat het alleen geldige resultaten geeft voor gesorteerde invoerbereiken:

// search the vector for the first element with value 42
std::vector<int>::iterator it = std::lower_bound(v.begin(), v.end(), 42);
if (it != v.end() && *it == 42) {
    // we found the element!
}

Opmerking: Als de gevraagde waarde geen deel uitmaakt van de vector, std::lower_bound() een iterator naar het eerste element dat groter is dan de gevraagde waarde. Met dit gedrag kunnen we een nieuw element op de juiste plaats in een reeds gesorteerde vector invoegen:

int const new_element = 33;
v.insert(std::lower_bound(v.begin(), v.end(), new_element), new_element);

Als u veel elementen tegelijk moet invoegen, is het wellicht efficiënter om eerst push_back() voor alle elementen aan te roepen en vervolgens std::sort() roepen zodra alle elementen zijn ingevoegd. In dit geval kunnen de verhoogde sorteerkosten zich terugbetalen tegen de lagere kosten voor het invoegen van nieuwe elementen aan het einde van de vector en niet in het midden.

Als uw vector meerdere elementen van dezelfde waarde bevat, zal std::lower_bound() proberen een iterator terug te brengen naar het eerste element van de gezochte waarde. Als u echter een nieuw element na het laatste element van de gezochte waarde moet invoegen, moet u de functie std::upper_bound() omdat hierdoor minder verschuivingen van elementen std::upper_bound() :

v.insert(std::upper_bound(v.begin(), v.end(), new_element), new_element);

Als u zowel de bovengrens als de ondergrens iterators nodig hebt, kunt u de functie std::equal_range() gebruiken om beide efficiënt met één aanroep op te halen:

std::pair<std::vector<int>::iterator,
          std::vector<int>::iterator> rg = std::equal_range(v.begin(), v.end(), 42);
std::vector<int>::iterator lower_bound = rg.first;
std::vector<int>::iterator upper_bound = rg.second;

Om te testen of een element bestaat in een gesorteerde vector (hoewel niet specifiek voor vectoren), kunt u de functie std::binary_search() :

bool exists = std::binary_search(v.begin(), v.end(), value_to_find);

Functies die grote vectoren retourneren

#include <vector>
#include <iostream>

// If the compiler is unable to perform named return value optimization (NRVO)
// and elide the move altogether, it is required to move from v into the return value.
std::vector<int> fillVector(int a, int b) {
    std::vector<int> v;
    v.reserve(b-a+1);
    for (int i = a; i <= b; i++) {
        v.push_back(i);
    }
    return v; // implicit move
}

int main() { // declare and fill vector
    std::vector<int> vec = fillVector(1, 10);

    // print vector
    for (auto value : vec)
        std::cout << value << " "; // this will print "1 2 3 4 5 6 7 8 9 10 "

    std::cout << std::endl;

    return 0;
}

#include <vector>
#include <iostream>

// passing a std::vector by reference
void fillVectorFrom_By_Ref(int a, int b, std::vector<int> &v) {
    assert(v.empty());
    v.reserve(b-a+1);
    for (int i = a; i <= b; i++) {
        v.push_back(i);
    }
}

int main() {// declare vector
    std::vector<int> vec;
    
    // fill vector
    fillVectorFrom_By_Ref(1, 10, vec);
    // print vector
    for (std::vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it)
        std::cout << *it << " "; // this will print "1 2 3 4 5 6 7 8 9 10 "
    std::cout << std::endl;
    return 0;
}

Vind max en min element- en respectieve index in een vector

Om het grootste of kleinste element te vinden dat in een vector is opgeslagen, kunt u respectievelijk de methoden std::max_element en std::min_element gebruiken. Deze methoden worden gedefinieerd in de kop <algorithm> . Als meerdere elementen equivalent zijn aan het grootste (kleinste) element, retourneren de methoden de iterator naar het eerste dergelijke element. Retourneer v.end() voor lege vectoren.

std::vector<int> v = {5, 2, 8, 10, 9}; 
int maxElementIndex = std::max_element(v.begin(),v.end()) - v.begin();
int maxElement = *std::max_element(v.begin(), v.end());

int minElementIndex = std::min_element(v.begin(),v.end()) - v.begin();
int minElement = *std::min_element(v.begin(), v.end());

std::cout << "maxElementIndex:" << maxElementIndex << ", maxElement:" << maxElement << '\n';
std::cout << "minElementIndex:" << minElementIndex << ", minElement:" << minElement << '\n';

Output:

maxElementIndex: 3, maxElement: 10
minElementIndex: 1, minElement: 2

std::vector<int> v = {5, 2, 8, 10, 9}; 
auto minmax = std::minmax_element(v.begin(), v.end());

std::cout << "minimum element: " << *minmax.first << '\n';
std::cout << "maximum element: " << *minmax.second << '\n';

Matrices die vectoren gebruiken

Vectoren kunnen worden gebruikt als een 2D-matrix door ze te definiëren als een vector van vectoren.

Een matrix met 3 rijen en 4 kolommen met elke cel geïnitialiseerd als 0 kan worden gedefinieerd als:

std::vector<std::vector<int> > matrix(3, std::vector<int>(4));

  std::vector<std::vector<int>> matrix = { {0,1,2,3},
                                           {4,5,6,7}, 
                                           {8,9,10,11}
                                         };

Waarden in een dergelijke vector zijn vergelijkbaar met een 2D-array

int var = matrix[0][2];

Itereren over de gehele matrix is vergelijkbaar met die van een normale vector maar met een extra dimensie.

for(int i = 0; i < 3; ++i)
{
    for(int j = 0; j < 4; ++j)
    {
        std::cout << matrix[i][j] << std::endl;
    }
}

for(auto& row: matrix)
{
    for(auto& col : row)
    { 
        std::cout << col << std::endl;
    }
}

Een vector van vectoren is een handige manier om een matrix weer te geven, maar het is niet de meest efficiënte: afzonderlijke vectoren zijn verspreid over het geheugen en de gegevensstructuur is niet cache-vriendelijk.

Ook moet in een juiste matrix de lengte van elke rij hetzelfde zijn (dit is niet het geval voor een vector van vectoren). De extra flexibiliteit kan een bron van fouten zijn.