Множество — тип и структура данных в информатике, является реализацией математического объекта множество.
Данные типа множество позволяют хранить ограниченное число значений определённого типа без определённого порядка. Повторение значений, как правило, недопустимо. За исключением того, что множество в программировании конечно, оно в общем соответствует концепции математического множества. Для этого типа в языках программирования обычно предусмотрены стандартные операции над множествами.
В зависимости от идеологии, разные языки программирования рассматривают множество как простой или сложный тип данных.
Реализации
Множество в Паскале
В языке Паскаль множество — составной тип данных, хранящий информацию о присутствии в множестве объектов любого счетного типа. Мощность этого типа определяет размер множества — 1 бит на элемент. В Turbo Pascal есть ограничение на 256 элементов, в некоторых других реализациях это ограничение ослаблено.
Пример работы с множествами:
Типы данных
Неинтерпретируемые
Логический • Низший тип • Коллекция • Перечисляемый тип • Исключение • First-class function • Opaque data type • Recursive data type • Семафор • Поток • Высший тип • Type class • Unit type • Void
Абстрактный тип данных • Структура данных • Интерфейс • Kind (type theory) • Примитивный тип • Subtyping • Шаблоны C++ • Конструктор типа • Parametric polymorphism
Полезное
Смотреть что такое «Множество (тип данных)» в других словарях:
Тип данных — (встречается также термин вид данных) фундаментальное понятие теории программирования. Тип данных определяет множество значений, набор операций, которые можно применять к таким значениям и, возможно, способ реализации хранения значений и… … Википедия
тип данных — Множество величин, объединенных определенной совокупностью допустимых операций. [ИСО/МЭК 2382 15] [ГОСТ Р 52292 2004] тип данных тип Множество значений вместе с множеством допустимых над ними операций [ГОСТ 28397 89] тип данных В программировании … Справочник технического переводчика
тип данных — 2.35 тип данных (data type): Поименованная совокупность данных с общими статическими и динамическими свойствами, устанавливаемыми формализованными требованиями к данным рассматриваемого типа. Источник: ГОСТ Р ИСО/МЭК ТО 10032 2007: Эталонная… … Словарь-справочник терминов нормативно-технической документации
тип данных элемента данных — 3.1.6 тип данных элемента данных (Data Element Datatype; DE datatype): Спецификация множества различных значений для элемента данных, характеризуемая свойствами этих значений и возможными операциями над этими значениями. Примечание 1 Множество… … Словарь-справочник терминов нормативно-технической документации
Целое (тип данных) — Целое, целочисленный тип данных (англ. Integer), в информатике один из простейших и самых распространённых типов данных в языках программирования. Служит для представления целых чисел. Множество чисел этого типа представляет собой… … Википедия
Комплексный тип данных — Некоторые языки программирования предоставляют специальный тип данных для комплексных чисел. Наличие встроенного типа упрощает хранение комплексных величин и вычисления над ними. Содержание 1 Арифметика над комплексными 2 Поддержка в языках … Википедия
Алгебраический тип данных — в теории программирования любой тип, значения которого являются значениями некоторых иных типов, «обёрнутыми» конструкторами алгебраического типа. Другими словами, алгебраический тип данных имеет набор конструкторов типа, каждый из которых… … Википедия
Абстрактный тип данных — Для улучшения этой статьи по информационным технологиям желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Проставив сноски, внести более точные у … Википедия
Указатель (тип данных) — У этого термина существуют и другие значения, см. Указатель. Диаграмма указателей Указатель (пойнтер, англ. pointer) переменная, диапазон значений которой состоит из адресов ячеек памяти и специального значения нулевого адреса.… … Википедия
Обобщённый алгебраический тип данных — один из видов алгебраических типов данных, который характеризуется тем, что его конструкторы могут возвращать значения не своего типа. Это понятие реализовано в нескольких языках программирования, в частности в языках ML и Haskell, причём в… … Википедия
Теория множеств: основы и базовые операции над множествами
Мы знаем довольно много о структурах данных, понимаем их устройство, разбираемся, какие структуры работают быстро и помогают решать конкретные задачи. Но эти знания бесполезны, если мы не понимаем, как это использовать в реальной жизни. Это похоже на изучение геометрии в школе. Вы долго считаете предмет бесполезным, пока однажды не появляется необходимость рассчитать площадь пола, чтобы заказать новое ковровое покрытие. Впрочем, пользу геометрии можно почувствовать, даже если вы никогда не считали площадь пола в комнате самостоятельно.
Сегодня поговорим о структуре данных, которая в теории очень догматична, а на практике очень популярна. На самом деле вы так или иначе уже сталкивались с этой структурой, а также слышали о ней на уроках математики в школе. Вы уже догадались, что речь идёт о множествах.
Теория множеств без страха
Прежде чем разбирать устройство множеств, давайте поймём, откуда они появляются. То есть давайте сразу погрузимся в теорию — да-да, в теорию множеств! Не бойтесь сложностей — высока вероятность того, что вы уже так или иначе использовали эту теорию. Возможно, вы сталкивались с теорией множеств, когда проходили в школе диаграмму Венна. Диаграмму Венна включили в программу изучения множеств, так как она хорошо иллюстрирует отношения подмножеств.
Мы выяснили, что теория множеств не должна никого пугать. Теперь пришло время разобраться, что это за теория на самом деле. Множество — математическая концепция. Теорией множеств описывают отношения множеств.
Множество — ни что иное, как неупорядоченная коллекция, в которой нет дублирующихся элементов.
В этом определении есть три важных слова: «неупорядоченная», «дублирующихся» и «элементов». Эти слова точно передают суть и устройство множества. Если мы это запомним, то будем знать основную информацию о том, как работает эта структура данных.
Нужно понять, почему это важно. Для начала давайте посмотрим на множества в действии. Как сказано выше, отношения множеств удачно иллюстрирует диаграмма Венна. Давайте взглянем на два множества: книги, которые есть у человека дома, и книги, которые этот человек прочитал.
Если вы знакомы с диаграммой Венна, то понимаете, что в центре в зелёном круге находятся книги, которыми человек владеет, и которые он прочитал. Здесь множества пересекаются. Также вы понимаете, что два множества — прочитанные человеком книги и книги, которые есть у человека — существуют внутри другого множества. Это все существующие в мире книги.
Диаграмма Венна — хорошая база для понимания теории множеств, так как с её помощью легче понять более сложные вещи. Допустим, вы хотите представить два множества книг в какой-то структуре данных. Вы уже знаете, что книги надо разделить на два множества: которые человек прочитал и которые есть у него дома. Для удобства назовём первое множество Set X, а второе Set Y. Эти множества после реконфигурации в структуры данных можно представить с помощью диаграммы Венна.
Можно заметить, что множества Set X и Set Y стали похожи на объекты или хэши: элементы внутри них не имеют индексов или других элементов, позволяющих их упорядочить. В них также нет повторяющихся элементов, что делает эти структуры данных множествами. Как вы уже знаете, множество — это коллекция неупорядоченных элементов, которые не повторяются.
Начните изучать разработку с бесплатного курса «Основы современной вёрстки». Вы научитесь создавать статические веб-страницы, стилизовать элементы, использовать редакторы кода с полезными расширениями. В конце курса вы опубликуете свой первый сайт на GitHub Pages.
Об операциях с множествами без боли
Какие возможности открывает представление множеств в формате структур данных? С ними теперь можно выполнять разные операции. Две самые важные операции, которые выполняются над множествами — это пересечение и объединение.
Пересечение множеств часто записывается с помощью такой нотации: X ∩ Y. Пересечение определяет, где два множества пересекаются. Другими словами, эта операция возвращает все элементы, которые входят в два множества. В нашем примере пересечение Set X и Set Y возвращает все книги, которые человек читал и которые есть у него дома. Хороший ключ к пониманию пересечения — ключевое слово «и». Мы получаем книги, которые человек читал и которые есть у него дома. Несмотря на то, что полученные с помощью пересечения книги существуют в двух множествах, мы не повторяем их, так как в множестве могут быть только уникальные элементы.
Объединение двух множеств обозначается так: X ∪ Y. Объединение возвращает общность двух множеств или объединённое множество. Иными словами, с помощью объединения множеств можно получить новое множество элементов, которые существуют хотя бы в одном исходном множестве. В нашем случае объединение вернёт все книги, которые человек читал, а также все книги, которые есть у него дома. Обратите внимание, если книга входит одновременно в Set X и Set Y, она не может дублироваться в новом множестве после объединения, так как в множества входят только уникальные элементы.
С помощью диаграммы Венна пересечение и объединение можно представить так:
Теперь давайте рассмотрим более сложные вещи. Объединение и пересечение — важные операции над множествами, но это только азы теории. Нам надо познакомиться с другими операциями, чтобы решать более серьёзные задачи. Важно понимать разность множеств и относительные дополнения множеств. Ниже мы разберём, почему это важные операции, но сначала нужно понять, как они работают.
Как понятно из названия, разность множеств определяет разницу между множествами. Иными словами, мы определяем, какие элементы останутся в множестве X, если удалить из него все элементы, которые содержатся в множестве Y. Это действие можно обозначить так: X — Y. В примере на иллюстрации ниже разница между множеством X и множеством Y — это элементы, которые существуют в Set X, но не существуют в Set Y. Они обозначены буквами C, Z и W.
Относительное дополнение — противоположность разности множеств. Например, относительное дополнение Y по сравнению с X возвращает все элементы множества Y, которые не входят в множество X. Относительное дополнение можно обозначить так: X \ Y. Относительное дополнение X \ Y фактически возвращает такой же набор элементов, как разность Y — X. В нашем примере множество Y меньше множества X. Единственный элемент, который входит в Set Y, но не входит в Set X — число 2.
По сути, мы просто вычитаем множество X из множества Y и отвечаем на вопрос: что существует в Y, чего нет в X?
Вы могли заметить, что в части примеров мы имеем дело со строками, в другой части в качестве элементов выступают буквы и числа. Здесь надо подчеркнуть важный момент: множество может включать любой тип элементов или объектов. Вы можете рассматривать множества как хэши: они включают любые сущности, если те встречаются во множестве только один раз.
Теперь давайте рассмотрим ещё одну операцию, она самая сложная из всех. Но не пугайтесь, с ней тоже можно разобраться.
В некоторых случаях требуется найти противоположность пересечению множеств. Иными словами, речь идёт о книгах, которые есть у человека, и книгах, которые он прочитал, но которые не входят одновременно в оба множества. Как назвать это подмножество? И как найти его?
Правильное название для этого кейса — симметрическая разность множеств. Также употребляют термины «дизъюнктивное объединение» и «несвязное объединение». Симметрическая разность возвращает все элементы, которые входят в одно из множеств, но не входят в пересечение этих множеств. Пример на иллюстрации поможет разобраться с дизъюнктивным объединением.
В примере выше симметрическая разность похожа на поиск относительного дополнения множества X и множества Y. Если подходить к этому с позиции математики, поиск симметричной разницы — то же самое, что и объединение относительных дополнений множества X и множества Y. Эту операцию можно записать так: X △ Y= (X ∖ Y) ∪ (Y ∖ X).
Но не дайте сбить себя с толку!
Всё, что нужно для поиска симметрической разности — найти элементы, которые есть в множестве X, но отсутствуют в множестве Y, и какие элементы есть в множестве Y, но отсутствуют в множестве X. Иными словами, надо найти уникальные элементы в каждом множестве.
В примере выше числа 1, 2 и 3 входят в множества X и Y одновременно. А буквы A, B, C, X, Y, Z входят только в множества X или Y. Поэтому они представляют симметрическую разность множеств X и Y.
Мы рассмотрели теоретические вопросы. Теперь можно посмотреть, как теория множеств работает на практике.
Множества вокруг нас
К этому моменту вы наверняка задумались, зачем надо изучать теорию множеств. Это хороший вопрос, и пришло время ответить на него.
Уже догадались? Множества повсюду. Это структуры данных, которые мы можем использовать при работе с разными языками программирования, например, Python, Java, Ruby, JavaScript и так далее. Если вы знакомы с этими или другими языками программирования, то уже вспомнили методы, которые позволяют работать с множествами.
Вот пример на JavaScript.
Очевидно, что имена методов могут меняться в зависимости от языка. Например, метод has из примера выше в Ruby называется include?, но эти методы работают практически одинаково. А в Python при работе с множествами можно использовать методы intersection, union и symmetric_difference.
Но в чём именно польза множеств? Понятно, что с ними можно работать в разных языках программирования, но зачем это нужно на практике?
Один из моментов — множества могут сэкономить вам много времени. Помните все эти сложные операции — intersection, union, difference? Уже догадались? Продолжительность выполнения этих операций зависит от размера множеств. Это связано с тем, что для выполнения операций нам надо обойти все элементы множества. Обычно даже гигантские множества можно обойти достаточно быстро.
Но как насчёт основных операций? Как насчёт добавления элементов в одно из множеств, удаления элементов, поиска конкретного элемента в множестве? Все эти операции выполняются за константное время или 0(1). Это очень мощный инструмент, и это значит, что множества могут быть даже более удобной структурой данных, чем словарь или хэш.
Но подождите, почему все операции с множествами выполняются так быстро? Как это возможно? Как оказалось, под капотом множества представляют собой хэши. Теперь вся информация собирается воедино. С хэш-таблицами знакомо большинство программистов, но почему с их помощью так удобно реализовывать множества?
Это возможно благодаря нескольким факторам. Первый: в хэш-таблицах каждый элемент всегда имеет уникальный индекс. Это очень хорошо с точки зрения реализации множеств, так как множества могут включать только уникальные элементы. Второй фактор: в хэш-таблицах порядок элементов не имеет значения. В множествах порядок элементов тоже не имеет значения. Наконец, хэш-таблицы обеспечивют константное время доступа 0(1). Это идеально для выполнения базовых операций с множествами.
Заключение
Теория множеств используется в разных областях computer science. Это важная для программистов концепция, понимание которой помогает разработчикам эффективно работать с данными.
Адаптированный перевод статьи Set Theory: the Method To Database Madness by Vaidehi Joshi.
Никогда не останавливайтесь: В программировании говорят, что нужно постоянно учиться даже для того, чтобы просто находиться на месте. Развивайтесь с нами — на Хекслете есть сотни курсов по разработке на разных языках и технологиях.
С нуля до разработчика. Возвращаем деньги, если не удалось найти работу.
Данные типа множество позволяют хранить ограниченное число значений определённого типа без определённого порядка. Повторение значений, как правило, недопустимо. За исключением того, что множество в программировании конечно, оно в общем соответствует концепции математического множества. Для этого типа в языках программирования обычно предусмотрены стандартные операции над множествами.
В зависимости от идеологии, разные языки программирования рассматривают множество как простой или сложный тип данных.
Связанные понятия
Упоминания в литературе
Связанные понятия (продолжение)
Из-за путаницы с терминологией словом «оператор» в программировании нередко обозначают операцию (англ. operator), см. Операция (программирование).Инстру́кция или опера́тор (англ. statement) — наименьшая автономная часть языка программирования; команда или набор команд. Программа обычно представляет собой последовательность инструкций.
В информатике, спи́сок (англ. list) — это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией математического понятия конечной последовательности.
В языках программирования объявле́ние (англ. declaration) включает в себя указание идентификатора, типа, а также других аспектов элементов языка, например, переменных и функций. Объявление используется, чтобы уведомить компилятор о существовании элемента; это весьма важно для многих языков (например, таких как Си), требующих объявления переменных перед их использованием.
По одной из классификаций, языки программирования неформально делятся на сильно и слабо типизированные (англ. strongly and weakly typed), то есть обладающие сильной или слабой системой типов. Эти термины не являются однозначно трактуемыми, и чаще всего используются для указания на достоинства и недостатки конкретного языка. Существуют более конкретные понятия, которые и приводят к называнию тех или иных систем типов «сильными» или «слабыми».
Сопрограммы (англ. coroutines) — методика связи программных модулей друг с другом по принципу кооперативной многозадачности: модуль приостанавливается в определённой точке, сохраняя полное состояние (включая стек вызовов и счётчик команд), и передаёт управление другому. Тот, в свою очередь, выполняет задачу и передаёт управление обратно, сохраняя свои стек и счётчик.
В информатике и теории автоматов состояние цифровой логической схемы или компьютерной программы является техническим термином для всей хранимой информации, к которой схема или программа в данный момент времени имеет доступ. Вывод данных цифровой схемы или компьютерной программы в любой момент времени полностью определяется его текущими входными данными и его состоянием.
Просто о списках, словарях и множествах или ТОП 5 структур данных
Привет. Ей! Не говорите “Да блин! Я знаю, чем отличается список от вектора, мне не нужна эта статья”. Прошу, загляните под кат и освежите свои знания. Я надеюсь, однако, что вы сможете почерпнуть из этой статьи намного больше и, некоторые, возможно, наконец-то разберутся, почему существует так много типов данных для коллекций объектов.
Введение
Так уж сложилось, что в программировании коллекции представляет много, нет ОЧЕНЬ МНОГО различных сущностей — списки, массивы, вектора, множества, стеки, очереди, ассоциативные массивы и у большинства из этих структур данных есть еще по несколько подвидов.
Должны же быть причины, чтобы для простого представления какой-либо совокупности объектов существовало настолько много различных вариаций.
Должны же быть отличия между списком и массивом? Между ассоциативным массивом и хеш-таблицей?
Коллекция
Для начала — самое скучное (да, я люблю такое). Что такое коллекция вообще?
Коллекция — структура данных (тип, класс, даже лучше сказать интерфейс), которая создана, чтобы содержать в себе некоторое количество объектов (в зависимости от языка и терминологии они должны быть одного типа или могут быть разных типов).
Различные типы коллекций могут быть статическими или динамическими, т.е. изменять свой размер или оставаться постоянными, могут быть упорядоченными (точнее учитывающими порядок элементов) и неупорядоченными (соответственно не учитывающими).
Над коллекциями предусмотрено несколько стандартных операций (сейчас мы поговорим о мутабельных, т.е. изменяемых коллекциях), таких как: получение размера, добавление элемента, удаление элемента, поиск (есть какой-либо элемент в коллекции или нет), их очень много.
Ладно, свой негласный долг я выполнил, теперь поехали!
1 Вектор (Vector, Array)
А вы чего ждали?
Вектор (он же одномерный массив) — упорядоченный набор элементов с произвольным доступом по числовому индексу. Что для нас важно в этом определении? Да ничего. Шучу, на самом деле нам важно почти каждое слово:
Доступ к элементам производится по числовому индексу (обычно начиная с 0-го индекса, хотя есть и исключения), обычно доступ к элементу коллекции по индексу записывается как myFavoriteCats[i] или blackKitties[5]. Причем для обозначения этого самого числа — индекса используют букву i.
А когда одной буквы не хватает приплетают сюда j и k.
Итак, далее мы понимаем, что доступ произвольный — значит мы можем обращаться к элементам под индексами 0, 42, 2014 и вобщем-то ожидаем, что операция будет сложности O(1), т.е. константной и независимо от того какой из элементов мы запросим он нам со скоростью света тут же вернется.
Далее — вектор — упорядоченная коллекция, что собственно понятно — у нас есть такие понятия как первый, последний элемент, для каждого конкретно взятого элемента мы также можем назвать предыдущий и следующий.
Релизация
Обычно вектор (как низкоуровневая структура) будет представлять из себя дескриптор, содержащий различную информацию, неотделимую от самой структуры (разумнее всего держать там только размер вектора) и указатель на первый элемент.
Такая реализация позволит за константное время получить доступ к произвольному элементу вектора по его индексу, а также позволит выполнять копирование, конкатенацию и другие простые операции на низком уровне.
И действительно, получить доступ к определенному элементу очень просто — прибавляем к указателю на первый элемент индекс (с некоторыми поправками на размер типа данных) и получаем указатель на нужный элемент! Осталось разыменовать и у нас в переменной нужная кошечка!
Ладно, вектор — классная структура, но и у него есть недостатки (а у кого их нет?!), например нельзя просто так взять и добавить в вектор новый элемент! Особенно втиснуть его в середину. Нельзя также сказать, что кошки с номерами 0, 1 и 4 у нас есть, а с номерами 2 и 3 — нет (раньше они были, но оказалось, что это собаки).
Можно представить себе вектор, как книжную полку с отделениями, в каждом из которых помещается ровно одна книга. Чтобы засунуть новый роман Донцовой между 10-ым и 11-ым томом Большой Совецкой Энциклопедии нужно сильно постараться и переложить все тома с 11-го по 65-ый тома (можно схитрить и поставить 11-ый том в конец, но я вам этого не говорил, да и мы в таком случае потеряем упорядоченность).
В моей памяти все именно так
Применение
В нашем случае вектор бы идеально подошел для топ-10 самых милых котят, т.к. добавлять и удалять элементы не нужно (только изменять), пропусков между 1-ым и 5-ым местом быть не должно, да и удобно обращаться по номеру.
Ладно. В любом случае вектор классный, мы просто посмотрим какие есть еще коллекции.
2 Список (List)
Первый том
Ух! Список задач на сегодня, список покупок в магазине. Список гостей на свадьбу… Так. Ближе к делу.
Мы уже знаем, что элементы вектора лежат акуратненько друг за другом, красиво и ровно. Это дает нам как преимущества так и недостатки.
Список в этом плане полностью противоположная вещь — его элементы могут быть разбросаны по памяти как угодно! Из-за этого мы теряем возможность быстро получить элемент по индексу, а также не можем быстро скопировать весь список, но получаем довольно приятную штуку — мы можем вставлять элементы за константное время в любое место! По слухам удаляются элементы из списка тоже за O(1).
Реализация
Хм. А как с формальным определением?
Список — упорядоченный набор элементов, для каждого из которых хранится указатель на следующий (или для двусвязного списка и на следующий и на предыдущий) элементы списка.
Для последнего элемента списка мы храним нулевой указатель (на диаграммах я буду использовать указатель на нулевую кошку (Null Cat), не пугайтесь).
Внимание! В каноничной реализации списка, для того, чтобы получить размер списка, необходимо обойти весь список — дойдя до нулевого указателя (линейное время — сложность O(n)) и хотя в некоторых реализациях размер кешируется в дескрипторе списка (или в первом элементе), не стоит на это полагаться.
Если бы я мог, я бы один элемент списка разместил на северном полюсе, а другой где-нибудь в окресностях Бетельгейзе
Применение
Список бы подошел для (внимание!) списка бездомных котят, отсортированных по возрасту (по возрастанию). Нам как-раз нужно часто добавлять и удалять элементы из списка (вы не подумайте ничего такого — котят забирают), да и чаще понадобятся первые элементы списка — я бы взял себе маленького пушистого котенка, а не 8-ми-летнего манула.
Ладно. Списки это вроде простая структура. Что есть еще?
3 Множество (Set)
Это Сет
Похожее понятие есть в математике, а точнее в теории множеств. Множество отличается и от вектора и от списка, хотя их реализация может быть похожа.
Множество — неупорядоченный набор элементов, без повторов. Ух. И все? Ни тебе произвольного доступа, ничего! Зачем такое нужно?
Как мы знаем в векторе можно быстро получить элемент по индексу, в списке можно быстро добавить или удалить элемент, а что с множеством?
В множестве можно быстро проверить, есть какой-либо элемент внутри, или его нет. Скажем если бы я хотел узнать, находится ли конкретная кошка в моем списке любимых, то и для списка и для вектора мне пришлось бы перебрать (в худжем случае) все элементы!
Реализация
В множестве, т.к. оно неупорядочено можно сортировать элементы при добавлении и в случае чего устроить бинарный поиск. Хм. Вот ведь парадокс, коллекция неупорядоченная, а внутри все будет по-порядку. Тут важно понять, что если вы добавите новый элемент в множество, не факт, что он пойдет в конец.
На самом деле, работая с множеством вообще нельзя полагаться на какой-либо порядок элементов, он может быть любым — именно поэтому множество и неупорядоченная коллекция.
Стоит отметить, что множество может быть реализовано множеством различных способов, например можно использовать хеширование, для еще более быстрого поиска элементов, поэтому подробно реализацию я рассматривать не буду. Скажу лишь, что можно схитрить и использовать наши знания по спискам.
Вообще есть еще упорядоченные множества, множества с повторами (мультимножество), и вероятно должно быть упорядоченное мультимножество.
Теория множеств дается проще, если брать множество котят
Применение
Множество идеально подойдет для списка любимых котят, потому что их множество. Ха! Шучу.
Но оно действительно подойдет, потому-что такую коллекцию не нужно сортировать (упорядоченность не важна) и мы легко сможем проверить, находится ли какой-нибудь конкретный кот в этом множестве (скажем у меня 100 котят и любимых я кормлю креветками).
Ну ладно. Множества тоже хороши, но неужели есть что-то еще?
4 Словарь (Associative Array, Map, Dictionary)
Признайтесь, это лучше, чем просто словарь
Словарь (он же ассоциативный массив) — это тот-же вектор, но с небольшими отличиями. В качестве индекса (который в словаре будет называться ключ) могут выступать не только числа, но и любые другие типы данных (даже другие коллекции!). Также допустимы пропуски, если мы все-таки будем использовать в качестве ключа целое число, например у нас может быть элемент связанный с ключем 5, но при этом отсутствовать элемент связанный с ключем 4.
Что все это значит на практике? Всего-лишь, то, что в квадратных скобках для ображения к элементу по “индексу” мы можем указывать произвольный тип, например allMyCats[“Murka”].
Реализация
Невооруженным видно, что можно просто завести массив (или список) пар (Ключ, Значение) и добавить специальную функцию, которая будет пробегать по этому списку и возвращать определенное значение по связанному с ним ключу.
Мы также не можем сказать какая пара первая, какая последняя и что раньше “Murka” или “Borka”, поэтому словарь считается неупорядоченной структурой.
Опять-же с каждым ключем может быть связано лишь одно значение, поэтому для приведенного примера с именами кошек словарь в чистом виде подходит слабо.
Реализация, как и в случае со множеством, может быть совершенно различной, можно упорядочить пары по ключу и использовать для получения элемента бинарный поиск (в таком случае элементы должны быть упорядочеваемыми). Опять-же можно реализовать словарь с помощью хеширования ключа, что довольно часто используется со строками.
Применение
Самый правдоподобный и грамотный способ — использовать словарь вместе со списком, где ключем словаря будет строка — имя кошки, а значением — список кошек с таким именем. Это позволит быстро найти всех кошек по имени Мурка и выбрать из них ту, которая в данный момент нужна.
Примерно так выглядит в памяти std::map >
И у меня для вас новость — типы коллекций закончились. Ну все. Вообще больше нет. Совсем.
5 Стек (Stack)
Еще один кот и будет Stack Overflow
Ха! Я вас обманул (всмысле пошутил)! Есть еще пара структур данных, которые представляют коллекции.
Итак стек — коллекция с необычным доступом, точнее с необычными правилами относительно того, как могут быть добавлены и удалены элементы.
Все просто — добавляемый элемент, называемый “последним”, первый выбывает из из стека.
Стек очень нужен и полезен в программировании. Например с помощью стека осуществляется вложенный вызов процедур — в стек сохраняются адрес возврата и аргументы вызванной функции.
Реализация
В высокоуровневой реализации ничего особенно интересного нет — указатель на список и элементы добавляются в начало этого списка, и удаляются с него-же.
В низкоуровневой реализации (точнее то, как он реализован в современных архитектурах) есть интересные моменты.
Стек там является небольшим зарезервированным участком памяти и совместно с ним хранится два указателя — на начало стека (где лежит первый доавленный элемент) и конец стека — где лежит последний добавленный.
Если в стек поместить слишком много данных программа завершится со всем знакомой ошибкой — Stack Overflow, это значит, что указатель на конец стека превысил верхний допустимый предел.
Также может случиться обратная ситуация (Stack Underflow), если попытаться забрать из стека больше чем в нем есть, но в высокоуровневых языках она не встречается (понятно почему — нам не дают напрямую работать со стеком).
Если кому интересно как это все работает — изучение ассемблера для какой-нибудь популярной архитектуры, вроде i386, может вам помочь.
Применение
Можно было-бы описать в этом месте стек из бедных котят высотой с гору, но на самом деле в высокоуровневых языках стек редко необходим, часто хватает рекурсии, которая использует стек неявно. Я не стал прикладывать надуманный пример (и не смог придумать нормальный, простите), поэтому переходим к следующему пункту.
Разное
На самом деле есть еще куча коллекций, таких как очередь, двусторонняя очередь (дек), двусвязанный список, кольцевое множество, очереди с приоритетом.
Есть деревья (да их целый лес!) и графы.
Есть вероятностные структуры данных, такие как вероятностное множество и список с пропусками.
Я очень хочу про все это написать, но времени и места на хабре не всегда мало.
Однако есть множество (или вектор) вещей, относящихся к теме, которые я хотел бы упомянуть хоть вскользь, да просит меня любопытный читатель и пойдет читать умную книгу.
Строки
В первую очередь то, как реализованы строки в некоторых языках может показаться странным. Самое простое и эффективное решение это наверное решение C — строка это набор символов, с нулевым символом в конце, что позволяет обходиться без дескриптора.
В C++ std::string уже больше походит на вектор.
Ну а в старом паскале дескриптор (точнее всего-лишь длина) хранится в нулевом элементе массива.
В Haskell String — это список символов ([Char]), из чего вытекает, что получение длины строки имеет сложность O(n). Зато их очень удобно оббегать рекурсивно.
В общем случае, строка — это упорядоченный набор символов и не более. Какой именно тип коллекции будет использован — не важно (ну я бы не советовал использовать множество, ха!).
Очередь (Queue)
Очередь очень похожа на стек и в тоже время является его противоположностью — первым мы получим обратно не тот элемент, что мы добавили последним, а тот, что “стоит в очереди” дольше всех. Очередь очень удобная структура, но несмотря, на то, что принцип ее работы схож со стеком, в эффективной реализации есть небольшое отличие.
Для стека мы могли схитрить и выделить приемлемый по размеру участок памяти, в случае чего его расширяя, потому-что стек то уменьшается, то увеличивается, т.к. элементы и добавляются и удаляются “с одного конца”. Если же мы представим работу очереди, то она будет “ползти в памяти” — начало будет постоянно сдвигаться вверх, поэтому трюк, который применим для стека, будет работать хуже и тут уже намного лучше будет использовать двусвязный список (и не забудьте хранить указатели на первый и последний элементы).
Еще можете попробовать реализвать очередь на двух стеках, но это тоже менее эффективно.
Также есть дек (двусторонняя очередь — deque). В ней можно добавлять элементы как в конец, так и в начало. И забирать их тоже и с конца и с начала.
Заключение
Ух. Я начинаю повторяться
Я совсем не упомянул, про комбинирование различных коллекций, благодаря которым образуются матрицы, таблицы. Также я не затронул деревья, кольцевое множество, почти ничего не написал про очереди, очень мало информации по хешированию (я таки отделался парой слов от этой темы) и другим методам оптимизации.
Однако я думаю статья исполнит свою роль — просто и понятно изложит основы структур данных для читателей разной степени подготовленности. И я буду рад продолжить и осветить множество (или очередь, ха!) других тем в таком-же ключе.
Спасибо тем, кто смог дочитать аж до этих строк (как они это выдержали?).
Типы данных
