Стандартный шаблон обобщённого программирования языка C++ std::vector<T> — реализация динамического массива.
Шаблон vector расположен в заголовочном файле <vector>. Как и все стандартные компоненты, он расположен в пространстве имён std. Данный интерфейс эмулирует работу стандартного массива C (например, быстрый произвольный доступ к элементам), а также некоторые дополнительные возможности, вроде автоматического изменения размера вектора при вставке или удалении элементов.
Все элементы вектора должны принадлежать одному типу. Например, нельзя совместно хранить данные типов char и int в одном экземпляре вектора. Класс vector обладает стандартным набором методов для доступа к элементам, добавления и удаления элементов, а также получения количества хранимых элементов.
Вектор может быть инициализирован любым типом, имеющим конструктор копии и определённый operator= и удовлетворяющим следующим условиям:
Здесь 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 и C++, первый элемент имеет индекс 0, последний — size() - 1.
Где v — это объект типа (возможно const) vector<T>, а i — индекс необходимого элемента вектора.
Класс vector — это контейнер. Согласно стандарту C++, любой контейнер должен содержать методы begin(), end(), size(), max_size(), empty(), и swap().
Ниже приведён краткий перечень доступных методов с описанием и указанием сложности
В дополнение к функциям прямого доступа к элементам, описанным выше, элементы вектора можно получить посредством итераторов.
Итераторы обычно используются парами, один из которых используется для указания текущей итерации, а второй служит для обозначения конца контейнера. Итераторы создаются при помощи таких стандартных методов как 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 }Стандартная библиотека C++ определяет специализацию шаблона вектора для типа bool. Согласно специализации, вектор должен упаковать элементы так, чтобы каждый элемент типа bооl использовал только один бит памяти. Это многие называют ошибкой, так как vector<bool> не соответствует требованиям контейнера стандартной библиотеки C++. Например, контейнер <T>::reference должен быть верным lvalue типа T. Это не выполняется в случае с vector<bool>::reference, которая является объектом-заместителем, конвертируемым в bool. Кроме того, 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-ю '