В 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 специально её не определили, чтобы вы не могли использовать библиотеку неэффективным способом) или если по смыслу реализации контейнера эта функция ненужна.
Деки
Термин «дек» (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++ необходимость в самостоятельном программировании динамических массивов отпала. Векторы обладают всеми свойствами динамических массивов, но имеют более надежный и удобный интерфейс.
Ассоциативные контейнеры
Ассоциативные контейнеры автоматически сортируют свои элементы по некоторому критерию. Критерий представляется в виде функции, которая сравнивает либо значения, либо специальные ключи, определяемые для этих значении. По умолчанию элементы или ключи контейнеров сравниваются при помощи оператора <. Впрочем, программист может передать в контейнер собственную функцию сравнения и определить новый порядок сортировки.
Ассоциативные контейнеры обычно реализуются в виде бинарных деревьев. У каждого элемента (узла) есть один родитель и два потомка. Все предки слева от узла имеют меньшие значения, а все предки справа — большие значения. Ассоциативные контейнеры различаются по типу элементов и по тому, как они обходятся с дубликатами. Ниже перечислены стандартные ассоциативные контейнеры, определенные в STL.
Множества — коллекции, в которых элементы сортируются в соответствии с их значениями. Каждый элемент присутствует в коллекции только в одном экземпляре, дубликаты не разрешаются.
Мультимножества - то же, что и множества, но с возможностью хранения дубликатов. Это означает, что мультимножество может содержать несколько элементов с одинаковыми элементами.
Отображения —.коллекции, состоящие из пар «ключ/значение». У каждого элемента имеется ключ, определяющий порядок сортировки, и значение. Каждый ключ присутствует в коллекции только в одном экземпляре, дубликаты не разрешаются. Отображение также может использоваться как ассоциативный массив, то есть массив с произвольным типом индекса.
Мультиотображения - то же, что и отображений, но с возможностью дублирований ключей. Это означает, что мультиотображение может содержать несколько элементов с одинаковыми ключами. Мультиотображение также может использоваться в качестве словаря.
У всех шаблонов классов ассоциативных контейнеров имеется необязательный аргумент для передачи критерия сортировки. По умолчанию в качестве критерия сортировки используется оператор <. Критерий сортировки также применяется при проверке на равенство; два элемента равны, если каждый из них не больше другого.
Множество можно считать особой разновидностью отображения, в котором значение идентично ключу. Все разновидности ассоциативных контейнеров обычно реализуются на базе бинарных деревьев.
Контейнерные адаптеры
Помимо основных контейнерных классов стандартная библиотека C++ содержит специальные контейнерные адаптеры, предназначенные для особых целей. В их реализации применяются основные контейнерные классы. Ниже перечислены стандартные контейнерные адаптеры, определенные в библиотеке.
Стеки — контейнеры, элементы которых обрабатываются по принципу LIFO (последним прибыл, первым обслужен);
Очереди — контейнеры, элементы которых обрабатываются по принципу FIFO (первым прибыл, первым обслужен). Иначе говоря, очередь представляет собой обычный буфер.
Приоритетные очереди — контейнеры, элементам которых назначаются приоритеты. Приоритет определяется на основании критерия сортировки, переданного программистом (по умолчанию используется оператор <). В сущности, приоритетная очередь представляет собой буфер, следующий элемент которого всегда обладает максимальным приоритетом в очереди. Если максимальный приоритет назначен сразу нескольким элементам, порядок следования элементов не определен.
Исторически контейнерные адаптеры считаются частью STL. Однако с точки зрения программиста, это всего лишь специализированные контейнеры, которые используют общую архитектуру контейнеров, итераторов и алгоритмов, предоставленную STL.
Итераторы
Итератором называется объект, предназначенный для перебора элементов контейнера STL (всех или некоторого подмножества). Итератор представляет некоторую позицию в контейнере. Ниже перечислены основные операторы, работу с которыми поддерживает итератор.
* — получение элемента в текущей позиции итератора. Если элемент состоит из отдельных членов, для обращения к ним непосредственно через итератор используется оператор ->.
++ — перемещение итератора к следующему элементу. Многие итераторы также поддерживают перемещение в обратном направлении, для чего используется оператор --.
= = и!= — проверка совпадений позиций, представленных двумя итераторами.
= — присваивание итератора (позиции элемента, на которую он ссылается).
Этот набор операторов в точности соответствует интерфейсу обычных указателей С и C++ при переборе элементов массива. Различие заключается в том, что итераторы могут быть умными указателями, обеспечивающими перебор в более сложных контейнерных структурах данных. Внутреннее поведение итератора зависит от структуры данных, в которой осуществляется перебор. Таким образом, каждая разновидность контейнеров обладает собственным итератором. В каждом контейнерном классе тип итератора определяется в виде вложенного класса. В результате все итераторы обладают одинаковым интерфейсом, но имеют разные типы. В итоге мы приводим к концепции унифицированного программирования: операции выполняются с одинаковым интерфейсом, но с разными типами, что позволяет использовать шаблоны для определения унифицированных операций, работающих с произвольными типами, которые поддерживают заданный интерфейс.
Во всех контейнерных классах поддерживаются базовые функции, применяемые для перебора элементов при помощи итераторов. Ниже перечислены важнейшие из этих функций.
begin() — возвращает итератор, установленный в начало последовательности элементов контейнера. Началом считается позиция первого элемента (если он есть).
end() — возвращает итератор, установленный в конец последовательности элементов контейнера. Концом считается позиция за последним элементом.
Итак, функции begin() и end() определяют полуоткрытый интервал, который содержит первый элемент, но выходит за пределы последнего элемента (рис. 5.3). Полуоткрытый интервал обладает двумя достоинствами:
- появляется простое условие завершения перебора в контейнере: цикл продолжается до тех пор, пока не будет достигнута позиция end();
- предотвращается специальная обработка пустых интервалов, поскольку в пустом интервале begin() совпадает с end().
Рис. 9.3. Функции begin() и end()
Следующий пример демонстрирует применение итераторов. В нем выводятся значения всех элементов списка.
#include "stdafx.h"
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<char> coll; // Список с символьными элементами
// Присоединение элементов от ‘a’ до 'z'
for (char с = 'a'; с <='z'; ++с) coll.push_back(с);
/* Вывод содержимого списка
* - перебор всех элементов.*/
list<char>::const_iterator pos;
for (pos = coll.begin(); pos!= coll.end(); ++pos) cout<<*pos<<' ';
cout<<endl;
}
После того как список создан и заполнен символами от «а» до «z», все элементы выводятся в цикле for:
list<char>::const_iterator pos;
for (pos = coll.begin(); pos!= coll.end(); ++pos) cout<<*pos<<' ';
Итератор pos объявляется непосредственно перед началом цикла. В объявлении выбирается тип итератора для обращения к элементам контейнерного класса без возможности модификации: list<char>::const_iterator pos;
В каждом контейнере определены два типа итераторов:
· контейнер::iterator — используется для перебора элементов в режиме чтения/записи;
· контейнер::const_iterator — используется для перебора элементов в режиме чтения.
Скажем, в классе list эти определения выглядят примерно так:
namespace std {
template <class T>
class list {
public:
typedef... iterator;
typedef... const_iterator;
...
}
}
Конкретный тип итераторов iterator и const_iterator зависит от реализации.
В теле цикла for итератор pos инициализируется позицией первого элемента: pos = coll.begin();
Цикл продолжается до тех пор, пока pos не выйдет за пределы интервала контейнерных элементов: pos!= coll.end();
В этом условии итератор pos сравнивается c конечным итератором. Оператор ++pos в заголовке цикла перемещает итератор pos к следующему элементу.
В итоге итератор pos перебирает все элементы, начиная с первого, пока не дойдет до конца (рис. 54), Если контейнер не содержит ни одного элемента, тело цикла не выполняется, потому что значение coli.begin() будет равным значению coil.end().
Рис. 9.4. Итератор pos при переборе элементов списка
В теле цикла текущий элемент представляется выражением *pos. Модификация текущего элемента невозможна, потому что итератор был объявлен с типом const_iterator, а значит, с точки зрения итератора элементы являются константными. Но если объявить неконстантный итератор для перебора неконстантных элементов, значения можно будет изменить. Пример:
// Приведение всех символов в списке к верхнему регистру
list<char>::iterator pos;
for(pos = coll.begin(); pos!= coll.end(); ++pos) *pos = toupper(*pos);
Обратите внимание на использование префиксной версии оператора ++. Возможно, в этом случае она работает эффективнее постфиксной версии, которая создает временный объект для возвращения старой позиции итератора. Из-за этого в общем случае рекомендуется использовать ++pos вместо pos++, а следующее решение нежелательно:
for (pos = coll.begin(); pos!= coll.end(); pos++) {
// Работает.
// но медленнее
…
}
По этой причине можно рекомендовать ограничиваться префиксными формами операторов увеличения и уменьшения. Цикл, приведенный выше, может использоваться с любым типом контейнера — достаточно сменить тип итератора. Ниже приведены примеры использования ассоциативных контейнеров.
