Контейнеры и итераторы

Пример диапазона с массивом:

char data[] = "Hello, world!";
// Диапазон с 7-го элемента по 12-й содержит слово "world".
auto begin = data + 7; // Начало диапазона -- первый итератор в паре.
auto end = data + 12;  // Конец диапазона -- второй итератор в паре.
assert(end - begin == 5); // Расстояние между итераторами == количеству элементов в диапазоне.
// Перечислим подряд все элементы диапазона.
while (begin != end)
  cout.put(*begin++); // > world

В зависимости от внутреннего устройства контейнера не все характерные для указателей операции могут быть выполнены эффективно на его итераторах. Например, при доступе к связному списку обращение по числовому индексу может потребовать значительного числа операций. Итераторы могут не поддерживать неэффективные операции. Чтобы выделить характерные виды итераторов, в Стандарте C++ определены “категории итераторов”. Принадлежность итератора той или иной категории определяется набором поддерживаемых им операций.

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

Категории итераторов

Основная конструкция, поддерживаемая итератором ввода выглядит так:

Value value = *it++; // прочитать следующее значение, it -- итератор

Итератор можно передвигать на одну позицию вперед (инкремент) и разыменовывать (операции * и ->), получая доступ к текущему значению. Итераторы можно сравнивать между собой на равенство и неравенство.

Основная конструкция, поддерживаемая итератором вывода, выглядит так:

*it++ = value;

Для упрощения работы с итераторами Стандартная библиотека предоставляет ряд средств (заголовочный файл <iterator>). Перечислим их.

Элементы Стандартной библиотеки для работы с итераторами

Класс характеристик iterator_traits<T>

В случае iterator_traits<T> это набор вложенных объявлений типов:

• value_type — тип значения, на которое указывает итератор типа T (далее по списку просто “итератор”);
• reference — тип ссылки, возвращаемой при разыменовании итератора;
• pointer — тип указателя, возвращаемого при обращении к объекту итератора через operator-> (может не быть “настоящим” указателем);
• difference_type — целочисленный тип, представляющий значения смещений итераторов относительно друг друга;
• iterator_category — тип, указывающий на набор операций, поддерживаемых итератором. iterator_category является синонимом одного из предопределенных теговых классов:
  • random_access_iterator_tag, если T — итератор произвольного доступа. random_access_iterator_tag — наследник bidirectional_iterator_tag;
  • bidirectional_iterator_tag, если T — двунаправленный итератор. bidirectional_iterator_tag является наследником forward_iterator_tag;
  • forward_iterator_tag, если T — однонаправленный итератор. forward_iterator_tag является наследником input_iterator_tag и output_iterator_tag;
  • input_iterator_tag, если T — итератор ввода;
  • output_iterator_tag, если T — итератор вывода.

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

• итератор произвольного доступа — RanIt;
• итератор двунаправленного доступа — BidIt;
• итератор однонаправленного доступа — FwdIt;
• итератор ввода — InIt;
• итератор вывода — OutIt.

Класс iterator

Класс-шаблон iterator<Category, T, Distance = ptrdiff_t, Pointer = T*, Reference = T&>. Здесь Category — один из тегов, перечисленных выше, а T — тип значения, на которое указывает итератор. Данный класс используется в качестве базового при создании других классов итераторов: он определяет вложенные типы, доступные затем через iterator_traits, что позволяет не определять вручную частную специализацию шаблона iterator_traits для своего типа итератора.

Вспомогательные функции distance, advance, next, prev

Функция distance(from, to) вычисляет расстояние между парой переданных ей итераторов from и to (количество применений оператора инкремента к первому итератору до достижения им второго, либо обычная разность для итераторов произвольного доступа).

Данная функция является хорошим примером использования категории итератора для выбора адекватного алгоритма (данная техника называется “статическая диспетчеризация вызова”). Её можно было бы определить следующим образом:

namespace std
{
  namespace implementation
  {
    // Общий вариант функции: линейный алгоритм,
    // определяет, сколько шагов надо сделать от первого итератора, чтобы достичь второго.
    // AnyTag позволяет принять любой тег.
    template <class It, class AnyTag>
    auto _distance(It from, It to, AnyTag)
    {
      typename iterator_traits<It>::difference_type steps = 0;
      while (from != to)
      {
        ++from;
        ++steps;
      }
      return steps;
    }
    // Однако, если итератор является итератором произвольного доступа,
    // то для него определена операция "-", позволяющая эффективно (за постоянное время)
    // вычислить расстояние между итераторами.
    template <class It>
    auto _distance(It from, It to, random_access_iterator_tag)
    {
      return to - from;
    }
  }
  // Внешний интерфейс distance, выполняет выбор нужного варианта
  // с помощью третьего параметра.
  template <class It>
  auto distance(It from, It to)
  {
    typename iterator_traits<It>::iterator_category tag;
    return implementation::_distance(from, to, tag);
  }
}

Функция advance(it, n) сдвигает итератор it (принимает по ссылке) на заданное число шагов n (сдвиг назад при отрицательных значениях n определен для двунаправленных итераторов).

Функции next(it), next(it, n) и prev(it), prev(it, n) возвращают итератор, сдвинутый соответственно вперед или назад на одну или n позиций.

Итераторы-адаптеры

Класс обратный итератор reverse_iterator<Iterator> оборачивает объект двунаправленного итератора Iterator, обращая порядок обхода последовательности: инкремент обратного итератора приводит к декременту базового итератора и наоборот. Извлечь базовый итератор можно с помощью функции-члена base. Стандартные контейнеры используют reverse_iterator для реализации функций rbegin и rend, с помощью которых можно представить последовательность значений, хранимых в контейнере, как диапазон, при обходе перебираемый в обратном порядке (прямой порядок можно получить с помощью функций begin и end). Чтобы обеспечить корректность диапазона [rbegin, rend), базовый итератор сдвинут на одну позицию вперед. Таким образом, если r — обратный итератор, то истинно выражение &*r == &*prev(r.base()). Создать обёртку-обратный итератор из другого итератора “на месте” можно с помощью функции make_reverse_iterator (введена в стандарт C++14).

Класс перемещающий итератор move_iterator<Iterator> является обёрткой, подменяющей копирующее присваивание перемещением. Создать объект данного класса из “обычного итератора” (it) на месте можно с помощью функции make_move_iterator(it).

Класс итератор вставки в конец back_insert_iterator<Container> является итератором вывода, реализующим операцию записи через вызов функции-члена push_back для контейнера типа Container, указатель на который хранится в объекте итератора. Создать такой итератор на месте можно с помощью функции back_inserter(container), что бывает удобно при сохранении последовательности, размер которой заранее неизвестен (пример см. ниже).

Класс итератор вставки в начало front_insert_iterator<Container> аналогичен предыдущему, но вызывает функцию push_front. Создать объект на месте можно с помощью функции front_inserter(container).

Класс итератор вставки insert_iterator<Container> похож на два предыдущих, но предназначен для вставки элементов в произвольной позиции внутри контейнера, поэтому помимо указателя на контейнер хранит итератор, задающий позицию вставки в этом контейнере. При записи вызывает функцию контейнера insert и обновляет текущую позицию. Создать объект insert_iterator на месте можно с помощью функции inserter(container, it), где it — начальная позиция записи.

Класс итератор потока ввода istream_iterator<T, CharT = char, Traits = char_traits<CharT>, Dist = ptrdiff_t> является итератором ввода, предназначенным для чтения из basic_istream<CharT, Traits> (в частности istream). Типы CharT и Traits обеспечивают возможность использования пользовательских типов символов. Второй из них — класс характеристик, содержащий ряд базовых типов и операций над символами и передаваемыми по указателю строками. Для стандартных символьных типов определены соответствующие версии стандартного шаблона char_traits.

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

Объекты back_inserter и istream_iterator можно использовать вместе, например, для организации считывания последовательности произвольной длины разделённых пробельными символами чисел. В примере чтение производится из потока cin в контейнер xs, который может иметь тип vector<int> (здесь copy — стандартный алгоритм, о которых см. ниже):

copy(istream_iterator<int>(cin),
     istream_iterator<int>(), back_inserter(xs));

