<joke>C++ технический и сложный для понимания :-D</joke>

Контейнеры — это типы данных из STL, которые могут содержать данные.

Пример: vector как динамический массив

Адаптеры — это типы данных из STL, которые адаптируют контейнер для обеспечения определенного интерфейса.

Пример: stack предоставление интерфейса стека поверх выбранного контейнера

(примечание: оба на самом деле являются шаблонами, а не типами данных, но так определение выглядит лучше)

Контейнер — это определенная структура данных, которая содержит данные, обычно в неограниченном количестве. Каждый тип контейнера имеет ограничения на эффективный доступ, добавление или удаление данных.

Ниже приведены несколько примеров контейнеров, использующих классы STL.

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

Вот контейнеры последовательности, что означает, что данные надежно упорядочены (то есть у них есть передняя и задняя часть. Я НЕ имею в виду, что они автоматически сортируются!).

• вектор немного похож на массив с гибкими размерами. Векторы имеют произвольный доступ, то есть вы можете получить доступ к любому элементу с целочисленным индексом за постоянное время (точно так же, как массив). Вы также можете добавлять или удалять из задней части вектора амортизированное постоянное время. Однако где-нибудь еще, и вы, вероятно, рассматриваете возможность повторного копирования всех элементов.
• Очередь, или двусторонняя очередь, похожа на вектор, но вы можете добавить ее к началу или концу за амортизированное постоянное время. Вы по-прежнему можете обращаться к элементам в постоянное время, но не гарантируется, что элементы двухсторонней очереди будут непрерывными в памяти, как векторы или массивы.
• список – это связанный список, то есть данные, связанные друг с другом указателями. У вас есть постоянный доступ к началу и концу, но для того, чтобы добраться до середины, вам нужно перебрать список. Однако вы можете добавлять элементы в любом месте списка за постоянное время, если у вас уже есть указатель на один из ближайших узлов.

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

Это ассоциативные контейнеры, означающие, что элементы больше не упорядочены, а вместо этого имеют ассоциации друг с другом, используемые для определения уникальности или сопоставления:

• Набор – это контейнер с уникальными элементами. Вы можете добавить только один из каждого элемента в набор; любые другие дополнения игнорируются.
• Мультимножество похоже на множество, но в него можно поместить более одного элемента. Мультимножество отслеживает, сколько элементов каждого типа содержится в структуре.
• Карта, также известная как ассоциативный массив, представляет собой структуру, в которую вы вставляете пары "ключ-значение". затем вы можете найти любое значение, указав ключ. Так что это немного похоже на массив, к которому вы можете получить доступ с помощью строкового индекса (ключа) или любого другого типа индекса. (Если вы вставляете другую пару ключ-значение, а ключ уже существует, вы просто перезаписываете значение исходного ключа.)
• Мультикарта – это карта, позволяющая вставлять несколько значений для одного и того же ключа. Когда вы выполняете поиск ключа, вы возвращаете контейнер со всеми значениями в нем.

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

Контейнерные адаптеры, с другой стороны, представляют собой интерфейсы, созданные путем ограничения функциональности уже существующего контейнера и предоставления другого набора функций. Когда вы объявляете адаптеры контейнеров, у вас есть возможность указать, какие контейнеры последовательности образуют базовый контейнер. Эти:

• стек — это контейнер, обеспечивающий доступ по принципу "последним пришел — первым обслужен" (LIFO). По сути, вы удаляете элементы в порядке, обратном их вставке. Трудно добраться до каких-либо элементов в середине. Обычно это идет поверх deque.
• очередь – это контейнер, обеспечивающий доступ по принципу "первым пришел – первым обслужен" (FIFO). Вы удаляете элементы в том же порядке, в котором вы их вставляете. Трудно добраться до каких-либо элементов в середине. Обычно это идет поверх deque.
• priority_queue – это контейнер, обеспечивающий доступ к элементам в порядке сортировки. Вы можете вставлять элементы в любом порядке, а затем в любое время извлекать «наименьшее» из этих значений. Очереди с приоритетами в C++ STL используют внутреннюю структуру кучи, которая, в свою очередь, в основном поддерживается массивом; таким образом, обычно это идет поверх vector.

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

Техническое определение контейнера из документации SGI STL довольно хорошее:

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

Итак, контейнер — это структура данных, которая содержит («содержит») набор объектов некоторого типа. Основная идея заключается в том, что существуют разные типы контейнеров, каждый из которых хранит объекты по-разному и обеспечивает разные характеристики производительности, но все они имеют стандартный интерфейс, так что вы можете легко заменить один на другой без особых изменений. кода, который использует контейнер. Идея состоит в том, что контейнеры максимально взаимозаменяемы.

Адаптеры контейнеров — это классы, которые предоставляют подмножество функций контейнера, но могут предоставлять дополнительные функции, упрощающие использование контейнеров в определенных сценариях. Например, вы можете легко использовать std::vector или std::deque для структуры данных стека и вызывать push_back, back и pop_back в качестве интерфейса стека; std::stack предоставляет интерфейс, который может использовать std::vector или std::deque или другой контейнер последовательности, но предоставляет более стандартные функции-члены push, top и pop для доступа к членам.