Что такое коллекция в программировании

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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

Wikimedia Foundation . 2010 .

Учебники. Программирование для начинающих.

Programm.ws — это сайт, на котором вы можете почитать литературу по языкам программирования , а так-же посмотреть примеры работающих программ на С++, ассемблере, паскале и много другого..

Программирование — в обычном понимании, это процесс создания компьютерных программ.
В узком смысле (так называемое кодирование) под программированием понимается написание инструкций — программ — на конкретном языке программирования (часто по уже имеющемуся алгоритму — плану, методу решения поставленной задачи). Соответственно, люди, которые этим занимаются, называются программистами (на профессиональном жаргоне — кодерами), а те, кто разрабатывает алгоритмы — алгоритмистами, специалистами предметной области, математиками.
В более широком смысле под программированием понимают весь спектр деятельности, связанный с созданием и поддержанием в рабочем состоянии программ — программного обеспечения ЭВМ. Более точен современный термин — «программная инженерия» (также иначе «инженерия ПО»). Сюда входят анализ и постановка задачи, проектирование программы, построение алгоритмов, разработка структур данных, написание текстов программ, отладка и тестирование программы (испытания программы), документирование, настройка (конфигурирование), доработка и сопровождение.

Delphi для профессионалов

Глава 7. Списки и коллекции

Коллекции

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

Коллекции объектов широко используются в компонентах VCL. Например, панели компонента TCoolBar (см. гл. 5) объединены в коллекцию. Класс TCooiBands , объединяющий панели, является наследником класса TCollection . А отдельная панель — экземпляром класса TCoolBar , происходящего от класса TCollectionitem .

Поэтому знание свойств и методов классов коллекции позволит успешно использовать их при работе со многими компонентами (TDBGrid, TListview, TStatusBar, TCoolBar и т. д.).

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

Рис. 7.1. Редактор коллекции

Список Редактора объединяет элементы коллекции. При выборе одной строки из списка свойства объекта коллекции становятся доступны в Инспекторе объектов. В список можно добавлять новые элементы и удалять существующие, а также менять их взаимное положение.

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

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

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

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

Связанные понятия

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

Примитивный (встроенный, базовый) тип — тип данных, предоставляемый языком программирования как базовая встроенная единица языка.

В языках программирования объявле́ние (англ. declaration) включает в себя указание идентификатора, типа, а также других аспектов элементов языка, например, переменных и функций. Объявление используется, чтобы уведомить компилятор о существовании элемента; это весьма важно для многих языков (например, таких как Си), требующих объявления переменных перед их использованием.

По́ле кла́сса или атрибу́т (переменная-член, data member, class field, instance variable) в объектно-ориентированном программировании — переменная, связанная с классом или объектом. Все данные объекта хранятся в его полях. Доступ к полям осуществляется по их имени. Обычно тип данных каждого поля задаётся в описании класса, членом которого является поле.

Каламбур типизации является прямым нарушением типобезопасности. Традиционно возможность построить каламбур типизации связывается со слабой типизацией, но и некоторые сильно типизированные языки или их реализации предоставляют такие возможности (как правило, используя в связанных с ними идентификаторах слова unsafe или unchecked). Сторонники типобезопасности утверждают, что «необходимость» каламбуров типизации является мифом.

Упоминания в литературе

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

Время от времени возникает необходимость в переустановке операционной системы, например после серьезного сбоя. Чаще всего при этом прибегают к радикальной операции – форматированию, то есть полному уничтожению данных на жестком диске. Дизайнеру же приходится работать с большими (иногда до сотен гигабайт) библиотеками текстур и моделей, и зачастую эти библиотеки хранятся на жестком диске. Если на компьютере будет только один жесткий диск, то при форматировании эти библиотеки неизбежно будут удалены. По этой причине жесткий диск необходимо разбить как минимум на два раздела, например C: и D:. При этом на разделе C: будет установлена операционная система и рабочие программы, а на разделе D: будут храниться рабочие проекты, текстуры и модели. При необходимости обновления операционной системы и форматирования диска C:, все проекты и библиотеки останутся в целостности и сохранности на диске D:. Не лишним будет взять за правило делать периодически резервные копии наиболее ценных коллекций на съемные носители информации – CD или DVD.

Словарь Ахмановой предоставляет довольно большую коллекцию лексических омонимов при практически полном отсутствии грамматических (некоторые даны в приложении). Как отметила О.С. Ахманова, омонимия определяется наличием определённого отношения. «Можно определять омонимы как 2 или более слова, состоящие из тождественных фонемных рядов и различающиеся только семантически или семантически и грамматически одновременно» [Ахманова, 1986, с. 4]. Ахманова выделяет в слове его языковую оболочку, которая оказывается растяжимой, легко допускающей соотнесение со всё новыми и новыми разновидностями или оттенками языкового содержания или значения [там же]. Автор считает, вслед за Виноградовым В.В., полноценным омонимом лексическую единицу, которая в разных контекстных окружениях получает разное лексическое значение. С точки зрения Виноградова В.В., омонимы – это звуковое и грамматическое совпадение языковых единиц, которые семантически не связаны друг с другом.

