Последовательные контейнеры

В STL поддерживаются следующие разновидности последовательных контейнеров:

· векторы;

· деки;

· списки.

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

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

#include "stdafx.h"

#include <iostream>

#include <vector> //1

using namespace std;

int main(){

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

// Вставка элементов со значениями от 1 до 6 в конец вектора

for (int i = 1; i<= 6; ++i) coll.push_back(i); //3

// Вывод элементов, разделенных пробелами

for (int i = 0; i<coll.size(); ++i) cout <<coll[i] <<' '; //4

}

Для того чтобы мы могли воспользоваться стандартным контейнером vector из библиотеки STL, мы должны включить в нашу программу строку: #include <vector>. Далее в строке 2 мы определяем контейнер coll типа vector с элементами типа int. Объекты типа vector имеют компонентные функции (см. приложение 1) и одной из них push_back() мы воспользовались, чтобы вставить в вектор значения переменой i. Как видно из названия функции, всавка нового элемента всегда происходит в конец вектора.

В строке 4 мы выводим на экран элементы контейнера coll, для этого мы вызываем компонентные функции size() и operator[] объекта типа vector с помощью которых узнаём количество элементов в контейнере и получае доступ к ним соответственно.

На экране будет отображено: 1 2 3 4 5 6.

Когда мы говорили, что разные контейнеры имеют одинаковый интерфейс это значит, что и в других контейнерах (дек и список) почти с 90% вероятностью имеют такие же функции, в частности, push_back(), size(), operator[] для вставки, определения размера контейнера и доступа к элементу как и в контейнере vector. Подобная компонентная функция может отсутствовать в котейнере, если эффективно реализовать данную функцию для данного типа контейнера не представляется возможным (поэтому разработчики библиотеки STL специально её не определили, чтобы вы не могли использовать библиотеку неэффективным способом) или если по смыслу реализации контейнера эта функция ненужна.

Если рассматривать внутренюю реализацию вектора, то следует отметить, что все элементы вектора всегда размещаются в динамической памяти. Вектор позволяет добавлять и удалять элементы из него. При добавлении элемента, если количество элементов в векторе привысит значение capacity, то вектор будет перемещён, т.е. будет выделен в куче новая область памяти (обычно в два раза больше чем текущее количество элементов в векторе). Туда будут скопированы элементы вектора, а старая память из кучи будет возвращена системе.

Таким образом, нет смысла запоминать адреса или ссылки объектов, которые хранятся в векторе, так как вектор может быть перемещён и эти адреса и ссылки станут недействительными.

Деки

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

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

#include "stdafx.h"

#include <iostream>

#include <deque>

using namespace std;

int main()

{

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

// Вставка в начало элементов со значениями от 1.1 до 6.6

for (int i = 1; i <= 6; ++i) coll.push_front(i*1.1);//Вставка в начало дека

// Вывод элементов, разделенных пробелами

for (int i = 0; i<coll.size(); ++i) cout << coll[i] <<' ';

}

Следующая директива включает заголовочный файл для работы с деками: #liclude <deque>. Объявление deque<float> coll создает пустую коллекцию coll вещественных чисел. Функция push_front( ) предназначена для вставки элементов.

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

6.6 5.5 4.4 3.3 2.2 1.1

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

Внутренее устройство дека отличается от вектора. Если вектор хранит все свои элементы последовательно в одном фрагменте динамической памяти, то дек нет. Дек размещает свои элементы в одинаковых по размеру фрагментах динамической памяти («чангах»). Из-за такого способа реализации деку не нужно перемещать уже вставленные элементы при вставке/удалении новых элементов в начало или конец дека (т.е. адреса уже вставленных элементов дека остаются неизменными). При вставке/удалении элементов из середины дека, адреса оставщихся элементов могут изменится.

Списки

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

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

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

#include "stdafx.h"

#include <iostream>

#include <list>

using namespace std;

int main(){

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

// Присоединение элементов от ‘a’' до 'z'

for (char c = 'a'; c<= 'z'; ++c) coll.push_back(c);

while(!coll.empty()) { // Проверяем пуст ли список

cout<<coll.front()<<' '; // вывести первый элемент

coll.pop_front(); // удалить первый элемент

}

}

Как обычно, заголовочный файл <list> используется для определения контейнера типа list, содержащего символьные элементы: list <char> coll. Функция ernpty( ) возвращает логический признак отсутствия элементов в контейнере. Цикл выполняется до тех пор, пока функция возвращает false, то есть пока контейнер содержит элементы:

В теле цикла функция front( ) возвращает первый элемент, а функция pop_front( ) удаляет этот элемент из контейнера. Учтите, что функция pop_front( ) не возвращает удаляемый элементу, поэтому эти две команды не удается заменить одной командой.

Результат выполнения программы зависит от кодировки. В кодировке ASCII он выглядит так : a b с d е f g h i j k l m n о р г s t u v w x у z.

Конечно, процедура «вывода» содержимого цикла, которая выводит и удаляет первый элемент, выглядит несколько странно - обычно в цикле перебираются все элементы, Тем не менее списки не поддерживают произвольный доступ к элементам, поэтому оператор [] будет работать недостаточно эффективно. Существует другой способ перебора и вывода элементов, основанный на применении итераторов.

Строки

Строки также могут использоваться в качестве контейнеров STL. Под строками подразумеваются объекты строковых классов C++ (basic_string<>, string и wstring). В целом строки аналогичны векторам, но их элементы всегда относятся к символьному типу.

Обычные массивы

Другая разновидность контейнеров является не классом, а одним из типов базового языка С и C++: речь идет об обычных массивах со статическим или динамическим размером. Обычные массивы не относятся к контейнерам STL, поскольку они не поддерживают функции типа size( ) или empty( ), однако архитектура STL позволяет вызывать для них алгоритмы. Это особенно удобно при обработке статических массивов в списках инициализаций:

Принципы работы с массивами хорошо известны, нова лишь возможность использования массивов с алгоритмами из библиотеки STL. В C++ необходимость в самостоятельном программировании динамических массивов отпала. Векторы обладают всеми свойствами динамических массивов, но имеют более надежный и удобный интерфейс.