C++
std :: wektor

Wprowadzenie

Uwagi

Inicjalizacja std :: vector

std::vector można zainicjować na kilka sposobów, deklarując go:

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}

Wektor można zainicjować z innego kontenera na kilka sposobów:

Kopiuj konstrukcję (tylko z innego wektora), która kopiuje dane z v2 :

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 (zakres) kopiowanie konstrukcji, które kopiuje elementy do 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()));

Za pomocą funkcji członka assign() można ponownie zainicjować std::vector po jego budowie:

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}

Wstawianie elementów

Dołączanie elementu na końcu wektora (przez kopiowanie / przenoszenie):

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.

Zauważ, że std::vector nie ma funkcji członka push_front() ze względu na wydajność. Dodanie elementu na początku powoduje przeniesienie wszystkich istniejących elementów w wektorze. Jeśli chcesz często wstawiać elementy na początku kontenera, możesz zamiast tego użyć std::list lub std::deque .

Wstawianie elementu w dowolnej pozycji wektora:

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}

Wstawianie innego wektora w dowolnej pozycji wektora:

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

Wstawianie tablicy w dowolnej pozycji wektora:

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

Użyj reserve() przed wstawieniem wielu elementów, jeśli znany jest wcześniej wynikowy rozmiar wektora, aby uniknąć wielokrotnych realokacji (patrz rozmiar i pojemność wektora ):

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

Pamiętaj, aby nie popełnić błędu wywołania resize() w tym przypadku, w przeciwnym razie utworzysz wektor z 200 elementami, w których tylko ta ostatnia będzie miała zamierzoną wartość.

Iterating Over std :: vector

Możesz iterować po std::vector na kilka sposobów. Dla każdej z poniższych sekcji v jest zdefiniowane w następujący sposób:

std::vector<int> v;

Iteracja w kierunku do przodu

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

Iteracja w odwrotnym kierunku

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

Chociaż nie ma wbudowanego sposobu użycia zakresu opartego na odwróceniu iteracji; stosunkowo łatwo jest to naprawić. Zakres oparty na zastosowaniach begin() i end() celu uzyskania iteratorów, a tym samym symulacja tego za pomocą obiektu otoki może osiągnąć oczekiwane rezultaty.

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

Egzekwowanie stałych elementów

Ponieważ C ++ 11 cbegin() i cend() metody pozwalają uzyskać stałą iterator do wektora, nawet jeśli wektor jest non-const. Stały iterator umożliwia czytanie, ale nie modyfikowanie zawartości wektora, co jest przydatne do wymuszania poprawności const:

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

Jest to łatwe do wdrożenia we wcześniejszych wersjach C ++:

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

Uwaga na temat wydajności

Ponieważ klasa std::vector jest w zasadzie klasą zarządzającą dynamicznie przydzielaną ciągłą tablicą, ta sama zasada wyjaśniona tutaj dotyczy wektorów C ++. Dostęp do zawartości wektora za pomocą indeksu jest znacznie bardziej efektywny, jeśli przestrzega się zasady kolejności rzędów. Oczywiście każdy dostęp do wektora przenosi również zawartość zarządzania do pamięci podręcznej, ale jak wielokrotnie dyskutowano (zwłaszcza tu i tutaj ), różnica w wydajności iteracji po std::vector porównaniu do surowej tablicy jest nieistotny. Tak więc ta sama zasada wydajności dla surowych tablic w C ma również zastosowanie do std::vector w C ++.

Dostęp do elementów

Istnieją dwa podstawowe sposoby uzyskiwania dostępu do elementów w std::vector

• dostęp na podstawie indeksu
• iteratory

Dostęp na podstawie indeksu:

Można to zrobić za pomocą operatora indeksu dolnego [] lub funkcji składowej at() .

Oba zwracają odniesienie do elementu w odpowiedniej pozycji w std::vector (chyba że jest to vector<bool> ), dzięki czemu można go czytać, a także modyfikować (jeśli wektor nie jest const ).