Класс итератор потока вывода ostream_iterator<T, CharT = char, Traits = char_traits <CharT>> является итератором вывода, предназначенным для записи в объект basic_ostream<CharT, Traits> (в частности, ostream). Кроме указателя на поток вывода итератор хранит указатель типа CharT* на строку-разделитель, которая выводится после каждой записи (если указатель ненулевой). Выведем последовательность чисел xs, разделенную запятыми в поток cout:

copy(xs.begin(), xs.end(),
     ostream_iterator<int>(cout, ", "));

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

Стандартные контейнеры

Стандартные контейнеры можно разбить на две большие группы: линейные и ассоциативные. В свою очередь, линейные контейнеры можно разделить на связные списки (forward_list и list) и контейнеры произвольного доступа (deque, vector и array).

Ассоциативные контейнеры представлены восемью контейнерами, являющимися комбинациями следующих вариантов (в скобках даны части названий соответствующих стандартных классов): множество (*set) или словарь (*map), допускающие повторение элементов (*multi*) или не допускающие, упорядоченные или неупорядоченные (unordered*).

Все контейнеры содержат вложенные типы iterator и const_iterator, определяющие итераторы чтения-записи и только чтения соответственно. Диапазон итераторов, охватывающий содержимое контейнера, можно получить с помощью функций begin и end (iterator, для чтения-записи), а также cbegin и cend(const_iterator для чтения). Контейнеры с двунаправленными итераторами предоставляют также функции-члены rbegin, rend, crbegin и crend для обратного обхода.

Все контейнеры можно проверять на пустоту функцией empty. Контейнер cont пуст, если cont.begin() == cont.end(), end() возвращает итератор, указывающий на условный элемент, находящийся за последним элементом контейнера. Количество элементов можно получить с помощью функции size (за исключением forward_list). Контейнер можно очистить от содержимого вызовом функции clear (за исключением array).

В <iterator> также определены шаблоны свободных функций begin, end, cbegin, cend, rbegin, rend, crbegin и crend, по умолчанию переадресующие вызов одноименным функциям-членам, кроме того, даны определения этих функций для статических массивов и std::valarray. Именно на них опирается форма цикла for(:). Пусть cr — некоторый “контейнер” (в том числе, возможно, статический массив), тогда запись

for (T x : cr) work(x);

семантически эквивалентна записи

{
  using std::begin;
  using std::end;
  const auto e = end(cr);
  for (auto p = begin(cr); p != e; ++p)
  { T x = *p; work(x); }
}

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

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

Прямой доступ к первому элементу контейнера (кроме неупорядоченных ассоциативных контейнеров) можно получить функцией front. Все контейнеры, итераторы которых являются по крайней мере двунаправленными, предоставляют функцию back для доступа к последнему элементу, а также противоположно направленные итераторы reverse_iterator и const_reverse_iterator, соответствующие диапазоны можно получить с помощью функций rbegin, rend и crbegin, crend.

Все контейнеры можно сравнивать на равенство и неравенство, а также обменивать их содержимое с помощью функции swap. Все контейнеры, кроме неупорядоченных ассоциативных, можно сравнивать лексикографически операторами <, <=, > и >=.

Для управления динамической памятью стандартные контейнеры используют специальные классы, называемые аллокаторы. Аллокатор привязан к типу элемента, который определяет минимальную единицу управления памятью и предоставляет ряд вспомогательных определений. Работа осуществляется с помощью четырех основных функций: allocate для выделения памяти под заданное количество элементов, deallocate для освобождения памяти, construct для вызова конструктора и destroy для вызова деструктора. Аллокатор должен предоставлять метафункцию rebind, позволяющую получить аналогичный аллокатор для элементов другого типа:

// Alloc -- реализация некоторого аллокатора для конкретного типа элементов.
// Получить вариант этого аллокатора для элементов типа U:
using AllocForU = typename Alloc::template rebind<U>::other;

Стандартная библиотека (в составе заголовочного файла <memory>) предоставляет allocator<T>, являющийся оберткой операторов new/new[] и delete/delete[]. Его можно использовать в качестве модели при написании своих аллокаторов.

Линейные контейнеры

Односвязный список <forward_list> forward_list<T, A = allocator<T>> предоставляет доступ к элементам типа T через однонаправленный итератор. Для создания узлов список использует аллокатор, полученный через A::rebind. Особенность односвязного списка состоит в том, что элементы можно добавлять и удалять только после заданной позиции:

• insert_after — вставить элемент;
• emplace_after — создать новый элемент, вызвав конструктор для переданных параметров;
• erase_after — удалить элемент.

Имеется дополнительная фиктивная позиция “перед первым элементом”, возвращаемая функциями before_begin и cbefore_begin (вариант, возвращающий const_iterator). Элементы можно вставлять в начало: вызов fl.push_front(item) эквивалентен

fl.insert_after(fl.before_begin(), item)

аналогично fl.emplace_front(...) (где ... — произвольный набор параметров конструктора элемента) эквивалентен

fl.emplace_after(fl.before_begin(), ...)

Функция pop_front удаляет первый элемент списка.

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

• merge сливает два отсортированных списка в один, элементы не копируются, а передаются из правого списка в левый;
• splice_after — вставляет переданный список целиком после указанного элемента;
• remove — удаляет все элементы, значение которых равно заданному;
• remove_if — удаляет все элементы в соответствии с предикатом;
• reverse — обращает порядок элементов;
• unique — удаляет все подряд идущие дубликаты;
• sort — сортирует список на месте.

В целом данные функции аналогичны соответствующим стандартным алгоритмам (см. их список в соответствующем разделе ниже), но выполняются как минимум быстрее, а как максимум — просто выполняются, потому что та же стандартная универсальная сортировка std::sort(from, to) требует итераторов произвольного доступа и поэтому вообще не применима к спискам.

Двусвязный список <list> list<T, A = allocator<T>> предоставляет доступ к элементам через двунаправленный итератор. В отличие от односвязного списка элементы вставляются перед заданной позицией (функции insert, emplace, splice), доступна вставка и удаление с конца (push_back, emplace_back, pop_back), удаление элемента, на который указывает итератор (erase). Функции вида *_after отсутствуют.

Дек <deque> deque<T, A = allocator<T>> предоставляет доступ к элементам через итератор произвольного доступа. Так же, как и list, позволяет эффективно добавлять и удалять элементы с обоих концов. Для доступа по индексу предназначены две функции: оператор [] и at(индекс). В отличие от первой вторая проверяет индекс и в случае недопустимого значения бросает исключение out_of_range.

Контейнер deque допускает выполнение вставки и удаления элементов в произвольной позиции аналогично list, однако в случае deque эти операции затратны: могут требовать времени линейного по размеру контейнера. Кроме того, необходимо помнить, что вставка и удаление элементов может “испортить” ранее сохраненные итераторы или указатели из-за потенциального перемещения хранимых элементов в памяти (в то время как итераторы списков сохраняются, если элементы, на которые они указывают, не были удалены).

Динамический массив <vector> или вектор (см. также здесь) vector<T, A = allocator<T>> предоставляет доступ к элементам через итератор произвольного доступа. В отличие от deque не позволяет вставлять и удалять элементы в начале. Динамический массив гарантирует расположение хранимых элементов подряд в непрерывном участке памяти, адрес которого возвращает функция data. При добавлении элементов и исчерпании заранее выделенного хранилища может быть выделен новый динамический массив большего размера, куда будут перенесены элементы. Старое хранилище при этом удаляется, все сохраненные итераторы “портятся” и становятся эквивалентны указателям на удаленные объекты.

Массив позволяет заранее подготовить хранилище достаточного размера с помощью функции reserve (может вызвать перемещение элементов). Узнать размер хранилища можно с помощью функции capacity. Функция shrink_to_fit выделяет хранилище размера, равного реально занятому, и переносит туда элементы, освобождая незанятую память.

