C++
станд :: вектор

Вступление

замечания

Инициализация std :: vector

std::vector может быть инициализирован несколькими способами, объявляя его:

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}

Вектор может быть инициализирован из другого контейнера несколькими способами:

Скопировать построение (только с другого вектора), которое копирует данные из 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);

Итератор (диапазон) copy-construction, который копирует элементы в 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()));

С помощью функции-члена assign() , std::vector может быть повторно инициализирован после его построения:

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}

Вставка элементов

Добавление элемента в конце вектора (путем копирования / перемещения):

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.

Обратите внимание, что std::vector не имеет функции-члена push_front() из-за причин производительности. Добавление элемента в начале приводит к перемещению всех существующих элементов в векторе. Если вы хотите часто вставлять элементы в начале вашего контейнера, вы можете вместо этого использовать std::list или std::deque .

Вставка элемента в любую позицию вектора:

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}

Вставка другого вектора в любую позицию вектора:

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

Вставка массива в любую позицию вектора:

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

Используйте use reserve() перед тем, как вставить несколько элементов, если результирующий векторный размер известен заранее, чтобы избежать множественных перераспределений (см. Размер и емкость вектора ):

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

Обязательно не делайте ошибку при вызове resize() в этом случае, или вы случайно создадите вектор с 200 элементами, в которых только последняя ста будет иметь значение, которое вы намеревались.

Итерация над std :: vector

Вы можете перебирать std::vector несколькими способами. Для каждого из следующих разделов v определяется следующим образом:

std::vector<int> v;

Итерация в прямом направлении

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

Итерация в обратном направлении

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

Хотя нет встроенного способа использовать диапазон, основанный на обратном итерации; относительно просто исправить это. Диапазон, основанный на использовании begin() и end() для получения итераторов, и, таким образом, имитация этого объекта-обертки может обеспечить требуемые результаты.

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

Начиная с C ++ 11 cbegin() и cend() позволяют получить константный итератор для вектора, даже если вектор не const. Постоянный итератор позволяет вам читать, но не изменять содержимое вектора, что полезно для обеспечения корректности 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';
}

Это легко реализовать в более ранних версиях C ++:

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

Замечание об эффективности

Поскольку класс std::vector - это в основном класс, который управляет динамически распределенным смежным массивом, тот же принцип, описанный здесь, относится к векторам C ++. Доступ к содержимому вектора по индексу намного эффективнее при соблюдении принципа строкового порядка. Разумеется, каждый доступ к вектору также помещает его содержимое управления в кеш, но, как обсуждалось много раз (особенно здесь и здесь ), разница в производительности для итерации по std::vector по сравнению с необработанным массивом является незначительным. Таким образом, тот же принцип эффективности для необработанных массивов в C также применяется для std::vector C ++.

Доступ к элементам

Существует два основных способа доступа к элементам в std::vector

• доступ по индексу
• итераторы

Доступ по индексу:

Это можно сделать либо с помощью оператора индекса [] , либо с помощью функции-члена at() .

Оба возвращают ссылку на элемент в соответствующей позиции в std::vector (если это не vector<bool> ), так что он может быть прочитан, а также изменен (если вектор не const ).

[] и at() отличаются тем, что [] не гарантированно выполняет проверку границ, а at() . Доступ к элементам, где index < 0 или index >= size является неопределенным поведением для [] , а at() выбрасывает исключение std::out_of_range .

Примечание. В приведенных ниже примерах для ясности используется инициализация типа C ++ 11, но операторы могут использоваться со всеми версиями (если не указано 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

Поскольку метод at() выполняет проверку границ и может генерировать исключения, он медленнее, чем [] . Это делает [] предпочтительным кодом, где семантика операции гарантирует, что индекс находится в границах. В любом случае доступ к элементам векторов осуществляется в постоянное время. Это означает, что доступ к первому элементу вектора имеет одинаковую стоимость (по времени) доступа к второму элементу, третьему элементу и так далее.

Например, рассмотрим этот цикл

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

Здесь мы знаем, что индексная переменная i всегда находится в границах, поэтому было бы потерей циклов ЦП, чтобы проверить, что i находится в границах для каждого вызова operator[] .

Функции функции front() и back() позволяют легко обращаться к первому и последнему элементу вектора соответственно. Эти позиции часто используются, и специальные аксессоры могут быть более читабельными, чем их альтернативы, используя [] :

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}

Примечание . Неопределенное поведение вызывает функцию front() или back() для пустого вектора. Вы должны проверить , что контейнер не опустошить , используя empty() функции - члена (который проверяет , если контейнер пуст) перед вызовом front() или back() . Простой пример использования 'empty ()' для проверки пустого вектора:

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

