Как изменить capacity vector

В описании контейнера vector можно встретить такие функции как size и resize, capacity и reserve. С первого взгляда кажется, что половина явно лишняя, ведь размер у вектора может быть только один.
Почему так? Потому что память для вектора выделяется «про запас»(подробнее ниже), и надо уметь управлять и количеством элементов вектора, и количеством памяти, которое он занимает. size и resize — нужны для работы с реальным числом элементов вектора, capacity и reserve — для работы с памятью.
size — выдает количество элементов в векторе
resize — изменяет количество элементов в векторе
capacity — выдает под сколько элементов выделена память
reserve — резервиует память

Вот что сделает код, скомпиленный Visual C++ 6.0:

vector <int> v;
v.push_back(1); //size==1, capacity==1
v.push_back(17); //size==2, capacity==2
v.push_back(23); //size==3, capacity==4


Зачем нужен этот запас?
Допустим, у нас есть вектор из n элементов. Что происходит, когда программист добавляет еще один? Когда есть запасная память, элемент пишется туда. Когда ее нет, выделяется непрерывный кусок памяти достаточный для n*K элементов, где K — коэффицент. В него копируются предыдущие n, добавляется наш новый элемент, старый кусок размером n освобождается. Если бы запаса не было, то память бы выделялась каждый раз при добавлении нового элемента, что страшно неэффективно.
Зачем нужен reserve, если все и без участия программиста так хорошо работает? Это может быть полезно в некоторых ситуациях. Например, знание того, как выделяется память под вектор, можно использовать и в начале, при его задании. Допустим, я точно знаю, что в векторе будет где-то 100-110 элементов. Я сразу же создам вектор размером 110, это поможет избежать перевыделений памяти, положительно скажется на производительности.

vector <int> v;
v.reserve(110);

Это вовсе не означает, что зарезервировано место для 110-ти элементов ровно. Зарезервировано место как минимум для 110 элементов, возможно больше.

Почему обязательно нужно выделять непрерывный кусок памяти, почему при увеличении размера вектора нельзя выделить кусочек где-нибудь еще? Чтобы можно было передавать vector как параметр в функции, которые требуют массив. Например, в какую-нибудь старую библиотечную С-функцию, которая принимает массив и его размер, можно передать вектор, при условии, что он не пустой. Это было сделано специально, чтобы убедить людей пользоваться векторами. Ведь можно продолжать использовать старые библиотеки.

//если где-то описана такая функция
void myPrint(int* v, int vsize);

Коэффицент К
(Все приведенные ниже рассуждения верны только для first-fit схем выделения памяти, то есть выделяется первый по порядку подходящий кусок)
Что за коэффицент K, который используется при выделении памяти , чему он равен? Так, как у нас там происходит выделение памяти… Новую выделили, прокопировали туда данные, старую освободили. И так несколько раз. Если память идет подряд, то образуется пробел, который можно было бы использовать. Нужно подобрать такой коэффицент, который позволит эти пробелы использовать. Было вычислено, что коэффицент должен быть меньше, чем (1+sqrt(5))/2. Что примечательно, выражение (1+sqrt(5))/2 — это же «золотое сечение».
Откуда берется это число?

Я видела вот такое доказательство:
Пусть у нас изначально размер вектора был S, S>0.
После первого перевыделения памяти, он стал K*S.
После второго K*K*S.

Нам нужно, чтобы K*K*S влезло в S+K*S, то есть K*K*S<=S+K*S. S>0, на него можно сократить.
K^2-K-1<=0
Решаем, получаем
K<=(1+sqrt(5))/2 (второй корень, отрицательный, не интересен)
Правильно? Не правильно. Кусок K*S все еще занят, его нельзя использовать.

Нам нужно, чтобы в момент выделения K^(n+1)*S память размером S+K*S+K^2*S+...+K^(n-1)*S была достаточной, чтобы вместить этот K^(n+1)*S. K^n*S все еще занят, мы его использовать не можем. В итоге получаем.
S+K*S+K^2*S+...+K^(n-1)*S <= K^(n+1)*S или, зная, что S>0
1+K+K^2+...+K^(n-1) <= K^(n+1)
Решать я это не буду, Andrew Koenig считает, что подходящий в данном случае корень (1+sqrt(5))/2, доверюсь ему.
Если говорить уж совсем точно, то (1+sqrt(5))/2 не совсем правильное число, нужнен коэффицент поменьше. Потому что нужна еще дополнительная память для разных служебных нужд.
В Visual C++ 6.0 взята константа 2. Такой коэффицент использовать пробелы не дает. А вот в Visual C++ 7 уже используется константа 1.5.

