C++17 STL Стандартная библиотека шаблонов

6. Компиляция и запуск программы дадут следующий ожидаемый результат. Можно убрать условие (x < xs) из функции call_cart, чтобы увидеть полное декартово произведение, содержащее избыточные пары и пары с одинаковыми номерами:

$ ./cartesian_product

(1, 2)

(1, 3)

(2, 3)

Как это работает

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

Взглянем на нее более внимательно. Нам следует получить представление о том, что должно произойти (рис. 4.4).

Работа проходит в три шага.

1. Берем наше множество 1, 2, 3 и создаем на его основе три новых. Первая часть каждого из этих множеств — один элемент множества, а вторая — все множества.

2. Объединяем первый элемент с каждым элементом множества и получаем все пары.

3. Из полученных пар выбираем те, которые не являются избыточными (например, пары (1,2) и (2,1) избыточны) и не содержат одинаковых чисел (как, скажем, (1,1)).

Теперь вернемся к реализации:

constexpr auto cartesian ([=](auto ...xs) constexpr {

  return [=](auto f) constexpr {

    (void)std::initializer_list {

      ((void)call_cart(f, xs, xs...), 0)...

    };

  };

});

Внутреннее выражение, call_cart(xs, xs...), явно представляет собой разделение множества (1,2,3) на эти новые множества наподобие 1, [1,2,3]. Полное выражение, ((void)call_cart(f,xs, xs...),0)..., имеющее снаружи дополнительную конструкцию ..., выполняет такое разделение для каждого значения множества, так что мы также получаем множества 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{

    (((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 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';