В приведенном выше примере создается вектор с последовательностью чисел от 1 до 10. Затем он выталкивает элементы вектора до тех пор, пока вектор не станет пустым (используя «empty ()»), чтобы предотвратить неопределенное поведение. Затем вычисляется сумма чисел в векторе и отображается пользователю.

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]

итераторы:

Итераторы более подробно объясняются в примере «Итерация по std::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

Это соответствует стандарту, что итераторы std::vector<T> на самом деле являются T* s, но большинство стандартных библиотек этого не делают. Не делая этого и улучшает сообщения об ошибках, улавливает непереносимый код и может использоваться для управления итераторами с проверками отладки в сборках без релиза. Затем в релиз-сборках класс, обтекающий базовый указатель, оптимизирован.

Вы можете сохранить ссылку или указатель на элемент вектора для косвенного доступа. Эти ссылки или указатели на элементы в vector остаются стабильными, и доступ остается определенным, если вы не добавляете / не удаляете элементы в элементе или перед элементом в vector , или вы не можете изменить vector емкость. Это то же самое, что и правило для недействительности итераторов.

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 в качестве массива C

Существует несколько способов использования std::vector в качестве массива C (например, для совместимости с библиотеками C). Это возможно, потому что элементы в векторе хранятся смежно.

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

Перед C ++ 11 вы берете адрес первого элемента вектора для получения эквивалентного указателя, если вектор не пуст, эти оба метода взаимозаменяемы:

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

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

Примечание. Если вектор пуст, v[0] и v.front() не определены и не могут быть использованы.

При сохранении базового адреса данных вектора обратите внимание, что многие операции (такие как push_back , resize и т. Д.) Могут изменить местоположение памяти данных вектора, тем самым аннулируя предыдущие указатели данных . Например:

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

Итератор / указатель Invalidation

Итераторы и указатели, указывающие на std::vector могут стать недействительными, но только при выполнении определенных операций. Использование недействительных итераторов / указателей приведет к неопределенному поведению.

Операции, которые делают недействительными итераторы / указатели, включают:

• Любая операция вставки, которая изменяет capacity vector , аннулирует все итераторы / указатели:

  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.

• Любая операция вставки, которая не увеличивает емкость, все равно приведет к недействительности итераторов / указателей, указывающих на элементы в позиции вставки и мимо нее. Это включает в себя 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.
  

• Любая операция удаления приведет к недействительности итераторов / указателей, указывающих на удаленные элементы и на любые элементы, прошедшие удаленные элементы. Это включает в себя 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= (копирование, перемещение или иное) и clear() приведет к аннулированию всех итераторов / указателей, указывающих на вектор.

Удаление элементов

Удаление последнего элемента:

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

Удаление всех элементов:

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

Удаление элемента по индексу:

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

Примечание. Для vector удаляющего элемент, который не является последним элементом, все элементы за удаленным элементом должны быть скопированы или перемещены, чтобы заполнить пробел, см. Примечание ниже и std :: list .

Удаление всех элементов в диапазоне:

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

Примечание . Вышеуказанные методы не изменяют емкость вектора, а только размер. См. Размер и емкость файла .

Метод erase , который удаляет ряд элементов, часто используется как часть идиомы стирания-удаления . То есть, сначала std::remove перемещает некоторые элементы в конец вектора, а затем erase их. Это относительно неэффективная операция для любых индексов, меньших последнего индекса вектора, потому что все элементы после стертых сегментов должны быть перемещены в новые позиции. Для критически важных приложений, требующих эффективного удаления произвольных элементов в контейнере, см. Std :: list .

Удаление элементов по значению:

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}

Удаление элементов по условию:

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

Удаление элементов с помощью лямбда, не создавая дополнительной функции предиката

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

Удаление элементов по условию из цикла:

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
}

Хотя важно не увеличивать it в случае удаления, вам следует рассмотреть возможность использования другого метода при повторном стирании в цикле. Рассмотрим remove_if для более эффективного способа.

Удаление элементов по условию из обратной петли:

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

Обратите внимание на некоторые моменты для предыдущего цикла:

• Учитывая обратный итератор it , указывая на какой - то элемент, метод base дает регулярный (не обратный) итератор , указывающий на тот же элемент.

• vector::erase(iterator) стирает элемент, на который указывает итератор, и возвращает итератор элементу, который следует за данным элементом.

• reverse_iterator::reverse_iterator(iterator) строит обратный итератор с итератора.

Помещенный в целом, линия it = rev_itr(v.erase(it.base())) говорит: взять реверсивный итератор it , есть v Сотрите элемент указал его регулярной итератора; принимает полученный итератор, построить обратный итератор от него, и назначить его на обратный итератор it .

Удаление всех элементов с помощью v.clear() не освобождает память ( capacity() вектора остается неизменной). Чтобы освободить место, используйте:

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