Swap Trick
Про выделение памяти ясно. А как с освобождением памяти? Да, при увеличении размера вектора будет выделена память, а когда вектор уменьшается? Нет, она не будет освобождена. Что несколько неудобно, потому что если в векторе было 10000 элементов, а потом их количество уменьшилось до 10 и осталось где-то в таких пределах, то получается что куча памяти пропадает зря. Что можно сделать в такой ситуации? Сделать новый вектор и туда прокопировать старый. Это можно сделать красиво с помощью swap trick.
vector<int>(v).swap(v);
В этой строчке происходит следующее: создается безымянный vector <int>, который инициализируется элементами из v, а потом он меняется с вектором v местами. Это вовсе не гарантирует, что памяти будет выделено ровно столько, сколько нужно, а не больше. Это зависит от реализации. Но, скорее всего, все будет лучше, чем было.
Я читала у Герба Саттера, что swap сохраняет в корректном состоянии все итераторы, ссылки и указатели.

Может я чего-то не понимаю, но у меня получилось вот что.

std::vector <int> v;
std::vector <int>::iterator it;

Updated 23.11.2005:
Вычитала, что в Visual C++ 7.1 при вызове метода clear() память таки высвобождается. Не могу проверить для 7.1, зато проверила для Microsoft Visual C++ Toolkit 2003. Действительно, память освобождается.

То есть для такого кода:
vector <int> v;
v.reserve(17);
cout<<v.capacity()<<endl;
v.clear();
cout<<v.capacity()<<endl;

Вывод получается следующим
Microsoft Visual C++ Toolkit 2003:
17
0
MSVC++6.0:
17
17
MinGW gcc 3.4.4:
17
17

Стандарт не указывает должна ли освобождаться память при вызове метода clear(), так что все компиляторы здесь действуют по Стандарту.

Ссылки по теме:
Vector Resizing Algorithm
comp.lamg.c++.moderated, vector growth factor of 1.5

Technorati tag: C++

Тема есть продолжением темы:

• Общие сведения о классе vector. Обзор методов. Создание динамического массива. Способы доступа к элементам вектора

Содержание

• 1. Метод size(). Определить размер вектора
• 2. Метод max_size(). Максимально-допустимый размер массива
• 3. Метод capacity(). Определить размер массива с учетом зарезервированной памяти
• 4. Метод empty(). Определить, пустой ли вектор
• 5. Метод shrink_to_fit(). Установить размер массива в памяти по количеству элементов в нем без дополнительного резервирования памяти
• 6. Метод resize(). Изменить размер массива
• 7. Метод reserve(). Зарезервировать дополнительную память для элементов массива
• Связанные темы

Поиск на других ресурсах:

1. Метод size(). Определить размер вектора

Текущее количество элементов в динамическом массиве vector можно определить с помощью метода size(). Синтаксис объявления метода size() следующий

size_t vector<T>::size() const

здесь T – тип элементов массива.

Пример.

// Некоторый класс
class MyClass
{
  // ...
};

...

// Метод size()
// 1. Создать вектор из 5 чисел типа int и получить его размер
vector<int> A1(5);
int n1 = A1.size(); // n1 = 5

// 2. Создать вектор из 10 экземпляров типа MyClass и получить его размер
vector<MyClass> A2(10);
int n2 = A2.size(); // n2 = 10

// 3. Создать пустой вектор типа bool и получить его размер
vector<bool>* A3 = new vector<bool>(); // создать через указатель
int n3 = A3->size(); // n3 = 0

...

  ⇑

2. Метод max_size(). Максимально-допустимый размер массива

Метод max_size() позволяет получить максимально-допустимое количество элементов массива. Это значение зависит от типа элементов массива vector. Для различных типов оно разное
В зависимости от типа данных массива vector, это значение может колебаться. Чем больше размер данных каждого элемента массива vector, тем меньше значение max_size().
Синтаксис объявления метода max_size() следующий:

