Какая структура данных позволит организовать работу с данными как со стеком

Основные структуры данных. Матчасть. Азы

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

Еще в далеком 1976 швейцарский ученый Никлаус Вирт написал книгу Алгоритмы + структуры данных = программы.

40+ лет спустя это уравнение все еще верно. И если вы самоучка и надолго в программировании пробегитесь по статье, можно по диагонали. Можно код кофе.

В статье так же будут вопросы, которое вы можете услышать на интервью.

Что такое структура данных?

Структура данных — это контейнер, который хранит данные в определенном макете. Этот «макет» позволяет структуре данных быть эффективной в некоторых операциях и неэффективной в других.

Какие бывают?

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

Нелинейные, если обход узлов нелинейный, а данные не последовательны. Пример: граф и деревья.

Основные структуры данных.

1. Массивы
2. Стеки
3. Очереди
4. Связанные списки
5. Графы
6. Деревья
7. Префиксные деревья
8. Хэш таблицы

Массивы

Массив — это самая простая и широко используемая структура данных. Другие структуры данных, такие как стеки и очереди, являются производными от массивов.

Изображение простого массива размера 4, содержащего элементы (1, 2, 3 и 4).

Каждому элементу данных присваивается положительное числовое значение (индекс), который соответствует позиции элемента в массиве. Большинство языков определяют начальный индекс массива как 0.

Бывают

Одномерные, как показано выше.
Многомерные, массивы внутри массивов.

Основные операции

• Insert-вставляет элемент по заданному индексу
• Get-возвращает элемент по заданному индексу
• Delete-удаление элемента по заданному индексу
• Size-получить общее количество элементов в массиве

Вопросы

• Найти второй минимальный элемент массива
• Первые неповторяющиеся целые числа в массиве
• Объединить два отсортированных массива
• Изменение порядка положительных и отрицательных значений в массиве

Стеки

Стек — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

Это не массивы. Это очередь. Придумал Алан Тюринг.

Примером стека может быть куча книг, расположенных в вертикальном порядке. Для того, чтобы получить книгу, которая где-то посередине, вам нужно будет удалить все книги, размещенные на ней. Так работает метод LIFO (Last In First Out). Функция «Отменить» в приложениях работает по LIFO.

Изображение стека, в три элемента (1, 2 и 3), где 3 находится наверху и будет удален первым.

Основные операции

• Push-вставляет элемент сверху
• Pop-возвращает верхний элемент после удаления из стека
• isEmpty-возвращает true, если стек пуст
• Top-возвращает верхний элемент без удаления из стека

Вопросы

• Реализовать очередь с помощью стека
• Сортировка значений в стеке
• Реализация двух стеков в массиве
• Реверс строки с помощью стека

Очереди

Подобно стекам, очередь — хранит элемент последовательным образом. Существенное отличие от стека – использование FIFO (First in First Out) вместо LIFO.

Пример очереди – очередь людей. Последний занял последним и будешь, а первый первым ее и покинет.

Изображение очереди, в четыре элемента (1, 2, 3 и 4), где 1 находится наверху и будет удален первым

Основные операции

• Enqueue—) — вставляет элемент в конец очереди
• Dequeue () — удаляет элемент из начала очереди
• isEmpty () — возвращает значение true, если очередь пуста
• Top () — возвращает первый элемент очереди

Вопросы

• Реализовать cтек с помощью очереди
• Реверс первых N элементов очереди
• Генерация двоичных чисел от 1 до N с помощью очереди

Связанный список

Связанный список – массив где каждый элемент является отдельным объектом и состоит из двух элементов – данных и ссылки на следующий узел.

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

Бывают

Однонаправленный, каждый узел хранит адрес или ссылку на следующий узел в списке и последний узел имеет следующий адрес или ссылку как NULL.

Двунаправленный, две ссылки, связанные с каждым узлом, одним из опорных пунктов на следующий узел и один к предыдущему узлу.

Круговой, все узлы соединяются, образуя круг. В конце нет NULL. Циклический связанный список может быть одно-или двукратным циклическим связанным списком.

