В информатике , А контейнер является классом , А структура данных , [1] [2] или абстрактный тип данных (ADT), экземпляры которого представляют собой коллекции других объектов. Другими словами, они хранят объекты организованным образом с соблюдением определенных правил доступа. Размер контейнера зависит от количества содержащихся в нем объектов (элементов). Базовые (унаследованные) реализации различных типов контейнеров могут различаться по размеру и сложности и обеспечивать гибкость в выборе правильной реализации для любого заданного сценария.
Назначение и свойства
Контейнеры можно охарактеризовать следующими тремя свойствами:
- доступ , то есть способ доступа к объектам контейнера. В случае массивов доступ осуществляется с помощью индекса массива. В случае стеков доступ осуществляется в соответствии с порядком LIFO (последний пришел - первым ушел), а в случае очередей - в соответствии с порядком FIFO (первым пришел - первым ушел);
- хранение , то есть способ хранения предметов контейнера;
- traversal , то есть способ обхода объектов контейнера.
Ожидается, что классы-контейнеры будут реализовывать методы для выполнения следующих действий:
- создать пустой контейнер (конструктор);
- вставлять предметы в контейнер;
- удалять объекты из контейнера;
- удалить все объекты в контейнере (очистить);
- получить доступ к объектам в контейнере;
- доступ к количеству объектов в контейнере (count).
Иногда контейнеры реализуются вместе с итераторами .
Типы
Контейнеры можно разделить на однозначные или ассоциативные контейнеры .
Однозначные контейнеры хранят каждый объект независимо. Доступ к объектам можно получить напрямую или с помощью итератора .
Ассоциативный контейнер использует ассоциативный массив , карту или словарь, состоящий из пар ключ-значение, так что каждый ключ появляется в контейнере не более одного раза. Ключ используется для поиска значения, объекта, если он хранится в контейнере. Ассоциативные контейнеры используются в языках программирования как шаблоны классов.
К абстрактным типам данных контейнера относятся:
Общие структуры данных, используемые для реализации этих абстрактных типов, включают:
- Массивы и их производные
- Связанные списки
- Деревья двоичного поиска (BST), особенно самобалансирующиеся BST
- Хеш-таблицы
Графические контейнеры
В наборах инструментов виджетов также используются контейнеры, которые представляют собой специальные виджеты для группировки других виджетов, таких как окна и панели . Помимо своих графических свойств, они имеют тот же тип поведения, что и классы-контейнеры, поскольку они хранят список своих дочерних виджетов и позволяют добавлять, удалять или извлекать виджеты среди своих дочерних элементов .
Смотрите также
Рекомендации
- ^ Пол Э. Блэк (редактор), запись о структуре данных в Словаре алгоритмов и структур данных . США Национального института стандартов и технологии +0,15 декабрь 2004 Достигана 4 октября 2011.
- ^ Структура данных входав Британской энциклопедии (2009) Онлайн-запись, доступ 4 октября 2011 г.