Связанные понятия (продолжение)

Конста́нта в программировании — способ адресации данных, изменение которых рассматриваемой программой не предполагается или запрещается.

Запись — агрегатный тип данных, инкапсулирующий без сокрытия набор значений различных типов.

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

Пара́метр в программировании — принятый функцией аргумент. Термин «аргумент» подразумевает, что конкретно и какой конкретной функции было передано, а параметр — в каком качестве функция применила это принятое. То есть вызывающий код передает аргумент в параметр, который определен в члене спецификации функции.

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

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

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

Динамическая идентификация типа данных (англ. run-time type information, run-time type identification, RTTI) — механизм в некоторых языках программирования, который позволяет определить тип данных переменной или объекта во время выполнения программы.

Литерал (англ. literal ) — запись в исходном коде компьютерной программы, представляющая собой фиксированное значение. Литералами также называют представление значения некоторого типа данных.

Символьный тип (Сhar) — тип данных, предназначенный для хранения одного символа (управляющего или печатного) в определённой кодировке. Может являться как однобайтовым (для стандартной таблицы символов), так и многобайтовым (к примеру, для Юникода). Основным применением является обращение к отдельным знакам строки.

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

Ме́тод в объектно-ориентированном программировании — это функция или процедура, принадлежащая какому-то классу или объекту.

Свойство — способ доступа к внутреннему состоянию объекта, имитирующий переменную некоторого типа. Обращение к свойству объекта выглядит так же, как и обращение к структурному полю (в структурном программировании), но, в действительности, реализовано через вызов функции. При попытке задать значение данного свойства вызывается один метод, а при попытке получить значение данного свойства — другой.

Замыкание (англ. closure) в программировании — функция первого класса, в теле которой присутствуют ссылки на переменные, объявленные вне тела этой функции в окружающем коде и не являющиеся её параметрами. Говоря другим языком, замыкание — функция, которая ссылается на свободные переменные в своей области видимости.

Абстрактное синтаксическое дерево (АСД) — в информатике конечное помеченное ориентированное дерево, в котором внутренние вершины сопоставлены (помечены) с операторами языка программирования, а листья — с соответствующими операндами. Таким образом, листья являются пустыми операторами и представляют только переменные и константы.

Таблица виртуальных методов (англ. virtual method table, VMT) — координирующая таблица или vtable — механизм, используемый в языках программирования для поддержки динамического соответствия (или метода позднего связывания).

Абстрактный класс в объектно-ориентированном программировании — базовый класс, который не предполагает создания экземпляров. Абстрактные классы реализуют на практике один из принципов ООП — полиморфизм. Абстрактный класс может содержать (и не содержать) абстрактные методы и свойства. Абстрактный метод не реализуется для класса, в котором описан, однако должен быть реализован для его неабстрактных потомков. Абстрактные классы представляют собой наиболее общие абстракции, то есть имеющие наибольший.

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

Опера́ция — конструкция в языках программирования, аналогичная по записи математическим операциям, то есть специальный способ записи некоторых действий.

Из-за путаницы с терминологией словом «оператор» в программировании нередко обозначают операцию (англ. operator), см. Операция (программирование).Инстру́кция или опера́тор (англ. statement) — наименьшая автономная часть языка программирования; команда или набор команд. Программа обычно представляет собой последовательность инструкций.

Логи́ческий тип да́нных, или булев тип, или булевый тип (от англ. Boolean или logical data type) — примитивный тип данных в информатике, принимающий два возможных значения, иногда называемых истиной (true) и ложью (false). Присутствует в подавляющем большинстве языков программирования как самостоятельная сущность или реализуется через численный тип данных. В некоторых языках программирования за значение истина полагается 1, за значение ложь — 0.

Пространство имён — некоторое множество каким-либо образом взаимосвязанных имён или терминов.

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

Перечисляемый тип (сокращённо перечисле́ние, англ. enumeration, enumerated type) — в программировании тип данных, чьё множество значений представляет собой ограниченный список идентификаторов.

Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Подсчёт ссы́лок (англ. reference counting) — техника хранения количества ссылок, указателей или дескрипторов на какой-то ресурс, например на объект или на блок памяти. Обычно используется как средство освобождения объектов, которые больше не нужны и на них больше нет ссылок.

Абстра́ктный тип да́нных (АТД) — это математическая модель для типов данных, где тип данных определяется поведением (семантикой) с точки зрения пользователя данных, а именно в терминах возможных значений, возможных операций над данными этого типа и поведения этих операций.

О́чередь — абстрактный тип данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, англ. first in, first out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

