C++
std :: vector

Einführung

Bemerkungen

Initialisieren eines std :: -Vektors

Ein std::vector kann auf verschiedene Weise initialisiert werden, während er deklariert wird:

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}

Ein Vektor kann auf verschiedene Weise aus einem anderen Container initialisiert werden:

Kopieren Sie die Konstruktion (nur von einem anderen Vektor), um Daten aus v2 kopieren:

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 (Bereich) Kopierkonstruktion, die Elemente in v kopiert:

// 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()));

Ein std::vector kann nach seiner Konstruktion mit Hilfe der Mitgliedsfunktion assign() erneut initialisiert werden:

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}

Elemente einfügen

Ein Element am Ende eines Vektors anhängen (durch Kopieren / Verschieben):

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.

Beachten Sie, dass std::vector Performancegründen keine push_front() . Durch das Hinzufügen eines Elements am Anfang werden alle im Vektor vorhandenen Elemente verschoben. Wenn Sie häufig Elemente am Anfang Ihres Containers einfügen möchten, können Sie stattdessen std::list oder std::deque verwenden.

Einfügen eines Elements an einer beliebigen Position eines Vektors:

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}

Einfügen eines anderen Vektors an einer beliebigen Position des Vektors:

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

Einfügen eines Arrays an einer beliebigen Position eines Vektors:

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

Verwenden Sie reserve() bevor Sie mehrere Elemente einfügen, wenn die resultierende Vektorgröße vorher bekannt ist, um Mehrfachzuweisungen zu vermeiden (siehe Vektorgröße und -kapazität ):

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

Stellen Sie sicher, dass Sie in diesem Fall nicht den Fehler machen, resize() aufzurufen. resize() erstellen Sie versehentlich einen Vektor mit 200 Elementen, bei dem nur die letzten 100 den gewünschten Wert haben.

Iteration über std :: vector

Sie können einen std::vector auf verschiedene Arten durchlaufen. Für jeden der folgenden Abschnitte ist v wie folgt definiert:

std::vector<int> v;

Iteration in Vorwärtsrichtung

// 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";
}

Iteration in umgekehrter Richtung

// 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";
}

Es gibt zwar keine integrierte Methode, um den Bereich für die Iteration umzukehren. es ist relativ einfach, dies zu beheben. Der Bereich für die Verwendungszwecke begin() und end() , um Iteratoren zu erhalten, und die Simulation dieser Werte mit einem Wrapper-Objekt kann die von uns benötigten Ergebnisse erzielen.

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";
    }
}

Erzwingen von const-Elementen

Seit C ++ 11 können Sie mit den cbegin() und cend() einen konstanten Iterator für einen Vektor erhalten, auch wenn der Vektor nicht konstant ist. Mit einem konstanten Iterator können Sie den Inhalt des Vektors lesen, aber nicht modifizieren. Dies ist nützlich, um die const-Korrektheit zu erzwingen:

// 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';
}

Dies ist in früheren Versionen von C ++ leicht zu implementieren:

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

Ein Hinweis zur Effizienz

Da die Klasse std::vector im Grunde eine Klasse ist, die ein dynamisch zugewiesenes zusammenhängendes Array verwaltet, gilt das gleiche Prinzip, das hier erläutert wird , auch für C ++ - Vektoren. Der Zugriff auf den Inhalt des Vektors nach Index ist viel effizienter, wenn das Prinzip der Reihenhauptordnung angewendet wird. Natürlich fügt jeder Zugriff auf den Vektor auch seinen Verwaltungsinhalt in den Cache ein. Wie jedoch oft diskutiert wurde (insbesondere hier und hier ), ist der Leistungsunterschied beim Durchlaufen eines std::vector Vergleich zu einem rohen Array Ist vernachlässigbar. Das gleiche Prinzip der Effizienz für unformatierte Arrays in C gilt also auch für C ++ s std::vector .

Zugriff auf Elemente

Es gibt zwei Möglichkeiten, auf Elemente in einem std::vector zuzugreifen

• Indexbasierter Zugriff
• Iteratoren

Indexbasierter Zugriff:

Dies kann entweder mit dem Indexoperator [] oder der Memberfunktion at() .