size_t vector<T>::max_size() const

здесь T – тип элементов динамического массива.

Пример.

...

// Некоторый класс
class Complex
{
public:
  double re;
  double im;

  // ...
};

...

// Метод max_size()
// 1. Создать вектор из 5 чисел типа int и получить его максимально-допустимый размер
vector<int> A1(5);
int max1 = A1.max_size(); // max1 = 1073741823

// 2. Создать вектор из 10 экземпляров типу Complex
// и получить его максимально-допустимый размер
vector<Complex> A2(10);
int max2 = A2.max_size(); // max2 = 268435455

// 3. Создать пустой вектор типа bool и получить его максимально-допустимый размер
vector<bool>* A3 = new vector<bool>(); // создать через указатель
int max3 = A3->max_size(); // max3 = 2147483647
cout << max3 << endl;

...

  ⇑

3. Метод capacity(). Определить размер массива с учетом зарезервированной памяти

Метод capacity() возвращает количество элементов, выделенное для массива.

При добавлении нового элемента в массив, нужно выделить дополнительную память на 1 элемент больше. Однако, компилятор может увеличить размер памяти на несколько элементов чтобы при последующем добавлении еще одного элемента не выполнять повторно такие операции как освобождение памяти под предварительно созданный массив, выделение нового фрагмента и тому подобное. Таким образом ускоряется быстродействие.

Синтаксис объявления метода следующий

size_t vector<T>::capacity<T> const

здесь T – тип элементов массива.

Пример. В примере демонстрируется разница между методами size() и capacity().

#include <iostream>
#include <vector>
using namespace std;

void main()
{
  // Метод capacity()
  // Создать массив из 10 элементов типа float
  vector<float> A1(10);

  // Вывести реальное количество элементов массива
  int capacity = A1.capacity();
  int size = A1.size();
  cout << "A1.capacity() = " << capacity << endl;
  cout << "A1.size() = " << size << endl;

  // Добавить 1 элемент в конец массива
  A1.push_back(5);
  cout << "+1 item" << endl;

  // Вывести новые значения количества элементов в массиве
  capacity = A1.capacity();
  size = A1.size();
  cout << "A1.capacity() = " << capacity << endl; // 15
  cout << "A1.size() = " << size << endl; // 11
}

Результат выполнения программы

A1.capacity() = 10
A1.size() = 10
+1 item
A1.capacity() = 15
A1.size() = 11

Как видно из результата, при добавлении нового элемента, количество элементов в массиве увеличилась на 1 и составляет 11 (метод size()). Однако, сам размер массива увеличился на 5 элементов и составляет 15 (метод capacity()). Теперь можно добавлять еще 4 элемента без лишнего перераспределения памяти. Если добавление элементов будет выполняться в цикле, то такой подход позволит ускорить выполнение программы.

  ⇑

4. Метод empty(). Определить, пустой ли вектор

С помощью метода empty() можно определить, пустой ли массив (количество элементов в массиве равно 0). Общая форма метода empty() следующая:

bool vector<T> empty() const

здесь T – тип элементов массива.

Пример.

#include <iostream>
#include <vector>
using namespace std;

void main()
{
  // Метод empty() - определить, пустой ли вектор
  vector<double> A(5); // Создать массив из 5 элементов

  // Проверка, пустой ли массив
  if (A.empty())
    cout << "Vector A is empty." << endl;
  else
    cout << "Vector A is not empty." << endl;

  // Очистить массив
  A.clear();

  // Еще раз проверить, пустой ли массив
  if (A.empty())
    cout << "Vector A is empty." << endl;
  else
    cout << "Vector A is not empty." << endl;
}

Результат выполнения программы

Vector A is not empty.
Vector A is empty.

  ⇑

5. Метод shrink_to_fit(). Установить размер массива в памяти по количеству элементов в нем без дополнительного резервирования памяти

