Vector (std::vector<T>) — стандартный шаблон обобщённого программирования языка C++, реализующий динамический массив.
Шаблон vector расположен в заголовочном файле <vector>. Как и все стандартные компоненты, он расположен в пространстве имён std. Данный интерфейс эмулирует работу стандартного массива C (например, быстрый произвольный доступ к элементам), а также некоторые дополнительные возможности, вроде автоматического изменения размера вектора при вставке или удалении элементов.
Все элементы вектора должны принадлежать одному типу. Например, нельзя совместно хранить данные типов char и int в одном экземпляре вектора. Класс vector обладает стандартным набором методов для доступа к элементам, добавления и удаления элементов, а также получения количества хранимых элементов.
Инициализация Вектор может быть инициализирован любым типом, имеющим конструктор копии и определённый operator= и удовлетворяющим следующим условиямISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages — C++ § 23.1 Container requirements [lib.container.requirements] para. 4: Выражение Возвращаемый тип Условие 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.
Выражение Возвращаемый тип Проверка границы? 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 Изменяет .capacity() вектора 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) при условии, что .capacity() меньше количества элементов в векторе, в противном случае — O(n) 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 использовал только один бит памятиISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages — C++ § 23.2.5 Class vector<bool> [lib.vector.bool] para. 1. Это многие называют ошибкой, так как vector<bool> не соответствует требованиям контейнера стандартной библиотеки C++. Например, контейнер <T>::reference должен быть верным lvalue типа T. Это не выполняется в случае с vector<bool>::reference, которая является объектом-заместителем, конвертируемым в boolISO/IEC (2003). ISO/IEC 14882:2003(E): Programming Languages — C++ § 23.2.5 Class vector<bool> [lib.vector.bool] para. 2. Кроме того, vector<bool>::iterator не даёт bool& при разыменовании. Существует соглашение между комитетом по стандартизации C++ и группой разработчиков библиотеки, что vector<bool> должен быть исключён, а затем удалён из стандартной библиотеки, а функциональность будет восстановлена, но под другим именем.
Использование Программы на 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()); }