Beide geben an der entsprechenden Stelle im std::vector einen Verweis auf das Element zurück (es sei denn, es handelt sich um einen vector<bool> ), sodass es sowohl gelesen als auch modifiziert werden kann (wenn der Vektor nicht const ).

[] und at() unterscheiden sich dahingehend, dass [] nicht garantiert wird, dass Grenzen geprüft werden, während at() tut. Der Zugriff auf Elemente, bei denen index < 0 oder index >= size ist, ist für [] definiertes Verhalten , während at() eine Ausnahme std::out_of_range .

Anmerkung: In den folgenden Beispielen wird zur Vereinfachung die Initialisierung im C ++ 11-Stil verwendet. Die Operatoren können jedoch mit allen Versionen verwendet werden (sofern nicht C ++ 11 markiert ist).

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

Da die at() Methode eine Begrenzungsprüfung durchführt und Ausnahmen auslösen kann, ist sie langsamer als [] . Dies macht [] bevorzugten Code, bei dem die Semantik der Operation gewährleistet, dass der Index in Grenzen ist. In jedem Fall erfolgen Zugriffe auf Elemente von Vektoren in konstanter Zeit. Das heißt, der Zugriff auf das erste Element des Vektors hat (zeitlich) die gleichen Kosten für den Zugriff auf das zweite Element, das dritte Element usw.

Betrachten Sie zum Beispiel diese Schleife

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

Hier wissen wir, dass die Indexvariable i immer in Grenzen ist. Es wäre also eine Verschwendung von CPU-Zyklen, zu prüfen, ob i für jeden Aufruf an operator[] in Grenzen ist.

Die Elementfunktionen front() und back() ermöglichen einen einfachen Referenzzugriff auf das erste bzw. letzte Element des Vektors. Diese Positionen werden häufig verwendet, und die speziellen Zugriffsmethoden können mit [] besser gelesen werden als ihre Alternativen:

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}

Hinweis : Das Aufrufen von front() oder back() auf einem leeren Vektor ist undefiniert . Sie müssen vor dem Aufruf von front() oder back() überprüfen, ob der Container nicht leer ist, indem Sie die empty() Member-Funktion (die prüft, ob der Container leer ist) anzeigen. Ein einfaches Beispiel für die Verwendung von 'empty ()' zum Testen auf einen leeren Vektor folgt:

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;
}

Im obigen Beispiel wird ein Vektor mit einer Zahlenfolge von 1 bis 10 erstellt. Anschließend werden die Elemente des Vektors herausgefahren, bis der Vektor leer ist (mithilfe von 'empty ()'), um undefiniertes Verhalten zu verhindern. Dann wird die Summe der Zahlen im Vektor berechnet und dem Benutzer angezeigt.

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]

Iteratoren:

Iteratoren werden im Beispiel "Iterieren über std::vector " und im Artikel Iteratoren näher erläutert. Kurz gesagt, sie verhalten sich ähnlich wie Zeiger auf die Elemente des Vektors:

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

Er steht im Einklang mit dem Standard , dass ein std::vector<T> ‚s Iteratoren tatsächlich sein T* s, aber die meisten Standard - Bibliotheken tun dies nicht. Wenn Sie dies nicht tun, werden sowohl Fehlermeldungen verbessert als auch nicht portabler Code abgerufen. Außerdem können Sie die Iteratoren mit Debugging-Überprüfungen in Builds ohne Releases versehen. In Release-Builds wird der Klassenumbruch um den zugrundeliegenden Zeiger entfernt.

Sie können eine Referenz oder einen Zeiger auf ein Element eines Vektors für den indirekten Zugriff beibehalten. Diese Verweise oder Zeiger auf Elemente im vector bleiben stabil und der Zugriff bleibt definiert, es sei denn, Sie fügen Elemente am oder vor dem Element im vector oder entfernen die vector . Dies entspricht der Regel für das Ungültigmachen von Iteratoren.

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.

Verwendung von std :: vector als C-Array

Es gibt mehrere Möglichkeiten, einen std::vector als C-Array zu verwenden (z. B. zur Kompatibilität mit C-Bibliotheken). Dies ist möglich, weil die Elemente in einem Vektor zusammenhängend gespeichert werden.

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

Vor C ++ 11 müssten Sie die Adresse des ersten Elements des Vektors verwenden, um einen entsprechenden Zeiger zu erhalten. Wenn der Vektor nicht leer ist, sind diese beiden Methoden austauschbar:

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

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