Сравне́ние в программировании — общее название ряда операций над па́рами значений одного типа, реализующих математические отношения равенства и порядка. В языках высокого уровня такие операции, чаще всего, возвращают булево значение («истина» или «ложь»).

Зарезерви́рованное сло́во (или ключево́е сло́во) — в языках программирования слово, имеющее специальное значение. Идентификаторы с такими именами запрещены.

В информатике лексический анализ («токенизация», от англ. tokenizing) — процесс аналитического разбора входной последовательности символов на распознанные группы — лексемы, с целью получения на выходе идентифицированных последовательностей, называемых «токенами» (подобно группировке букв в словах). В простых случаях понятия «лексема» и «токен» идентичны, но более сложные токенизаторы дополнительно классифицируют лексемы по различным типам («идентификатор, оператор», «часть речи» и т. п.). Лексический.

В программировании, строковый тип (англ. string «нить, вереница») — тип данных, значениями которого является произвольная последовательность (строка) символов алфавита. Каждая переменная такого типа (строковая переменная) может быть представлена фиксированным количеством байтов либо иметь произвольную длину.

Ленивые вычисления (англ. lazy evaluation, также отложенные вычисления) — применяемая в некоторых языках программирования стратегия вычисления, согласно которой вычисления следует откладывать до тех пор, пока не понадобится их результат. Ленивые вычисления относятся к нестрогим вычислениям. Усовершенствованная модель ленивых вычислений — оптимистичные вычисления — переходит в разряд недетерминированных стратегий вычисления.

Итератор (от англ. iterator ― перечислитель) — интерфейс, предоставляющий доступ к элементам коллекции (массива или контейнера) и навигацию по ним. В различных системах итераторы могут иметь разные общепринятые названия. В терминах систем управления базами данных итераторы называются курсорами. В простейшем случае итератором в низкоуровневых языках является указатель.

Хеш-табли́ца — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.

Свёртка списка (англ. folding, также известна как reduce, accumulate) в программировании — функция высшего порядка, которая производит преобразование структуры данных к единственному атомарному значению при помощи заданной функции. Операция свёртки часто используется в функциональном программировании при обработке списков. Свёртка может быть обобщена на произвольный алгебраический тип данных при помощи понятия катаморфизма из теории категорий.

Фу́нкция вы́сшего поря́дка — в программировании функция, принимающая в качестве аргументов другие функции или возвращающая другую функцию в качестве результата. Основная идея состоит в том, что функции имеют тот же статус, что и другие объекты данных. Использование функций высшего порядка приводит к абстрактным и компактным программам, принимая во внимание сложность производимых ими вычислений.

Объе́ктный мо́дуль (также — объектный файл, англ. object file) — файл с промежуточным представлением отдельного модуля программы, полученный в результате обработки исходного кода компилятором. Объектный файл содержит в себе особым образом подготовленный код (часто называемый двоичным или бинарным), который может быть объединён с другими объектными файлами при помощи редактора связей (компоновщика) для получения готового исполнимого модуля либо библиотеки.

Область видимости (англ. scope) в программировании — часть программы, в пределах которой идентификатор, объявленный как имя некоторой программной сущности (обычно — переменной, типа данных или функции), остаётся связанным с этой сущностью, то есть позволяет посредством себя обратиться к ней. Говорят, что идентификатор объекта «виден» в определённом месте программы, если в данном месте по нему можно обратиться к данному объекту. За пределами области видимости тот же самый идентификатор может быть.

Функции первого класса являются неотъемлемой частью функционального программирования, в котором использование функций высшего порядка является стандартной практикой. Простым примером функции высшего порядка будет функция Map, которая принимает в качестве своих аргументов функцию и список и возвращается список, после применения функции к каждому элементу списка. Чтобы язык программирования поддерживал Map, он должен поддерживать передачу функций как аргумента.

Интроспекция (англ. type introspection) в программировании — возможность запросить тип и структуру объекта во время выполнения программы. Особое значение имеет в языке Objective C, однако имеется почти во всех языках, позволяющих манипулировать типами объектов как объектами первого класса; среди языков, поддерживающих интроспекцию — C++ (с RTTI), Go, Java, JavaScript, Perl, Ruby, Smalltalk; в PHP и Python интроспекция интегрирована в сам язык. Интроспекция может использоваться для реализации ad-hoc-полиморфизма.

Мона́да — это абстракция линейной цепочки связанных вычислений. Монады позволяют организовывать последовательные вычисления.

Вывод типов (англ. type inference) — в программировании возможность компилятора самому логически вывести тип значения у выражения. Впервые механизм вывода типов был представлен в языке ML, где компилятор всегда выводит наиболее общий полиморфный тип для всякого выражения. Это не только сокращает размер исходного кода и повышает его лаконичность, но и нередко повышает повторное использование кода.

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

Дестру́ктор — специальный метод класса, служащий для деинициализации объекта (например освобождения памяти).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Известные реализации

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

См. также

Примечания

Ссылки

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