Статический массив <array> array<T, N> предоставляет доступ к элементам через итератор произвольного доступа и является оберткой над статическим массивом T[N], адрес которого можно получить функцией data. В отличие от T[N] array<T, N> является полноценным типом, значения которого можно копировать (передавать в функции по значению), значения которого не конвертируются автоматически в указатели на них. Наконец, при желании array<T, N> можно использовать в качестве базового класса (но с осторожностью, как и любой контейнер, так как стандартные контейнеры не предназначены для такой цели и, в частности, не содержат виртуальных функций). Адресовать элементы по индексу можно так же, как в случае deque и vector. Изменять количество элементов нельзя, поэтому никаких функций для вставки и удаления элементов array не предоставляет. Функция fill заполняет массив копиями переданного значения.

Ассоциативные контейнеры

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

• count возвращает количество элементов, эквивалентных заданному (“ключу”);
• find возвращает либо итератор, указывающий на некоторый хранимый элемент, эквивалентный заданному, либо end(), если таковых нет;
• equal_range возвращает пару итераторов, задающих диапазон всех хранимых элементов, эквивалентных заданному.

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

make_pair(ac.lower_bound(key), ac.upper_bound(key))

Упорядоченное множество уникальных элементов <set> set<K, C = less<K>, A = allocator<K>>. Данный контейнер не позволяет изменять хранимые значения “на месте”, set<K>::iterator и set<K>::const_iterator функционально эквивалентны и возвращают const K& при разыменовании. Для того чтобы изменить хранимый в set объект, его нужно сначала удалить, а затем вставить изменённый вариант.

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

Последний вариант insert возвращает пару (итератор, булевское значение), первый элемент которой указывает место вставленного или найденного значения, второй же позволяет узнать, было значение вставлено (true) или уже находилось во множестве на момент вставки (false).

Для двух последних видов insert существуют аналоги emplace_hint и emplace, принимающие параметры конструктора и создающие значения “на месте”.

Удаление элементов выполняется функцией erase, которая принимает итератор или диапазон итераторов, задающие элементы множества, или значение. Первые два варианта возвращают итератор, указывающий на элемент, следующий за удаленными. Последний вариант возвращает количество удаленных элементов (0 или 1 в случае set).

// Пример использования erase в цикле: удалить из
// множества все строки с заданной подстрокой.
void erase_subs(set<string> &s, const string &subs)
{
  auto p = s.begin(), pe = s.end();
  while (p != pe)
  {
    if (p->find(subs) != string::npos)
      p = s.erase(p);
    else
      ++p;
  }
}

Упорядоченное мультимножество <set> multiset. В отличие от set вставка одного значения функцией insert всегда возвращает итератор, указывающий на вставленное значение.

// Сортировка деревом с помощью multiset.
template <class FwdIt>
void tree_sort(FwdIt begin, FwdIt end)
{
  using VT = typename iterator_traits<FwdIt>::value_type;
  // Заполнить multiset значениями из [begin, end).
  // Без копирования, если возможно: осуществляем перемещение.
  multiset<VT> tree(make_move_iterator(begin), make_move_iterator(end));
  // Копируем обратно. К сожалению, здесь не получится "честно" переместить
  // из-за того, что итераторы "только для чтения".
  copy(tree.begin(), tree.end(), begin);
}

В примере используется функция copy из <algorithm> (см. раздел, посвященный стандартным алгоритмам).

Упорядоченный словарь с уникальными ключами <map> map<K, T, C = less<K>, A = allocator<pair<const K, T>>> хранит значения типа std::pair<const K, T>, где K играет роль ключа, по которому осуществляется выборка, а T — хранимое значение. Поэтому при разыменовании итератора поле first позволяет прочитать ключ, а поле second предоставляет доступ к хранимому значению.

Основная операция map — индексирование с помощью operator[], которому передается значение ключа. Данный оператор возвращает ссылку на значение, отвечающее переданному ключу. Если в словаре не было значения с таким ключом, то будет создано новое значение (конструктором по умолчанию), ссылка на которое и будет возвращена. Таким образом, [] не позволяет узнать, было значение найдено или же создано в момент обращения. Так как индексирование может изменять структуру контейнера (создавать новые узлы), оно неприменимо к значениям типа const map<...> (например, если map передан по const-ссылке — в этом случае следует использовать функцию find).

Пусть map<K, T> m, тогда запись m[k] = t по смыслу эквивалентна

m.insert(make_pair(k, T())).first->second = t

Действительная реализация может быть эффективнее и не создавать лишний раз объект T (в коде выше — явный вызов конструктора по умолчанию T()). Если поведение operator[] представляется неудобным, то ему есть по крайней мере две альтернативы. Во-первых, можно использовать find, чтобы по ключу получить либо итератор, указывающий на соответствующую пару (ключ, значение), либо итератор end(), если ключа в словаре нет. Во-вторых, можно использовать функцию at, принимающую ключ и возвращающую ссылку на значение. В случае отсутствия искомого ключа в словаре at бросает исключение.

Упорядоченный словарь с неуникальными ключами <map> multimap не определяет operator[] и, по сути, напоминает multiset пар, поиск среди которых ведется только по первому полю (ключу). В качестве примера использования multimap рассмотрим задачу об обращении словаря, хранимого в текстовом файле. Для простоты положим, что словарь состоит из пар слов, упорядоченных по первому слову, слова могут повторяться.

// Тип "слово-перевод" (пара слов) -- элемент словаря.
using Entry = pair<string, string>;
// Тип "Словарь".
using Dictionary = multimap<string, string>;
// Ввод-вывод, переопределяем стандартные операторы ввода-вывода.
namespace std
{
  istream& operator>>(istream &is, Entry &en)
  {
    return is >> en.first >> en.second;
  }
  ostream& operator<<(ostream &os, const Entry &en)
  {
    return os << en.first << ' ' << en.second;
  }
  istream& operator>>(istream &is, Dictionary &d)
  {
    istream_iterator<Entry> begin(is), end;
    d = Dictionary(begin, end);
    return is;
  }
  ostream& operator<<(ostream &os, const Dictionary &d)
  {
    ostream_iterator<Entry> out(os, "\n");
    copy(d.begin(), d.end(), out);
    return os;
  }
}
// Операция обращения словаря. Порождает новый словарь по заданному словарю.
Dictionary reverse(const Dictionary &d)
{
  Dictionary result;
  for (const auto &el : d)
    result.emplace(el.second, el.first);
  return result;
}
// Чтение-обращение-запись.
void dictionary_reverse(istream &from, ostream &to)
{
  Dictionary read;
  from >> read;
  to << reverse(read);
}

К стандартным неупорядоченным ассоциативным контейнерам относятся классы-шаблоны unordered_set<K, H = hash<K>, E = equal_to<K>, A = allocator<K>>, unordered_map<K, T, H = hash<K>, E = equal_to<K>, A = allocator<pair<const K, T>>>, unordered_multiset, unordered_multimap. Они предоставляют похожую на аналогичные упорядоченные ассоциативные контейнеры функциональность.

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

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

При вставке большого количества элементов можно в нужный момент форсировать “рехэш” (увеличение объёма выделенного хранилища и перераспределения элементов, которое занимает значительное время), вызывая функцию rehash, что в некотором смысле напоминает reserve для vector.

Алгоритмы и функторы

Стандартная библиотека C++ содержит несколько десятков функций, называемых алгоритмами, оперирующих на наборах элементов, заданных диапазонами итераторов. Таким образом, итераторы выступают в качестве “клея”, соединяющего алгоритмы и контейнеры. Однако функционал алгоритмов был бы весьма ограничен, если бы не возможность задавать произвольные операции с помощью функторов.

Неупорядоченные ассоциативные контейнеры (хэш-таблицы) используют два функтора: компаратор, задающий отношение “равно”, и хэш, задающий способ вычисления хэш-функции для элементов контейнера, возвращающий целое число.

Большая часть стандартных алгоритмов определена в заголовочном файле <algorithm>. Далее приведен список некоторых стандартных алгоритмов с краткими описаниями.

Список стандартных алгоритмов