Метод shrink_to_fit() позволяет выровнять память, выделенную (зарезервированную) для элементов массива (метод capacity()) с памятью, занятой элементами массива (метод size()).
Количество зарезервированных элементов (для которых выделена память) возвращается методом capacity(). Количество элементов, определенных в массиве, возвращаются методом size(). Значение, возвращаемое методом capacity() всегда больше или равно значения, возвращаемого методом size().
Если значение, полученное методом capacity() больше значения, полученного методом size(), то метод shrink_to_fit() позволяет выровнять эти значения. При этом уменьшается размер памяти, возвращаемый методом capacity().
Метод эффективен, когда в результате различных операций с массивом, остается большой избыток зарезервированных элементов в массиве.

Общая форма метода следующая

void shrink_to_fit()

После вызова этого метода, методы size() и capacity() всегда будут возвращать одинаковые значения.

Пример.

#include <iostream>
#include <vector>
using namespace std;

void main()
{
  // Метод shrink_to_fit() - изменить значение зарезервированной памяти для массива
  // 1. Создать массив целых чисел на основе списка инициализации
  initializer_list<int> L = { 1, 2, 3, 4, 5 };
  vector<int> A1(L);

  // 2. Вывести количество элементов, для которых уже распределена память
  cout << "Allocated size = " << A1.capacity() << endl; // 5

  // 3. Вывести текущее количество элементов
  cout << "Size = " << A1.size() << endl; // 5

  // 4. Прибавить к массиву 1 элемент
  A1.push_back(6);
  cout << "+1 item" << endl;

  // 5. Еще раз вывести распределенное количество элементов
  // и текущее количество элементов
  cout << "Allocated size = " << A1.capacity() << endl; // 7
  cout << "Size = " << A1.size() << endl; // 6

  // 6. Выровнять распределенное количество с текущим количеством
  A1.shrink_to_fit();
  cout << "shrink_to_fit()" << endl;

  // 7. Повторно вывести распределенное и фактическое количество элементов
  cout << "Allocated size = " << A1.capacity() << endl; // 6
  cout << "Size = " << A1.size() << endl; // 6
}

Результат выполнения программы

Allocated size = 5
Size = 5
+1 item
Allocated size = 7
Size = 6
shrink_to_fit()
Allocated size = 6
Size = 6

Как видно из результата, после добавления элемента в массив, размер массива увеличился с 5 до 6. Это естественно и метод size() это показал. Но реальный размер массива увеличился с 5 до 7, о чем показал метод capacity(). То есть, выделилось на 1 элемент больше.
Вызов метода shrink_to_fit() перераспределил память так, что количество выделенной памяти под элементы стала равна количеству памяти, занятой элементами.

  ⇑

6. Метод resize(). Изменить размер массива

Метод resize() позволяет изменять размер динамического массива в большую или в меньшую сторону. Метод имеет две перегруженные реализации.
Первая реализация имеет следующее объявление

void resize(const size_t _NewSize)

здесь

• _NewSize – новый размер массива. Если _NewSize больше текущего размера массива, то все остальные элементы дополняются нулевыми значениями.

Вторая реализация имеет следующее объявление

void resize(const size_t _NewSize, const T& Val)

здесь

• _NewSize – новый размер массива;
• T – тип элементов массива;
• Val — значения, которыми дополняются элементы массива в случае, если значение _NewSize больше текущего размера.

Пример.

...

// Метод resize() - изменить размер массива
// 1. Создать массив целых чисел на основе списка инициализации
initializer_list<int> L = { 1, 2, 3, 4, 5 };
vector<int> A1(L);

// 2. Изменить размер массива A1
A1.resize(8); // A1 = { 1, 2, 3, 4, 5, 0, 0, 0 }

// 3. Уменьшить размер массива A1 с заполнением значениями 10
A1.resize(6, 10); // A1 = { 1, 2, 3, 4, 5, 0 }

// 4. Увеличить размер массива A1 с заполнением значениями 15
A1.resize(9, 15); // A1 = { 1, 2, 3, 4, 5, 0, 15, 15, 15 }

...

  ⇑

7. Метод reserve(). Зарезервировать дополнительную память для элементов массива

Метод reserve() позволяет выделить (зарезервировать) память для элементов массива, которая возвращается методом capacity(). Реальное количество элементов в массиве, которое возвращается методом size(), не изменяется.
Правильное использование метода в программе позволяет ускорить выполнение программы в случаях, когда активно изменяется размер массива (часто выполняются операции добавления, удаления элементов из массива). Это осуществляется за счет уменьшения количества операций, связанных с перераспределением памяти.

