Контейнер - это определенная структура данных, которая содержит данные, как правило, в неограниченном количестве. Каждый тип контейнера имеет ограничения в отношении эффективного доступа, добавления или удаления данных.
Ниже приведены несколько примеров контейнеров, использующих классы STL.
Контейнеры последовательности
Вот контейнеры последовательности, означающие, что данные упорядочены надежно (т. Е. У них есть фронт и тыл. Я НЕ имею в виду, что они автоматически сортируются!).
- A vector немного похож на массив гибкого размера. Векторы имеют произвольный доступ, что означает, что вы можете получить доступ к любому элементу с целочисленным индексом за постоянное время (как к массиву). Вы можете добавить или удалить из конца массива в (почти) постоянное время, а также. Однако в любом другом месте, и вы, вероятно, ожидаете, что вам придется переписывать потенциально все элементы.
- A deque , или двусторонняя очередь, похожа на вектор, но вы можете добавить ее вперед или назад. Вы по-прежнему можете обращаться к элементам в постоянное время, но не гарантируется, что элементы deque будут непрерывными в памяти, как векторы или массивы.
- A list - это связанный список, означающий данные, которые связаны указателями. У вас есть постоянный доступ к началу и концу, но чтобы попасть куда-то посередине, вам нужно перебрать список. Однако вы можете добавлять элементы в любое место списка в постоянное время, если у вас уже есть указатель на один из соседних узлов.
Ассоциативные контейнеры
Это ассоциативные контейнеры, означающие, что элементы больше не упорядочены, а вместо этого имеют ассоциации друг с другом, используемые для определения уникальности или отображений:
- A set - контейнер с уникальными элементами. Вы можете добавить только один из каждого элемента в набор; любые другие дополнения игнорируются.
- A multiset подобен набору, но вы можете добавить в него более одного элемента. MultiSet отслеживает, сколько элементов каждого типа находится в структуре.
- A map , также известный как ассоциативный массив, - это структура, в которую вы вставляете пары ключ-значение; тогда вы можете найти любое значение, указав ключ. Так что это немного похоже на массив, к которому вы можете обращаться с помощью строкового индекса (ключа) или любого другого вида индекса. (Если вы вставите другую пару ключ-значение, и ключ уже существует, вы просто перезапишите значение для исходного ключа.)
- A multimap - карта, которая позволяет вставлять несколько значений для одного и того же ключа. Когда вы выполняете поиск по ключу, вы возвращаете контейнер со всеми значениями в нем.
Контейнерные адаптеры
Контейнерные адаптеры, с другой стороны, представляют собой интерфейсы, созданные путем ограничения функциональных возможностей в ранее существующем контейнере и обеспечения другого набора функциональных возможностей. Когда вы объявляете адаптеры контейнеров, у вас есть возможность указать, какие контейнеры последовательности образуют базовый контейнер. Это:
- A stack - это контейнер, обеспечивающий доступ Last-In, First-Out (LIFO). По сути, вы удаляете элементы в обратном порядке. Трудно добраться до каких-либо элементов в середине. Обычно это происходит поверх deque .
- A queue - это контейнер, обеспечивающий доступ First-In, First-Out (FIFO). Вы удаляете элементы в том же порядке, в котором вы их вставляете. Трудно добраться до каких-либо элементов в середине. Обычно это происходит поверх deque .
- A priority_queue - это контейнер, обеспечивающий упорядоченный доступ к элементам. Вы можете вставлять элементы в любом порядке, а затем извлекать «самые низкие» из этих значений в любое время. Приоритетные очереди в C ++ STL внутренне используют структуру кучи, которая, в свою очередь, в основном поддерживается массивом; таким образом, обычно это идет поверх вектора .
См. эту справочную страницу для получения дополнительной информации, включая сложность времени для каждой из операций и ссылки на подробные страницы для каждого из типов контейнеров.