Коллекция (программирование) - История изменений

Patarakin в 09:05, 19 октября 2022

2022-10-19T09:05:27Z

@@ Строка 1: / Строка 1: @@
 '''Коллекция''' в программировании — программный объект, содержащий в себе, тем или иным образом, набор значений одного или различных типов, и позволяющий обращаться к этим значениям.
@@ Строка 5: / Строка 4: @@
 == Коллекции и контейнеры ==
-Коллекция или [[Контейнер (программирование)|контейнер]] группирует некоторое переменное (возможно, нулевое) число элементов данных, которые имеют некоторое общее значение для решения проблемы. Над ними проводятся операции некоторым способом. Обычно элементы данных имеют один и тот же тип, или же (в языках, поддерживающих [[Наследование (программирование)|наследование]]) типы будут получены из некоторого общего типа-предка. Коллекция — понятие, применимое к [[Абстрактный тип данных|абстрактным типам данных]], и не предписывает определённую реализацию через конкретную структуру данных, хотя часто существует устоявшийся выбор. Контейнеры в [[Теория типов|теории типов]] — абстракции, которые разрешают коллекциям различных структур, таких как [[Список (информатика)|списки]] и [[Дерево (структура данных)|деревья]], быть представленными некоторым однородным способом. ([[Унарная операция|Унарный]]) [[Контейнер (программирование)|контейнер]] определён индексами S и семейством типов на позициях P, индексируемыми через S: задана [[Функция (математика)|функция]] от типов индексов к типу элементов. Контейнеры можно рассматривать как канонические классы для коллекций различных типов. Списки индексируются через [[натуральные числа]] (включая [[0 (число)|ноль]]). Для списков определён максимальный индекс. Натуральные числа как индексы [[Изоморфизм|изоморфны]] спискам. Для [[Дерево (структура данных)|деревьев]] структура дерева может быть выражена через индексы без конкретной информации о содержимом узлов. Индексы элементов структуры в памяти изоморфны путям от [[Корень (значения)|корня дерева]] до его [[Узел (значения)|узлов]].
+Коллекция или [[Контейнер (программирование)|контейнер]] группирует некоторое переменное (возможно, нулевое) число элементов данных, которые имеют некоторое общее значение для решения проблемы. Над ними проводятся операции некоторым способом. Обычно элементы данных имеют один и тот же тип, или же (в языках, поддерживающих [[Наследование (программирование)|наследование]]) типы будут получены из некоторого общего типа-предка. Коллекция — понятие, применимое к [[Абстрактный тип данных|абстрактным типам данных]], и не предписывает определённую реализацию через конкретную структуру данных, хотя часто существует устоявшийся выбор. Контейнеры в [[Теория типов|теории типов]] — абстракции, которые разрешают коллекциям различных структур, таких как [[Список (информатика)|списки]] и [[Дерево (структура данных)|деревья]], быть представленными некоторым однородным способом.
 == Классификация ==
@@ Строка 46: / Строка 45: @@
 * [[Стандартная библиотека шаблонов|STL]] — реализация в виде библиотеки шаблонов для C++.
-== См. также ==
+----
 [[Категория:Структуры данных]]

Patarakin: 1 версия импортирована

2022-10-19T07:30:50Z

1 версия импортирована

← Предыдущая версия	Версия от 10:30, 19 октября 2022
(нет различий)

ru_wikipedia>Alex NB OT: Проект Check Wikipedia: исправление ошибки 48 по запросу

2021-12-03T01:28:06Z

Проект Check Wikipedia: исправление ошибки 48 по запросу

Новая страница

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

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

== Коллекции и контейнеры ==
Коллекция или [[Контейнер (программирование)|контейнер]] группирует некоторое переменное (возможно, нулевое) число элементов данных, которые имеют некоторое общее значение для решения проблемы. Над ними проводятся операции некоторым способом. Обычно элементы данных имеют один и тот же тип, или же (в языках, поддерживающих [[Наследование (программирование)|наследование]]) типы будут получены из некоторого общего типа-предка. Коллекция — понятие, применимое к [[Абстрактный тип данных|абстрактным типам данных]], и не предписывает определённую реализацию через конкретную структуру данных, хотя часто существует устоявшийся выбор. Контейнеры в [[Теория типов|теории типов]] — абстракции, которые разрешают коллекциям различных структур, таких как [[Список (информатика)|списки]] и [[Дерево (структура данных)|деревья]], быть представленными некоторым однородным способом. ([[Унарная операция|Унарный]]) [[Контейнер (программирование)|контейнер]] определён индексами S и семейством типов на позициях P, индексируемыми через S: задана [[Функция (математика)|функция]] от типов индексов к типу элементов. Контейнеры можно рассматривать как канонические классы для коллекций различных типов. Списки индексируются через [[натуральные числа]] (включая [[0 (число)|ноль]]). Для списков определён максимальный индекс. Натуральные числа как индексы [[Изоморфизм|изоморфны]] спискам. Для [[Дерево (структура данных)|деревьев]] структура дерева может быть выражена через индексы без конкретной информации о содержимом узлов. Индексы элементов структуры в памяти изоморфны путям от [[Корень (значения)|корня дерева]] до его [[Узел (значения)|узлов]].

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

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

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

=== По реализации ===
На уровне реализации коллекция может представлять собой одну из следующих структур данных:
* [[Массив (программирование)|Массив]]
* [[Односвязный список]]
* [[Двусвязный список]]
* [[Стек]]
* [[Хеш-таблица]]
* [[Битовый массив]]

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

== Известные реализации ==
* [[Glib]] — библиотека, реализующая большинство коллекций под лицензией [[GNU LGPL]]
* [[Стандартная библиотека шаблонов|STL]] — реализация в виде библиотеки шаблонов для C++.

== См. также ==
* [[Итератор (программирование)|Итератор]]

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://commons.apache.org/collections/ apache.org]
* [http://code.google.com/p/google-collections/ google.com]
* [https://web.archive.org/web/20071018214704/http://jezuk.co.uk/cgi-bin/view/mango Mango Java library]
* [http://www.w3.org/TR/rdf-mt/#ReifAndCont Коллекции и контейнеры в спецификации RDF]

{{rq|sources|wikify}}

{{Типы данных}}
{{Структуры данных}}
[[Категория:Структуры данных]]