vector (C++)



Стандартный шаблон обобщённого программирования языка 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 }

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

Стандартная библиотека 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-ю '' 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) для сбалансированного двоичного дерева поиска.


Имя:*
E-Mail:
Комментарий:
Информационный некоммерческий ресурс fccland.ru ©
При цитировании информации ссылка на сайт обязательна.
Копирование материалов сайта ЗАПРЕЩЕНО!