Самое частое, линейный однонаправленный список. Пример – файловая система.

Основные операции

• InsertAtEnd — Вставка заданного элемента в конец списка
• InsertAtHead — Вставка элемента в начало списка
• Delete — удаляет заданный элемент из списка
• DeleteAtHead — удаляет первый элемент списка
• Search — возвращает заданный элемент из списка
• isEmpty — возвращает True, если связанный список пуст

Вопросы

• Реверс связанного списка
• Определение цикла в связанном списке
• Возврат N элемента из конца в связанном списке
• Удаление дубликатов из связанного списка

Графы

Граф-это набор узлов (вершин), которые соединены друг с другом в виде сети ребрами (дугами).

Бывают

Ориентированный, ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами.
Неориентированные, к каждому из ребер можно осуществлять переход в обоих направлениях.
Смешанные

Встречаются в таких формах как

• Матрица смежности
• Список смежности

Общие алгоритмы обхода графа

• Поиск в ширину – обход по уровням
• Поиск в глубину – обход по вершинам

Вопросы

• Реализовать поиск по ширине и глубине
• Проверить является ли граф деревом или нет
• Посчитать количество ребер в графе
• Найти кратчайший путь между двумя вершинами

Деревья

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

Древовидные структуры везде и всюду. Дерево скилов в играх знают все.

• N дерево
• Сбалансированное дерево
• Дерево Бинарного Поиска

«Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. » — Procs

Три способа обхода дерева

• В прямом порядке (сверху вниз) — префиксная форма.
• В симметричном порядке (слева направо) — инфиксная форма.
• В обратном порядке (снизу вверх) — постфиксная форма.

Вопросы

• Найти высоту бинарного дерева
• Найти N наименьший элемент в двоичном дереве поиска
• Найти узлы на расстоянии N от корня
• Найти предков N узла в двоичном дереве

Trie ( префиксное деревое )

Разновидность дерева для строк, быстрый поиск. Словари. Т9.

Вот как такое дерево хранит слова «top», «thus» и «their».

Слова хранятся сверху вниз, зеленые цветные узлы «p», «s» и «r» указывают на конец «top», «thus « и «their» соответственно.

Вопросы

• Подсчитать общее количество слов
• Вывести все слова
• Сортировка элементов массива с префиксного дерева
• Создание словаря T9

Хэш таблицы

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

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

По сути это массив, в котором ключ представлен в виде хеш-функции.

Эффективность хеширования зависит от

• Функции хеширования
• Размера хэш-таблицы
• Метода борьбы с коллизиями

Вопросы

• Найти симметричные пары в массиве
• Найти, если массив является подмножеством другого массива
• Описать открытое хеширование

Список ресурсов

Вместо заключения

Матчасть так же интересна, как и сами языки. Возможно, кто-то увидит знакомые ему базовые структуры и заинтересуется.

Спасибо, что прочли. Надеюсь не зря потратили время =)

PS: Прошу извинить, как оказалось, перевод статьи уже был тут и очень недавно, я проглядел.
Если интересно, вот она, спасибо Hokum, буду внимательнее.

Алгоритмы и структуры данных для начинающих: стеки и очереди

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

Стек — это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (Last-In-First-Out или LIFO). Это значит, что мы будем иметь доступ только к последнему добавленному элементу.

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

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

Если мы положим, например, красную тарелку, затем синюю, а затем зеленую, то сначала надо будет снять зеленую, потом синюю, и, наконец, красную. Главное, что надо запомнить — тарелки всегда ставятся и на верх стопки. Когда кто-то берет тарелку, он также снимает ее сверху. Получается, что тарелки разбираются в порядке, обратном тому, в котором ставились.

Теперь, когда мы понимаем, как работает стек, введем несколько терминов. Операция добавления элемента на стек называется «push», удаления — «pop». Последний добавленный элемент называется верхушкой стека, или «top», и его можно посмотреть с помощью операции «peek». Давайте теперь посмотрим на заготовку класса, реализующего стек.