[] i at() różnią się tym, że [] nie ma gwarancji wykonywania sprawdzania granic, podczas gdy at() robi. Dostęp do elementów, w których index < 0 lub index >= size jest niezdefiniowanym zachowaniem dla [] , podczas gdy at() zgłasza wyjątek std::out_of_range .

Uwaga: Poniższe przykłady używają inicjalizacji w stylu C ++ 11 dla przejrzystości, ale operatory mogą być używane ze wszystkimi wersjami (chyba że oznaczono 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

Ponieważ metoda at() wykonuje sprawdzanie granic i może zgłaszać wyjątki, jest wolniejsza niż [] . To sprawia, że [] preferowany kod, w którym semantyka operacji gwarantuje, że indeks jest w granicach. W każdym razie dostęp do elementów wektorów odbywa się w stałym czasie. Oznacza to, że dostęp do pierwszego elementu wektora ma taki sam koszt (w czasie) dostępu do drugiego elementu, trzeciego elementu i tak dalej.

Rozważmy na przykład tę pętlę

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

Wiemy, że zmienna indeksu i jest zawsze w granicach, więc marnowaniem cykli procesora byłoby sprawdzanie, czy i jest w granicach dla każdego wywołania operator[] .

Funkcje elementu front() i back() umożliwiają łatwy dostęp do odniesienia odpowiednio do pierwszego i ostatniego elementu wektora. Te pozycje są często używane, a specjalne akcesoria mogą być bardziej czytelne niż ich alternatywy za pomocą [] :

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}

Uwaga : Zachowanie niezdefiniowane front() lub back() na pustym wektorze jest niezdefiniowane . Przed wywołaniem front() lub back() należy sprawdzić, czy kontener nie jest pusty, używając funkcji członkowskiej empty() (która sprawdza, czy kontener jest pusty back() . Oto prosty przykład użycia „empty ()” do testowania pustego wektora:

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

Powyższy przykład tworzy wektor o sekwencji liczb od 1 do 10. Następnie wyrzuca elementy wektora, aż wektor będzie pusty (używając „empty ()”), aby zapobiec niezdefiniowanemu zachowaniu. Następnie suma liczb w wektorze jest obliczana i wyświetlana użytkownikowi.

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]

Iteratory:

Iteratory zostały wyjaśnione bardziej szczegółowo w przykładzie „Iterowanie po std::vector ” oraz w artykule Iteratory . Krótko mówiąc, działają one podobnie do wskaźników do elementów wektora:

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

Jest to zgodne ze standardem, że iteratory std::vector<T> faktycznie są T* , ale większość standardowych bibliotek tego nie robi. Nie wykonanie tej czynności poprawia komunikaty o błędach, wyłapuje nieprzenośny kod i może służyć do instrumentowania iteratorów sprawdzaniem debugowania w wersjach innych niż wydania. Następnie, w kompilacjach wersji, owijanie klas wokół podstawowego wskaźnika jest optymalizowane.

Możesz zachować odwołanie lub wskaźnik do elementu wektora w celu uzyskania pośredniego dostępu. Te odniesienia lub wskaźniki do elementów w vector pozostają stabilne, a dostęp pozostaje zdefiniowany, chyba że dodasz / usuniesz elementy na lub przed elementem w vector lub spowodujesz zmianę zdolności vector . Jest to to samo, co reguła unieważniania iteratorów.

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.

Używanie std :: vector jako tablicy C.

Istnieje kilka sposobów użycia std::vector jako tablicy C (na przykład w celu zachowania zgodności z bibliotekami C). Jest to możliwe, ponieważ elementy w wektorze są przechowywane w sposób ciągły.

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

Przed wersją C ++ 11 wziąłbyś adres pierwszego elementu wektora, aby uzyskać równoważny wskaźnik, jeśli wektor nie jest pusty, obie metody są wymienne:

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

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

Uwaga: Jeśli wektor jest pusty, v[0] i v.front() są niezdefiniowane i nie można ich użyć.

