vector (C++)

Vector (std::vector<T>) — стандартный шаблон обобщённого программирования языка C++, реализующий динамический массив.

Шаблон vector расположен в заголовочном файле <vector>. Как и все стандартные компоненты, он расположен в пространстве имён std. Данный интерфейс эмулирует работу стандартного массива C (например, быстрый произвольный доступ к элементам), а также некоторые дополнительные возможности, вроде автоматического изменения размера вектора при вставке или удалении элементов.

Все элементы вектора должны принадлежать одному типу. Например, нельзя совместно хранить данные типов char и int в одном экземпляре вектора. Класс vector обладает стандартным набором методов для доступа к элементам, добавления и удаления элементов, а также получения количества хранимых элементов.

Инициализация

Вектор может быть инициализирован любым типом, имеющим конструктор копии и определённый operator= и удовлетворяющим следующим условиям^[1]:

Выражение	Возвращаемый тип	Условие
`t = u`	`T&`	`t` эквивалентен `u`
`T(t)`		`t` эквивалентен `T(t)`
`T(u)`		`u` эквивалентен `T(u)`
`&u`	`const T*`	показывает адрес `u`
`t.~T()`

Здесь T — тип, которым инициализирован vector, t — переменная типа T, u — переменная типа (возможно const) T.

Например:

vector<int> myVector; // Пустой вектор из элементов типа int
vector<float> myVector(10); // Вектор из 10-и элементов типа float
vector<char> myVector(5, ' '); // Вектор, состоящий из 5-и пробелов

class T {
 ...
};
int n = 10;
vector<T> myVector(n); // Вектор из 10-и элементов пользовательского типа T

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

Доступ к отдельному элементу вектора можно получить, используя операции, описанные в таблице ниже. По соглашению Си и C++, первый элемент имеет индекс 0, последний — size() - 1^[2].

Выражение	Возвращаемый тип	Проверка границы?
`v.at(i)`	`T&` или `const T&` для элемента i	Возможен выброс исключения `out_of_range`
`v[i]`	`T&` или `const T&` для элемента i	Неопределённое поведение при `i >= v.size()`
`v.front()`	`T&` или `const T&` для первого элемента	Неопределённое поведение при `v.empty() == true`
`v.back()`	`T&` или `const T&` для последнего элемента	Неопределённое поведение при `v.empty() == true`

Где v — это объект типа (возможно const) vector<T>, а i — индекс необходимого элемента вектора.

Некоторые методы

Класс vector — это контейнер. Согласно стандарту C++, любой контейнер должен содержать методы begin(), end(), size(), max_size(), empty(), и swap().

Ниже приведён краткий перечень доступных методов с описанием и указанием сложности

	Метод	Описание	Сложность
Конструкторы	`vector::vector`	Конструктор по умолчанию. Не принимает аргументов, создаёт новый экземпляр вектора	`O(1)` (выполняется за константное время)
	`vector::vector(const vector& c)`	Конструктор копии по умолчанию. Создаёт копию вектора `c`	`O(n)` (выполняется за линейное время, пропорциональное размеру вектора `c`)
	`vector::vector(size_type n, const T& val = T())`	Создаёт вектор с `n` объектами. Если `val` объявлена, то каждый из этих объектов будет инициализирован её значением; в противном случае объекты получат значение конструктора по умолчанию типа `T`.	`O(n)`
	`vector::vector(input_iterator start, input_iterator end)`	Создаёт вектор из элементов, лежащих между `start` и `end`	`O(n)`
Деструктор	`vector::~vector`	Уничтожает вектор и его элементы
Операторы	`vector::operator=`	Копирует значение одного вектора в другой.	`O(n)`
Операторы	`vector::operator==`	Сравнение двух векторов	`O(n)`
Доступ к элементам	`vector::at`	Доступ к элементу с проверкой выхода за границу	`O(1)`
	`vector::operator[]`	Доступ к определённому элементу	`O(1)`
	`vector::front`	Доступ к первому элементу	`O(1)`
	`vector::back`	Доступ к последнему элементу	`O(1)`
