Коллекция данных

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

Коллекция позволяет записывать в себя значения и извлекать их. Назначение коллекции — служить хранилищем объектов и обеспечивать доступ к ним. Обычно коллекции используются для хранения групп однотипных объектов, подлежащих стереотипной обработке. Для обращения к конкретному элементу коллекции могут использоваться различные методы, в зависимости от её логической организации. Реализация может допускать выполнение отдельных операций над коллекциями в целом. Наличие операций над коллекциями во многих случаях может существенно упростить программирование.

Коллекции и контейнеры

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

Классификация

По общим характеристикам

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

По логике организации

В зависимости от того, как логически организован доступ к данным коллекции, выделяются следующие основные типы:

• Вектор — элементы коллекции упорядочены, каждый имеет собственный номер, называемый индексом, по которому к нему можно в любой момент обратиться. Как правило, в качестве индексов выступают последовательные целые числа либо значения, приводимые к ним. Для обращения к элементу вектора используется имя вектора и значение индекса. При добавлении нового элемента он добавляется либо в конец вектора, либо в позицию с заданным индексом. Удаление элемента из вектора приводит к образованию пустого элемента.
• Матрица — элементы имеют два упорядоченных индекса, каждый из которых является целым числом или значением, приводимым к целому. Для доступа к элементу нужно указать имя матрицы и оба индекса. Новый элемент может быть добавлен только в позицию с заданной парой индексов. Удаление приводит к оставлению пустого элемента.
• Многомерный массив — логическое развитие идеи вектора и матрицы до большего (в общем случае — произвольного) числа индексов.
• Список — элементы коллекции упорядочены, идентификаторов у элементов нет. Список — коллекция с последовательным доступом. В любой момент доступен первый элемент коллекции (обычно также доступен и последний). От любого элемента коллекции можно получить доступ к следующему по порядку, таким образом, можно последовательно дойти от первого элемента списка до любого желаемого. Возможна реализация, допускающая обратный проход (к предыдущему элементу от известного). Новый элемент может добавляться в начало или в конец списка. При удалении элемента из начала списка первым элементом становится следующий за ним, при удалении из конца — предыдущий, из середины — предыдущий и последующий элементы становятся, соответственно, предыдущим и последующим один для друго.
• Стек — коллекция, реализующая принцип хранения «LIFO» («последним пришёл — первым вышел»). В стеке постоянно доступен только один элемент — тот, который был добавлен последним. Новый элемент может быть добавлен в стек, он станет текущим. Текущий элемент всегда можно удалить («взять») из стека, после этого становится доступен элемент, который был добавлен непосредственно перед ним.
• Очередь — коллекция, реализующая принцип хранения «FIFO» («первым пришёл — первым вышел»). В очереди постоянно доступен только один элемент — тот, который был добавлен самым первым из имеющихся. При добавлении нового элемента он попадает в очередь. Текущий элемент можно удалить — тогда текущим станет элемент, добавленный первым из оставшихся.
• Ассоциативный массив (словарь) — неупорядоченная коллекция, хранящая пары «ключ — значение». Доступ к элементам производится по ключу. В качестве ключа могут использоваться значения различных типов, единственное ограничение — тип ключа должен допускать сравнение на равенство. Любая пара может быть в любой момент удалена. Добавляться может только пара (с определённым ключём). Может вводиться запрет на дублирование ключей в коллекции. Если такого ограничения нет, то при обращении по дублирующемуся ключу может выдаваться либо n-е найденное значение (где n либо постоянно, либо определяется формой запроса), либо все значения с данным ключём.
• Множество — неупорядоченная коллекция, хранящая набор уникальных значений и поддерживающая для них операции добавления, удаления и определения вхождения. Как правило, для множеств поддерживаются операции, аналогичным операциям с математическими множествами: объединение, пересечение, симметричная разность множеств и несимметричная разность множеств.
• Мультимножество — неупорядоченная коллекция, аналогичная множеству, но допускающая наличие в коллекции одновременно двух и более одинаковых значений.

По реализации

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

• Массив
• Односвязный список
• Двусвязный список
• Стек
• Хеш-таблица
• Битовый массив

Операции над коллекциями

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

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

Ссылки

• apache.org
• google.com
• Mango Java library
• Коллекции и контейнеры в спецификации RDF