Hinweis: Wenn der Vektor leer ist, sind v[0] und v.front() nicht definiert und können nicht verwendet werden.

Wenn Sie die Basisadresse der Vektordaten speichern, beachten Sie, dass viele Operationen (wie push_back , resize usw.) den Datenspeicherort des Vektors resize können, wodurch vorherige Datenzeiger ungültig werden . Zum Beispiel:

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

Iterator / Zeiger-Invalidierung

Iteratoren und Zeiger, die auf einen std::vector können nur bei bestimmten Operationen ungültig werden. Die Verwendung ungültiger Iteratoren / Zeiger führt zu undefiniertem Verhalten.

Zu den Operationen, die Iteratoren / Zeiger ungültig machen, gehören:

• Jeder Einfügevorgang, der die capacity des vector ändert, macht alle Iteratoren / Zeiger ungültig:

  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.

• Jeder Einfügevorgang, der die Kapazität nicht erhöht, macht die Iteratoren / Zeiger, die auf Elemente an der Einfügeposition zeigen, über diese hinaus ungültig. Dazu gehört auch das 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.
  

• Bei jedem Entfernungsvorgang werden Iteratoren / Zeiger ungültig, die auf die entfernten Elemente und auf alle Elemente nach den entfernten Elementen zeigen. Dazu gehört auch das 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= (Kopieren, Verschieben oder anderweitig) und clear() alle Iteratoren / Zeiger ungültig, die in den Vektor zeigen.

Elemente löschen

Das letzte Element löschen:

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

Alle Elemente löschen:

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

Element nach Index löschen:

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

Hinweis: Für einen vector ein Element zu löschen , die nicht das letzte Element ist, alle Elemente über das gelöschte Element werden müssen kopiert oder verschoben , die Lücke zu füllen, siehe Hinweis unten und std :: list .

Alle Elemente eines Bereichs löschen:

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

Hinweis: Die oben genannten Methoden ändern nicht die Kapazität des Vektors, sondern nur die Größe. Siehe Vektorgröße und Kapazität .

Die erase , die eine Reihe von Elementen entfernt, wird häufig als Teil des Lösch-Entfernungs- Idioms verwendet. Das heißt, zuerst std::remove verschiebt einige Elemente an das Ende des Vektors und erase sie dann. Dies ist eine relativ ineffiziente Operation für alle Indizes, die unter dem letzten Index des Vektors liegen, da alle Elemente nach den gelöschten Segmenten an neue Positionen verschoben werden müssen. Geschwindigkeitskritische Anwendungen, die das effiziente Entfernen beliebiger Elemente in einem Container erfordern, finden Sie unter std :: list .

Elemente nach Wert löschen:

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}

Elemente nach Bedingung löschen:

// 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}

Löschen von Elementen durch Lambda, ohne zusätzliche Prädikatsfunktion zu erstellen

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()
);

Elemente nach Bedingung aus einer Schleife löschen:

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
}

Es ist zwar wichtig, dass Sie it im Falle eines Löschvorgangs nicht inkrementieren, Sie sollten jedoch eine andere Methode verwenden, wenn Sie sie dann wiederholt in einer Schleife löschen. remove_if Sie remove_if für einen effizienteren Weg.

Elemente nach Bedingung aus einer umgekehrten Schleife löschen:

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;
}

Beachten Sie einige Punkte für die vorhergehende Schleife:

• Bei einem Reverse - Iterator it zu einem Element zeigt, das Verfahren base gibt dem regulären (nicht umgekehrt) Iterator zeigt auf das gleiche Element.

• vector::erase(iterator) löscht das Element, auf das ein Iterator zeigt, und gibt einen Iterator an das Element zurück, das dem angegebenen Element folgte.

• reverse_iterator::reverse_iterator(iterator) einen Reverse-Iterator aus einem Iterator.

Setzen Sie insgesamt die Linie it = rev_itr(v.erase(it.base())) sagt: Nehmen Sie die Reverse - Iterator it haben v Löschen Sie das Element durch seine regelmäßigen Iterator zugespitzt; nehmen die resultierende Iterator, eine umgekehrte Iterator daraus, baut und Zuweisen zu dem umgekehrten Iterator it .