Podczas przechowywania adresu bazowego danych wektora należy pamiętać, że wiele operacji (takich jak push_back , resize itp.) Może zmienić lokalizację pamięci danych wektora, unieważniając w ten sposób poprzednie wskaźniki danych . Na przykład:

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

Iterator / Invalidation Pointer

Iteratory i wskaźniki wskazujące na std::vector mogą stać się nieprawidłowe, ale tylko podczas wykonywania niektórych operacji. Użycie niepoprawnych iteratorów / wskaźników spowoduje niezdefiniowane zachowanie.

Operacje, które unieważniają iteratory / wskaźniki, obejmują:

• Każda operacja wstawiania, która zmienia capacity vector , unieważnia wszystkie iteratory / wskaźniki:

  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.

• Każda operacja wstawiania, która nie zwiększa pojemności, nadal unieważnia iteratory / wskaźniki wskazujące na elementy w pozycji wstawiania i obok niej. Obejmuje to iterator end :

  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.
  

• Każda operacja usuwania unieważnia iteratory / wskaźniki wskazujące na usunięte elementy i wszelkie elementy za usuniętymi elementami. Obejmuje to iterator end :

  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= (kopiuj, przenieś lub w inny sposób) i clear() unieważnią wszystkie iteratory / wskaźniki wskazujące na wektor.

Usuwanie elementów

Usuwanie ostatniego elementu:

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

Usuwanie wszystkich elementów:

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

Usuwanie elementu według indeksu:

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

Uwaga: W przypadku vector usuwającego element, który nie jest ostatnim elementem, wszystkie elementy poza usuniętym elementem muszą zostać skopiowane lub przeniesione w celu wypełnienia luki, patrz uwaga poniżej i lista std :: .

Usuwanie wszystkich elementów z zakresu:

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

Uwaga: powyższe metody nie zmieniają pojemności wektora, tylko rozmiar. Zobacz Wektor Rozmiar i pojemność .

Metoda erase , która usuwa zakres elementów, jest często stosowana jako część idiomu usuwania-usuwania . Oznacza to, że najpierw std::remove przenosi niektóre elementy na koniec wektora, a następnie erase je. Jest to stosunkowo nieefektywna operacja dla indeksów mniejszych niż ostatni indeks wektora, ponieważ wszystkie elementy po skasowanych segmentach muszą zostać przeniesione na nowe pozycje. Dla aplikacji krytycznych dla prędkości, które wymagają skutecznego usuwania dowolnych elementów z kontenera, zobacz std :: list .

Usuwanie elementów według wartości:

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}

Usuwanie elementów według warunku:

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

Usuwanie elementów przez lambda, bez tworzenia dodatkowej funkcji predykatu

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

Usuwanie elementów według warunku z pętli:

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
}

Chociaż ważne jest, aby nie zwiększać it w przypadku usunięcia, należy rozważyć zastosowanie innej metody, gdy następnie jest ona wielokrotnie kasowana w pętli. Rozważ remove_if aby uzyskać bardziej wydajny sposób.

Usuwanie elementów według warunków z pętli zwrotnej:

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

Zwróć uwagę na kilka punktów dla poprzedniej pętli:

• Biorąc pod uwagę iterator zwrotny, it wskazuje na jakiś element, base metody daje zwykły (nieodwrotny) iterator wskazujący na ten sam element.

• vector::erase(iterator) kasuje element wskazywany przez iterator i zwraca iterator do elementu następującego po danym elemencie.

• reverse_iterator::reverse_iterator(iterator) konstruuje iterator do tyłu z iteratora.

Umieścić całkowicie, linii it = rev_itr(v.erase(it.base())) mówi: weź reverse iterator it mają v usunąć element wskazał jego regularnego iterator; się wynikowy iteracyjnej skonstruować iteracyjnej odwróconej od niej, i przypisać do odwrócenia iteracyjnej it .

