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

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

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

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

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

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

access , то есть способ доступа к объектам контейнера. В случае массивов доступ осуществляется с помощью индекса массива. В случае стеков доступ осуществляется в соответствии с порядком LIFO (last in, first out), а в случае очередей — в соответствии с порядком FIFO (first in, first out);
хранение , то есть способ хранения объектов контейнера;
обход , то есть способ обхода объектов контейнера.

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

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

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

Типы

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

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

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

Абстрактные типы данных контейнера включают в себя:

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

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

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

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

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

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

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

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

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

Универсальный базовый тип: Тип, который универсально может быть назначен любым другим (например, корневым классом Object).
Понижение ;
Замена класса: Предыдущие три подхода, описанные выше, используются для слабо типизированных языков; они обычно подразумевают наследование и полиморфизм, общие для типов.
Типы объединений (язык C/C++): Позволяет хранить типы данных разного размера; однако сложно гарантировать, какой тип будет сохранен в объединении при извлечении, и за этим следует тщательно следить.
Преобразование типов
Шаблоны или дженерики: Обеспечивает повторное использование и безопасность типов; может рассматриваться как обратное наследование. Однако этот подход может потребовать реализации специализации шаблона , что, как известно, является трудоемким процессом, учитывая, что типы различаются по своим методам. ^[3]^{: 281}

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

Ссылки

^ Пол Э. Блэк (ред.), статья о структуре данных в Словаре алгоритмов и структур данных . Национальный институт стандартов и технологий США . 15 декабря 2004 г. Доступ 4 октября 2011 г.
^ Структура данных записи в Encyclopaedia Britannica (2009) Онлайн-запись Доступно 4 октября 2011 г.
^ abcde Бадд, Тимоти (1997). Введение в объектно-ориентированное программирование (2-е изд.). Reading, Mass.: Addison-Wesley. ISBN 0-201-82419-1. OCLC 34788238.

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

Декларация и инициализация структуры данных контейнера