Что такое контейнеры / адаптеры?C ++ - PullRequest
37 голосов
/ 06 октября 2010

Что такое контейнеры / адаптеры ?

Кто-то, пожалуйста, объясните на языке непрофессионала .

Я пытался найти в Интернете, ноопределения и объяснения слишком технические и трудные для понимания.

У меня есть базовые знания о C ++ и его подтемах, таких как (class / templates / STL).

EDIT 1:

Может ли кто-нибудь дать мне практический пример применения контейнеров / адаптеров?

Просто для лучшего понимания :-)

Спасибо.

Ответы [ 3 ]

67 голосов
/ 06 октября 2010

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

Ниже приведены несколько примеров контейнеров, использующих классы 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 внутренне используют структуру кучи, которая, в свою очередь, в основном поддерживается массивом; таким образом, обычно это идет поверх вектора .

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

57 голосов
/ 06 октября 2010

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

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

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

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

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

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

6 голосов
/ 06 октября 2010

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

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

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...