Usunięcie wszystkich elementów za pomocą v.clear() nie v.clear() pamięci ( capacity() wektora pozostaje niezmieniona). Aby odzyskać miejsce, użyj:

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

v.shrink_to_fit();

shrink_to_fit nie gwarantuje odzyskania miejsca, ale większość obecnych implementacji tak robi.

Znalezienie elementu w std :: vector

Funkcja std::find , zdefiniowana w nagłówku <algorithm> , może zostać użyta do znalezienia elementu w std::vector .

std::find używa operator== do porównywania elementów dla równości. Zwraca iterator do pierwszego elementu w zakresie, który porównuje równy wartości.

Jeśli dany element nie zostanie znaleziony, std::find zwraca std::vector::end (lub std::vector::cend jeśli wektor jest 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)

Jeśli musisz wykonać wiele wyszukiwań w dużym wektorze, możesz najpierw rozważyć posortowanie wektora, zanim binary_search algorytmu binary_search .

Aby znaleźć pierwszy element w wektorze, który spełnia warunek, można użyć std::find_if . Oprócz dwóch parametrów podanych dla std::find , std::find_if akceptuje trzeci argument, który jest obiektem funkcji lub wskaźnikiem funkcji do funkcji predykatu. Predykat powinien przyjąć element z kontenera jako argument i zwrócić wartość konwertowalną na bool , bez modyfikowania kontenera:

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

Konwertowanie tablicy na std :: vector

Tablicę można łatwo przekształcić w std::vector , używając std::begin i 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);
}

Inicjalizator_listy C ++ 11 <> może być również użyty do natychmiastowej inicjalizacji wektora

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

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

wektor : Wyjątek od tylu zasad, tylu zasad

Standard (sekcja 23.3.7) określa, że zapewniona jest specjalizacja vector<bool> , która optymalizuje przestrzeń poprzez upakowanie wartości bool , tak aby każda z nich zajmowała tylko jeden bit. Ponieważ bity nie są adresowalne w C ++, oznacza to, że kilka wymagań dotyczących vector nie jest umieszczanych na vector<bool> :

• Przechowywane dane nie muszą być ciągłe, więc vector<bool> nie może zostać przekazany do API C, który oczekuje tablicy bool .
• at() , operator [] i dereferencje iteratorów nie zwracają odwołania do bool . Zamiast tego zwracają obiekt proxy, który (niedoskonale) symuluje odwołanie do bool , przeciążając jego operatory przypisania. Na przykład następujący kod może być niepoprawny dla std::vector<bool> , ponieważ usunięcie odwołania z iteratora nie zwraca odwołania:

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

Podobnie funkcje oczekujące argumentu bool& nie mogą być używane z wynikiem operator [] lub at() zastosowanym do vector<bool> lub z wynikiem dereferencji jego iteratora:

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

Implementacja std::vector<bool> zależy zarówno od kompilatora, jak i architektury. Specjalizacja realizowana jest poprzez upakowanie n booleanów w najniższej adresowalnej części pamięci. Tutaj n jest rozmiarem w bitach najniższej pamięci adresowalnej. W większości nowoczesnych systemów jest to 1 bajt lub 8 bitów. Oznacza to, że jeden bajt może przechowywać 8 wartości boolowskich. Jest to ulepszenie w stosunku do tradycyjnej implementacji, w której 1 wartość logiczna jest przechowywana w 1 bajcie pamięci.

Uwaga: Poniższy przykład pokazuje możliwe wartości bitowe poszczególnych bajtów w tradycyjnym kontra zoptymalizowanym vector<bool> . Nie zawsze będzie to prawdą we wszystkich architekturach. Jest to jednak dobry sposób na wizualizację optymalizacji. W poniższych przykładach bajt jest reprezentowany jako [x, x, x, x, x, x, x, x].

Tradycyjny std::vector<char> przechowujący 8 wartości boolowskich:

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

Reprezentacja bitowa:

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

