Vector (C++)

Стандартная библиотека языка программирования C++

fstream iomanip ios iostream sstream

Стандартная библиотека шаблонов

algorithm bitset deque functional iterator vector list map set stack queue

C++11

array forward_list unordered_map unordered_set

Стандартная библиотека языка программирования Си

cassert cctype cerrno climits clocale cmath csetjmp csignal cstdarg cstddef cstdint cstdio cstdlib cstring ctime

vector — это шаблон из стандартной библиотеки C++, реализующий динамический массив произвольного доступа. Это одна из структур данных, именуемых контейнерами (например, list, deque и т. д.)

Устройство

Шаблон 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 {
 ...
};
n = 10;
vector<T> myVector(n); // Вектор из 10-и элементов пользовательского типа T

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

Доступ к отдельному элементу вектора можно получить, используя операции, описанные в таблице ниже. По соглашению C и 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)	Cоздает вектор из элементов, лежащих между 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 (итератор произвольного доступа), который позволяет обходить контейнер в любом порядке, а также изменять содержимое вектора в процессе обхода. Однако, при изменении вектора итератор может стать недействительным.

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

    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;

или можно подключить заголовочный файл vector.h, где пространство имён std уже подключено

#include <vector.h>
// После этого, можно проинициализировать переменную
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[0], arr, sizeof arr); 
  // Напечатает "1234567890"
  printf("%s", &vec[0]); 
}

Обратите внимание, что использование 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> // для использования алгоритмов: sort / unique / erase
 
void main() {
 
    vector<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")
 
    // сортируем все элементы вектора
    sort(v_str.begin(), v_str.end());    
    // Результат сортировки вектора: {"aa", "aa", "bb", "dd", "xx", "xx", "zz"}
 
    // Удаляем дубликаты
    v_str.erase( unique(v_str.begin(), v_str.end() ), v_str.end() );   
    // Результат сортировки и удаления дубликатов: {"aa","bb","dd","xx","zz"}
 
    return void;
}

Доводы за и против

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

См. также

• C++
• Стандартная библиотека C++
• Стандартная библиотека шаблонов

Источники

1. ↑ ISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages — C++ § 23.1 Container requirements [lib.container.requirements] para. 4
2. ↑ Josuttis Nicolai C++ Standard Library - A Tutorial and Reference. — Addison-Wesley, 1999.
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). Архивировано из первоисточника 31 августа 2012. Проверено 1 мая 2007.
5. ↑ A Specification to deprecate vector<bool> (March 2007). Архивировано из первоисточника 31 августа 2012. Проверено 1 мая 2007.
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. Архивировано из первоисточника 31 августа 2012. Проверено 1 января 2009.

Ссылки

• С++ определение std::vector