Класс Stack

Класс Stack определяет методы Push , Pop , Peek для доступа к элементам и поле Count . В реализации мы будем использовать LinkedList<T> для хранения элементов.

Метод Push

• Поведение: Добавляет элемент на вершину стека.
• Сложность: O(1).

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

Метод Pop

• Поведение: Удаляет элемент с вершины стека и возвращает его. Если стек пустой, кидает InvalidOperationException .
• Сложность: O(1).

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

Метод Peek

• Поведение: Возвращает верхний элемент стека, но не удаляет его. Если стек пустой, кидает InvalidOperationException .
• Сложность: O(1).

Метод Count

• Поведение: Возвращает количество элементов в стеке.
• Сложность: O(1).

Зачем нам знать, сколько элементов находится в стеке, если мы все равно не имеем к ним доступа? С помощью этого поля мы можем проверить, есть ли элементы на стеке или он пуст. Это очень полезно, учитывая, что метод Pop кидает исключение.

Пример: калькулятор в обратной польской записи

Классический пример использования стека — калькулятор в обратной польской, или постфиксной, записи. В ней оператор записывается после своих операндов. То есть, мы пишем:

Другими словами, вместо «4 + 2» мы запишем «4 2 +». Если вам интересно происхождение обратной польской записи и ее названия, вы можете узнать об этом на Википедии или в поисковике.

То, как вычисляется обратная польская запись и почему стек так полезен при ее использовании, хорошо видно из следующего алгоритма:

То есть, для выражения «4 2 +» действия будут следующие:

В конце на стеке окажется одно значение — 6.

Далее приводится полный код простого калькулятора, который считывает выражение (например, 4 2 + ) из консоли, разбивает входные данные по пробелам ( [«4», «2», «+»] ) и выполняет алгоритм вычисления. Вычисление продолжается до тех пор, пока не будет встречено слово quit .

Очередь

Очереди очень похожи на стеки. Они также не дают доступа к произвольному элементу, но, в отличие от стека, элементы кладутся (enqueue) и забираются (dequeue) с разных концов. Такой метод называется «первый вошел, первый вышел» (First-In-First-Out или FIFO). То есть забирать элементы из очереди мы будем в том же порядке, что и клали. Как реальная очередь или конвейер.

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

Класс Queue

Класс Queue , как и стек, будет реализован с помощью связного списка. Он будет предоставлять методы Enqueue для добавления элемента, Dequeue для удаления, Peek и Count . Как и класс Stack , он не будет реализовывать интерфейс ICollection<T> , поскольку это коллекции специального назначения.

Метод Enqueue

• Поведение: Добавляет элемент в очередь.
• Сложность: O(1).

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

Метод Dequeue

• Поведение: Удаляет первый помещенный элемент из очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

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

Метод Peek

• Поведение: Возвращает элемент, который вернет следующий вызов метода Dequeue . Очередь остается без изменений. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

Двусторонняя очередь

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

Класс Deque

Класс Deque проще всего реализовать с помощью двусвязного списка. Он позволяет просматривать, удалять и добавлять элементы в начало и в конец списка. Основное отличие двусторонней очереди от обычной — методы Enqueue , Dequeue , и Peek разделены на пары для работы с обоими концами списка.

Метод EnqueueFirst

• Поведение: Добавляет элемент в начало очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueFirst .
• Сложность: O(1).

Метод EnqueueLast

• Поведение: Добавляет элемент в конец очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueLast .
• Сложность: O(1).

Метод DequeueFirst

• Поведение: Удаляет элемент из начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод DequeueLast

• Поведение: Удаляет элемент с конца очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод PeekFirst

• Поведение: Возвращает элемент из начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод PeekLast

• Поведение: Возвращает элемент с конца очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

Пример: реализация стека

Двусторонняя очередь часто используется для реализации других структур данных. Давайте посмотрим на пример реализации стека с ее помощью.

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

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

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

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