Durch das Löschen aller Elemente mit v.clear() wird kein Speicherplatz frei ( capacity() des Vektors bleibt unverändert). Um Platz zu gewinnen, verwenden Sie:

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

v.shrink_to_fit();

Das shrink_to_fit garantiert zwar nicht wirklich Speicherplatz zurückzugewinnen, aber die meisten aktuellen Implementierungen tun dies.

Ein Element in std :: vector finden

Mit der Funktion std::find , definiert im Header <algorithm> , kann ein Element in einem std::vector .

std::find verwendet den operator== , um Elemente auf Gleichheit zu vergleichen. Es gibt einen Iterator an das erste Element in dem Bereich zurück, der dem Wert gleich ist.

Wenn das betreffende Element nicht gefunden wird, gibt std::find std::vector::end (oder std::vector::cend wenn der Vektor 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)

Wenn Sie viele Suchvorgänge in einem großen Vektor durchführen müssen, sollten Sie den Vektor zuerst sortieren, bevor Sie den binary_search Algorithmus verwenden.

Um das erste Element in einem Vektor zu finden, der eine Bedingung erfüllt, kann std::find_if verwendet werden. Zusätzlich zu den zwei für std::find angegebenen Parametern akzeptiert std::find_if ein drittes Argument, das ein Funktionsobjekt oder einen Funktionszeiger auf eine Prädikatfunktion ist. Das Prädikat sollte ein Element aus dem Container als Argument akzeptieren und einen in bool konvertierbaren Wert zurückgeben, ohne den Container zu bool :

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

Konvertieren eines Arrays in std :: vector

Ein Array kann einfach mit Hilfe von std::begin und std::end in einen std::vector umgewandelt werden:

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);
}

Eine C ++ 11-Initialisierungsliste <> kann auch verwendet werden, um den Vektor sofort zu initialisieren

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

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

Vektor : Die Ausnahme zu so vielen Regeln

Der Standard (Abschnitt 23.3.7) gibt an, dass eine Spezialisierung des vector<bool> vorgesehen ist, die den Speicherplatz optimiert, indem die bool Werte bool werden, sodass jeder nur ein Bit beansprucht. Da Bits in C ++ nicht adressierbar sind, bedeutet dies, dass einige Anforderungen an den vector nicht auf den vector<bool> :

• Die gespeicherten Daten müssen nicht zusammenhängend sein, sodass ein vector<bool> nicht an eine C-API übergeben werden kann, die ein bool Array erwartet.
• at() , operator [] und Dereferenzierung von Iteratoren geben keine Referenz auf bool . Sie geben stattdessen ein Proxy-Objekt zurück, das (unvollkommen) einen Verweis auf einen bool simuliert, indem seine Zuweisungsoperatoren überladen werden. Der folgende Code ist beispielsweise für std::vector<bool> möglicherweise nicht gültig, da die Dereferenzierung eines Iterators keine Referenz zurückgibt:

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

Ebenso können Funktionen, die ein bool& argument erwarten, nicht mit dem Ergebnis des operator [] oder at() auf den vector<bool> oder mit dem Ergebnis der Dereferenzierung des Iterators verwendet werden:

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

Die Implementierung von std::vector<bool> hängt sowohl vom Compiler als auch von der Architektur ab. Die Spezialisierung wird implementiert, indem n Booleans in den untersten adressierbaren Speicherbereich gepackt werden. Hier ist n die Größe des niedrigsten adressierbaren Speichers in Bits. In den meisten modernen Systemen sind dies 1 Byte oder 8 Bit. Das bedeutet, dass ein Byte 8 boolesche Werte speichern kann. Dies ist eine Verbesserung gegenüber der herkömmlichen Implementierung, bei der ein boolescher Wert in 1 Byte Speicher gespeichert wird.

Hinweis: Das folgende Beispiel zeigt mögliche bitweise Werte einzelner Bytes in einem traditionellen vs. optimierten vector<bool> . Dies gilt nicht immer für alle Architekturen. Es ist jedoch eine gute Möglichkeit, die Optimierung zu visualisieren. In den folgenden Beispielen wird ein Byte als [x, x, x, x, x, x, x, x] dargestellt.

Traditionelles std::vector<char> speichert 8 boolesche Werte:

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

