2, [1,2,3] и 3, [1,2,3].

Шаги 2 и 3 выполняются с помощью call_cart:

auto call_cart ([](auto f, auto x, auto ...rest) constexpr {

  (void)std::initializer_list<int>{

    (((x < rest)

       ? (void)f(x, rest)

       : (void)0)

    ,0)...

  }

});

Параметр x всегда содержит одно значение, взятое из множества, а rest включает все множество. Опустим условие (x < rest). Здесь выражение f(x, rest) и распакованный набор параметров ... генерируют вызовы функции f(1, 1), f(1, 2) и т.д., что приводит к появлению пар на экране. Это был шаг 2.

Шаг 3 достигается за счет фильтрации всех пар, к которым применяется условие

(x < rest)

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

Глава 5

Основы работы с алгоритмами STL

В этой главе:

□ копирование элементов из одних контейнеров в другие;

□ сортировка контейнеров;

□ удаление конкретных элементов из контейнеров;

□ преобразование содержимого контейнеров;

□ поиск элементов в упорядоченных и неупорядоченных векторах;

□ ограничение допустимых значений вектора конкретным численным диапазоном с помощью std::clamp;

□ определение шаблонов в строках с помощью std::search и выбор оптимальной реализации;

□ выборка данных из крупных векторов;

□ создание перестановок во входных последовательностях;

□ реализация инструмента для слияния словарей. 

Введение

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

Рассмотрим стандартную задачу, например сложение элементов вектора. Это можно без труда сделать с помощью цикла, в котором мы суммируем все элементы вектора и поместим их в переменную-аккумулятор sum:

vector<int> v {100, 400, 200 /*, ... */ };

int sum {0};

for (int i : v) { sum += i; }

cout << sum << 'n';

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

cout << accumulate(begin(v), end(v), 0) << 'n';

В таком случае при создании вручную цикл занимает не намного больше места и прочесть его не сложнее, чем одну строку, в которой говорится, что она делает: accumulate. Во многих ситуациях, однако, может возникнуть неловкий момент: приходится читать состоящий из десятка строк цикл только затем, чтобы узнать, что он решает стандартную задачу Х, вместо того чтобы увидеть одну строку кода, в которой используется стандартный алгоритм, чье имя явно указывает на то, какую задачу он решает, например accumulate, copy, move, transform или shuffle.

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

Еще одним важным качеством алгоритмов STL является эффективность. Многие из них предоставляют несколько специализированных реализаций одного алгоритма, по-разному решающих задачу, в зависимости от типа итератора, для которого они используются. Например, обнулить элементы вектора, содержащего целые числа, можно с помощью алгоритма std::fill. Поскольку итератор вектора может указать компилятору, что итерирует по непрерывной памяти, он может выбрать ту реализацию алгоритма std::fill, которая задает процедуру C memset. Если программист изменяет тип контейнера с vector на list, то алгоритм STL больше не может использовать процедуру memset и должен итерировать по списку, чтобы обнулять элементы по одному. В том случае, если программист сам задействует процедуру memset, алгоритм обнуления сможет работать только с векторами и массивами, поскольку другие структуры не хранят данные во фрагментах непрерывной памяти. В большинстве случаев не стоит изобретать велосипед, поскольку авторы библиотеки STL уже реализовали эти идеи и вам ничто не мешает воспользоваться их трудом.

Подытожим. Алгоритмы STL предоставляют такие преимущества.

□ Легкость сопровождения: по названию алгоритма сразу понятно, что именно он делает. Явные циклы зачастую труднее прочесть, и им нужно знать о том, какие именно структуры данных будут применяться, в отличие от стандартных алгоритмов.

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

□ Эффективность: по умолчанию алгоритмы STL эффективны как минимум настолько же, насколько эффективны циклы, написанные вручную.

Большинство алгоритмов работают с итераторами. Принципы работы итераторов мы уже рассмотрели в главе 3. В настоящей главе сконцентрируемся на использовании алгоритмов STL для решения конкретных задач, чтобы понять, какие возможности они предоставляют. Разбор всех алгоритмов превратит эту книгу в очень скучный справочный материал по С++, а подобное руководство уже доступно для широкого круга читателей.

Самый лучший способ стать мастером STL заключается в том, чтобы всегда иметь справочный материал по С++ под рукой или хотя бы в закладках браузера. При решении какой-нибудь задачи каждый программист должен задуматься: «Существует ли в STL алгоритм для решения моей задачи?» — прежде чем писать код самостоятельно.

Хорошая и полная справка по C++ доступна по адресу http://en.cppreference.com/w/. Кроме того, этот материал можно скачать для чтения в режиме офлайн.

 

 На собеседованиях хорошее знание алгоритмов STL зачастую считается показателем глубоких знаний языка С++. 

Копируем элементы из одних контейнеров в другие

Большинство важных структур данных STL поддерживают итераторы. Это значит, что вы как минимум сможете получить итераторы с помощью функций