Объявления метода следующее

void reserve(size_t Newcapacity)

здесь

• Newcapacity – новый размер массива с учетом зарезервированных элементов.

Пример.

#include <iostream>
#include <vector>
using namespace std;

void main()
{
  // Метод reserve() - зарезервировать дополнительную память для массива
  // 1. Объявить массив из 5 элементов типа float
  vector<float> A(5);

  // 2. Вывести количество элементов массива и зарезервированное количество
  cout << A.size() << endl; // 5
  cout << A.capacity() << endl; // 5

  // 3. Зарезервировать дополнительную память для массива
  A.reserve(12);

  // 4. Вывести количество элементов массива и зарезервировано место для элементов массива
  cout << A.size() << endl; // 5
  cout << A.capacity() << endl; // 12
}

Результат выполнения программы

5
5
5
12

  ⇑

Связанные темы

• Общие сведения о классе vector. Обзор методов. Создание динамического массива. Способы доступа к элементам вектора
• Методы, изменяющие данные в массиве. Методы push_back(), pop_back(), clear(), swap(), operator=(), erase(), insert(), assign()
• Методы, обеспечивающие доступ к элементам массива: at(), front(), back(), data(), begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin(), crend()

  ⇑

материал взят с сайта artlang

Данная статья рассчитана на неискушенного программиста C++. С другой стороны любой, кто программирует на C++ обязан знать то, что описывается ниже. Речь пойдет об одном из самых популярных контейнеров в STL. А именно, о векторе (std::vector). С него, обычно, начинается описание контейнеров в книгах по языку C++ и STL. Считается, что это наиболее простой контейнер, с понятным интерфейсом и предсказуемым временем операций. Однако, за описанием интерфейса часто “теряются” основные правила при работе с вектором, которые могут быть не так очевидны для начинающего программиста. Написать свой хороший вектор крайне сложно — такие реализации далеки от совершенства, значит надо знать как работают стандартные.

Для закрепления материала предлагаю пройти тест на понимание std::vector.

Внутреннее устройство вектора

Джосаттис в своей книге описывает вектор так: “Этот контейнер моделирует динамический массив. Таким образом, вектор — это абстракция, управляющая своими элементами в стиле динамического массива из языка C. Однако в стандарте не указано, что реализация вектора использует динамический массив. Скорее это следует из ограничений и спецификаций сложности его операций”.

Вектор представляет собой шаблонный класс в пространстве имен std:

namespace std {
    template < typename T, 
               typename Allocator = allocator<T> >
    class vector;
}

Второй необязательный шаблонный параметр задает модель памяти. По умолчанию используется шаблонный класс allocator. Этот класс предоставляет стандартная библиотека C++, и именно он отвечает за выделение и освобождение памяти. Если вектору в качестве второго параметра передать какой-либо другой распределитель памяти (allocator), то вектор, возможно, уже будет основан не на C-массиве. Однако, обычно второй параметр остается заданным по умолчанию, поэтому рассмотрим подробнее стандартный распределитель памяти — std::allocator. Он, кстати, используется по умолчанию для всех контейнеров библиотеки STL.

Вектору (и всем другим контейнерам STL) от аллокатора нужно прежде всего, чтобы он выделял и освобождал некоторую область памяти, в тот момент когда это требуется контейнеру, Стандартный аллокатор делает это так:

template<class T>
class allocator
{
public:
    typedef T value_type;
    
    typedef value_type *pointer;
    typedef const value_type *const_pointer
        
    typedef size_t size_type;
    
    pointer allocate(size_type _Count)  // Выделяем память для _Count элементов
    {                                   // типа value_type  
        void *_Ptr = 0;

        if (_Count == 0)  // Если ничего не запросили, то ничего и не делаем
            ;
        else if (((size_t)(-1) / sizeof (value_type) < _Count)
            || (_Ptr = ::operator new(_Count * sizeof (value_type))) == 0)
        {
            throw bad_alloc();  // Выделение памяти не удалось
        }   
        return ((pointer)_Ptr);
    }
    