• copy(from, from_end, to) — копирует диапазон [from, from_end) в диапазон [to, to_end), в процессе вычисляя и возвращая итератор to_end, что позволяет конкатенировать последовательности цепным вызовом copy; например, чтобы получить конкатенацию [f1, e1) и [f2, e2), начинающуюся в d, вызовем copy(f2, e2, copy(f1, e1, d)).
• copy_if(from, from_end, to, pred) — отличается от copy тем, что копирует только те элементы, для которых предикат pred возвращает истину (“фильтр”).
• copy_n(from, count, to) — копирует диапазон [from, from + count) в [to, to + count). Возвращает вычисленный в процессе итератор to + count.
• copy_backward(from, from_end, to_end) — копирует элементы из диапазона [from, from_end) в диапазон [to, to_end), двигаясь от to_end назад. Возвращает to. Данный алгоритм не обращает порядок самих элементов, а отличается от copy тем, что сначала копирует последний элемент последовательности, а в конце — первый (copy — наоборот).
• move(from, from_end, to) — отличается от copy тем, что вместо копирования выполняет перемещение, поэтому элементы исходной последовательности [from, from_end) могут потерять исходные значения.
• move_backward(from, from_end, to_end) — отличается от move так же, как copy_backward отличается от copy.

В случае, если диапазон, занимаемый копируемой или перемещаемой последовательностью, пересекается с диапазоном-местом назначения копирования или перемещения, то следует выбирать move или copy для сдвига “назад” и move_backward или copy_backward для сдвига “вперёд”.

• swap_ranges(a, a_end, b) — последовательно обменивает содержимое элементов [a, a_end) и элементов [b, b_end), в процессе находя b_end. Возвращает b_end.

• fill(to, to_end, value) — записывает value в каждый элемент диапазона [to, to_end). Ничего не возвращает.
• fill_n(to, n, value) — записывает value в [to, to + n), возвращает (to + n), полученный в процессе. Значения n < 1 игнорируются.
• generate(to, to_end, gen) — заполняет [to, to_end) значениями, сгенерированными генератором gen; например, заполнить вектор v псевдослучайными числами можно так:

generate(v.begin(), v.end(), rand);

• generate_n(to, n, gen) — соответствует generate так же, как fill_n соответствует fill, например, вывести в cout семь псевдослучайных чисел можно так:

ostream_iterator<int> out_it(cout, " ");
generate_n(out_it, 7, rand);

• reverse(begin, end) — обращает последовательность [begin, end), выполняя серию обменов (по умолчанию с помощью std::swap).
• reverse_copy(from, from_end, to) — копирует последовательность [from, from_end) в обратном порядке в [to, to_end), возвращает значение to_end.
• rotate(begin, new_begin, end) — выполняет циклический сдвиг (“прокрутку” как закольцованной ленты) элементов последовательности [begin, end) таким образом, что new_begin становится новым началом, а элементы [begin, new_begin) попадают в конец; возвращает (begin + (end - new_begin)). Операцию rotate можно элегантно (хотя и не совсем оптимально) реализовать на основе обращения порядка элементов в поддиапазонах (через reverse):

template <class BidIt>
BidIt rotate(BidIt begin, BidIt new_begin, BidIt end)
{
  reverse(begin, new_begin);
  reverse(new_begin, end);
  reverse(begin, end);
  return next(begin, distance(new_begin, end));
}

• rotate_copy(from, new_begin, from_end, to) — копирует в [to, to_end) сначала кусок [new_begin, from_end), затем за ним — [from, new_begin). Возвращает вычисленный в процессе to_end.

• find(begin, end, value) — ищет среди элементов диапазона [begin, end) первое вхождение value, возвращает итератор, указывающий на найденное вхождение, либо end, если value не найдено.
• find_if(begin, end, pred) — отличается от find тем, что вместо поиска конкретного значения, выполняет поиск первого элемента, для которого выполняется предикат pred.
• find_if_not(begin, end, pred) — отличается от find_if тем, что выполняет поиск первого элемента, для которого не выполняется предикат pred.
• all_of(begin, end, pred) — возвращает истину, если все элементы [begin, end) удовлетворяют предикату pred. Эквивалент find_if_not(begin, end, pred) == end.
• any_of(begin, end, pred) — возвращает истину, если среди элементов [begin, end) найдётся хотя бы один, удовлетворяющий предикату pred. Эквивалент find_if(begin, end, pred) != end.
• none_of(begin, end, pred) — возвращает истину, если ни один из элементов [begin, end) не удовлетворяют предикату pred. Эквивалент !any_of(begin, end, pred).
• count(first, end, value) — считает, сколько элементов из [begin, end) равны value. Или, другими словами, сколько раз value встречается в диапазоне [begin, end).
• count_if(first, end, pred) — считает, для скольких элементов из [begin, end) выполняется предикат pred.
• search(a, a_end, s, s_end, eq) — ищет начало первой подпоследовательности [a, a_end), совпадающей с [s, s_end), используя отношение равенства, заданное двуместным предикатом eq.
• search_n(a, a_end, n, val, eq) — ищет начало первой подпоследовательности [a, a_end), состоящей из n идущих подряд элементов, равных val (в смысле предиката eq).
• find_end(begin, end, sub, sub_end, comp) — ищет в последовательности [begin, end) последнее вхождение подпоследовательности [sub, sub_end). Компаратор comp выполняет роль сравнения на равенство. Если его не указать, будет использоваться операция ==.
• find_first_of(begin, end, what, what_end, comp) — ищет в последовательности [begin, end) первое вхождение любого элемента из последовательности [what, what_end). Компаратор comp выполняет роль сравнения на равенство. Если его не указать, будет использоваться операция ==.
• adjacent_find(begin, end, comp) — пытается найти первый элемент из [begin, end) такой, что для него и следующего за ним элемента выполняется двуместный предикат comp. Возвращает позицию найденного элемента или end, если ничего не найдено. Существует также вариант adjacent_find(begin, end), использующий в качестве comp оператор равенства, т. е. возвращающий позицию первой пары равных элементов.

• mismatch(a, a_end, b, b_end, eq) — возвращает пару итераторов, указывающих на первые элементы [a, a_end) и [b, b_end), для которых компаратор eq возвращает ложь.
• equal(a, a_end, b, b_end, eq) — проверяет равенство последовательностей [a, a_end) и [b, b_end), оператор равенства задается предикатом eq; как и в других подобных случаях, есть вариант данного алгоритма без предиката, который использует оператор ==.
• lexicographical_compare(a, a_end, b, b_end, comp) — проверяет, меньше ли [a, a_end), чем [b, b_end), лексикографически, comp — компаратор элементов.
• max_element(begin, end, comp) — возвращает первое вхождение максимального элемента из [begin, end), comp задает компаратор. Существует вариант max_element(begin, end), использующий в качестве comp оператор меньше.
• min_element(begin, end, comp) — аналогичен max_element, но возвращает позицию первого минимального элемента. Пример использования min_element для реализации простейшей сортировки выбором минимального элемента (стандартная функция iter_swap выполняет обмен значений, на которые указывают переданные ей итераторы):

// Сортировка выбором минимума.
template <class FwdIt>
void min_select_sort(FwdIt from, FwdIt to)
{
  for (; from != to; ++from)
    iter_swap(from, min_element(from, to));
}

• minmax_element(begin, end, comp) — за один проход находит и минимальный, и максимальный элементы, возвращает пару итераторов, семантически близок, но не эквивалентен конструкции

make_pair(min_element(begin, end, comp),
          max_element(begin, end, comp));

Дело в том, что второй итератор в паре, возвращаемой minmax_element указывает не на первый максимальный элемент в диапазоне, а на последний максимальный элемент. Кроме того, minmax_element эффективнее, так как проходит по последовательности только один раз, а не два.

Пример сортировки выбором одновременно минимума и максимума:

// Сортировка выбором минимума и максимума.
template <class BidIt>
void minmax_select_sort(BidIt from, BidIt to)
{
  while (from != to)
  {
    const auto last = prev(to);
    if (from == last)
      return;
    const auto ab = minmax_element(from, to);
    if (from != ab.second)
    {
      iter_swap(from, ab.first);
      iter_swap(last, ab.second);
    }
    else
    {
      iter_swap(last, ab.second);
      if (ab.first != last)
        iter_swap(from, ab.first);
    }
    to = last;
    ++from;
  }
}

