1 что такое коллекция dictionary

Под капотом у Dictionary и ConcurrentDictionary

Итак, поехали.

Если вы уже знакомы с самим Dictionary, то можете пропустить следующий раздел.

Dictionary представляет собой реализацию стандартной Hashtable.
Здесь интересны следующие функции:

Инициализация

Инициализация происходит либо при создании (если передана начальный размер коллекции), либо при добавлении первого элемента, причем в качестве размера будет выбрано ближайшее простое число (3). При этом создаются 2 внутренние коллекции — int[] buckets и Entry[] entries. Первая будет содержать индексы элементов во второй коллекции, а она, в свою очередь, — сами элементы в таком виде:

Добавление элементов

При добавлении элемента вычисляется хэшкод его ключа и затем — индекс корзины в которую он будет добавлен по модулю от величины коллекции:

Выглядеть это будет примерно так:

Затем проверяется нет ли уже такого ключа в коллекции, если есть — то операция Add выбросит исключение, а присваивание по индексу просто заменит элемент на новый. Если достигнут максимальный размер словаря, то происходит расширение (выбирается новый размер ближайшим простым числом).
Сложность оперции соответственно — O(n).

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

Таким образом получаем однонаправленный связный список. Данный механизм разрешения коллизий называется chaining. Если при добавлении элемента число коллизий велико (больше 100 в текущей версии), то при расширении коллекции происходит операция перехэширования, перед выполнением которой случайным образом выбирается новый генератор хэшкодов.
Сложность добавления O(1) или O(n) в случае коллизии.

Удаление элементов

При удалении элементов мы затираем его содержимое значениями по умолчанию, меняем указатели next других элементов при неоходимости и сохраняем индекс этого элемента во внутреннее поле freeList, а старое значение — в поле next. Таким образом, при добавлении нового элемента мы можем повторно использовать такие свободные ячейки:

Сложность снова O(1) или O(n) в случае коллизии.

Другое

Так же стоит отметить 2 момента:
1) При очистке словаря, его внутренний размер не изменяется. То есть, потенциально, вы просто тратите место.
2) GetEnumerator просто возвращает итератор по коллекции entires (сложность O(1)). Если вы только добавляли элементы — они вернутся в том же порядке. Однако если вы удаляли элементы и добавляли новые — порядок соответственно изменится, поэтому на него полагаться не стоит (тем более, что в будущих версиях фреймворка это может измениться).

Так и что же с ConcurrentDictionary?

Казалось бы, есть 2 решения в лоб для обеспечения потокобезопасности — обернуть все обращения к словарю в блокировки или обернуть все его методы в них же. Однако, по понятным причинам, такое решение будет медленным — задержки, добавляемые lock, да и ограничение на 1 поток, который мог бы работать с коллекцией не добавляют быстродействия.

В Microsoft пошли более оптимальным путем и Dictionary притерпел некоторые изменения. Так, благодаря внутренней структуре словаря и его корзин, блокировка осуществляется по ним, с помощью метода

В то же время обычный словарь не смог бы работать с этой схемой, потому что все корзины используют один и тот же массив entries, поэтому корзины стали представлять собой обычный single linked list: volatile Entry[] m_buckets (поле объявлено как volitale, чтобы обеспечить неблокирующую синхронизацию в ситуации когда один поток пытается выполнить какую-то операцию, а другой в этот момент изменяет размер коллекции).

В итоге корзины стали выглядеть вот так:

lockNo — это индекс в новом массиве, который содержит объекты синхронизации — object[] m_locks. Его использование позволяет разным потокам изменять разные корзины в одно и то же время. Размер этой коллекции зависит от параметра ConcurrencyLevel который можно задать через конструктор. Он определяет примерное число потоков которые будут одновременное работать с коллекцией (по умолчанию это число_процессоров * 4). Чем выше это значение, тем проще будут происходить операции записи, но так же станут гораздо дороже операции, которые требуют полной блокировки всей коллекции (Resize, ToArray, Count, IsEmpty, Keys, Values, CopyTo, Clear). Также этот параметр определяет сколько элементов коллекции приходится на один lock (как отношение числа корзин к размеру этой коллекции) и когда элементов становится больше, чем надо — коллекция расширяется, потому что в противном случае поиск элемента требует не O(1), а уже O(n) за счет обхода связных списков. Чтобы немного снизить число первоначальных расширений коллекции, начальный размер словаря уже не 3, а 31.

Все операции приобрели вид:

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

Впрочем, для некоторых операций блокировка не нужна в принципе — это TryGetValue, GetEnumerator, ContainsKey и индексация. Почему? Потому что все изменения размера корзин видны за счет того что поле volatile, любые добавления или изменения элементов происходят путем создания нового элемента и замены им старого, а удаления происходят просто заменой указателя на следующий узел.

Другое

лучше использовать dictionary.Select(x => x.Value).ToArray(), чем dictionary.Values.ToArray()

И это не совсем верно — вместо «лучше» тут должно быть «быстрее» — за счет отсутствия блокировок, но надо принять во внимание, что данные подходы могут вернуть разные данные.

Источник

Python: коллекции, часть 1/4: классификация, общие подходы и методы, конвертация

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

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

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

Для кого: для изучающих Python и уже имеющих начальное представление о коллекциях и работе с ними, желающих систематизировать и углубить свои знания, сложить их в целостную картину.