Итераторы	`vector::begin`	Возвращает итератор на первый элемент вектора	`O(1)`
	`vector::end`	Возвращает итератор на место после последнего элемента вектора	`O(1)`
	`vector::rbegin`	Возвращает `reverse_iterator` на конец текущего вектора.	`O(1)`
	`vector::rend`	Возвращает `reverse_iterator` на начало вектора.	`O(1)`
Работа с размером вектора	`vector::empty`	Возвращает `true`, если вектор пуст	`O(1)`
	`vector::size`	Возвращает количество элементов в векторе	`O(1)`
	`vector::max_size`	Возвращает максимально возможное количество элементов в векторе	`O(1)`
	`vector::reserve`	Устанавливает минимально возможное количество элементов в векторе	`O(n)`
	`vector::capacity`	Возвращает количество элементов, которое может содержать вектор до того, как ему потребуется выделить больше места.	`O(1)`
	`vector::shrink_to_fit`	Уменьшает количество используемой памяти за счёт освобождения неиспользованной (C++11)	`O(1)`
Модификаторы	`vector::clear`	Удаляет все элементы вектора	`O(n)`
	`vector::insert`	Вставка элементов в вектор	Вставка в конец, при условии, что память не будет перераспределяться — `O(1)`, в произвольное место — `O(n)`
	`vector::erase`	Удаляет указанные элементы вектора (один или несколько)	`O(n)`
	`vector::push_back`	Вставка элемента в конец вектора	`O(1)`
	`vector::pop_back`	Удалить последний элемент вектора	`O(1)`
	`vector::resize`	Изменяет размер вектора на заданную величину	`O(n)`
	`vector::swap`	Обменять содержимое двух векторов	`O(1)`
Другие методы	`vector::assign`	Ассоциирует с вектором поданные значения	`O(n)`, если установлен нужный размер вектора, `O(n*log(n))` при перераспределении памяти
Другие методы	`vector::get_allocator`	Возвращает аллокатор, используемый для выделения памяти	`O(1)`

Итераторы

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

Итераторы обычно используются парами, один из которых используется для указания текущей итерации, а второй служит для обозначения конца контейнера. Итераторы создаются при помощи таких стандартных методов как begin() и end(). Функция begin() возвращает указатель на первый элемент, а end() — на воображаемый несуществующий элемент, следующий за последним.

Вектор использует наиболее функционально богатый тип итераторов — RandomAccessIterator (итератор произвольного доступа), который позволяет обходить контейнер в любом порядке, а также изменять содержимое вектора в процессе обхода. Однако, при изменении вектора итератор может стать недействительным.

Пример подсчёта суммы элементов вектора при помощи итераторов:

#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

int main()
{
vector<int> the_vector;
vector<int>::iterator the_iterator;
    for (int i=0; i < 10; i++) {
        the_vector.push_back(i);
    }
    int total = 0;
    the_iterator = the_vector.begin();
    while (the_iterator != the_vector.end()) {
      total += *the_iterator++; 
    }
    cout << "summa= " << total << endl;
    return 0;
}

    vector<int> the_vector;
    vector<int>::iterator the_iterator;
 
    for (int i=0; i < 10; i++) {
        the_vector.push_back(i);
    }
    int total = 0;
    the_iterator = the_vector.begin();
    while (the_iterator != the_vector.end()) {
      total += *the_iterator; /* Обратите внимание, что доступ к элементу можно получить посредством разыменования итератора */
      ++the_iterator;
    }
    cout << "Итого=" << total << endl;

Результат:
Итого=45

Объём вектора и изменение размера

Типичная реализация вектора — это указатель на динамический массив. Размер вектора — это фактическое число элементов, а объём — количество используемой им памяти.

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

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

#include <vector>
int main() {
  std::vector<int> v(1); // Создаём вектор, состоящий из одного элемента типа int, значение которого равно 0
 
  int& first = *v.begin(); // Создаём ссылку на первый элемент
 
  v.insert(v.end(), v.capacity(), 0); // Добавляем новые элементы
 
  int i = first; // Неопределённое поведение. Ссылка может быть недействительной
}

