Всем программистам знакомы понятия массива, списка, очереди, стека и другие названия для типов хранилищ множества данных. Как разобраться что есть что, и для чего нужно? Этим я и попробую заняться.
Коллекцией я буду называть любой информационный объект, способный адресовать счётное количество других однородных объектов. Этим я надеюсь не пересечься любым другим подобным названием, которое может иметь сходное значение, таким как массив, набор и т. п.
Неотъемлемым свойством любой коллекции является то, что она обеспечивает доступ к другим объектам, которые именуются элементами коллекции. Функциональные качества определяются тем, каким образом этот доступ предоставляется.
Первой важной характеристикой доступа является адресация. Адресация бывает двух основных видов:
Различные виды коллекций могут предоставлять оба вида адресации, один из них, и даже не предоставлять никакого.
Ключевая адресация самая простая для понимания. Она подразумевает, что каждому элементу коллекции поставлен в соответствие некий уникальный ключ или совокупность ключей, каждый из которых однозначно определяет этот элемент. При этом могут существовать ключи, которым не соответствует ни один элемент. Таким образом, зная ключ, из такой коллекции всегда можно достать один элемент. Характерным примером коллекции с ключевой адресацией является файловая система, где ключом является путь к файлу, а сам файл — элементом хранилища. Ключом может являться что угодно: число, строка и т. д.
Существуют два простых типа коллекций, реализующих ключевую адресацию:
Здесь есть один момент: ключ можно связать со значением, так, что из значения можно вычислить ключ. Это можно назвать переходной формой между собственно картой и множеством, и в вырожденном случае (тождественная связь) это будет множеством, однако во всех остальных случаях это следует считать именно картой.
В основе порядковой адресации концепция, что элементы коллекции упорядочены, то есть образуют единую последовательность, где у каждого элемента (кроме крайних) есть следующий и предыдущий, и (если это не кольцо) любые два элемента могут быть сравнены в отношении порядка — какой перед каким стоит.
Можно выделить два основных типа коллекций с порядковой адресацией:
Неплотная цепь — самый универсальный вид коллекций с порядковым доступом. Он позволяет добавлять элементы в любое порядковое место. Для этого при добавлении явно указывается точка вставки, это может быть начало (иначе называемый — „голова“), конец („хвост“) или точка между любыми двумя соседними элементами. Операция замены элемента уже не элементарна, она состоит из удаления элемента и вставки нового в то же место.
Особым видом неплотной цепи является кольцо, отличающееся тем, что её начало соединено с концом, в результате чего отсутствуют крайние элементы. При этом, при сохранении последовательности, пропадает общее однозначное отношение «идущий впереди / сзади».
Плотная цепь получается ограничением возможностей добавления и удаления краями списка. Таким образом элементы плотной цепи никогда не сдвигаются и не раздвигаются. Можно выделить следующие подвиды плотных списков:
Башня характеризуется тем, что своё место каждый элемент занимает в с соответствии со своим содержимым. Это требует наличия некотоей функции сравнения элементов, обеспечивающего упорядочивание. В качестве практического примера можно привести упорядочивание по величине, алфавиту или приоритету.
Классическая организация упорядочивания подразумевает, что функция сравнения получает аргументами два значения и на выходе имеет три возможных значения: –1 (меньше), 0 (равно), +1 (больше). Она должна обладать свойствами сравнения:
Надо заметить, что не все способы упорядочивания однозначны — если функция сравнения может давать равенство для двух различных элементов, то нельзя определить, в каком порядке их ставить. Тогда образуется переходная форма между башней и списком: в этом случае порядок элементов может зависеть от явных указаний по размещению или порядка добавления.
На самом деле можно определить ещё один очень простой вид коллекции. Это коллекция, не поддерживающая ни тот, ни другой типы адресации. Его можно назвать кучей. Несмотря на кажущуюся бессмысленность, куча, тем не менее, может найти применение. Например, некоторые методы работы массивной обработки данных вообще не требуют адресации. К таким можно отнести операции:
Рассмотрев простые типы коллекций, можно перейти к комбинированным, таким, которые дают и порядковый, и ключевой методы доступа. И, надо сказать, что комбинированные типы иногда дают больше, чем просто сумму возможностей.
| Куча | Множество | Карта |
|---|---|---|
| Цепь | Иерархия | Карта-цепь |
| Башня | Словарь | Карта-башня |
Иерархия — это коллекция, в которой каждому значению поставлено в соответствие некоторое положение относительно всех остальных. Такой вид коллекции характерен, например, для системы приоритетов.
Словарь — множество, члены которого упорядочены в соответствии со своими значениями. В данном случае словарь применяется только как набор всех слов, но не их определений.
Карта, элементы которой дополнительно явно упорядочены. Отличительной чертой является то, что для добавления элемента в карту-цепь требуется указание как ключа, так и места вставки.
Один из самых интересных комбинированных типов. Это карта, в которой порядок зависит от ключей или значений (или и того, и другого).
Самым простым и полезным видом карты-башни является массив, коллекция, ключами которой являются последовательные целые числа. Они же определяют порядок элементов.