Контейнеры, итераторы, функторы, алгоритмы

Кувшинов Д.Р.

2016

Общее оглавление

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

Контейнер container — класс, объекты которого способны хранить набор однотипных значений (обобщение понятия “массив”). Контейнер предоставляет средства доступа к своему содержимому. В Стандартной библиотеке C++ эти средства доступа строятся на обобщении понятия “указатель на элемент массива”, которое носит название итератор iterator.

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

Последовательность может представлять собой контейнер, часть контейнера, массив, файл или генерироваться “на ходу”.

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

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++ определены “категории итераторов”. Принадлежность итератора той или иной категории определяется набором поддерживаемых им операций.

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

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

Итератор ввода input iterator предназначен только для однократного чтения (ввода) последовательности значений.

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

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

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

Итератор вывода output iterator предназначен только для однократной записи (вывода) последовательности. В остальном аналогичен итератору ввода.

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

*it++ = value;


Однонаправленный итератор forward iterator является расширением концепции “итератор ввода”, т.е. предоставляет возможности итератора ввода (и, возможно, но не гарантированно, итератора вывода). Кроме того, однонаправленный итератор допускает многократное чтение и запись линейной последовательности, по которой можно двигаться только в одну сторону (как по односвязному списку — “вперёд” с помощью операции ++).

Двунаправленный итератор bidirectional iterator является расширением концепции “однонаправленный итератор”. Двунаправленный итератор допускает движение в двух направлениях: вперед (с помощью ++) и назад (с помощью операции --).

Итератор произвольного доступа random access iterator является расширением концепции “двунаправленный итератор” и наиболее похож по своему поведению на обычный указатель на элемент массива (который является частным случаем итератора произвольного доступа).

Итератор произвольного доступа допускает адресацию по индексу (оператор []), сдвиг в обе стороны на некоторое количество позиций (добавление и вычитание целого числа), вычисление расстояния с помощью вычитания и сравнение на “меньше” и “больше” (согласованное с расстоянием, которое имеет знак).

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


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

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

Классом характеристик traits class называют класс-шаблон, предоставляющий для своего параметра набор некоторых базовых определений, как правило типов и констант, которые некоторым образом характеризуют тип, подставленный в класс характеристик в качестве параметра шаблона.

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

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

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


Класс 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. Особенность односвязного списка состоит в том, что элементы можно добавлять и удалять только после заданной позиции:

Имеется дополнительная фиктивная позиция “перед первым элементом”, возвращаемая функциями 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++ также является поддержка более высокоуровневых операций, что проистекает из невозможности эффективного использования одних только итераторов для реализации этих операций:

В целом данные функции аналогичны соответствующим стандартным алгоритмам (см. их список в соответствующем разделе ниже), но выполняются как минимум быстрее, а как максимум — просто выполняются, потому что та же стандартная универсальная сортировка 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 заполняет массив копиями переданного значения.


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

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

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

Все упорядоченные контейнеры предоставляют доступ к элементам через двунаправленные итераторы и позволяют найти позицию первого элемента, не меньшего искомого, с помощью функции 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);
}

Перегрузки операций << и >> помещены в пространство имён std из-за особенностей связывания имён в C++. Дело в том что используются объекты типов istream_iterator и ostream_iterator, определённые в std, поэтому они “видят” определения операций << и >>, также определённые в std (ввод-вывод встроенных и стандартных типов, вроде int и string), которые “затеняют” определения из глобального пространства имён.


Подумайте, как можно переделать пример с обращением словаря, чтобы не пришлось хранить одни и те же слова дважды (предполагая, что прочитанный словарь нам больше не требуется и его можно уничтожить в процессе обращения)?


Неупорядоченные контейнеры <unordered_set>, <unordered_map> построены на хэш-таблице (обычно это хэш-таблица списков эквивалентных элементов — блоков или “бакетов” bucket) и опираются на некоторую хэш-функцию (по умолчанию std::hash<T> из <functional>, определённую для ряда стандартных типов) и операцию “равно” (по умолчанию используется оператор ==).

Два элемента считаются эквивалентными, если их хэши равны и операция “равно” возвращает истину. Неупорядоченные контейнеры предоставляют доступ к элементам через однонаправленные итераторы.

К стандартным неупорядоченным ассоциативным контейнерам относятся классы-шаблоны 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++ содержит несколько десятков функций, называемых алгоритмами, оперирующих на наборах элементов, заданных диапазонами итераторов. Таким образом, итераторы выступают в качестве “клея”, соединяющего алгоритмы и контейнеры. Однако функционал алгоритмов был бы весьма ограничен, если бы не возможность задавать произвольные операции с помощью функторов.

Функтором или функциональным объектом functor, function object в C++ называют класс, объекты которого можно использовать “как функции”. Технически это оформляется с помощью перегрузки operator(). Данный “оператор” является единственным оператором C++, допускающим перегрузку с произвольной сигнатурой, поэтому объекты функтора могут имитировать произвольные функции. Соответственно о функторах часто говорят как о функциях: “функтор вызывается”, “функтор принимает и возвращает значения” и т. п. Кроме того, обычные функции, передаваемые по указателю, могут считаться частным случаем функторов, поскольку могут быть использованы в тех же контекстах.

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

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

Обычно предикаты являются одноместными (унарными), т. е. принимают один параметр.

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

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

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


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

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


generate(v.begin(), v.end(), rand);
ostream_iterator<int> out_it(cout, " ");
generate_n(out_it, 7, rand);


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));
}



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



При удалении элементов из контейнера с помощью алгоритмов 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, " "));
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, " "));


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


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

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

  1. Если последовательность содержит менее двух элементов, то она уже отсортирована — ничего не делать.
  2. Разбить последовательность на две половины: те, что меньше опорного элемента и те, что не меньше.
  3. Отсортировать каждую половину.
// Рекурсивная быстрая сортировка с выбором первого элемента в качестве опорного.
// (Самый примитивный вариант.)
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”.


#include <random> // mt19937

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



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

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

  1. Если последовательность содержит менее двух элементов, то она уже отсортирована — ничего не делать.
  2. Разбить последовательность на две половины.
  3. Отсортировать каждую половину.
  4. Выполнить слияние двух отсортированных половин. Результат — отсортированная исходная последовательность.
// Рекурсивная сортировка слияниями с внешним буфером достаточного размера.
// 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”.

// Рекурсивная сортировка слияниями "на месте".
// 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));
}


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

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


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

accumulate(v.begin(), v.end(), 1, multiplies<>())
inner_product(next(c.begin()), c.end(), c.begin(),
  dist(c.front(), c.back()), plus<>(), dist)


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

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

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

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;
  }

К сожалению, шаблоны конструкторов могут порождать неожиданные проблемы: например, “затенять” некоторые другие конструкторы. Кроме того, мы бы хотели применять данный конструктор только в том случае, если FwdIt — прямой итератор. Итератор ввода уже не годится. Этого можно добиться с помощью правил C++ (SFINAE: substitution failure is not an error — ошибка в сигнатуре функции-шаблона при подстановке параметров шаблонов не приводит к ошибке компиляции, а приводит лишь к исключению данного варианта функции из набора перегруженных функций) и стандартных компонент из заголовочного файла <type_traits>. Результат выглядит несколько страшновато, тем не менее, он вполне “читаемый”:

  // Инициализировать значениями из диапазона, заданного итераторами
  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);
}

Код целиком:

C++, HTML


Общее оглавление

Кувшинов Д.Р. © 2016