C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц
Шрифт:
Интервал:
Закладка:
Все контейнеры, предоставляемые STL, можно разделить на такие категории, которые подробнее рассматриваются в следующем разделе:
□ непрерывные хранилища;
□ списки;
□ деревья поиска;
□ хеш-таблицы;
□ адаптеры контейнеров.
Рассмотрим более подробно каждый из пунктов.
Непрерывные хранилища
Самый простой способ хранения объектов — поместить их рядом друг с другом в одном большом фрагменте памяти. Произвольный доступ к такому фрагменту выполняется за время O(1).
Это проще всего сделать так: воспользоваться контейнером std::array (он представляет собой обертку для обычных массивов в стиле C). Вам практически всегда следует выбирать их вместо обычных массивов, поскольку это не потребует никаких усилий, но работать станет комфортнее и безопаснее. Как и в случае с обычными массивами, массивы STL имеют фиксированный размер, определяемый при создании.
Контейнер std::vector вступает в дело, когда вам нужно хранилище, похожее на массив, но с изменяемой длиной. Он использует память из кучи для хранения объектов. Если при добавлении элемента в вектор происходит превышение размера вектора, то все элементы автоматически перемещаются в более крупный фрагмент вновь выделенной памяти, старый же фрагмент удаляется. Более того, если новый элемент помещается между двумя старыми, то может даже перемещать существующие элементы в памяти. При удалении элемента из середины вектора класс vector автоматически сдвинет оставшиеся элементы так, чтобы закрыть получившуюся дыру.
Добавление (или удаление) в начало (или конец) контейнера std::vector сразу многих объектов может повлечь выполнение большого количества операций выделения памяти для получения пространства, а также потенциально затратных операций по перемещению объектов. В таких ситуациях стоит воспользоваться контейнером std::deque (deque («дек») расшифровывается как double-ended queue (двусторонняя очередь)). Объекты хранятся в непрерывных фрагментах памяти, которые не зависят друг от друга. Это позволяет быстро увеличивать размер дека, поскольку объекты, расположенные в таких фрагментах памяти, не будут перемещаться, когда выделяется память для нового фрагмента и размещается в начале или конце контейнера.
Хранение списков
Контейнер std::list представляет собой классический двухсвязный список. Ни больше ни меньше. Если вам нужно выполнять обход списка только в одном направлении, то больше подойдет контейнер std::forward_list — он быстрее работает и занимает меньше места, поскольку в нем хранятся лишь указатели на следующий элемент. Пройти список можно только последовательно, за время O(n). Вставку и удаление элементов в заданную позицию можно выполнить за время O(1).
Деревья поиска
Если для объектов характерен естественный порядок, такой, что их можно отсортировать с использованием математического отношения <, то их можно поддерживать в этом же порядке с помощью деревьев поиска. Из названия следует: конкретный элемент дерева легко находится благодаря ключу поиска, что дает возможность выполнять эту операцию за время O(log(n)).
В STL есть несколько видов таких деревьев, самым простым является std::set — в нем хранятся уникальные сортируемые объекты.
Контейнер std::map отличается тем, что данные в нем хранятся парами. Пара состоит из ключа и значения. Дерево поиска использует ключ для сортировки элементов, таким образом можно задействовать std::map в качестве ассоциативного контейнера. Как и в случае с контейнером std::set, все ключи в дереве должны быть в единственном экземпляре.
Контейнеры std::multiset и std::multimap являются частными случаями контейнеров, показанных выше, для которых отсутствует требование уникальности ключей.
Хеш-таблицы
Деревья поиска не единственный способ реализации ассоциативных контейнеров. В хеш-таблицах элементы можно найти за время O(1), но они игнорируют естественный порядок элементов, поэтому не так просто пройти по упорядоченному списку. Пользователь может изменять размеры хеш-таблицы, можно даже выбрать отдельно хеш-функцию, что немаловажно, поскольку от этого зависят производительность и потребление памяти.
Контейнеры std::unordered_set и std::unordered_map весьма похожи на std::set и std::map, что можно утверждать на основании их взаимозаменяемости.
Как и реализации поисковых деревьев, у обоих контейнеров есть «коллеги» std::unordered_multiset и std::unordered_multimap, которые не имеют ограничения на уникальность объектов/ключей, поэтому можно хранить несколько элементов для одного ключа.
Адаптеры контейнеров
Массивы, списки, деревья и хеш-таблицы не единственный способ хранения данных и получения к ним доступа. Еще есть стеки, очереди и т.д. Аналогично тому, как более сложные структуры могут быть реализованы с использованием более примитивных, в STL такие структуры создаются благодаря следующим классам — адаптерам контейнеров: std::stack, std::queue и std::priority_queue.
Приятная новость: если нам нужна подобная структура данных, можно просто выбрать адаптер. Далее, понимая, что нас не устраивает производительность, мы можем просто изменить параметр шаблона, чтобы адаптер выбрал другую реализацию контейнера. На практике это значит, например, возможность замены находящейся в основе экземпляра std::stack реализации с std::vector на std::deque.
Используем идиому erase-remove для контейнера std::vector
Многие программисты-новички узнают о существовании класса std::vector, который в основном работает как автоматически увеличивающийся массив, и останавливаются на этом. Далее они лишь ищут в документации сведения о том, как решать конкретные задачи, например удалять элементы. Такого рода использование контейнеров STL не задействует и сотой доли их возможностей в создании чистого, удобного в сопровождении и быстрого кода.
Текущий раздел посвящен вопросу удаления элементов из середины объекта вектора. Если элемент исчезает из вектора и при этом он находился между другими элементами, то все элементы, стоящие справа от него, должны сместиться на одну позицию влево (в результате время выполнения операции составляет O(n)). Многие начинающие программисты будут решать задачу с помощью цикла, ведь это так просто. К сожалению, при этом они, скорее всего, упустят потенциальные возможности оптимизации. В конечном счете цикл, написанный вручную, не быстрее и не читабельнее, чем способ решения задачи средствами STL, которые мы еще рассмотрим далее.
Как это делается
В этом примере мы наполним объект класса std::vector целыми числами, а затем выбросим из него конкретные элементы. При этом мы воспользуемся корректным способом удаления нескольких элементов из вектора.
1. Конечно, прежде чем начинать что-то делать, включим некоторые заголовочные файлы:
#include <iostream>
#include <vector>
#include <algorithm>
2. Далее мы объявляем, что будем использовать пространство имен std, чтобы поменьше печатать:
using namespace std;
3. Теперь создадим вектор, состоящий из целых чисел, и заполним его некими числами:
int main()
{
vector<int> v {1, 2, 3, 2, 5, 2, 6, 2, 4, 8};
4. Удалим некоторые элементы. Что именно? В