Будем рассматривать стандартные встроенные коллекционные типы данных в Python: список (list), кортеж (tuple), строку (string), множества (set, frozenset), словарь (dict). Коллекции из модуля collections рассматриваться не будут, хотя многое из статьи должно быть применимым и при работе с ними.

ОГЛАВЛЕНИЕ:

1. Классификация коллекций

Пояснения терминологии:

Индексированность – каждый элемент коллекции имеет свой порядковый номер — индекс. Это позволяет обращаться к элементу по его порядковому индексу, проводить слайсинг («нарезку») — брать часть коллекции выбирая исходя из их индекса. Детально эти вопросы будут рассмотрены в дальнейшем в отдельной статье.

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

Изменяемость коллекции — позволяет добавлять в коллекцию новых членов или удалять их после создания коллекции.

Примечание для словаря (dict):

UPD: Важное замечание от sakutylev: Для того, чтобы объект мог быть ключом словаря, он должен быть хешируем. У кортежа, возможен случай, когда его элемент является не хешируемым объектом, и соответственно сам кортеж тогда тоже не является хешируемым и не может выступать ключом словаря.

2 Общие подходы к работе с любой коллекцией

Разобравшись в классификацией, рассмотрим что можно делать с любой стандартной коллекцией независимо от её типа (в примерах список и словарь, но это работает и для всех остальных рассматриваемых стандартных типов коллекций):

2.1 Печать элементов коллекции с помощью функции print()

2.2 Подсчёт количества членов коллекции с помощью функции len()

2.3 Проверка принадлежности элемента данной коллекции c помощью оператора in

x in s — вернет True, если элемент входит в коллекцию s и False — если не входит
Есть и вариант проверки не принадлежности: x not in s, где есть по сути, просто добавляется отрицание перед булевым значением предыдущего выражения.

Для словаря возможны варианты, понятные из кода ниже:

Можно ли проверять пары? Можно!

Для строки можно искать не только один символ, но и подстроку:

2.4 Обход всех элементов коллекции в цикле for in

В данном случае, в цикле будут последовательно перебираться элементы коллекции, пока не будут перебраны все из них.

Обратите внимание на следующие моменты:

Но чаще всего нужны пары ключ(key) — значение (value).

Чтобы этого избежать подобных побочных эффектов, можно, например, итерировать копию коллекции:

2.5 Функции min(), max(), sum()

3 Общие методы для части коллекций

Объяснение работы методов и примеры:

Особые методы сравнения множеств (set, frozenset)

При равенстве множеств они одновременно и подмножество и надмножество друг для друга

4 Конвертация одного типа коллекции в другой

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

Обратите внимание, что при преобразовании одной коллекции в другую возможна потеря данны:

Дополнительные детали:

Это ограничение можно обойти, создав словарь комбинируя ключи со значениями с использованием zip():

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

Источник

C#. Урок 10. Коллекции

Коллекции являются одним из наиболее часто используемых инструментов в разработке программного обеспечения. В этом уроке мы познакомимся с пространством имен System.Collections.Generic, коллекциями List, Dictionary и типом Tuple.

Исходный код примеров из этой статьи можете скачать из нашего github-репозитория.

Коллекции

Самым примитивным способом хранения объектов в C# является использование массивов. Одной из основных проблем, с которой столкнется разработчик следуя такому подходу, является то, что массивы не предоставляют инструментов для динамического изменения размера. В языке C# есть два пространства имен для работы со структурами данных:

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

Коллекции в языке C#. Пространство имен System.Collections.Generic

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

Познакомимся поближе с несколькими классами из приведенной таблицы.

Класс List

Создание объекта класса List

Можно создать пустой список и добавить в него элементы позже, с помощью метода Add() :

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

Работа с объектами List

Свойства класса List

Методы класса List

Код метода ListToString :

Создадим список игроков и выполним с ним ряд действий:

Класс Dictionary

Создание объекта класса Dictionary

Словарь с набором элементов:

Работа с объектами Dictionary

Свойства класса Dictionary

Методы класса Dictionary

Кортежи Tuple и ValueTuple

Относительно недавним нововведением в языке C# (начиная с C# 7) являются кортежи. Кортежем называют структуру данных типа Tuple или ValueTuple (чуть ниже мы рассмотрим различия между ними), которые позволяют группировать объекты разных типов друг с другом. С практической точки зрения они являются удобным способом возврата из метода нескольких значений – это наиболее частый вариант использования кортежей.

Различия между Tuple и ValueTuple приведены в таблице ниже.

Создание кортежей

Рассмотрим несколько вариантов создания кортежей.

Создание кортежа без явного и с явным указанием имен полей:

При этом для доступа к элементам кортежа в первом варианте используются свойства Item с числом, указывающем на порядок элемента, во втором – заданные пользователем имена:

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

При этом возможность обращаться через свойства Item1 и Item2 для созданных выше переменных остается:

Работа с кортежами

Кортежи можно присваивать друг другу, при этом необходимо, чтобы соблюдались следующие условия:

Операцию присваивания можно использовать для деструкции кортежа.

Исходный код примеров из этой статьи можете скачать из нашего github-репозитория.

Источник

Просто о списках, словарях и множествах или ТОП 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). В ней можно добавлять элементы как в конец, так и в начало. И забирать их тоже и с конца и с начала.

Заключение

Ух. Я начинаю повторяться

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

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

Спасибо тем, кто смог дочитать аж до этих строк (как они это выдержали?).

Источник