• for_each(begin, end, fun) — применяет функтор fun к каждому элементу из [begin, end), возвращает fun. В C++11 обычно проще для этой цели использовать цикл for(:).
• transform(from, from_end, to, fun) — применяет одноместный функтор к [from, from_end), записывая возвращаемые им значения в [to, to_end). Возвращает to_end.
• transform(a, a_end, b, to, fun) — применяет двуместный функтор к парам элементов из [a, a_end), [b, b_end), записывая возвращенные им значения в [to, to_end), возвращает to_end. Последовательности [a, a_end) и [b, b_end) должны быть одинаковой длины (поэтому b_end не фигурирует в списке параметров).
• replace(begin, end, old_val, new_val) — пробегает [begin, end) и заменяет каждое вхождение old_val на new_val.
• replace_if(begin, end, pred, new_val) — заменяет в [begin, end) на new_val все элементы, для которых истинен предикат pred.
• replace_copy(begin, end, to, old_val, new_val) — копирует в [to, to_end) последовательность [begin, end), заменяя каждое вхождение old_val (проверяет на равенство с помощью операции ==) на копию new_val. Возвращает вычисленный to_end.
• replace_copy_if(begin, end, to, pred, new_val) — копирующий аналог replace_if.

• remove(begin, end, value) — перемещает содержимое [begin, end) от конца к началу, затирая все вхождения value и возвращает конец новой последовательности (не содержащей value). Для реального удаления оставшегося “хвоста” из контейнера требуется вызвать функцию-член erase.
• remove_if(begin, end, pred) — действует аналогично remove, но затирает те элементы, для которых pred возвращает истину.
• remove_copy(begin, end, to, val) и remove_copy_if(begin, end, to, pred) — копируют исходные последовательности, пропуская заданные элементы (аналогично replace–replace_copy и replace_if–replace_copy_if).
• unique(begin, end, eq) — действует аналогично remove_if, но использует двуместный предикат eq, применяемый к парам подряд идущих элементов. Существует также вариант unique(begin, end), использующий в качестве eq оператор == и позволяющий удалять из последовательности идущие подряд дубликаты (откуда и происходит название функции).

При удалении элементов из контейнера с помощью алгоритмов remove, remove_if или unique требуется результат вызова алгоритма передать в функцию контейнера erase для удаления “хвоста”. На деле среди стандартных контейнеров эту схему эффективно можно применить лишь к deque и vector.

Следующий код считывает последовательность слов с потока ввода, сортирует слова, удаляет дубликаты и выводит полученную последовательность. Обратите внимание, что в нем не встречается ни одного ключевого слова C++.

vector<string> words;
// Считать слова с потока ввода в words.
copy(istream_iterator<string>(cin), istream_iterator<string>(), back_inserter(words));
cin.clear();
// Отсортировать слова.
sort(words.begin(), words.end());
// Удалить все повторения.
words.erase(unique(words.begin(), words.end()), words.end());
// Вывести результат в поток вывода.
copy(words.begin(), words.end(), ostream_iterator<string>(cout, " "));

• unique_copy(begin, end, to, pred) — копирует элементы, пропуская идущие подряд повторяющиеся значения (см. unique). Можно немного модифицировать предыдущий пример, убрав удаление дубликатов:

vector<string> words;
// Считать слова с потока ввода в words.
copy(istream_iterator<string>(cin), istream_iterator<string>(), back_inserter(words));
cin.clear();
// Отсортировать слова.
sort(words.begin(), words.end());
// Вывести результат в поток вывода, пропуская дубликаты.
unique_copy(words.begin(), words.end(), ostream_iterator<string>(cout, " "));

• binary_search(begin, end, val, comp) — выполняет проверку наличия в отсортированной последовательности [begin, end) (возвращает bool) значения, эквивалентного значению val в силу компаратора comp методом двоичного поиска. Если comp не указан, то используется операция <.
• lower_bound(begin, end, val, comp) — двоичным поиском на отсортированной в соответствии с компаратором comp последовательности [begin, end) находит первый элемент, который не меньше в смысле comp, чем val; возвращает соответствующий итератор, или end, если таковой не был найден. Есть вариант без параметра comp, использующий для сравнения элементов оператор <.
• upper_bound(begin, end, val, comp) — похож на lower_bound, но возвращает позицию первого элемента, который в смысле comp больше, чем val, либо end, если таковой не найден.
• equal_range(begin, end, val, comp) — находит диапазон элементов, эквивалентных val в смысле comp, по семантике то же, что и

make_pair(lower_bound(begin, end, val, comp),
          upper_bound(begin, end, val, comp));

• partition(begin, end, pred) — разделяет [begin, end) на два участка: [begin, par), для элементов которого предикат pred выполняется, и [par, end), для элементов которого pred не выполняется; возвращает точку разбиения par.

Пример использования partition.

Рекурсивная быстрая сортировка с выбором первого элемента диапазона в качестве опорного. Общий алгоритм выглядит следующим образом:

0. Если последовательность содержит менее двух элементов, то она уже отсортирована — ничего не делать.
1. Разбить последовательность на две половины: те, что меньше опорного элемента и те, что не меньше.
2. Отсортировать каждую половину.

// Рекурсивная быстрая сортировка с выбором первого элемента в качестве опорного.
// (Самый примитивный вариант.)
template <class FwdIt>
void quick_sort(FwdIt from, FwdIt to)
{
  if (from == to)
    return;
  // Запомнить ссылку на начальный элемент.
  auto &pivot = *from;
  auto from1 = next(from);
  if (from1 == to)
    return;
  // Выполнить разбиение остатка на тех, что меньше, и тех, что не меньше.
  auto part = partition(from1, to,
    [&](const auto &item) { return item < pivot; });
  // Дефектный случай: разделили диапазон на один элемент и все остальные.
  if (part == from1)
    return quick_sort(from1, to);
  // Поставить опорный элемент на соответствующее место.
  iter_swap(from, prev(part));
  // Отсортировать части разбиения.
  quick_sort(from, part);
  quick_sort(part, to);
}

См. также реализацию в “стиле C”.

• partition_copy(begin, end, true_begin, false_begin, pred) — выполняет “сепарацию” последовательности [begin, end) на элементы, удовлетворяющие предикату pred (копируются в диапазон [true_begin, true_end)), и на элементы, не удовлетворяющие этому предикату (копируются в диапазон [false_begin, false_end)). Возвращает пару вычисленных в процессе предикатов (true_end, false_end).
• stable_partition(begin, end, pred) — “устойчивый” аналог partition. Любая пара элементов, одновременно удовлетворяющих или одновременно неудовлетворяющих предикату pred, сохраняет расположение относительно друг друга после выполнения stable_partition. К сожалению, это может приводить к значительному падению скорости относительно неустойчивого partition, который не даёт гарантии сохранения относительного порядка.
• partition_point(begin, end, pred) — если диапазон [begin, end) можно представить в виде двух диапазонов [begin, pp) и [pp, end) таких, что для каждого элемента из первого диапазона pred возвращает истину, и для каждого элемента второго диапазона pred возвращает ложь, то функция partition_pointалгоритмом двоичного поиска находит и возвращает значение итератора pp.
• is_partitioned(begin, end, pred) — проверяет, можно ли представить диапазон [begin, end) в виде двух диапазонов [begin, pp) и [pp, end) таких, что для каждого элемента из первого диапазона pred возвращает истину, и для каждого элемента второго диапазона pred возвращает ложь.

• is_permutation(a, a_end, b, b_end, eq) — проверяет, является ли последовательность [a, a_end) перестановкой последовательности [b, b_end). Компаратор eq задаёт способ сравнения элементов на равенство. Если его не указать, используется ==. В худшем случае для проверки требуется квадратичное время.
• next_permutation(begin, end, comp) — переставить элементы последовательности [begin, end) так, чтобы получить ближайшую следующую перестановку. Под следующей понимается та перестановка, которая лексикографически больше исходной в силу компаратора comp (если его не указать, используется <). Возвращает истину в случае осуществления перестановки и ложь, если следующей перестановки не существует.
• prev_permutation(begin, end, comp) — действие обратно next_permutation.
• shuffle(begin, end, rng) — выполняет случайную перестановку элементов диапазона [begin, end), используя генератор (псевдо)случайных чисел rng. Требуются итераторы произвольного доступа. Пример использования с одним из стандартных генераторов псевдослучайных чисел:

#include <random> // mt19937
template <class RanIt>
void random_shuffle(RanIt from, RanIt to)
{
  std::mt19937 rng(to - from);
  std::shuffle(from, to, rng);
}

• sort(begin, end, comp) — сортирует [begin, end) на месте за линейно-логарифмическое время в соответствии с компаратором comp (неустойчивая сортировка; как правило, это гибридный алгоритм на основе быстрой, пирамидальной сортировок и сортировки вставками). Алгоритмы сортировки требуют итераторы произвольного доступа. Алгоритмы поиска и сортировки, принимающие компаратор, также существуют в вариантах, где comp не передается, а в качестве компаратора используется оператор <, например, sort(begin, end) сортирует по возрастанию.
• is_sorted(begin, end, comp) — проверяет, отсортирована ли последовательность [begin, end) в силу компаратора comp. Если comp не указан, то используется операция <, т. е. выполняется проверка на отсортированность по возрастанию.
• is_sorted_until(begin, end, comp) — находит первую позицию, нарушающую сортировку последовательности [begin, end) в силу компаратора comp. Если comp не указан, то используется операция <.
• stable_sort(begin, end, comp) — отличается от sort тем, что гарантирует устойчивость (сохраняет исходный порядок эквивалентных элементов), однако работает несколько медленнее (обычно в 1.5–3 раза).
• partial_sort(begin, mid, end, comp) — выполняет частичную сортировку [begin, end) так, что участок [begin, mid) представляет собой начало отсортированной последовательности, а порядок элементов “хвоста” [mid, end) не определен.
• partial_sort_copy(begin, end, to, to_end, comp) — заполняет диапазон [to, to_end) начальным участком сортировки [begin, end). Итераторы begin и end могут быть итераторами ввода (т. е. исходная последовательность просматривается лишь однажды), а итераторы to, to_end должны быть итераторами произвольного доступа. Возвращает конец отсортированной последовательности: если в исходной последовательности элементов не меньше, чем to_end - to, то это to_end, иначе — to + distance(begin, end).
• nth_element(begin, nth, end, comp) — выполняет частичную сортировку [begin, end), пока в [begin, nth) не окажутся элементы, которые не больше любых элементов из [nth, end), а на позиции nth — тот элемент, который бы там стоял, если бы мы отсортировали последовательность “по-честному”. В отличие от сортировки, данный алгоритм выполняется за линейное время. Типичный пример использования — определение медианного значения последовательности.

• merge(a, a_end, b, b_end, to, comp) — сливает две заранее отсортированные последовательности [a, a_end) и [b, b_end), копируя элементы в [to, to_end), находит и возвращает to_end. После выполнения слияния, новая последовательность также является отсортированной и содержит все элементы двух исходных последовательностей. Существует вариант без comp, использующий операцию <.

Пример использования merge.

Рекурсивная нисходящая сортировка слияниями. Общий алгоритм выглядит следующим образом:

0. Если последовательность содержит менее двух элементов, то она уже отсортирована — ничего не делать.
1. Разбить последовательность на две половины.
2. Отсортировать каждую половину.
3. Выполнить слияние двух отсортированных половин. Результат — отсортированная исходная последовательность.

// Рекурсивная сортировка слияниями с внешним буфером достаточного размера.
// size -- количество элементов в диапазоне [from, to) и размер буфера.
template <class FwdIt, class T, class SizeT>
void merge_sort(FwdIt from, FwdIt to, T *buffer, SizeT size)
{
  switch (size)
  {
  case 0: case 1: return;
  case 2: // Случай, когда элементов всего два.
    {
      const auto other = next(from);
      if (*other < *from)
        iter_swap(from, other);
    }
    return;
  default:
    {
      const auto
        first_half_size = size / 2,
        second_half_size = size - first_half_size;
      const auto mid = next(from, first_half_size);
      // Сортировка половинок.
      merge_sort(from, mid, buffer, first_half_size);
      merge_sort(mid, to, buffer, second_half_size);
      // Слияние половинок с перемещением в буфер.
      const auto buffer_end = merge(
        make_move_iterator(from), make_move_iterator(mid),
        make_move_iterator(mid), make_move_iterator(to),
        buffer);
      // Перемещение обратно из буфера объединённой последовательности.
      move(buffer, buffer_end, from);
    }
  }
}
// Сортировка слияниями с автоматическим созданием буфера.
template <class FwdIt>
void merge_sort(FwdIt from, FwdIt to)
{
  using value_type = typename
    iterator_traits<FwdIt>::value_type;
  const auto size = distance(from, to);
  auto buffer = make_unique<value_type[]>(size);
  merge_sort(from, to, buffer.get(), size);
}

См. также реализацию в “стиле C”.

• inplace_merge(a, a_mid, a_end, comp) — слияние двух отсортированных соседних участков [a, a_mid) и [a_mid, a_end) в одну отсортированную последовательность [a, a_end) “на месте”. Функция ничего не возвращает. Вариант без comp использует для сравнения элементов операцию <. Если данный алгоритм сможет выделить промежуточный буфер в процессе работы, то он затратит линейное по размеру всей последовательности время. В противном случае ему понадобится линейно-логарифмическое время. Поэтому вариант сортировки слияниями на основе этого алгоритма может оказаться несколько медленнее обычной сортировки слияниями.

// Рекурсивная сортировка слияниями "на месте".
// size -- количество элементов в диапазоне [from, to)
template <class BidIt, class SizeT>
void inplace_merge_sort(BidIt from, BidIt to, SizeT size)
{
  switch (size)
  {
  case 0: case 1: return;
  case 2: // Случай, когда элементов всего два.
    {
      const auto other = next(from);
      if (*other < *from)
        iter_swap(from, other);
    }
    return;
  default:
    {
      const auto
        first_half_size = size / 2,
        second_half_size = size - first_half_size;
      const auto mid = next(from, first_half_size);
      // Сортировка половинок.
      inplace_merge_sort(from, mid, first_half_size);
      inplace_merge_sort(mid, to, second_half_size);
      // Слияние половинок с перемещением в буфер.
      inplace_merge(from, mid, to);
    }
  }
}
template <class BidIt>
void inplace_merge_sort(BidIt from, BidIt to)
{
  inplace_merge_sort(from, to, distance(from, to));
}

• includes(a, a_end, b, b_end, comp) — предполагая, что последовательности [a, a_end) и [b, b_end) отсортированы, проверяет, что все элементы второй содержатся в первой;
• set_difference(a, a_end, b, b_end, to, comp) — предполагая, что последовательности [a, a_end) и [b, b_end) отсортированы в силу компаратора comp, строит теоретико-множественную разность [a, a_end) и [b, b_end), записывая результат в [to, to_end), возвращает to_end.
• set_intersection(a, a_end, b, b_end, to, comp) — действует аналогично set_difference, но строит теоретико-множественное пересечение.
• set_union(a, a_end, b, b_end, to, comp) — действует аналогично set_difference, но строит теоретико-множественное объединение, в отличие от merge не сохраняет дубликаты.
• set_symmetric_difference(a, a_end, b, b_end, to, comp) — действует аналогично set_difference, но строит симметрическую разность.

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

• make_heap(begin, end, comp) — переставляет содержимое [begin, end) так, чтобы получалась двоичная куча, упорядоченная в соответствии с порядком, задаваемым компаратором comp.
• sort_heap(begin, end, comp) — сортирует кучу [begin, end). Комбинация make_heap + sort_heap позволяет легко реализовать средствами Стандартной библиотеки C++ алгоритм сортировки, известный как пирамидальная сортировка.

// Пирамидальная сортировка.
template <class RanIt>
void heap_sort(RanIt from, RanIt to)
{
  make_heap(from, to);
  sort_heap(from, to);
}

• push_heap(begin, end, comp) — добавить в двоичную кучу [begin, end-1) элемент, стоящий в позиции (end-1). После этого двоичной кучей становится весь диапазон [begin, end). Функцию make_heap можно было бы реализовать так:

template <class RanIt, class Comp>
void make_heap(RanIt from, RanIt to, Comp comp)
{
  if (to - from < 2)
    return;
  auto bound = from;
  do push_heap(from, ++bound, comp);
  while (bound != end);
}

• pop_heap(begin, end, comp) — перемещает максимальный в силу компаратора comp элемент непустой двоичной кучи [begin, end) в позицию (end-1). После этого элементы диапазона [begin, end-1) составляют двоичную кучу.
• is_heap(begin, end, comp) — проверяет, является ли диапазон [begin, end) двоичной кучей в силу компаратора comp.
• is_heap_until(begin, end, comp) — находит в диапазоне [begin, end) наибольший субдиапазон [begin, hp) такой, что [begin, hp) является двоичной кучей в силу компаратора comp. Возвращает hp.

Ряд “вычислительных” стандартных алгоритмов определен в заголовочном файле <numeric>. Перечислим их.

• iota(begin, end, val) — заполняет [begin, end) последовательно инкрементируемыми значениями val. Например, присвоить элементам вектора v значения, равные их индексам, можно вызовом iota(v.begin(), v.end(), 0).
• accumulate(begin, end, s0, adder) — накапливает сумму элементов [begin, end), начиная с s0 и добавляя элементы к накопленной сумме. По умолчанию в качестве adder используется оператор +. Так, посчитать сумму элементов контейнера v можно вызовом accumulate(v.begin(), v.end(), 0), а если мы хотим произведение, то запишем

accumulate(v.begin(), v.end(), 1, multiplies<>())

• inner_product(a, a_end, b, s0, adder, mult) — вычисляет внутреннее (скалярное) произведение двух последовательностей [a, a_end), [b, b_end) равной длины, которое определяется как сумма (задается adder, по умолчанию +) s0 и попарных произведений элементов последовательностей (задается mult, по умолчанию *); внутреннее произведение можно использовать нетривиально: например, пусть многоугольник задан контейнером c, содержащим точки, для которых определена операция dist, возвращающая расстояние, тогда периметр многоугольника можно посчитать вызовом

inner_product(next(c.begin()), c.end(), c.begin(),
  dist(c.front(), c.back()), plus<>(), dist)

• adjacent_difference(begin, end, to, diff) (дельта-кодирование) — записывает в [to, to_end) разности (задается diff, по умолчанию -) соседних элементов из [begin, end), при этом вначале выполняет *to = *begin, поэтому to_end отстоит от to на столько же шагов, насколько end отстоит от begin. Возвращает to_end.
• partial_sum(begin, end, to, adder) (дельта-декодирование) — записывает в [to, to_end) частичные суммы, накопленные при суммировании элементов [begin, end), т.~е. (условно) to[0] = begin[0]; to[i] = adder( to[i-1], begin[i]).

Средства конструирования функторов

Заголовочный файл <functional> содержит ряд классов-шаблонов, являющихся функторами-обёртками соответствующих операций: компараторы less (операция ‘<’), greater (операция ‘>’), less_equal (операция ‘<=’), greater_equal (операция ‘>=’), equal_to (операция ‘==’), not_equal_to (операция ‘!=’), двуместные операции plus (операция ‘+’), minus (операция ‘-’), multiplies (операция ’*’) и т.д. Например, отсортировать vector<int> v по убыванию можно так:

sort(v.begin(), v.end(), greater<>());

Все эти операции являются шаблонами, принимающими тип аргумента. Если его не указывать, он будет выводиться автоматически в месте применения (C++14).

Кроме того, <functional> предоставляет средство для оборачивания функций-членов mem_fn, средство связывания параметров функтора bind и контейнер произвольного функтора function.

Рассмотрим пример с использованием mem_fn. Допустим, требуется убрать из вектора strings все пустые строки. Строка std::string имеет функцию-член empty, которая выступает в роли предиката, но не может быть вызвана как свободная функция, принимающая const string&. Обёртка позволяет решить эту проблему: новый функтор будет принимать в качестве первого параметра ссылку или указатель на объект.

strings.erase(
  remove_if(strings.begin(), strings.end(), mem_fn(&string::empty)),
  strings.end());

Функция bind принимает базовый функтор и набор параметров, ему передаваемых при вызове обертки. При передаче значения его копия сохраняется в обёртке и передается при каждом вызове. Чтобы сохранить параметр по ссылке, следует использовать функции ref и cref (const-ссылка). Чтобы связать параметр, передаваемый в базовый функтор с параметром, принимаемым обёрткой, нужно указать местодержатель, имеющий вид placeholders::_n, где n — число (обязательно поддерживаются значения 1 и 2), задающее порядковый номер параметра обёртки (отсчитывается, начиная с единицы). Например, получить удвоенную последовательность v2 из v1 (считая, что они одинаковой длины), содержащей значения типа float, можно следующим образом:

transform(v1.begin(), v1.end(), v2.begin(),
  bind(multiplies<float>(), 2.f, placeholders::_1));

Впрочем, многие подобные применения на деле проигрывают в краткости и понятности записи циклу for(:). Например, удвоение каждого элемента контейнера v1 “на месте”:

for (auto &x: v1)
  x *= 2.f;

Другой пример: добавим в конец каждой строки из диапазона [from, to) другую строку suffix, которую передадим обёртке по ссылке, воспользовавшись функцией cref.

for_each(from, to, bind(mem_fn(&string::append),
  placeholders::_1, cref(suffix)));

На деле возможности mem_fn и bind довольно ограничены. Наиболее сильным средством, появившимся в ISO C++11, являются замыкания — объекты анонимных функторов, создаваемые в месте использования с помощью лямбда-выражений. Структура лямбда-выражения слагается из следующих элементов:

• [ перечисление захваченных замыканием переменных ]. Если функтор не нуждается ни в каких внешних переменных, то следует оставить внутренность пустой: []. Указание [=] предписывает компилятору помещать в замыкание копию каждой упомянутой в теле замыкания внешней переменной. Указание [&] предписывает компилятору помещать в замыкание не копии, а ссылки на переменные, а, например, указание [=, &s] предписывает помещать копии на все переменные, кроме s, которая будет захвачена по ссылке. Если не поставить перед именем знак &, то переменная будет скопирована. Наконец, если замыкание создаётся функцией-членом некоторого объекта, то в скобки можно поставить слово this как имя особой переменной: [this], это позволяет получить изнутри доступ к открытым (public) членам этого объекта как из функции-члена (но только к открытым).
• ( параметры функтора ) — список параметров, оформляется так же, как у обычной функции. Можно не указывать, если параметров нет. Вместо конкретного типа параметра можно указывать auto для передачи по значению, auto& для передачи по ссылке или auto&& для передачи по значению временных объектов и по ссылке — переменных.
• mutable — указывается, чтобы разрешить замыканию модификацию захваченных по значению переменных. Необязательный элемент: если он отсутствует, то все захваченные замыканием копии переменных будут считаться константами.
• -> возвращаемый тип — описание возвращаемого замыканием типа. Если не указать, то компилятор попытается вывести тип автоматически.
• { тело функции } — собственно тело функции.

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

transform(v1.begin(), v1.end(), v2.begin(),
    [](float x) { return 2.f * x; });
for_each(begin, end, [&suffix](string &s)
    { s.append(suffix); });

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

Еще одним важным элементом <functional> является класс-шаблон function<T(Args...)>. В качестве параметра шаблона передается функциональный тип, указывающий возвращаемый тип и сигнатуру некоторой функции.

Данный класс позволяет разместить в своем объекте произвольный функтор с подходящей сигнатурой (в том числе замыкание), а также указатель на функцию. Таким образом, за счет увеличения накладных расходов по памяти (может быть выделен блок динамической памяти) и процессорному времени при вызове (дополнительные косвенные обращения) достигается максимально возможная гибкость. Данный класс-шаблон может быть использован при реализации, например, паттерна “наблюдатель” для привязки обработчиков сообщений, заданных в произвольной форме. Узнать, что лежит внутри объекта function, можно с помощью функций target<T> и target_type. Первая возвращает указатель на хранимый объект T, если он имеет такой тип, либо nullptr в противном случае. Вторая возвращает type_info, описывающий тип хранимого объекта. Объект function может быть “пуст”, если к нему не привязали функтор или функцию. Проверить это можно, приведением к bool или с помощью операции !.