Specjalizowany std::vector<bool> przechowujący 8 wartości boolowskich:

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

Reprezentacja bitowa:

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

Zauważ w powyższym przykładzie, że w tradycyjnej wersji std::vector<bool> 8 wartości logicznych zajmuje 8 bajtów pamięci, podczas gdy w zoptymalizowanej wersji std::vector<bool> używają tylko 1 bajta pamięć. Jest to znacząca poprawa wykorzystania pamięci. Jeśli konieczne jest przekazanie vector<bool> do interfejsu API typu C, konieczne może być skopiowanie wartości do tablicy lub znalezienie lepszego sposobu korzystania z interfejsu API, jeśli pamięć i wydajność są zagrożone.

Rozmiar i pojemność wektora

Rozmiar wektora to po prostu liczba elementów w wektorze:

1. Bieżący rozmiar wektora jest sprawdzany przez funkcję elementu size() . Wygoda funkcji empty() zwraca wartość true jeśli rozmiar wynosi 0:

   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. Domyślnie skonstruowany wektor zaczyna się od rozmiaru 0:

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

3. Dodanie N elementów do wektora zwiększa rozmiar o N (np. Za pomocą funkcji push_back() , insert() lub resize() ).

4. Usunięcie N elementów z wektora zmniejsza rozmiar o N (np. Przez funkcje pop_back() , erase() lub clear() ).

5. Wektor ma górny limit rozmiaru specyficzny dla implementacji, ale najprawdopodobniej skończy się pamięć RAM, zanim go osiągniesz:

   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
   

Często popełniany błąd: rozmiar niekoniecznie (lub nawet zwykle) 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] );
}

Pojemność wektora różni się od wielkości . Podczas gdy rozmiar jest po prostu liczbą elementów, które ma obecnie wektor, pojemność określa liczbę elementów, dla których przydzielono / zarezerwowano pamięć. Jest to przydatne, ponieważ zbyt częste (ponowne) przydzielanie zbyt dużych rozmiarów może być kosztowne.

1. Bieżąca pojemność wektora jest sprawdzana przez funkcję członka capacity() . Pojemność jest zawsze większa lub równa wielkości :

   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. Możesz ręcznie zarezerwować pojemność za pomocą funkcji reserve( N ) (zmienia pojemność wektora na 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. Możesz poprosić o zwolnienie nadmiernej pojemności przez shrink_to_fit() (ale implementacja nie musi cię słuchać). Jest to przydatne do oszczędzania używanej pamięci:

   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 częściowo automatycznie zarządza pojemnością, a po dodaniu elementów może zdecydować o rozwoju. Implementatorzy lubią używać 2 lub 1,5 dla współczynnika wzrostu (złoty współczynnik byłby idealną wartością - ale jest to niepraktyczne ze względu na to, że jest liczbą wymierną). Z drugiej strony wektor zwykle nie kurczy się automatycznie. Na przykład:

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

Wektory łączące

Jeden std::vector można dołączyć do drugiego za pomocą funkcji członka 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());

Jednak to rozwiązanie nie powiedzie się, jeśli spróbujesz dołączyć wektor do siebie, ponieważ standard określa, że iteratory podane dla funkcji insert() nie mogą należeć do tego samego zakresu, co elementy obiektu odbiornika.

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

Jeśli kolejność elementów w wektorze odbiorczym nie ma znaczenia, biorąc pod uwagę liczbę elementów w każdym wektorze, można uniknąć niepotrzebnych operacji kopiowania:

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

Zmniejszenie pojemności wektora

std::vector automatycznie zwiększa swoją pojemność po wstawieniu w razie potrzeby, ale nigdy nie zmniejsza swojej pojemności po usunięciu elementu.

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

