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

Векторы

Вектор управляет элементами, хранящимися в динамическом массиве. Он обеспечивает произвольный доступ к элементам, то есть программа может напрямую обратиться к любому элементу по индексу. Операш1И присоединения элемента в конец массива и удаления элемента из конца массива выполняются очень быстро.

В следующем примере мы определяем вектор для значений типа int, вставляем в него шесть элементов и выводим элементы вектора.

stl/vectorl.cpp #include <iostreani> #1nclude <vector> using namespace std;

int mainO (

vector<int> co1l; Вектор с целыми элементами

Присоединение элементов со значениями от 1 до 6 for (int 1-1; i<*6: ++1) { coll.push backC1);

Вывод элементов, разделенных пробелами for (int i-=0: 1<со11 .sizeO; ++i) { cout « coll[1] « :

cout « endl;

Следующая директива включает заголовочный файл для работы с векторами;

#1nclude <vector>

Показанное ниже объявление создает вектор с элементами типа int: vector<int> coll:

Вектор не инициализируется, поэтому конструктор по умолчанию создает пустую коллекцию.

Функция push back() присоединяет элемент к контейнеру:

со]1.push back(1);

Строго говоря, присоединение элементов является очень быстрой операцией с учетом амортизации. Отдельные операции могут выполняться медленно, поскольку вектору приходится выделять новую память и копировать в нее существующие элементы. Но так как необходимость в перераспределении памяти возникает довольно редко, в целом операция выполняется очень быстро. Сложность работы алгоритмов рассматривается на с. 37.

Эта функция присутствует во всех последовательных контейнерах. Функция size() возвращает количество элементов в контейнере:

for (1nt i-0; 1<col1.size(): { }

Эта функция поддерживается всеми контейнерными классами. Оператор индексирования [] возвращает один элемент вектора:

cout « со11[1] « :

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

12 3 4 5 6

Деки

Термин «дек» (deque) происходит от сокращения фразы «double-ended queues (двусторонняя очередь). Дек представляет собой динамический массив, реализованный таким образом, что может расти в обоих направлениях. Таким образом, операции вставки элементов в конец и в начало коллекции выполняются очень быстро, а вставка в середину занимает больше времени, потому что требует перемещения элементов.

В следующем примере мы объявляем дек для вещественных чисел, вставляем в начало контейнера элементы от 1.1 до 6.6, а затем выводим значения элементов дека.

stl/dequel.cpp #include <1ostream> #include <deque> using namespace std:

int mainO

deque<float> coll: Дек с вещественными элементами

Вставка в начало элементов со значениями от 1.1 до 6.6 for (int i=l; i<=6: ++i) {

coll.push front(i*l.l); Вставка в начало дека

Вывод эленентов. разделенных пробелами for (int i=0: i<col 1.size(); ++i) { cout « CQll[i] « :

cout « endl:

Следующая директива включает заголовочный файл для работы с векторами: #include <deque>

Показанное ниже объявление создает пустую коллекцию вещественных чисел: deque<float> соП;

Функция push front() предназначена для вставки элементов;

coll.push front(1*l.1);

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

6.6 5.5 4.4 3.3 2.2 1.1

Элементы также могут вставляться в конец дека функцией push back(). Функция push front() не поддерживается векторами, поскольку в этом типе контейнера она будет выполняться слишком долго (при вставке элемента в начало вектора придется переместить все существующие элементы). Обычно контейнеры STL содержат только функции, обеспечивающие «хорошую» эффективность (то есть выполняемые с постоянной или логарифмической сложностью). Это сделано для того, чтобы предотвратить случайные вызовы неэффективных функций.

Списки

Класс list реализуется в виде двусвязного списка элементов. Это означает, что каждый элемент списка занимает отдельный блок памяти и содержит ссылки на предыдущий и следующий элементы. Списки не поддерживают произвольный доступ к элементам. Например, чтобы обратиться к десятому элементу, необходимо сначала перебрать первые девять элементов по цепочке ссылок. Тем не менее переход к следующему или предыдущему элементу выполняется с постоянным временем, поэтому обобщенная операщ-ш доступа к произвольному элементу имеет линейную сложность (среднее расстояние перехода пропорционально количеству элементов). Это гораздо хуже, чем амортизированное постоянное время доступа, обеспечиваемое векторами и деками.

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

В следующем примере мы создаем пустой список символов, заносим в него символы от «а» до «z» и выводим все элементы в цикле, который в каждой итерации выводит и удаляет первый элемент коллекции.

stl/llstl.cpp #1nclude <iostreani> #include <list> using namespace std;

int mainO {

I1st<char> coll; Список с символьными зленентами