    void deallocate(pointer _Ptr, size_type)
    {   
        ::operator delete(_Ptr);  // Освобождение памяти
    }
    
    // Остальная реализация не приводится, чтобы сохранить наглядность примера
};

Так аллокатор реализован у Microsoft (MSVC), и также он реализован в GCC. Нужно понимать, что operator new отличается от просто new. Вызов new (который все мы используем) на самом деле разбивается на два этапа, если так можно выразиться: сначала вызывается operator new, который возвращает указатель на некоторую выделенную область памяти, а затем вызывается конструктор, который создает объект в этой области. Вызвать конструктор напрямую невозможно, однако с помощью синтаксиса размещения можно заставить компилятор вызвать конструктор. Следующие два примера создания foo1 и foo2 идентичны:

#include <new>

class Foo
{
public: 
    Foo() {}
};

int main(int argc, char** argv) 
{
    // Вот так мы все привыкли создавать объект в "куче":
    Foo *foo1 = new Foo(); // Выделение памяти + Вызов конструктора

    // А вот какие вызовы происходят на самом деле:
    void *ptr = operator new(sizeof(Foo)); // Выделение памяти
    Foo *foo2 = ::new (ptr) Foo(); // Вызов конструктора, синтаксис размещения
    
    return 0;
}

Широко распространено заблуждение, что применение оператора new (первый случай в примере) подразумевает необходимость работать с кучей (heap). Вызов new, лишь означает, что будет вызвана функция operator new и эта функция возвратит указатель на некоторую область памяти, Стандартные operator new и operator delete действительно работают с кучей, но члены operator new и operator delete могут делать всё, что угодно! Нет ограничения на то, где будет выделена область памяти. Но вернемся к вектору.

После того, как память будет выделена, она “переходит” под управление вектора. До стандарта C++11 все аллокаторы должны были быть максимум “stateless”, т. е. не хранить никаких состояний. Поэтому все состояния (переменные) хранит вектор. Как Вы думаете, сколько нужно переменных вектору, чтобы реализовать весь свой интерфейс? Ответ — три. Трех указателей достаточно, чтобы вектор смог управлять памятью и обеспечил весь свой функционал:

• первый (first) указатель указывает на начало выделенной области памяти
• второй (last) указатель указывает на позицию следующую за последним элементом, хранящимся в выделенной области памяти
• третий (end) указывает на “конец” выделенной области памяти

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

// _Capacity - Количество элементов, которое может быть размещено в памяти вектора
first = Getal().allocate(_Capacity); // Getal() возвращает ссылку на аллокатор
last = first;  // В начале вектор пуст, затем last начинает смещаться к end
end = first + _Capacity; // Граница выделенного участка памяти, пересекать её нельзя!

Посмотрите теперь, как лаконично и кратко реализуются некоторые функции-члены вектора:

size_t capacity() const
{   // return current length of allocated storage
    return (end - first);
}

size_t size() const
{   // return length of sequence
    return (last - first);
}

bool empty() const
{   // test if sequence is empty
    return (first == last);
}

const_reference at(size_t pos) const
{   // subscript nonmutable sequence with checking
    if (last - first <= pos) throw out_of_range();
    
    return (*(first + pos));
}

const_reference operator[](size_t pos) const
{   // subscript nonmutable sequence
    return (*(first + pos));
}
// Сплошная арифметика указателей...

Когда программист добавляет в конец вектора новый элемент происходит примерно следующее:

void push_back(const value_type& val)
{   // insert element at end
    
    if (last == end) {      
    // Если память закончилась, 
    // то нужно запросить новую область, больше предыдущей    
        
        // размер текущей области памяти
        size_t _Capacity = capacity();
        
        // требуемый минимальный размер новой области
        size_t _Count = size() + 1;     
        
        if (max_size() - _Capacity / 2 < _Capacity) {
            
            // новая область больше на 50% предыдущей
            _Capacity = _Capacity + _Capacity / 2;  
        }
        
        if (_Capacity < size() + 1)  {
            
            // Если нет возможности увеличить на 50%, то
            // пробуем выделить минимально необходимый размер
            _Capacity = _Count;      
        }
        
        _Reallocate(_Capacity); 
        // Перераспределение памяти, значения fisrt, last и end
        // будут изменены! Предыдущий участок памяти будет освобожден. 
        // В новый участок будут скопированы все данные из предыдущего. 
        // Это не быстрый процесс...
    } 
    
    // Вызов копирующего конструктора, синтаксис размещения
    ::new ((void *)last) value_type(val);
    
    ++last; // Сдвигаем указатель с учетом вставленного элемента
}