v.shrink_to_fit();

Функция shrink_to_fit не гарантирует shrink_to_fit освобождения пространства, но большинство современных реализаций.

Поиск элемента в std :: vector

Функция std::find , определенная в заголовке <algorithm> , может использоваться для поиска элемента в std::vector .

std::find использует operator== для сравнения элементов для равенства. Он возвращает итератор в первый элемент в диапазоне, который сравнивается с значением.

Если этот элемент не найден, std::find возвращает std::vector::end (или std::vector::cend если вектор 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)

Если вам нужно выполнить много запросов в большом векторе, вы можете сначала рассмотреть сортировку вектора, прежде чем использовать алгоритм binary_search .

Чтобы найти первый элемент в векторе, который удовлетворяет условию, можно использовать std::find_if . В дополнение к двум параметрам, заданным для std::find , std::find_if принимает третий аргумент, который является объектом функции или указателем функции на функцию предиката. Предикат должен принять элемент из контейнера в качестве аргумента и вернуть значение, конвертируемое в 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

Преобразование массива в std :: vector

Массив можно легко преобразовать в std::vector , используя std::begin и 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);
}

C инициализатор_класса C ++ 11 может также использоваться для инициализации вектора сразу

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

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

вектор : Исключение для многих, так много правил

Стандарт (раздел 23.3.7) указывает, что предоставляется специализация vector<bool> , которая оптимизирует пространство, упаковывая значения bool , так что каждый занимает только один бит. Поскольку биты не адресуются в C ++, это означает, что на vector<bool> не помещаются несколько требований к vector :

• Сохраненные данные не обязательно должны быть смежными, поэтому vector<bool> не может быть передан в API C, который ожидает массив bool .
• at() , operator [] , а разыменование итераторов не возвращает ссылку на bool . Скорее они возвращают прокси-объект, который (несовершенно) имитирует ссылку на bool , перегружая его операторы присваивания. В качестве примера следующий код может быть недействительным для std::vector<bool> , поскольку разыменование итератора не возвращает ссылку:

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

Аналогично, функции, ожидающие bool& аргумент, не могут использоваться с результатом operator [] или at() примененного к vector<bool> , или с результатом разыменования его итератора:

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

Реализация std::vector<bool> зависит как от компилятора, так и от архитектуры. Специализация реализуется путем упаковки n Booleans в младший адресный раздел памяти. Здесь n - это размер в битах самой младшей адресуемой памяти. В большинстве современных систем это 1 байт или 8 бит. Это означает, что один байт может хранить 8 булевых значений. Это улучшение по сравнению с традиционной реализацией, где 1 булево значение хранится в 1 байт памяти.

Примечание. В приведенном ниже примере показаны возможные побитовые значения отдельных байтов в традиционном и оптимизированном vector<bool> . Это не всегда верно для всех архитектур. Это, однако, хороший способ визуализации оптимизации. В приведенных ниже примерах байт представлен как [x, x, x, x, x, x, x, x].

Традиционный std::vector<char> Сохранение 8 Булевых значений:

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

Поразрядное представление:

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

Специализированный std::vector<bool> Сохранение 8 Булевы значения:

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

Поразрядное представление:

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

Обратите внимание, что в традиционной версии std::vector<bool> 8 булевых значений занимают 8 байт памяти, тогда как в оптимизированной версии std::vector<bool> они используют только 1 байт объем памяти. Это значительное улучшение использования памяти. Если вам нужно передать vector<bool> в API стиля C, вам может потребоваться скопировать значения в массив или найти лучший способ использования API, если память и производительность подвержены риску.

Размер и емкость вектора

Размер вектора - это просто количество элементов в векторе:

1. Текущий размер вектора запрашивается функцией size() . Функция удобство empty() возвращает true если размер равен 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. По умолчанию сконструированный вектор начинается с размера 0:

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

3. Добавление N элементов к вектору увеличивает размер на N (например, с помощью функций push_back() , insert() или resize() ).

4. Удаление N элементов из вектора уменьшает размер на N (например, с помощью pop_back() , pop_back() erase() или clear() ).

5. Вектор имеет верхний предел для реализации по размеру, но вы, скорее всего, исчерпаете ОЗУ до его достижения:

   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
   

Общая ошибка: размер не обязательно (или даже обычно) 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] );
}

Векторная емкость отличается от размера . В то время как размер - это просто количество элементов, которые вектор имеет в настоящее время, емкость для количества элементов, на которые он выделил / зарезервировал память. Это полезно, потому что слишком частые (пере) выделения слишком больших размеров могут быть дорогими.