Aby zmniejszyć jego pojemność, możemy skopiować zawartość wektora do nowego wektora tymczasowego. Nowy wektor będzie miał minimalną pojemność potrzebną do przechowywania wszystkich elementów oryginalnego wektora. Jeśli zmniejszenie rozmiaru oryginalnego wektora było znaczne, wówczas zmniejszenie pojemności nowego wektora prawdopodobnie będzie znaczące. Następnie możemy zamienić oryginalny wektor na tymczasowy, aby zachować jego zminimalizowaną pojemność:

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

v.shrink_to_fit();

Używanie posortowanego wektora do szybkiego wyszukiwania elementów

Nagłówek <algorithm> udostępnia szereg przydatnych funkcji do pracy z posortowanymi wektorami.

Ważnym warunkiem pracy z posortowanymi wektorami jest to, że przechowywane wartości są porównywalne z < .

Niesortowany wektor można posortować za pomocą funkcji std::sort() :

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

Posortowane wektory umożliwiają wydajne wyszukiwanie elementów za pomocą funkcji std::lower_bound() . W przeciwieństwie do std::find() , wykonuje wydajne wyszukiwanie binarne w wektorze. Minusem jest to, że daje prawidłowe wyniki tylko dla posortowanych zakresów wejściowych:

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

Uwaga: Jeśli żądana wartość nie jest częścią wektora, std::lower_bound() zwróci iterator do pierwszego elementu, który jest większy niż żądana wartość. To zachowanie pozwala nam wstawić nowy element we właściwym miejscu w już posortowanym wektorze:

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

Jeśli musisz wstawić wiele elementów naraz, bardziej efektywne może być wywołanie push_back() dla wszystkich, a następnie wywołanie std::sort() po wstawieniu wszystkich elementów. W takim przypadku zwiększony koszt sortowania może się opłacić w porównaniu ze zmniejszonym kosztem wstawiania nowych elementów na końcu wektora, a nie na środku.

Jeśli twój wektor zawiera wiele elementów o tej samej wartości, std::lower_bound() spróbuje zwrócić iterator do pierwszego elementu std::lower_bound() wartości. Jeśli jednak chcesz wstawić nowy element po ostatnim elemencie std::upper_bound() wartości, powinieneś użyć funkcji std::upper_bound() ponieważ spowoduje to mniejsze przesuwanie elementów:

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

Jeśli potrzebujesz zarówno iteratorów górnej, jak i dolnej granicy, możesz użyć funkcji std::equal_range() aby skutecznie odzyskać oba z nich za pomocą jednego wywołania:

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;

Aby sprawdzić, czy element istnieje w posortowanym wektorze (chociaż nie jest specyficzny dla wektorów), możesz użyć funkcji std::binary_search() :

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

Funkcje zwracające duże wektory

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

Znajdź maksymalny i minimalny element i odpowiedni indeks w wektorze

Aby znaleźć największy lub najmniejszy element przechowywany w wektorze, możesz użyć odpowiednio metod std::max_element i std::min_element . Metody te są zdefiniowane w nagłówku <algorithm> . Jeśli kilka elementów jest równoważnych największemu (najmniejszemu) elementowi, metody zwracają iterator do pierwszego takiego elementu. Zwróć v.end() dla pustych wektorów.

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

Wynik:

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

Macierze wykorzystujące wektory

Wektory można wykorzystać jako matrycę 2D, definiując je jako wektor wektorów.

Macierz z 3 wierszami i 4 kolumnami z każdą komórką zainicjowaną jako 0 można zdefiniować jako:

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

Dostęp do wartości w takim wektorze można uzyskać podobnie do tablicy 2D

int var = matrix[0][2];

Iteracja po całej macierzy jest podobna do wektora normalnego, ale z dodatkowym wymiarem.

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

Wektor wektorów jest wygodnym sposobem reprezentacji macierzy, ale nie jest najbardziej wydajny: poszczególne wektory są rozproszone wokół pamięci, a struktura danych nie jest przyjazna dla pamięci podręcznej.

Ponadto, w odpowiedniej macierzy, długość każdego wiersza musi być taka sama (nie dotyczy to wektora wektorów). Dodatkowa elastyczność może być źródłem błędów.