В компьютерном программировании коллекция — это группа некоторого переменного количества элементов данных (возможно , нулевого), которые имеют некоторое общее значение для решаемой проблемы и над которыми необходимо работать вместе каким-то контролируемым образом. Как правило, элементы данных будут одного и того же типа или, в языках, поддерживающих наследование, производными от некоторого общего предкового типа. Коллекция — это концепция, применимая к абстрактным типам данных , и она не предписывает конкретную реализацию в качестве конкретной структуры данных , хотя часто существует традиционный выбор ( обсуждение теории типов см . в разделе «Контейнер »).
Примеры коллекций включают списки , множества , мультимножества , деревья и графы .
Массивы (или таблицы) фиксированного размера обычно не считаются коллекцией, поскольку они содержат фиксированное количество элементов данных, хотя обычно они играют роль в реализации коллекций. Массивы переменного размера обычно считаются коллекциями. [ нужна цитата ]
Многие коллекции определяют определенный линейный порядок с доступом к одному или обоим концам. Фактическая структура данных, реализующая такую коллекцию, не обязательно должна быть линейной — например, очередь с приоритетами часто реализуется в виде кучи , которая представляет собой своего рода дерево. Важные линейные коллекции включают:
В списке порядок элементов данных имеет значение. Дублирующиеся элементы данных допускаются. Примеры операций со списками: поиск элемента данных в списке и определение его местоположения (если он присутствует), удаление элемента данных из списка, добавление элемента данных в список в определенном месте и т. д. Если принципал операции над списком должны заключаться в добавлении элементов данных на одном конце и удалении элементов данных на другом; обычно это называется очередью или FIFO . Если основными операциями являются добавление и удаление элементов данных только на одном конце, это будет называться стеком или LIFO . В обоих случаях элементы данных сохраняются в коллекции в одном и том же порядке (если только они не удаляются и не вставляются повторно в другое место), поэтому это особые случаи коллекции списков. Другие специализированные операции со списками включают сортировку, где, опять же, порядок элементов данных имеет большое значение.
Стек — это структура данных LIFO с двумя основными операциями: push , которая добавляет элемент в «верх» коллекции, и pop , которая удаляет верхний элемент.
В приоритетной очереди сохраняются дорожки минимального или максимального элемента данных в коллекции в соответствии с некоторым критерием упорядочения, а порядок других элементов данных не имеет значения. Очередь приоритетов можно представить себе как список, в котором минимум или максимум всегда находится в начале, а остальные элементы хранятся в пакете.
Вместо этого другие коллекции можно интерпретировать как своего рода функцию: учитывая входные данные, коллекция дает выходные данные. Важные ассоциативные коллекции включают:
Набор можно интерпретировать как специализированное мультимножество, которое, в свою очередь, представляет собой специализированный ассоциативный массив, в каждом случае ограничивая возможные значения — рассматривая набор, представленный его индикаторной функцией .
В наборе порядок элементов данных не имеет значения (или не определен), но дублирование элементов данных не допускается. Примерами операций над наборами являются добавление и удаление элементов данных, а также поиск элемента данных в наборе. Некоторые языки поддерживают наборы напрямую. В других случаях наборы могут быть реализованы с помощью хэш-таблицы с фиктивными значениями; для представления набора используются только ключи.
В мультинаборе (или пакете), как и в наборе, порядок элементов данных не имеет значения, но в этом случае допускается дублирование элементов данных. Примерами операций с мультинаборами являются добавление и удаление элементов данных, а также определение количества дубликатов определенного элемента данных, присутствующих в мультинаборе. Мультимножества можно преобразовать в списки с помощью сортировки.
В ассоциативном массиве (или карте, словаре, таблице поиска), как и в словаре, поиск по ключу (например, слову) дает значение (например, определение). Значение может быть ссылкой на составную структуру данных. Хэш -таблица обычно является эффективной реализацией, поэтому этот тип данных часто называют «хешем».
В графе элементы данных связаны с одним или несколькими другими элементами данных в коллекции и чем-то похожи на деревья без концепции корня или отношений « родитель-потомок» , поэтому все элементы данных являются одноранговыми. Примерами операций над графами являются обходы и поиски, которые исследуют ассоциации элементов данных в поисках определенного свойства. Графики часто используются для моделирования реальных ситуаций и решения связанных с ними проблем. Примером может служить протокол связующего дерева , который создает графовое (или сетчатое) представление сети передачи данных и определяет, какие связи между узлами коммутации необходимо разорвать, чтобы превратить ее в дерево и тем самым предотвратить зацикливание данных.
В дереве, которое представляет собой особый вид графа, корневой элемент данных связан с некоторым количеством элементов данных, которые, в свою очередь, связаны с ним некоторым количеством других элементов данных, что часто рассматривается как отношения родитель-потомок . Каждый элемент данных (кроме корня) имеет одного родителя (у корня нет родителя) и некоторое количество дочерних элементов, возможно, нулевое. Примерами операций с деревьями являются добавление элементов данных для сохранения определенного свойства дерева для выполнения сортировки и т. д., а также обходы для посещения элементов данных в определенной последовательности.
Древовидные коллекции можно использовать для естественного хранения иерархических данных, представленных в виде дерева, например систем меню и файлов в каталогах системы хранения данных.
Специализированные деревья используются в различных алгоритмах. Например, при сортировке кучей используется разновидность дерева, называемая кучей .
Как описано здесь, коллекция и различные виды коллекций являются абстрактными понятиями. В литературе существует значительная путаница между абстрактными концепциями информатики и их конкретными реализациями на разных языках или типах языков. Утверждения о том, что такие коллекции, как списки, множества, деревья и т. д., являются структурами данных, абстрактными типами данных или классами, следует читать с учетом этого. Коллекции — это прежде всего абстракции, которые полезны при формулировании решений вычислительных задач. С этой точки зрения они сохраняют важные связи с лежащими в их основе математическими концепциями, которые могут быть утеряны, когда основное внимание уделяется реализации.
Например, очередь приоритетов часто реализуется в виде кучи, а ассоциативный массив часто реализуется в виде хеш-таблицы, поэтому в этой предпочтительной реализации эти абстрактные типы часто называются «кучей» или «хешем». это не совсем правильно.
Некоторые коллекции могут представлять собой примитивные типы данных на языке, например списки, тогда как более сложные коллекции реализуются как составные типы данных в библиотеках, иногда в стандартной библиотеке . Примеры включают в себя:
Коллекции реализованы как TYPE. Как и в случае с любым типом, определяемым программистом, вы должны сначала определить тип; тогда вы можете объявить экземпляры этого типа.