Пример — динамический массив

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

Версия 4

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

template <class T>
class Darr
{
public:
  // Совместимость со стандартными контейнерами.
  using value_type = T;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
  using reference = value_type&;
  using const_reference = const value_type&;
  using pointer = value_type*;
  using const_pointer = const value_type*;
private:
  std::unique_ptr<T[]> dt; // data
  size_type sz;            // size
public:
  // Конструкторы.
  explicit
  Darr(size_type n = 0)
    : dt(n ? std::make_unique<T[]>(n) : nullptr), sz(n) {}
  Darr(size_type n, const_reference val)
    : Darr(n)
  {
    fill(val);
  }
  Darr(const_pointer arr, size_type n): Darr(n)
  {
    const auto dp = data();
    for (size_type i = 0; i < n; ++i)
      dp[i] = arr[i];
  }
  Darr(const Darr<T> &other)
    : Darr(other.data(), other.size()) {}
  // Перемещающий конструктор (из временного объекта).
  Darr(Darr<T> &&other) = default;
  // Перемещающий оператор присваивания.
  Darr<T>& operator=(Darr<T> &&other) = default;
  // Копирующее присваивание.
  Darr<T>& operator=(const Darr<T> &other)
  {
    Darr<T>(other).swap(*this);
    return *this;
  }
  // Заполнить весь массив копиями одного значения.
  void fill(const_reference val)
  {
    const auto dp = data();
    for (size_type i = 0; i < sz; ++i)
      dp[i] = val;
  }
  // Освободить память.
  void clear() { dt.reset(); sz = 0; }
  // Обменять содержимое двух объектов Darr.
  void swap(Darr<T> &other)
  {
    using std::swap;
    swap(dt, other.dt);
    swap(sz, other.sz);
  }
  // Проверить на пустоту -- изменено.
  bool empty() const { return !dt; }
  // Узнать размер массива -- изменено.
  size_type size() const { return dt? sz: 0; }
  // Прямой доступ к хранимому массиву -- изменено.
  pointer data() { return dt.get(); }
  const_pointer data() const { return dt.get(); }
  // Обращение к элементу по индексу.
  reference operator[](size_type idx)
  {
    assert(idx < size());
    return dt[idx];
  }
  const_reference operator[](size_type idx) const
  {
    assert(idx < size());
    return dt[idx];
  }
  // Доступ к первому и последнему элементам.
  reference front()
  {
    assert(!empty());
    return *data();
  }
  const_reference front() const
  {
    assert(!empty());
    return *data();
  }
  reference back()
  {
    assert(!empty());
    return dt[sz - 1];
  }
  const_reference back() const
  {
    assert(!empty());
    return dt[sz - 1];
  }
  // Итераторы.
  using iterator = pointer;
  using const_iterator = const_pointer;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
  iterator begin() { return data(); }
  const_iterator begin() const { return data(); }
  const_iterator cbegin() const { return begin(); }
  iterator end() { return data() + size(); }
  const_iterator end() const { return data() + size(); }
  const_iterator cend() const { return end(); }
  reverse_iterator rbegin() { return{ end() }; }
  const_reverse_iterator rbegin() const { return{ end() }; }
  const_reverse_iterator crbegin() const { return rbegin(); }
  reverse_iterator rend() { return{ begin() }; }
  const_reverse_iterator rend() const { return{ begin() }; }
  const_reverse_iterator crend() const { return rend(); }
};

Определим операторы сравнения массивов на равенство и неравенство (поэлементное):

// Сравнение на равенство.
template <class T1, class T2>
bool operator==(const Darr<T1> &a, const Darr<T2> &b)
{
  const auto sz = a.size();
  if (sz != b.size())
    return false;
  const auto ap = a.data();
  const auto bp = b.data();
  for (std::size_t i = 0; i < sz; ++i)
    if (ap[i] != bp[i])
      return false;
  return true;
}
// Сравнение на неравенство.
template <class T1, class T2> inline
bool operator!=(const Darr<T1> &a, const Darr<T2> &b)
{
  return !(a == b);
}

C++, HTML

Версия 5

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

  // Инициализировать значениями из диапазона, заданного итераторами
  template <class FwdIt>
  Darr(FwdIt from, FwdIt to)
    : Darr(std::distance(from, to))
  {
    const auto dp = data();
    for (size_type i = 0; i < sz; ++i, ++from)
      dp[i] = *from;
  }

  // Инициализировать значениями из диапазона, заданного итераторами
  template <class FwdIt>
  Darr(FwdIt from, FwdIt to,
    std::enable_if_t<  // годится только для случая, когда FwdIt является прямым итератором.
      std::is_convertible<
        typename std::iterator_traits<FwdIt>::iterator_category,
        std::forward_iterator_tag>::value, int> = 0)
    : Darr(std::distance(from, to))
  {
    const auto dp = data();
    for (size_type i = 0; i < sz; ++i, ++from)
      dp[i] = *from;
  }

Массивы (особенно в тестовом коде) удобно инициализировать как статические массивы в C с помощью {}-инициализатора. К сожалению, данная конструкция не была введена в язык C++ как нормальный терм выражения (не имеет типа данных), однако введена ограниченная симуляция такого поведения, доступ к которой можно получить с помощью стандартного шаблона-класса initializer_list, определённого в одноимённом заголовочном файле (initializer_list).

Чтобы разрешить код вида

Darr<int> a = { 1, 2, 3 };

следует определить конструктор, принимающий initializer_list<T>:

  // Инициализировать {}-списком.
  explicit
  Darr(std::initializer_list<T> il)
    : Darr(std::begin(il), std::end(il)) {}

Более того, можно реализовать код вида

// Darr<int> a;
a = { 5, 6, 7 };

перегрузив оператор присваивания:

  // Присвоить {}-список.
  Darr<T>& operator=(std::initializer_list<T> il)
  {
    return *this = Darr<T>(il);
  }

Код целиком:

C++, HTML

Версия 6

Добавим функцию at (как в vector), бросающую исключение в случае попытки получить доступ по несуществующему индексу. Чтобы не дублировать код (const и не-const версии at), вынесем проверку и бросание исключения в отдельную private-функцию:

  void check_index(size_type idx)
  {
    if (sz <= idx)
      throw std::out_of_range("Darr: array index out of range");
  }

Теперь легко определить at:

  // Обращение к элементу по индексу с проверкой индекса.
  reference at(size_type idx)
  {
    check_index(idx);
    return dt[idx];
  }
  const_reference at(size_type idx) const
  {
    check_index(idx);
    return dt[idx];
  }

Заменим циклы в коде версии 5 на стандартные алгоритмы.

  Darr(size_type n, const_reference val): Darr(n)
  {
    fill(val);
  }
  Darr(const_pointer arr, size_type n): Darr(n)
  {
    std::copy_n(arr, n, data());
  }
  // Заполнить весь массив копиями одного значения.
  void fill(const_reference val)
  {
    std::fill_n(data(), size(), val);
  } 

То же сделаем и во внешних операторах сравнения (добавим также лексикографическое сравнение на меньше, больше и т. д.):

// Сравнение на равенство.
template <class T1, class T2>
bool operator==(const Darr<T1> &a, const Darr<T2> &b)
{
  return std::equal(a.begin(), a.end(), b.begin(), b.end());
}
// Сравнение на неравенство.
template <class T1, class T2> inline
bool operator!=(const Darr<T1> &a, const Darr<T2> &b)
{
  return !(a == b);
}
// Лексикографическое сравнение.
template <class T1, class T2>
bool operator<(const Darr<T1> &a, const Darr<T2> &b)
{
  return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}
template <class T1, class T2> inline
bool operator<=(const Darr<T1> &a, const Darr<T2> &b)
{
  return !(b < a);
}
template <class T1, class T2> inline
bool operator>(const Darr<T1> &a, const Darr<T2> &b)
{
  return b < a;
}
template <class T1, class T2> inline
bool operator>=(const Darr<T1> &a, const Darr<T2> &b)
{
  return !(a < b);
}