Коллекция (программирование)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Коллекции и контейнеры[править | править вики-текст]

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

Классификация[править | править вики-текст]

По общим характеристикам[править | править вики-текст]

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

По логике организации[править | править вики-текст]

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

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

По реализации[править | править вики-текст]

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

Операции над коллекциями[править | править вики-текст]

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

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

Известные реализации[править | править вики-текст]

  • Glib — библиотека, реализующая большинство коллекций под лицензией GNU LGPL
  • STL — реализация в виде библиотеки шаблонов для C++.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]