Хранение элементов в массиве

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

Давайте посмотрим на проблемы, которые могут возникнуть, и на их решение. Кроме того, нам понадобится информация об увеличении внутреннего массива из прошлой статьи о динамических массивах.

При создании очереди у нее внутри создается массив нулевой длины. Красные буквы «h» и «t» означают указатели _head и _tail соответственно.

Добавляем элемент в начало

Добавляем элемент в конец

Добавляем еще один элемент в начало

Обратите внимание: индекс «головы» очереди перескочил в начало списка. Теперь первый элемент, который будет возвращен при вызове метода DequeueFirst — 0 (индекс 3).

И еще один в конец

Массив заполнен, поэтому при добавлении элемента произойдет следующее:

• Алгорим роста определит размер нового массива.
• Элементы скопируются в новый массив с «головы» до «хвоста».
• Добавится новый элемент.

Добавляем значение в конец расширенного массива

Теперь посмотрим, что происходит при удалении элемента:

Удаляем элемент из начала

Удаляем элемент с конца

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

Теперь давайте посмотрим на реализацию.

Класс Deque (с использованием массива)

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

Алгоритм роста

Когда свободное место во внутреннем массиве заканчивается, его необходимо увеличить, скопировать элементы и обновить указатели на «хвост» и «голову». Эта операция производится при необходимости во время добавления элемента. Параметр startingIndex используется, чтобы показать, сколько полей в начале необходимо оставить пустыми (в случае добавления в начало).

Обратите внимание на то, как извлекаются данные, когда приходится переходить в начало массива при проходе от «головы» к «хвосту».

Метод EnqueueFirst

• Поведение: Добавляет элемент в начало очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueFirst .
• Сложность: O(1) в большинстве случаев; O(n), когда нужно расширение массива.

Метод EnqueueLast

• Поведение: Добавляет элемент в конец очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueLast .
• Сложность: O(1) в большинстве случаев; O(n), когда нужно расширение массива.

Метод DequeueFirst

• Поведение: Удаляет элемент с начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод DequeueLast

• Поведение: Удаляет элемент с конца очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод PeekFirst

• Поведение: Возвращает элемент с начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод PeekLast

• Поведение: Возвращает элемент с конца очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

Продолжение следует

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

Основные структуры данных

Структуры данных являются неотъемлемой частью любой программы. Без них вы не сможете реализовать ничего более полезного, чем "Hello, world!" . По другую сторону от структур данных находятся алгоритмы, но о них мы поговорим в другой раз. Эта заметка носит больше практический, а не теоретический характер, поэтому я не буду углубляться в детали и принципы работы, а лишь расскажу о свойствах самых ходовых контейнерных классов, которые можно найти (или написать самому) на большинстве существующих языков программирования. То есть основное внимание мы сосредоточим на их практической ценности с точки зрения использования в наших программах.

Примеры я буду приводить на C++, но структуры данных (как и алгоритмы) не зависит от языка реализации, то есть являются абстракциями, принцип работы и область применения которых везде неизменны, поэтому вы легко сможете применить те же приемы практически на любом другом языке программирования.

Реклама

Массив

А начнем мы с массивов, о которых вы не могли не слышать. Они имеют неизменный размер и позволяют хранить наборы однотипных объектов. Их преимущество заключается в константном времени доступа к произвольному элементу. Не будем вдаваться в тонкости нотации O-большого и проводить формальный анализ, просто примем к сведению, что получить произвольный элемент массива по его индексу можно очень быстро. Однако то, что размер массива должен быть фиксированным, является серьезным ограничением. Поэтому массивы лучше всего применять в тех ситуациях. когда количество элементов известно заранее.

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

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

Но вот мы встретились с первой сложностью. Третий день недели в русскоязычных странах — среда, а представленный выше код выведет "ЧТ". Элементы индексируются с нуля, поэтому произошел сдвиг. Как можно решить эту проблему?

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

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