Данный код взят из исходников STL MSVC, но он не сильно отличается от аналогичного кода в GCC. Код был несколько упрощен, чтобы суть алгоритма не была “размыта” и оставалась ясной.

Итак. Вектор гарантирует (по стандарту), что вставка в конец происходит очень быстро за одно и тоже время. Однако если мы попадаем под условие last == end (если выделенная память закончилась) то время вставки в конец сильно возрастает. То на сколько затянется процесс трудно спрогнозировать и это в большей степени зависит от конструкторов копирования и деструкторов элементов, находящихся в векторе. Так как они будут вызваны для каждого существующего элемента в векторе при перераспределении памяти.

Приемы эффективного использования

В предыдущем примере хорошо видно, как реализация вектора “пытается бороться” с неэффективным использование памяти. Проблема возникает, когда память, выделенная аллокатором, заканчивается. В этот момент вектор запрашивает у аллокатора новый участок памяти, больше предыдущего, которой смог бы разместить все элементы уже содержащиеся в векторе, а также новые. Для этого повторно выделяется память из “кучи”. Операция эта достаточно медленная, и к тому же блокирующая в общем случае (heap lock — это “узкое место” многопоточных приложений). Таких операций должно быть как можно меньше.

Поэтому вектор запрашивает память “про запас”, чтобы не инициировать новое перераспределение памяти при добавлении следующего элемента. Если бы вектор на каждый push_back вызывал перераспределение памяти, он был бы очень медленным. Вместо этого, когда память оказывается исчерпана, вектор запрашивает на 50% больше памяти, чем у него было. Так он уменьшает количество повторных обращений к аллокатору и, тем самым, перераспределений памяти.

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

Рассмотрим пример, в котором мы заполним вектор одним миллионом объектов класса Foo. Будем считать, что к Foo не применяется оптимизация при копировании:

class Foo
{
public: 
    
    explicit Foo(long long) {}
    Foo(const Foo&) {}
    ~Foo() {}
};


int main(int argc, char** argv) 
{
    std::vector<Foo> vec;

    for (long long ii = 0; ii < 1000000; ++ii) {
        vec.push_back(Foo(ii));
    }
    return 0;
}

По выходу из блока for, оказалось что:

1. копирующий конструктор был вызван более 3 миллионов раз
2. деструктор был вызван более 3 миллионов раз
3. перераспределение памяти произошло 35 раз (в начале емкость вектора была равна 0)

Ни одна из этих миллионов операций нам не была нужна. Поэтому попробуем избавиться от них.

reserve(num)

reserve — это функция-член вектора, которая увеличивает его емкость, то есть принудительно запрашивает у аллокатора область памяти такого размера, чтобы вектор, при желании, мог разместить в ней num элементов. Вызывать её стоит сразу после создания объекта вектора, пока в нем еще нет элементов. Допустим Вы можете не знать точного числа элементов, но Вы как минимум можете предположить это значение, затем накиньте еще 50% (если нет проблем с памятью) и это значение передайте reserve. Вызвать reserve имеет смысл практически всегда, даже если число элементов не большое. Так Вы поможете вектору избежать множества лишних шагов. Если в примере, сразу после создания объекта вектора, вызвать reserve:

std::vector<Foo> vec;
vec.reserve(1000000); // Сразу зарезервируем место под миллион элементов

то по выходу из блока for, окажется что:

• копирующий конструктор был вызван ровно 1 миллион раз
• деструктор был вызван ровно 1 миллион раз
• перераспределение памяти не происходило ни разу

Отличный результат! Миллионы лишних вызовов удалось избежать, к тому же перераспределение памяти ни разу не произошло! А всё потому что вектору хватило памяти разместить все наши элементы. Всегда помните об этом, и вызывайте reserve, после создания вектора. Это полезно еще и потому, что стандатрный механизм выделения “про запас” (на 50% больше, чем было) иногда может привести к избыточному выделению памяти. Много лишнего, это тоже плохо. Лучше контролируйте этот процесс сами.

