Контейнер (абстрактный тип данных)

Класс программного обеспечения или структура данных, экземпляры которых являются коллекциями других объектов.

В информатике контейнер — это класс или структура данных ^{[1] [2]} , экземпляры которых представляют собой коллекции других объектов. Другими словами, они хранят объекты организованным образом с соблюдением определенных правил доступа.

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

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

Функция и свойства

Контейнеры можно охарактеризовать следующими тремя свойствами:

• access — это способ доступа к объектам контейнера. В случае массивов доступ осуществляется по индексу массива. В случае стеков доступ осуществляется в соответствии с порядком LIFO (последний вошел — первый вышел), а в случае очередей — в порядке FIFO (первым вошел — первым вышел);
• Storage — способ хранения объектов контейнера;
• traversal — это способ обхода объектов контейнера.

Ожидается, что классы-контейнеры будут реализовывать CRUD -подобные методы для выполнения следующих действий:

• создать пустой контейнер (конструктор);
• вставлять объекты в контейнер;
• удалять объекты из контейнера;
• удалить все объекты в контейнере (очистить);
• получить доступ к объектам в контейнере;
• получить доступ к количеству объектов в контейнере (count).

Контейнеры иногда реализуются совместно с итераторами .

Типы

Контейнеры можно классифицировать как контейнеры с одним значением или ассоциативные контейнеры .

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

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

К абстрактным типам данных контейнера относятся:

• очереди ФИФО
• Стеки ЛИФО
• Приоритетные очереди
• Таблицы поиска (LUT)
• Структуры данных, связанные с ключами
  • Наборы , содержащие и индексирующие объекты по значению или по определенному свойству;
  • Карты , связывающие с каждым ключом «значение» для поиска.

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

• Массивы и их производные
• Связанные списки
• Двоичные деревья поиска (BST), особенно самобалансирующиеся BST.
• Хэш-таблицы

Графические контейнеры

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

В статически типизированных языках

Абстракции контейнера могут быть написаны практически на любом языке программирования, независимо от его системы типов. ^{[3] : 273} Однако в строго типизированных объектно-ориентированных языках разработчику может быть несколько сложно писать многоразовые однородные контейнеры.

Из-за различий в типах элементов это приводит к утомительному процессу написания и хранения коллекции контейнеров для каждого типа элемента. ^{[3] : 274–276.}

Многие типы элементов (например, целые числа или числа с плавающей запятой) по своей сути несовместимы друг с другом из-за занимаемого ими размера памяти и их семантического значения и, следовательно, требуют разных контейнеров (если, конечно, они не являются взаимно совместимыми или конвертируемыми). ^{[3] : 274–276} Современные языки программирования предлагают различные подходы, помогающие решить проблему: ^{[3] : 274–281}

Универсальный базовый тип

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

Понижение ;

Замена класса

Предыдущие три подхода, описанные выше, используются для слабо типизированных языков; они обычно подразумевают наследование и полиморфизм, общие для типов.

Типы объединения (язык C/C++)

Позволяет хранить типы данных разного размера; Однако трудно гарантировать, какой тип сохраняется в объединении при извлечении, и за этим следует тщательно следить.

Преобразование типов

Шаблоны или дженерики

Обеспечивает возможность повторного использования и типобезопасность; можно рассматривать как обратное наследование. Однако этот подход может потребовать реализации специализации шаблона , что, по общему мнению, является трудоемким процессом, учитывая, что типы различаются своими методами. ^{[3] : 281}

Смотрите также

• Список структур данных
• Стандартная библиотека шаблонов#Контейнеры
• Коллекция (абстрактный тип данных)
• Java ConcurrentMap

Рекомендации

1. Пол Э. Блэк (ред.), запись о структуре данных в Словаре алгоритмов и структур данных . Национальный институт стандартов и технологий США . 15 декабря 2004 г. По состоянию на 4 октября 2011 г.
2. Структура входных данных в Британской энциклопедии (2009). Интернет-запись по состоянию на 4 октября 2011 г.
3. Бадд, Тимоти (1997). Введение в объектно-ориентированное программирование (2-е изд.). Ридинг, Массачусетс: Аддисон-Уэсли. ISBN 0-201-82419-1. ОСЛК  34788238.

Внешние ссылки

• Объявление и инициализация структуры данных контейнера