Метод reserve() используется для предотвращения ненужного перераспределения памяти. После вызова reserve(n), объём вектора гарантированно будет не меньше n. Пример:

#include <vector>
int main() {
  std::vector<int> v(1); // Создаём вектор, состоящий из одного элемента типа int, значение которого равно 0
 
  v.reserve(10); // Резервируем место
 
  int& first = *v.begin(); // Создаём ссылку на первый элемент
 
  v.insert(v.end(), 5, 0); // Добавляем элементы в вектор
 
  int i = first; // OK, т.к не было перераспределения памяти
}

Вектор сохраняет определённый порядок его элементов, так, что при вставке нового элемента в начале или в середине вектора, последующие элементы перемещаются в обратном направлении с точки зрения их оператора присваивания и конструктора копии. Следовательно, ссылки и итераторы элементов после места вставки становятся недействительным. Пример:

#include <vector>
int main() {
  std::vector<int> v(2); // Создаём вектор, состоящий из двух элементов типа Int
 
  // Создаём ссылки на оба элемента
  int& first = v.front(); 
  int& last = v.back();
 
  v.insert(v.begin() + 1, 1, 1); // Добавляем новые элементы в середину вектора
 
  int i = first; // Неопределённое поведение, если вставка вызвала перераспределение памяти
  int j = last; // Неопределённое поведение, согласно стандарту C++, §23.2.4.3/1
}

Специализация vector<bool>

Стандартная библиотека C++ определяет специализацию шаблона вектора для типа bool. Согласно специализации, вектор должен упаковать элементы так, чтобы каждый элемент типа bооl использовал только один бит памяти^[3]. Это многие называют ошибкой^[4]^[5], так как vector<bool> не соответствует требованиям контейнера стандартной библиотеки C++. Например, контейнер <T>::reference должен быть верным lvalue типа T. Это не выполняется в случае с vector<bool>::reference, которая является объектом-заместителем, конвертируемым в bool^[6]. Кроме того, vector<bool>::iterator не даёт bool& при разыменовании. Существует соглашение между комитетом по стандартизации C++ и группой разработчиков библиотеки, что vector<bool> должен быть исключён, а затем удалён из стандартной библиотеки, а функциональность будет восстановлена, но под другим именем.^[7]

Использование

Программы на C++, которые используют вектор, должны содержать в себе заголовочный файл <vector>:

#include <vector>
// После этого, можно проинициализировать переменную
std::vector<T> myVector;

Здесь T — тип данных, которые будут храниться в контейнере, а myVector — переменная, которая будет использоваться. T может быть любым типом данных, включая тип данных, определённый пользователем.

Замена массиву

В C и C++, массив — это данные в смежных блоках памяти. Каждому блоку затем присваивается индекс, и узнать содержание каждого блока можно зная его индекс. Все элементы массива должны быть одного типа.

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

Поскольку элементы вектора хранятся непрерывно, адрес первого элемента вектора может быть передан функции в качестве массива (указатель на первый элемент). Следующий пример иллюстрирует, как вектор может использоваться с функциями стандартной библиотеки С memcpy и printf:

#include <cstring> // memcpy
#include <vector> 
#include <cstdio> // printf
int main() {
  using namespace std;
  const char arr[] = "1234567890";
  // Создадим вектор с 11-ю '\0'
  vector<char> vec(sizeof arr);  
  // Скопируем 11 элементов типа 'char' в вектор
  memcpy(vec.data(), arr, sizeof arr); 
  // Напечатает "1234567890"
  printf("%s", vec.data()); 
}

Обратите внимание, что использование memcpy и printf не приветствуется, в пользу более безопасных альтернатив из стандартной библиотеки C++

Пример использования

Следующий пример демонстрирует различные техники с участием вектора и алгоритмов стандартной библиотеки C++, в частности, перемешивание, сортировка, нахождение наибольшего элемента, а также удаление из вектора с использованием идиомы erase-remove.

