Контейнер (абстрактный тип данных)
 | Эту статью может потребовать очистки Википедии , чтобы она соответствовала стандартам качества . Конкретная проблема: текст неуклюжий. ( Март 2012 г. ) |
В информатике контейнер . — это класс или структура данных [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
Ссылки
[ редактировать ]- ^ Пол Э. Блэк (ред.), запись о структуре данных в Словаре алгоритмов и структур данных . США Национальный институт стандартов и технологий . 15 декабря 2004 г. По состоянию на 4 октября 2011 г.
- ↑ входных Структура данных в Британской энциклопедии (2009) . Интернет-запись по состоянию на 4 октября 2011 г.
- ^ Jump up to: а б с д и Бадд, Тимоти (1997). Введение в объектно-ориентированное программирование (2-е изд.). Ридинг, Массачусетс: Аддисон-Уэсли. ISBN 0-201-82419-1 . OCLC 34788238 .