emplace_back(args)

Идем дальше. Порой удается избежать вообще вызовов копирующего конструктора при добавлении нового элемента. Начиная со стандарта C++11 появилась функция-член emplace_back, которая конструирует элемент прямо на месте, где его и предполагалось разместить. При этом не вызывается ни копирующий конструктор, ни перемещающий. Аргументы, переданные функции emplace_back, точно также передаются затем конструктору элемента. Перепишем добавление элементов в примере, задействова emplace_back:

std::vector<Foo> vec;
vec.reserve(1000000); // Сразу зарезервируем место под миллион элементов

for (long long ii = 0; ii < 1000000; ++ii) {
    
    // Передаем аргументы так, будто вызываем обычный конструктор Foo
    vec.emplace_back(ii); 
}

По выходу из блока for, оказалось что:

• копирующий конструктор не вызывался ни разу
• деструктор не вызывался ни разу
• перераспределение памяти не происходило ни разу

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

POD

Еще одним способом оптимизировать работу с вектором, является использование POD (“plain old data”) типов в качестве элементов. Так как вектор управляет непрерывным участком памяти, он может применять тривиальные функции копирования, наподобие memcpy. Новый стандарт C++11 несколько расширил понятие POD. Обязательно ознакомьтесь с этими простыми структурами данных, и смело используйте их в качестве элеметов вектора, так как для них будет применяться оптимизация при копировании.

Добавляйте в конец и меньше ищите

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

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

// ... после цикла for
vec.insert(vec.begin() + 500000, Foo(1));

то мы получим:

• 500000 ненужных нам вызовов копирующего конструктора
• 500000 ненужных нам вызовов деструктора

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

Итог

Вектор — это отличный контейнер, который подходит для размещения очень большого количества элементов. Он умеет резервировать память, что отличает его от остальных контейнеров, и это нужно использовать. POD данные — идеальные кандидаты на элементы вектора, так как к ним вектор применяет простые и быстрые методы копирования. Начиная со стандарта C++11, мы можем конструировать объекты непосредственно на том месте, где они будут храниться, если будем использовать emplace_back. Это экономит вызовы копирующих конструкторов.

Вектор плохо подходит для поиска и вставкам элементов в произвольное место (эффективно добавляются элементы только в конец). Помните, при грамотном использовании вектора, Вы всегда получите быстродействие сравнивнимое с кодом на чистом C, при этом у Вас будет удобный интерфейс и автоматическое управление памятью, в придачу. Такого Вам не сможет дать ни один язык — одновременно и быстродействие, и удобство программирования. Если же быстродействие Вам не нужно — то, возможно, Вам не нужен и 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;
    }
}

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

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

std::vector<int> myVector;
myVector.reserve(4);

for (int i = 0; i < 100; ++i) {
fillVector(myVector);
//use of myVector
//....
myVector.resize(0);
}

Решение

struct upTo4ElemVectorOfInts
{
int data[4];
size_t elems_num;
};

void fillVector(upTo4ElemVectorOfInts& vec)
{
//fill vec.data with values
vec.elems_num = filled_num; //save how many values was filled in this iteration
}

upTo4ElemVectorOfInts myVector;

for (int i = 0; i < 100; ++i)
{
fillVector(myVector);
//use of myVector:
//- myVector.data contains data (it's equivalent of std::vector<>::data())
//- myVector.elems_num will tell you how many numbers you should care about
//nothing needs to be resized/cleared
}

template <class T, size_t Size>
struct upToSizeElemVectorOfTs
{
T data[Size];
size_t elems_num;
};

Другие решения

#include <iostream>
#include <vector>

int main() {
std::vector<int> v{1,2,3};
std::cout << v.capacity() << ' ';
v.resize(0);
std::cout << v.capacity() << 'n';
}

// Output: 3 3

for (int i = 0; i < 100; ++i) {
myVector.reserve(4);
//use of myVector
//....
myVector.resize(0);
}

std::vector<int> myVector( 4 );

std::vector<int> myVector;
myVector.reserve(4);