Основные принципы работы с контейнерами

Использование стандартных классов контейнеров

Стандартные классы контейнеры широко используются для создания сложных динамических структур данных. Наиболее распространенной является библиотека STL (Standard Template Library) - библиотека шаблонов, входящая в состав стандарта C++ ISO Standard - ISO/IEC 14882. Библиотека STL в настоящее время реализована во всех версиях C++ для всевозможных платформ, в противном случае реализация C++ не будет удовлетворять ISO/IEC 14882. В то же время в последние годы интенсивно развивается библиотека Qt, в которой предпринимается попытка по унификации средств во всех возможных направлениях, в том числе в направлении стандартных контейнеров.

Контейнер	Описание
Последовательности (Массивы/Связанные списки) – упорядоченные коллекции
vector	Динамический массив, обеспечивающий произвольный доступ подобно массиву языка С с возможностью изменения размера в случае вставки или удаления объекта. Физически выделяется линейная область памяти для всех элементов и обеспечивается перевыделение памяти в случае, если выделенной области недостаточно. В стандартной реализации каждое последующее выделение памяти удваивает текущий объем. Вставка и удаления объекта в конец вектора занимает фиксированное время. Вставка и удаления любого не последнего элемента занимает линейное время. Для массива элементов типа bool существует специальный тип bitset. #include <vector>
list	Двусвязный список, элементы которого в памяти размещаются произвольным образом. В противоположность типу vector, обеспечивается медленный доступ к конкретному элементу (линейное время), зато за постоянное время обеспечивается вставка и удаление любого элемента. #include <list>
deque	Дек (от англ. deq - double ended queue, т.е очередь с двумя концами). Реализован как вектор, в котором вставка или удаление элементов в конец или начало производится за постоянное время, однако корректность итераторов при таких операциях не гарантируется. #include <deque>
Ассоциативные контейнеры – неупорядоченные коллекции
set	Математическое множество, реализующее операции объединение, пересечение, разность, симметричную разность, а также проверку на включение. Тип данных, из которого формируется множество должен реализовывать оператор operator<() либо должны быть указана конкретная функция сравнения. Тип реализован с использованием балансированного дерева. Вставка или удаление элемента в множестве не нарушает итератор текущего положения во множестве. #include <set>
multiset	Тип аналогичен типу set за исключением того, что возможны дубликаты значений. #include <set>
map	Ассоциативный массив, обеспечивающий отображение одного типа данных – ключ (key) к другому - значению (value). Тип key должен реализовывать операцию сравнения operator<() либо должна быть указана конкретная функция сравнения. Тип реализован с использованием балансированного дерева. #include <map>
multimap	Тип аналогичен типу multiset за исключением того, что возможны дубликаты ключей. #include <map>
Адаптеры контейнеров
queue priority_queue stack	Контейнеры-интерфейсы к типам-последовательностям, обеспечивающие доступ с использованием соответствующих функций по принципу FIFO, упорядоченная очередь и LIFO, соответственно.

Подключение библиотеки стандартных классов производится включением соответствующего заголовочного файла. Следует отметить, что все классы STL помещены в пространство имен std, следовательно в программе сразу после включения необходимых заголовков целесообразно вписать строку:

либо использовать типы вместе со спецификатором std, например std::vector<int>.

Весьма полезным типом библиотеки STL является тип строка – std::string, декларация которого находится в файле <string>, а также классы-потоки ввода/вывода, задекларированные в заголовке <iostream> и имеющие имена cout, cin, cerr для потока вывода, ввода и ошибок, соответственно.

Внимание! Количество элементов контейнеров требует переменную типа size_t, а не int. То же относится к индексу типа vector. Причина заключается в том, что size_t зависим от разрядности ОС и в 64-х битной ОС будет иметь размер 64 бита, в то время как в 32-х битной ОС его размер будет соответствовать типу int, т.е. 32 бита.