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

Структуры данных являются неотъемлемой частью любой программы. Без них вы не сможете реализовать ничего более полезного, чем "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.

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

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

Заключение

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