21.2 – Обзор контейнеров STL

Безусловно, наиболее часто используемый функционал библиотеки STL – это ее контейнерные классы. Если вам нужно освежить в памяти контейнерные классы, просмотрите урок «16.6 – Контейнерные классы».

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

Контейнеры последовательностей

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

Начиная с C++11, STL содержит 6 контейнеров последовательностей: std::vector, std::deque, std::array, std::list, std::forward_list и std::basic_string.

Если вы когда-либо изучали физику, вы, вероятно, думаете о векторе как о сущности, имеющей одновременно величину и направление. Класс с названием vector в STL представляет собой динамический массив, который может увеличиваться по мере необходимости, чтобы хранить свои элементы. Класс vector обеспечивает произвольный доступ к своим элементам через operator[], а вставка и удаление элементов с конца вектора, как правило, происходит быстро.

Следующая программа вставляет в вектор 6 чисел и использует перегруженный оператор [] для доступа к ним, чтобы их напечатать.

#include <vector>
#include <iostream>

int main()
{

    std::vector<int> vect;
    for (int count=0; count < 6; ++count)
        vect.push_back(10 - count); // вставить в конец массива

    for (int index=0; index < vect.size(); ++index)
        std::cout << vect[index] << ' ';

    std::cout << '\n';
}

Эта программа дает следующий результат:

10 9 8 7 6 5

Класс deque (произносится как «дек») – это класс двусторонней очереди, реализованный как динамический массив, который может расти с обоих концов.

#include <iostream>
#include <deque>

int main()
{
    std::deque<int> deq;
    for (int count=0; count < 3; ++count)
    {
        deq.push_back(count);       // вставить в конец массива
        deq.push_front(10 - count); // вставить в начало массива
    }

    for (int index=0; index < deq.size(); ++index)
        std::cout << deq[index] << ' ';

    std::cout << '\n';
}

Эта программа дает следующий результат:

8 9 10 0 1 2

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

Хотя класс STL string (и wstring) обычно не включается в категорию контейнеров последовательностей, но, по сути, они ими являются, поскольку их можно рассматривать как вектор с элементами данных типа char (или wchar).

Ассоциативные контейнеры

Ассоциативные контейнеры – это контейнеры, которые автоматически сортируют свои входные данные, когда эти входные данные вставляются в контейнер. По умолчанию ассоциативные контейнеры сравнивают элементы с помощью operator<.

• set (набор) – это контейнер, в котором хранятся уникальные элементы, дублирование которых запрещено. Элементы отсортированы по их значениям.
• multiset – это set, в котором разрешены повторяющиеся элементы.
• map (также называемый ассоциативным массивом) – это набор, в котором каждый элемент представляет собой пару, называемую парой ключ/значение. Ключ используется для сортировки и индексации данных и должен быть уникальным. Значение – это фактические данные.
• multimap (также называемый словарем) – это map, который позволяет дублировать ключи. Реальные словари – это multimap'ы: ключ – это слово, а значение – это значение слова. Все ключи отсортированы в порядке возрастания, и вы можете искать значение по ключу. Некоторые слова могут иметь несколько значений, поэтому словарь – это multimap, а не map.

Адаптеры контейнеров

Адаптеры контейнеров – это специальные предопределенные контейнеры, адаптированные для конкретных целей. Интересная особенность адаптеров контейнеров заключается в том, что вы можете выбрать, какой контейнер последовательности вы хотите, чтобы они использовали.

• stack (стек) – это контейнер, в котором элементы работают по принципу LIFO («last in, first out», «последним вошел, первым вышел»), где элементы вставляются (push) и удаляются (pop) из конца контейнера. Стеки в качестве контейнера последовательности по умолчанию используют deque (что кажется странным, поскольку вектор кажется более естественным), но также могут использовать vector или list.
• queue (очередь) – это контейнер, в котором элементы работают по принципу FIFO («first in, first out», «первым вошел, первым вышел»), где элементы вставляются (push) в конец контейнера и удаляются (pop) спереди. Очереди по умолчанию используют deque (двухстороннюю очередь), но также могут использовать list.
• priority_queue (очередь с приоритетом) – это тип очереди, в которой элементы хранятся отсортированными (с помощью operator<). Когда элемент вставляется, он сортируется в этой очереди. Удаление элемента спереди возвращает элемент с наивысшим приоритетом в очереди с приоритетом.

Теги