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

Поделись знанием:
Перейти к: навигация, поиск

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

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





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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Напишите отзыв о статье "Коллекция (программирование)"

Примечания

Ссылки

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

Отрывок, характеризующий Коллекция (программирование)

– Кому тушить то? – послышался голос Данилы Терентьича, молчавшего до сих пор. Голос его был спокоен и медлителен. – Москва и есть, братцы, – сказал он, – она матушка белока… – Голос его оборвался, и он вдруг старчески всхлипнул. И как будто только этого ждали все, чтобы понять то значение, которое имело для них это видневшееся зарево. Послышались вздохи, слова молитвы и всхлипывание старого графского камердинера.


Камердинер, вернувшись, доложил графу, что горит Москва. Граф надел халат и вышел посмотреть. С ним вместе вышла и не раздевавшаяся еще Соня, и madame Schoss. Наташа и графиня одни оставались в комнате. (Пети не было больше с семейством; он пошел вперед с своим полком, шедшим к Троице.)
Графиня заплакала, услыхавши весть о пожаре Москвы. Наташа, бледная, с остановившимися глазами, сидевшая под образами на лавке (на том самом месте, на которое она села приехавши), не обратила никакого внимания на слова отца. Она прислушивалась к неумолкаемому стону адъютанта, слышному через три дома.
– Ах, какой ужас! – сказала, со двора возвративись, иззябшая и испуганная Соня. – Я думаю, вся Москва сгорит, ужасное зарево! Наташа, посмотри теперь, отсюда из окошка видно, – сказала она сестре, видимо, желая чем нибудь развлечь ее. Но Наташа посмотрела на нее, как бы не понимая того, что у ней спрашивали, и опять уставилась глазами в угол печи. Наташа находилась в этом состоянии столбняка с нынешнего утра, с того самого времени, как Соня, к удивлению и досаде графини, непонятно для чего, нашла нужным объявить Наташе о ране князя Андрея и о его присутствии с ними в поезде. Графиня рассердилась на Соню, как она редко сердилась. Соня плакала и просила прощенья и теперь, как бы стараясь загладить свою вину, не переставая ухаживала за сестрой.
– Посмотри, Наташа, как ужасно горит, – сказала Соня.
– Что горит? – спросила Наташа. – Ах, да, Москва.
И как бы для того, чтобы не обидеть Сони отказом и отделаться от нее, она подвинула голову к окну, поглядела так, что, очевидно, не могла ничего видеть, и опять села в свое прежнее положение.
– Да ты не видела?
– Нет, право, я видела, – умоляющим о спокойствии голосом сказала она.
И графине и Соне понятно было, что Москва, пожар Москвы, что бы то ни было, конечно, не могло иметь значения для Наташи.
Граф опять пошел за перегородку и лег. Графиня подошла к Наташе, дотронулась перевернутой рукой до ее головы, как это она делала, когда дочь ее бывала больна, потом дотронулась до ее лба губами, как бы для того, чтобы узнать, есть ли жар, и поцеловала ее.
– Ты озябла. Ты вся дрожишь. Ты бы ложилась, – сказала она.
– Ложиться? Да, хорошо, я лягу. Я сейчас лягу, – сказала Наташа.
С тех пор как Наташе в нынешнее утро сказали о том, что князь Андрей тяжело ранен и едет с ними, она только в первую минуту много спрашивала о том, куда? как? опасно ли он ранен? и можно ли ей видеть его? Но после того как ей сказали, что видеть его ей нельзя, что он ранен тяжело, но что жизнь его не в опасности, она, очевидно, не поверив тому, что ей говорили, но убедившись, что сколько бы она ни говорила, ей будут отвечать одно и то же, перестала спрашивать и говорить. Всю дорогу с большими глазами, которые так знала и которых выражения так боялась графиня, Наташа сидела неподвижно в углу кареты и так же сидела теперь на лавке, на которую села. Что то она задумывала, что то она решала или уже решила в своем уме теперь, – это знала графиня, но что это такое было, она не знала, и это то страшило и мучило ее.
– Наташа, разденься, голубушка, ложись на мою постель. (Только графине одной была постелена постель на кровати; m me Schoss и обе барышни должны были спать на полу на сене.)
– Нет, мама, я лягу тут, на полу, – сердито сказала Наташа, подошла к окну и отворила его. Стон адъютанта из открытого окна послышался явственнее. Она высунула голову в сырой воздух ночи, и графиня видела, как тонкие плечи ее тряслись от рыданий и бились о раму. Наташа знала, что стонал не князь Андрей. Она знала, что князь Андрей лежал в той же связи, где они были, в другой избе через сени; но этот страшный неумолкавший стон заставил зарыдать ее. Графиня переглянулась с Соней.
– Ложись, голубушка, ложись, мой дружок, – сказала графиня, слегка дотрогиваясь рукой до плеча Наташи. – Ну, ложись же.
– Ах, да… Я сейчас, сейчас лягу, – сказала Наташа, поспешно раздеваясь и обрывая завязки юбок. Скинув платье и надев кофту, она, подвернув ноги, села на приготовленную на полу постель и, перекинув через плечо наперед свою недлинную тонкую косу, стала переплетать ее. Тонкие длинные привычные пальцы быстро, ловко разбирали, плели, завязывали косу. Голова Наташи привычным жестом поворачивалась то в одну, то в другую сторону, но глаза, лихорадочно открытые, неподвижно смотрели прямо. Когда ночной костюм был окончен, Наташа тихо опустилась на простыню, постланную на сено с края от двери.
– Наташа, ты в середину ляг, – сказала Соня.
– Нет, я тут, – проговорила Наташа. – Да ложитесь же, – прибавила она с досадой. И она зарылась лицом в подушку.
Графиня, m me Schoss и Соня поспешно разделись и легли. Одна лампадка осталась в комнате. Но на дворе светлело от пожара Малых Мытищ за две версты, и гудели пьяные крики народа в кабаке, который разбили мамоновские казаки, на перекоске, на улице, и все слышался неумолкаемый стон адъютанта.
Долго прислушивалась Наташа к внутренним и внешним звукам, доносившимся до нее, и не шевелилась. Она слышала сначала молитву и вздохи матери, трещание под ней ее кровати, знакомый с свистом храп m me Schoss, тихое дыханье Сони. Потом графиня окликнула Наташу. Наташа не отвечала ей.
– Кажется, спит, мама, – тихо отвечала Соня. Графиня, помолчав немного, окликнула еще раз, но уже никто ей не откликнулся.
Скоро после этого Наташа услышала ровное дыхание матери. Наташа не шевелилась, несмотря на то, что ее маленькая босая нога, выбившись из под одеяла, зябла на голом полу.
Как бы празднуя победу над всеми, в щели закричал сверчок. Пропел петух далеко, откликнулись близкие. В кабаке затихли крики, только слышался тот же стой адъютанта. Наташа приподнялась.
– Соня? ты спишь? Мама? – прошептала она. Никто не ответил. Наташа медленно и осторожно встала, перекрестилась и ступила осторожно узкой и гибкой босой ступней на грязный холодный пол. Скрипнула половица. Она, быстро перебирая ногами, пробежала, как котенок, несколько шагов и взялась за холодную скобку двери.
Ей казалось, что то тяжелое, равномерно ударяя, стучит во все стены избы: это билось ее замиравшее от страха, от ужаса и любви разрывающееся сердце.
Она отворила дверь, перешагнула порог и ступила на сырую, холодную землю сеней. Обхвативший холод освежил ее. Она ощупала босой ногой спящего человека, перешагнула через него и отворила дверь в избу, где лежал князь Андрей. В избе этой было темно. В заднем углу у кровати, на которой лежало что то, на лавке стояла нагоревшая большим грибом сальная свечка.
Наташа с утра еще, когда ей сказали про рану и присутствие князя Андрея, решила, что она должна видеть его. Она не знала, для чего это должно было, но она знала, что свидание будет мучительно, и тем более она была убеждена, что оно было необходимо.
Весь день она жила только надеждой того, что ночью она уввдит его. Но теперь, когда наступила эта минута, на нее нашел ужас того, что она увидит. Как он был изуродован? Что оставалось от него? Такой ли он был, какой был этот неумолкавший стон адъютанта? Да, он был такой. Он был в ее воображении олицетворение этого ужасного стона. Когда она увидала неясную массу в углу и приняла его поднятые под одеялом колени за его плечи, она представила себе какое то ужасное тело и в ужасе остановилась. Но непреодолимая сила влекла ее вперед. Она осторожно ступила один шаг, другой и очутилась на середине небольшой загроможденной избы. В избе под образами лежал на лавках другой человек (это был Тимохин), и на полу лежали еще два какие то человека (это были доктор и камердинер).
Камердинер приподнялся и прошептал что то. Тимохин, страдая от боли в раненой ноге, не спал и во все глаза смотрел на странное явление девушки в бедой рубашке, кофте и вечном чепчике. Сонные и испуганные слова камердинера; «Чего вам, зачем?» – только заставили скорее Наташу подойти и тому, что лежало в углу. Как ни страшно, ни непохоже на человеческое было это тело, она должна была его видеть. Она миновала камердинера: нагоревший гриб свечки свалился, и она ясно увидала лежащего с выпростанными руками на одеяле князя Андрея, такого, каким она его всегда видела.