Теперь код получения символьного представления дня недели выглядит значительно лучше и понятнее, потому что не используются "волшебные числа":

Теперь на консоль и правда будет выведено "СР". Однако и этот подход не лишен недостатков. Например, сейчас у нас полностью отсутствует контроль доступа к элементам массива. То есть мы можем передать в качестве индекса 10 , что на C++ приведет к неопределенному поведению. Конечно, на более высокоуровневых языках программирования с этим немного лучше. В них предусмотрено исключение выхода за границы массива, но и это не совсем то, что нам хотелось бы.

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

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

Однако если у вас имеется достаточно уникальная задача, для которой стандартных решений найти не удалось, то вы вполне можете рассмотреть вариант создания массива для хранения констант, при условии, что их можно легко проиндексировать. Для каких-то других целей лучше использовать более подходящие структуры данных, о которых мы сейчас и поговорим.

Реклама

Вектор

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

В зависимости от реализации вектора, сложность алгоритма изменения его размера может быть разной. В простейшем случае алгоритм имеет линейную сложность по количеству элементов. Это означает, что при каждом изменении размера внутреннее содержимое вектора полностью копируется в новое место. Звучит не слишком эффективно? — Так оно и есть. Поэтому обычно внутренний массив выделяется с запасом, чтобы лишний раз избежать копирования, которое, тем не менее, придется делать, если запас иссякнет. Таким образом, если работать с векторами умеренных размеров, то издержки на операцию изменения размера на современных компьютерах не так велики, как кажется.

Рассмотрим простой пример использования вектора:

Эта программа просто запрашивает у пользователя в цикле целые числа. Поскольку заранее мы не можем сказать сколько чисел будет введено, то вектор подходит для их хранения гораздо лучше, чем обычный массив. Обратите внимание, что для преобразования строки в число мы используем функцию std::stoi() (добавленную в C++11). В отличие от аналогичной функции std::atoi() она возбуждает исключение, если преобразование окончилось неудачей.

Завершится цикл в момент, когда пользователь введет символ ‘q’ . После цикла мы проверяем, что пользователь указал хотя бы одно число, то есть то, что вектор чисел не пустой. Если числа и правда есть, то сначала мы выводим содержимое вектора на консоль, а затем отображаем число из середины вектора. Здесь мы использовали один интересный прием комбинирования итераторов и алгоритмов STL для вывода содержимого вектора. За основу мы взяли std::copy() , которому в качестве входного диапазона передали итераторы вектора, а выход привязали к стандартному потоку вывода std::cout , задав в качестве разделителя между значениями знак пробела.

Типичный сеанс работы с приложением будет выглядеть следующим образом:

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

Список, стек, очередь

Списки, как и векторы с массивами, позволяют хранить упорядоченные последовательности объектов. Однако между ними есть существенные различия: добавлять и удалять элементы в начале и конце списка можно без лишних затрат за константное время (в теории), но вот получить доступ к элементу по индексу можно лишь за линейное время (чем ближе к середине, тем дольше). Причем, вставку и удаление элементов, в отличие от векторов, достаточно эффективно можно проводить в любом месте списка. Конечно, вычислительная сложность в этом случае уже не константная, а линейная, но это все равно быстрее, чем копирование массивов внутри вектора.

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

Стеки и очереди, как правило, основываются на списках, поэтому имеют те же преимущества и недостатки. При этом стек работает по принципу "первым пришел — последним ушел", а очереди — "первым пришел — первым ушел".

Стеки, как правило, используют для хранения вложенных состояний. Если вы разрабатывали рекурсивные алгоритмы, то наверняка встречались с понятием "переполнение стека вызовов". При переходе на каждый новый уровень рекурсии во время рекурсивного спуска значения переменных на текущем уровне помещаются в стек. Если рекурсия организована корректно, то в процессе рекурсивного подъема данные из стека извлекаются и контекст работы функции восстанавливается, то есть переменные получают свои значения, которые были помещены в стек. Если же в алгоритме есть ошибка, то рекурсия может оказаться бесконечной, из-за чего стек рано или поздно переполнится и произойдет аварийное завершение приложения с ошибкой "Stack Overflow". В языках программирования высокого уровня вам не приходится задумываться о подобных деталях. Поэтому если у вас появилось желание изучить этот вопрос поподробнее, то рекомендую заняться изучением ассемблера. Там весь процесс управления стеком вызовов будем под вашим контролем.

