Урок №197. Контейнеры STL

  Юрий  | 

    | 

  Обновл. 10 Янв 2019  | 

 1563

 ǀ   1 

Безусловно, наиболее часто используемым функционалом STL являются контейнерные классы (или как их ещё называют – «контейнеры»).

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

   последовательные;

   ассоциативные;

   адаптеры.

Сейчас сделаем их краткий обзор.

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

Последовательные контейнеры (или ещё «Контейнеры последовательности») — это контейнерные классы, элементы которых находятся в последовательности. Их определяющей характеристикой является то, что вы можете вставить свой элемент в любое место контейнера. Наиболее распространенным примером последовательного контейнера является массив: при вставке четырёх элементов в массив, эти элементы будут находиться (в массиве) в точно таком же порядке, в котором вы их вставляли.

Начиная с C++11 STL содержит 6 контейнеров последовательности:

   std::vector;

   std::deque;

   std::array;

   std::list;

   std::forward_list;

   std::basic_string.

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

В следующей программе мы вставляем 5 целых чисел в вектор и с помощью перегруженного оператора индексации [] получаем к ним доступ для их последующего вывода:

Результат выполнения программы выше:

10 9 8 7 6

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

Результат выполнения программы выше:

7 8 9 10 0 1 2 3

List (или просто «список») — это двусвязный список, каждый элемент которого содержит 2 указателя: один указывает на следующий элемент списка, а ещё один – на предыдущий элемент списка. list предоставляет доступ только к началу и к концу списка — произвольный доступ запрещён. Если вы хотите найти значение где-то в середине, то вы должны начать с одного конца и перебирать каждый элемент списка до тех пор, пока не найдёте то, что ищите. Преимуществом двусвязного списка является то, что вставка элементов происходит очень быстро, если вы, конечно, знаете, куда хотите вставлять. Обычно для перебора элементов двусвязного списка используются итераторы.

Мы поговорим больше о двусвязных списках и итераторах в следующих уроках.

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

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


Ассоциативные контейнеры — это контейнерные классы, которые автоматически сортируют все свои элементы (в том числе и те, которые вставляете вы). По умолчанию ассоциативные контейнеры выполняют сортировку элементов, используя оператор сравнения <.

   set — это контейнер, в котором хранятся только уникальные элементы, повторения – запрещены. Элементы сортируются в соответствии с их значениями.

   multiset — это set, но в котором допускаются повторяющиеся элементы.

   map (или ещё «ассоциативный массив») — это set, в котором каждый элемент является парой «ключ-значение». Ключ используется для сортировки и индексации данных и должен быть уникальным. А значение — это фактические данные.

   multimap (или ещё «словарь») — это map, который допускает дублирование ключей. Все ключи отсортированы в порядке возрастания, и вы можете посмотреть значение по ключу.

Адаптеры

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

   stack (стек) — это контейнерный класс, элементы которого работают по принципу LIFOLast In, First Out» – «Последним Пришёл, Первым Ушёл»), т.е. элементы вставляются (вталкиваются) в конец контейнера и удаляются (выталкиваются) оттуда же (из конца контейнера). Обычно в стеках используется deque в качестве последовательного контейнера по умолчанию (что немного странно, поскольку vector был бы более подходящим вариантом), но вы также можете использовать vector или list.

   queue (очередь) — это контейнерный класс, элементы которого работают по принципу FIFOFirst In, First Out» – «Первым Пришёл, Первым Ушёл»), т.е. элементы вставляются (вталкиваются) в конец контейнера, но удаляются (выталкиваются) из начала контейнера. По умолчанию в очереди используется deque в качестве последовательного контейнера, но также может использоваться и list.

   priority_queue (очередь с приоритетом) — это тип очереди, в которой все элементы отсортированы (с помощью оператора сравнения <). При вставке элемента, он автоматически сортируется. Элемент с наивысшим приоритетом (самый большой элемент) находится в самом начале очереди с приоритетом, также как и удаление элементов — выполняется с самого начала очереди с приоритетом.

В следующем уроке мы рассмотрим итераторы STL.


Оценить статью:

Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (15 оценок, среднее: 5,00 из 5)
Загрузка...

Комментариев: 1

  1. Аватар Андрей:

    "Класс deque (или просто «дек») — это двусторонняя очередь, реализованная в виде динамического массива."

    не совсем так, реализовано по средством массива массивов, вроде как самый вероятный вариант реализации — вектор векторов.
    Первый динамический хранит указатели на вторые(одинаковой постоянной размерности).
    Данные хранятся именно во вторых..
    Соответственно для хранения не требует непрерывной области памяти. При расширение — добавляется новый блок(массив) для хранения данных и указатель на него(в начало или конец "массива указателей")

    "Обычно в стеках используется deque в качестве последовательного контейнера по умолчанию (что немного странно, поскольку vector был бы более подходящим вариантом)"

    скорей всего именно из за того что увеличение идет блоками, и не требует обязательно непрерывной области памяти для хранения- в итоге копирования всего внутреннего хранилища при увеличение — не происходит..

Добавить комментарий

Ваш E-mail не будет опубликован. Обязательные поля помечены *