Bitweise Darstellung:

[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]

Specialized std::vector<bool> speichert 8 boolesche Werte:

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

Bitweise Darstellung:

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

Beachten Sie im obigen Beispiel, dass in der traditionellen Version von std::vector<bool> 8 boolesche Werte 8 Byte Speicherplatz beanspruchen, wohingegen in der optimierten Version von std::vector<bool> nur 1 Byte verwendet wird Erinnerung. Dies ist eine deutliche Verbesserung der Speicherauslastung. Wenn Sie einen vector<bool> an eine API im C-Stil übergeben müssen, müssen Sie die Werte möglicherweise in ein Array kopieren oder einen besseren Weg finden, um die API zu verwenden, wenn Arbeitsspeicher und Leistung gefährdet sind.

Vektorgröße und Kapazität

Vektorgröße ist einfach die Anzahl der Elemente im Vektor:

1. Aktuelle Vektorgröße wird durch abgefragten size() Member - Funktion. Die Funktion empty() gibt true zurück true wenn size 0 ist:

   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. Der standardmäßig konstruierte Vektor beginnt mit einer Größe von 0:

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

3. Durch Hinzufügen von N Elementen zum Vektor wird die Größe um N erhöht (z. B. durch die Funktionen push_back() , insert() oder resize() ).

4. Durch das Entfernen von N Elementen aus dem Vektor wird die Größe um N verringert (z. B. durch pop_back() , erase() oder clear() Funktionen).

5. Vector hat eine implementierungsspezifische Obergrenze für die Größe, aber es ist wahrscheinlich, dass der RAM knapp wird, bevor er erreicht wird:

   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
   

Häufiger Fehler: Größe ist nicht notwendigerweise (oder sogar normalerweise) 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] );
}

Die Vektorkapazität unterscheidet sich von der Größe . Während size einfach ist, wie viele Elemente der Vektor derzeit hat, ist Kapazität für wie viele Elemente Speicherplatz reserviert / reserviert. Das ist nützlich, weil zu häufige (Neu-) Zuweisungen zu großer Größen teuer sein können.

1. Stromvektor Kapazität wird durch abgefragt capacity() Mitgliedsfunktion. Die Kapazität ist immer größer oder gleich der Größe :

   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. Sie können Kapazität manuell durch reserve( N ) -Funktion reserve( N ) Vektorkapazität wird in N geändert):

   // !!!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. Sie können anfordern, dass die überschüssige Kapazität von shrink_to_fit() freigegeben wird (aber die Implementierung muss Ihnen nicht gehorchen). Dies ist nützlich, um verwendeten Speicher zu sparen:

   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 verwaltet die Kapazität zum Teil automatisch, wenn Sie Elemente hinzufügen, entscheidet er sich möglicherweise für eine Vergrößerung. Implementierer verwenden gerne 2 oder 1,5 für den Wachstumsfaktor (Golden Ratio wäre der ideale Wert - ist jedoch aufgrund der rationalen Anzahl nicht praktikabel). Auf der anderen Seite schrumpfen Vektor normalerweise nicht automatisch. Zum Beispiel:

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

Verkettung von Vektoren

Ein std::vector kann mithilfe der Member-Funktion insert() an einen anderen angehängt werden:

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());

Diese Lösung schlägt jedoch fehl, wenn Sie versuchen, einen Vektor an sich selbst anzuhängen, da der Standard festlegt, dass die für insert() angegebenen Iteratoren nicht im selben Bereich liegen dürfen wie die Elemente des Empfängerobjekts.

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

Wenn die Reihenfolge der Elemente im Empfangsvektor keine Rolle spielt, können durch die Berücksichtigung der Anzahl der Elemente in jedem Vektor unnötige Kopiervorgänge vermieden werden:

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

Die Kapazität eines Vektors reduzieren

Ein std::vector erhöht nach Bedarf automatisch seine Kapazität beim Einfügen, verringert jedoch niemals seine Kapazität nach dem Entfernen von Elementen.

// 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)

Um seine Kapazität zu reduzieren, können wir den Inhalt eines Vektors in einen neuen temporären Vektor kopieren. Der neue Vektor hat die minimale Kapazität, die zum Speichern aller Elemente des ursprünglichen Vektors erforderlich ist. Wenn die Größenverringerung des ursprünglichen Vektors signifikant war, ist die Kapazitätsverringerung für den neuen Vektor wahrscheinlich signifikant. Wir können dann den ursprünglichen Vektor mit dem temporären Vektor tauschen, um seine minimierte Kapazität zu erhalten:

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