Часто очереди применяют для передачи данных между потоками, то есть они выступают в качестве защищенного мьютекстом канала связи. Соответствующий паттерн многопоточного программирования называется "Производители-Потребители". Его идея заключается в том, что несколько потоков-Производителей занимаются тем, что компонуют данные и помещают их в очередь на обработку. На другой стороне очереди их ждут потоки-Потребители, которые и занимаются обработкой данных, извлекая их из очереди. В результате соблюдается хронология решения задач. Те данные, которые были добавлены в очередь раньше, будут раньше переданы и на обработку. Кроме того, существует более сложная версия очереди — "очередь с приоритетом". Принцип ее работы в целом тот же, но вы получаете возможность нарушить хронологию при необходимости, если для какого-то набора данных установите более высокий приоритет, чем для остальных. Подобный пример использования очередей заслуживает того, чтобы стать темой отдельной заметки, поэтому здесь мы подробно на этом останавливаться не будем.

Посмотрим пример использования списка:

Как вы могли заметить, он практически дословно повторяет то, что мы уже видели в примере использования для векторов. Только теперь мы используем объявление std::list< int > , а не std::vector< int > . Однако доступ к элементам списка по индексу запрещен, поэтому соответствующий код закомментирован и работать не будет. Результат выполнения этого приложения такой же, как и в случае вектора, кроме того, что не выводится значение центрального элемента.

Следует учитывать, что на практике список может работать значительно медленнее вектора при вставке элементов в конец. К тому же, расход памяти у списка будет больше. Это связано с издержками принципа работы списков и фрагментацией оперативной памяти. С другой стороны, если вставку необходимо осуществлять не только в конец, а в произвольном месте последовательности, то список должен оказаться быстрее. Поэтому если у вас стоит выбор между использованием вектора или списка, то попробуйте провести профилирование кода. То есть замерьте производительность приложения в том и в другом случае, и выберите лучший вариант. Схожие рассуждения справедливы для стеков и очередей, поэтому ориентируйтесь по фактической скорости работы с учетом особенностей языка программирования и библиотеки контейнеров, которые вы используете.

Множество

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

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

Посмотрим, как будет выглядеть наш пример с вводом чисел в случае множества:

Довольно близко к тому, что было для списка (да и для вектора, без учета запроса элемента из середины). Однако обратите внимание, что добавление объектов в вектор и список осуществлялось с помощью push_back() , но у множества нет начала и конца, поэтому для него мы используем функцию-член insert() .

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

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

Ассоциативный массив

Ассоциативные массивы можно использовать в качестве более универсальной альтернативы вектору. Однако индексация в этом случае возможна не только по целочисленным индексам, а по любому типу, который удовлетворяет некоторым условиям. Сами эти условия зависят от реализации ассоциативного массива, а индекс называется ключом. Основными видами ассоциативных массивов являются карты и хэш-таблицы.

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

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

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

Давайте теперь немного скорректируем наш пример со считыванием чисел, чтобы задействовать возможности ассоциативного массива. Подсчитаем, сколько раз было введено каждое число:

Обратите внимание, как мы наращиваем счетчик для введенного числа. Мы обращаемся к элементу так же, как делали бы это для обычного массива. Однако размер карты нигде не был указан, поэтому элемент создается в момент первого обращения к нему. Последующие запросы с тем же ключом вернут соответствующий элемент, который уже существует и был инициализирован ранее. Обход карты мы осуществляем с помощью итератора в цикле for . Обращение к ключу осуществляется с помощью поля итератора first , а к соответствующему значению через second .

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

Прекрасно. Ровно то, что мы и хотели.

Заключение

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