#include <iostream>
#include <vector>
#include <algorithm> // sort, max_element, random_shuffle, remove_if, lower_bound 
#include <functional> // greater, bind2nd

// Используется для удобства. В реальных программах используйте с осторожностью
using namespace std;
 
int main() {
  int arr[4] = {1, 2, 3, 4};
  // Инициализирование вектора с использованием массива
  vector<int> numbers(arr, arr+4);
  // Добавляем числа в вектор
  numbers.push_back(5);
  numbers.push_back(6);
  numbers.push_back(7);
  numbers.push_back(8);
  // Теперь вектор выглядит так: {1, 2, 3, 4, 5, 6, 7, 8}
 
  // Произвольно перемешиваем элементы
  random_shuffle(numbers.begin(), numbers.end());
 
  // Получаем максимальный элемент, сложность O(n)
  vector<int>::const_iterator largest = max_element( numbers.begin(), numbers.end() );
 
  cout << "Наибольший элемент " << *largest << endl;
  cout << "Индекс этого элемента " << largest - numbers.begin() << endl;
 
  // Сортируем элементы, сложность O(n log n)
  sort(numbers.begin(), numbers.end());
 
  // Находим позицию цифры 5 в векторе, сложность O(log n)  
  vector<int>::const_iterator five = lower_bound(numbers.begin(), numbers.end(), 5);  
 
  cout << "Цифра 5 расположена под индексом " << five - numbers.begin() << endl;
 
  // Удаляем все элементы больше 4-х 
  numbers.erase(remove_if(numbers.begin(), numbers.end(), bind2nd(greater<int>(), 4)), 
                numbers.end() );
 
  // Печатаем оставшиеся
  for (vector<int>::const_iterator it = numbers.begin(); it != numbers.end(); ++it) {
    cout << *it << ' ';
  }
 
  return 0;
}

Вывод будет содержать:

Наибольший элемент 8

Индекс этого элемента 6 (зависит от реализации)

Цифра 5 расположена под индексом 4

1 2 3 4

Пример 2-мерного динамического вектора, а также пример доступа к нему и его модификации

typedef std::vector< std::vector<int> > pxMP;
 
void function() {
    int sizeX, sizeY; // указываем размер "на лету".
    pxMP pxMap(sizeX, std::vector<int>(sizeY)); // массив размера X/Y пикселей 0,1.
    pxMap[0][5] = 1;  /* доступ */
 
        // удаляем левый и правый столбец
        pxMap.pop_back();
        pxMap.erase(pxMap.begin());
 
        // удаляем верхнюю и нижнюю строки из всех столбцов, для начала создаём некоторые инструменты для этого:
        std::vector< std::vector<int> >::iterator iterlvl2; // итератор для второго измерения.
        std::vector< int >::iterator iterlvl1; // итератор для первого измерения
 
        // Уходим вглубь
        for (iterlvl2=pxMap.begin();iterlvl2 != pxMap.end();iterlvl2++) {
            iterlvl1 = (*iterlvl2).begin(); // Только для демонстрации
            (*iterlvl2).pop_back();
            (*iterlvl2).erase((*iterlvl2).begin()); // где мы?
 
            sizeY = (*iterlvl2).size(); // Устанавливаем sizeY пока мы на этом уровне. Потом мы не сможем этого сделать
        }
}

Пример одномерного динамического вектора, сортировка и удаление дубликатов:

#include <vector>
#include <string>
#include <algorithm> // Для использования алгоритмов std::sort, std::unique