v.shrink_to_fit();

Verwenden eines sortierten Vektors für die schnelle Elementsuche

Der <algorithm> -Header bietet eine Reihe nützlicher Funktionen zum Arbeiten mit sortierten Vektoren.

Eine wichtige Voraussetzung für das Arbeiten mit sortierten Vektoren ist, dass die gespeicherten Werte mit < vergleichbar sind.

Ein unsortierter Vektor kann mit der Funktion std::sort() sortiert werden:

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

Sortierte Vektoren ermöglichen eine effiziente Elementsuche mit der Funktion std::lower_bound() . Im Gegensatz zu std::find() führt dies eine effiziente binäre Suche nach dem Vektor durch. Der Nachteil ist, dass es nur für sortierte Eingabebereiche gültige Ergebnisse gibt:

// 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!
}

Hinweis: Wenn der angeforderte Wert nicht Teil des Vektors ist, gibt std::lower_bound() einen Iterator an das erste Element zurück, das größer als der angeforderte Wert ist. Dieses Verhalten ermöglicht es uns, ein neues Element an der richtigen Stelle in einen bereits sortierten Vektor einzufügen:

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

Wenn Sie viele Elemente gleichzeitig einfügen müssen, ist es möglicherweise effizienter, zuerst push_back() für alle Elemente und dann std::sort() aufzurufen, nachdem alle Elemente eingefügt wurden. In diesem Fall können sich die erhöhten Sortierkosten für die reduzierten Einfügungskosten neuer Elemente am Ende des Vektors und nicht in der Mitte bezahlt machen.

Wenn Ihr Vektor mehrere Elemente mit demselben Wert enthält, versucht std::lower_bound() , einen Iterator an das erste Element des gesuchten Werts zurückzugeben. Wenn Sie jedoch nach dem letzten Element des gesuchten Werts ein neues Element einfügen müssen, sollten Sie die Funktion std::upper_bound() da dies zu einer geringeren Verschiebung der Elemente führt:

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

Wenn Sie sowohl den oberen als auch den unteren Iterator benötigen, können Sie die Funktion std::equal_range() , um beide effizient mit einem Aufruf abzurufen:

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;

Um zu testen, ob ein Element in einem sortierten Vektor vorhanden ist (obwohl nicht vektorspezifisch), können Sie die Funktion std::binary_search() :

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

Funktionen, die große Vektoren zurückgeben

#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;
}

Finden Sie das maximale und minimale Element und den jeweiligen Index in einem Vektor

Um das in einem Vektor gespeicherte größte oder kleinste Element zu finden, können Sie die Methoden std::max_element bzw. std::min_element verwenden. Diese Methoden sind im Header <algorithm> definiert. Wenn mehrere Elemente dem größten (kleinsten) Element entsprechen, geben die Methoden den Iterator an das erste dieser Elemente zurück. Rückgabe v.end() für leere Vektoren.

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';

Ausgabe:

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';

Matrizen mit Vektoren

Vektoren können als 2D-Matrix verwendet werden, indem sie als Vektor von Vektoren definiert werden.

Eine Matrix mit 3 Zeilen und 4 Spalten, wobei jede Zelle als 0 initialisiert wird, kann folgendermaßen definiert werden:

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}
                                         };

Auf Werte in einem solchen Vektor kann ähnlich wie bei einem 2D-Array zugegriffen werden

int var = matrix[0][2];

Die Iteration über die gesamte Matrix ist der eines normalen Vektors ähnlich, jedoch mit einer zusätzlichen Dimension.

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;
    }
}

Ein Vektor von Vektoren ist eine bequeme Art, eine Matrix darzustellen, ist jedoch nicht die effizienteste: Einzelne Vektoren sind im Speicher verteilt und die Datenstruktur ist nicht für den Cache geeignet.

In einer richtigen Matrix muss die Länge jeder Zeile gleich sein (dies ist bei einem Vektor von Vektoren nicht der Fall). Die zusätzliche Flexibilität kann eine Fehlerquelle sein.