1. Текущая емкость вектора запрашивается функцией функции capacity() . Емкость всегда больше или равна размеру :

   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. Вы можете вручную зарезервировать емкость по reserve( N ) функции (она меняет векторную емкость на 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. Вы можете запросить избыточную емкость, которая будет выпущена с помощью shrink_to_fit() (но реализация не должна вас подчиняться). Это полезно для сохранения использованной памяти:

   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)
   

Вектор частично управляет емкостью автоматически, когда вы добавляете элементы, которые он может решить, чтобы расти. Исполнители любят использовать 2 или 1,5 для фактора роста (золотое соотношение будет идеальным значением, но нецелесообразным из-за рационального числа). С другой стороны, вектор обычно не сжимается автоматически. Например:

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

Конкатенационные векторы

Один std::vector может быть добавлен к другому с помощью функции-члена 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());

Однако это решение выходит из строя, если вы пытаетесь добавить вектор к себе, потому что стандарт указывает, что итераторы, данные для insert() не должны быть того же диапазона, что и элементы объекта получателя.

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

Если порядок элементов в принимающем векторе не имеет значения, учитывая количество элементов в каждом векторе, можно избежать ненужных операций копирования:

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

Уменьшение пропускной способности вектора

std::vector автоматически увеличивает свою емкость при вставке по мере необходимости, но никогда не уменьшает ее емкость после удаления элемента.

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

Чтобы уменьшить его емкость, мы можем скопировать содержимое вектора в новый временный вектор. Новый вектор будет иметь минимальную емкость, необходимую для хранения всех элементов исходного вектора. Если уменьшение размера исходного вектора было значительным, то уменьшение емкости для нового вектора, вероятно, будет значительным. Затем мы можем поменять исходный вектор на временный, чтобы сохранить его минимальную емкость:

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

v.shrink_to_fit();

Использование сортированного вектора для быстрого поиска элементов

Заголовок <algorithm> предоставляет ряд полезных функций для работы со отсортированными векторами.

Важным предварительным условием для работы с отсортированными векторами является то, что сохраненные значения сравнимы с < .

Несортированный вектор можно отсортировать с помощью функции std::sort() :

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

Сортированные векторы позволяют эффективно искать элементы, используя функцию std::lower_bound() . В отличие от std::find() , он выполняет эффективный двоичный поиск на векторе. Недостатком является то, что он дает только действительные результаты для отсортированных диапазонов ввода:

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

Примечание. Если запрошенное значение не является частью вектора, std::lower_bound() вернет итератор в первый элемент, который больше запрашиваемого значения. Такое поведение позволяет нам вставить новый элемент в нужное место в уже отсортированном векторе:

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

Если вам нужно вставить сразу несколько элементов, возможно, более эффективно сначала вызвать push_back() для всех них, а затем вызвать std::sort() после того, как будут вставлены все элементы. В этом случае увеличенная стоимость сортировки может окупиться сниженной стоимостью вставки новых элементов в конце вектора, а не в середине.

Если ваш вектор содержит несколько элементов одного значения, std::lower_bound() попытается вернуть итератор первому элементу std::lower_bound() значения. Однако, если вам нужно вставить новый элемент после последнего элемента std::upper_bound() значения, вы должны использовать функцию std::upper_bound() поскольку это приведет к меньшему смещению элементов:

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

Если вам нужны итераторы верхней и нижней границ, вы можете использовать функцию std::equal_range() для эффективного извлечения обоих из них одним вызовом:

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;

Чтобы проверить, существует ли элемент в отсортированном векторе (хотя это и не относится к векторам), вы можете использовать функцию std::binary_search() :

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

Функции, возвращающие большие векторы

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

Найти максимальный и минимальный элемент и соответствующий индекс в векторе

Чтобы найти самый большой или самый маленький элемент, хранящийся в векторе, вы можете использовать методы std::max_element и std::min_element соответственно. Эти методы определены в заголовке <algorithm> . Если несколько элементов эквивалентны наибольшему (наименьшему) элементу, методы возвращают итератор в первый такой элемент. Вернуть v.end() для пустых векторов.

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

Выход:

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

Матрицы с использованием векторов

Векторы могут использоваться в качестве 2D-матрицы, определяя их как вектор векторов.

Матрица с 3 строками и 4 столбцами с каждой ячейкой, инициализированной как 0, может быть определена как:

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

Значения в таком векторе могут быть доступны аналогично двумерному массиву

int var = matrix[0][2];

Итерация по всей матрице аналогична и для нормального вектора, но с дополнительной размерностью.

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

Вектор векторов - удобный способ представления матрицы, но это не самый эффективный: отдельные векторы разбросаны по памяти, а структура данных не кэширована.

Кроме того, в соответствующей матрице длина каждой строки должна быть одинаковой (это не относится к вектору векторов). Дополнительная гибкость может быть источником ошибок.