int main() 
{ 
    std::vector< std::string > v_str;    //Пустой вектор v_str
    v_str.push_back("zz");   // {"zz"}
    v_str.push_back("aa");   // {"zz", "aa"}
    v_str.push_back("bb");   // {"zz", "aa", "bb"}
    v_str.push_back("aa");   // {"zz", "aa", "bb", "aa"}
    v_str.push_back("xx");   // {"zz", "aa", "bb", "aa", "xx"}
    v_str.push_back("dd");   // {"zz", "aa", "bb", "aa", "xx", "dd"}
    v_str.push_back("xx");   // {"zz", "aa", "bb", "aa", "xx", "dd", "xx"}
 
    //Сортировка всех элементов вектора
    std::sort(v_str.begin(), v_str.end()); 
   
    //Результат сортировки вектора: {"aa", "aa", "bb", "dd", "xx", "xx", "zz"}
 
    // Удаление дубликатов
    v_str.erase( std::unique(v_str.begin(), v_str.end() ), v_str.end() );

    //Результат удаления дубликатов: {"aa","bb","dd","xx","zz"}
 
    return 0;
}

Преимущества и недостатки

Как и все реализации динамического массива, вектор не использует дополнительных структур данных, данные расположены в памяти рядом, за счёт чего они хорошо кешируются.
Вектор может быстро выделять память, необходимую для хранения конкретных данных. Это особенно полезно для хранения данных в списках, длина которых может быть не известна до создания списка, а удаление (за исключением, быть может, в конце) необходимо редко.
Как и другие контейнеры STL, может содержать примитивные типы данных, сложные или определённые пользователем.
Вектор разрешает произвольный доступ; то есть на элемент вектора можно ссылаться так же, как на элемент массива (по индексу). Связанные списки и множества, напротив, не поддерживают произвольный доступ и арифметические операции над указателями.
Удаление элемента из вектора или даже очистка вектора совершенно не обязательно освободит память, связанную с этим элементом. Это потому, что максимальный размер вектора с момента его создания является хорошей оценкой размера для нового вектора.
Векторы являются неэффективными для вставки элементов в любые места, кроме конца. Такая операция имеет О(n) (см. O-нотация) сложность по сравнению с O(1) для связанных списков. Удаление элемента из произвольного места также имеет сложность O(n) (необходимо сдвинуть к началу все элементы, располагающиеся после удаляемого, что в худшем случае даст n-1 перемещений). Это компенсируется скоростью доступа. Доступ к произвольному элементу вектора имеет сложность O(1) по сравнению с О(n) для связанного списка и O(log n) для сбалансированного двоичного дерева поиска.

Примечания

↑ ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages — C++ § 23.1 Container requirements [lib.container.requirements] para. 4
↑ Josuttis, Nicolai^[англ.]. C++ Standard Library - A Tutorial and Reference (англ.). — Addison-Wesley, 1999.
↑ ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages — C++ § 23.2.5 Class vector<bool> [lib.vector.bool] para. 1
↑ vector<bool>: More Problems, Better Solutions (неопр.) (PDF) (August 1999). Дата обращения: май 2007. Архивировано 31 августа 2012 года.
↑ A Specification to deprecate vector<bool> (неопр.) (March 2007). Дата обращения: май 2007. Архивировано 31 августа 2012 года.
↑ ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages — C++ § 23.2.5 Class vector<bool> [lib.vector.bool] para. 2
↑ 96. Vector<bool> is not a container (неопр.). Дата обращения: январь 2009. Архивировано 31 августа 2012 года.

Ссылки

C++-определение std::vector

[C++03_23.1/4-1] ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages — C++ § 23.1 Container requirements [lib.container.requirements] para. 4

[josuttis-2] Josuttis, Nicolai^[англ.]. C++ Standard Library - A Tutorial and Reference (англ.). — Addison-Wesley, 1999.

[C++03_23.2.5/1-3] ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages — C++ § 23.2.5 Class vector<bool> [lib.vector.bool] para. 1

[4] vector<bool>: More Problems, Better Solutions (неопр.) (PDF) (August 1999). Дата обращения: май 2007. Архивировано 31 августа 2012 года.

[5] A Specification to deprecate vector<bool> (неопр.) (March 2007). Дата обращения: май 2007. Архивировано 31 августа 2012 года.

[C++03_23.2.5/2-6] ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages — C++ § 23.2.5 Class vector<bool> [lib.vector.bool] para. 2

[7] 96. Vector<bool> is not a container (неопр.). Дата обращения: январь 2009. Архивировано 31 августа 2012 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]