Преобразования (серия «114 алгоритмов C++»)

Добро пожаловать в статью номер четыре из серии «114 стандартных алгоритмов C++». Алгоритмы преобразования изменяют состояние диапазонов, изменяя значения элементов, изменяя порядок элементов или удаляя элементы.

Несколько алгоритмов преобразования, которые мы сегодня обсудим, также имеют варианты ленивых представлений. Представления – это лениво вычисляемый и компонуемый вариант стандартных алгоритмов, представленный как часть функциональности диапазонов в C++20.

transform

Самое простое из возможных преобразований – применить функцию преобразования к каждому элементу.

Стандартная библиотека предоставляет как унарный, так и бинарный std::transform.

std::vector<int> data{1, 2, 3, 4, 5, 6, 7, 8};
std::transform(data.begin(), data.end(),
               data.begin(), [](int v) { return v*2; });
// data = {2, 4, 6, 8, 10, 12, 14, 16}

std::vector<int> add{8, 7, 6, 5, 4, 3, 2, 1};
std::transform(data.begin(), data.end(), add.begin(),
               data.begin(), [](int left, int right) {
                  return left+right; });
// data = {10, 11, 12, 13, 14, 15, 16, 17}

Поскольку выходной диапазон указывается с помощью итератора, оба алгоритма transform могут работать как встроенные, так и выводить в другой диапазон.

std::vector<int> data{1, 2, 3, 4, 5, 6, 7, 8};
std::vector<int> out;
std::transform(data.begin(), data.end(),
    std::back_inserter(out), [](int v) { return v*2; });
// out = {2, 4, 6, 8, 10, 12, 14, 16}

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

Эти ограничения отличают унарный std::transform от std::for_each.

struct MyStruct {
    void some_modifying_operation() {}
};

std::vector<int> data(8, 1);
std::ranges::for_each(data, [v = 0](int& el) mutable { el = ++v; });
// data = {1, 2, 3, 4, 5, 6, 7, 8}

// Неопределенный результат:
std::ranges::transform(data, data.begin(), [v = 0](int) mutable { return ++v; });

std::vector<MyStruct> db{{}, {}, {}};
std::ranges::for_each(db, [](auto& el) { el.some_modifying_operation(); });

// Недопустимо:
std::ranges::transform(db, db.begin(), 
    [](MyStruct& el) -> MyStruct& { el.some_modifying_operation(); return el; });
// Допустимо, работа над копией:
std::ranges::transform(db, db.begin(), 
    [](MyStruct el) -> MyStruct { el.some_modifying_operation(); return el; });

В этом примере используются изменяемые лямбда-выражения (строки 6 и 10) и обобщенный захват лямбда-выражений из C++14, который позволяет создавать и инициализировать переменные в разделе захвата лямбда-выражения.

transform также является первым алгоритмом, о котором мы говорили с ленивым вариантом. C++20 представил концепцию представлений как часть функциональных возможностей диапазонов.

std::vector<int> data{1, 2, 3, 4, 5, 6, 7};
auto is_even = [](int v) { return v % 2 == 0; };

std::vector<int> out;
auto even_squares = data
             | std::ranges::views::filter(is_even) 
             | std::ranges::views::transform([](int v) { return v*v; });

std::ranges::copy(even_squares, std::back_inserter(out));
// out = {4, 16, 36}

У меня есть отдельная статья о диапазонах C++20, в которой также рассматриваются представления. Основные выводы здесь следующие:

• создание представлений происходит во время компиляции; в строке 5 не выполняется операция времени выполнения;
• объект even_squares сам по себе является представлением; его дешево копировать и перемещать, и он не владеет просматриваемыми данными;
• каждый компонент представления вычисляется лениво; если мы читаем только один элемент из представления even_squares, views::filter будет вычисляться дважды, а views::transform только один раз.

adjacent_difference

Несмотря на название, adjacent_difference – это вариант бинарного преобразования, работающий с соседними элементами в одном диапазоне.

В отличие от transform, adjacent_difference гарантирует применение слева направо. Кроме того, поскольку входные диапазоны позволяют считывать каждый элемент только один раз, данный алгоритм внутренне сохраняет копию последнего прочитанного значения (для использования в качестве левого операнда).

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

std::vector<int> data{2, 4, 8, 16, 32, 64};
std::adjacent_difference(data.begin(), data.end(), data.begin());
// 2, 2 (4-2), 4 (8-4), 8 (16-8), 16 (32-16), 32 (64-32)

Однако, поскольку мы можем выбрать другой функтор (кроме std::minus), мы также можем использовать std::adjacent_difference для генерации последовательностей:

std::vector<int> data(10, 1);
std::adjacent_difference(data.begin(), std::prev(data.end()), 
                         std::next(data.begin()), std::plus<int>());
// Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,

Обратите внимание, что std::next(data.begin()) для выходного диапазона здесь имеет решающее значение. Алгоритм adjacent_difference будет считывать каждый элемент только один раз и запоминать ранее прочитанное значение для левого аргумента. std::next гарантирует, что мы генерируем один элемент перед любым аргументом.

remove, remove_if

Название remove немного вводит в заблуждение. remove сдвинет элементы в диапазоне таким образом, что начальный поддиапазон не будет содержать указанные элементы.

Подобно std::unique, данный алгоритм не может изменить размер диапазона, поэтому вместо этого он возвращает итератор для обозначения нового конца.

std::vector<int> data{1, 2, 3, 4, 5};
auto it = std::remove(data.begin(), data.end(), 3);
data.resize(it-data.begin()); // только диапазоны произвольного доступа
// data = {1, 2, 4, 5}

auto is_even = [](int v) { return v % 2 == 0; };
it = std::remove_if(data.begin(), data.end(), is_even);
data.erase(it, data.end()); // стереть поддиапазон
// data = {1, 5}

Эта схема именования будет повторяться в нескольких алгоритмах. Базовая версия всегда является вариантом, который работает на основе предоставленного значения (строка 2), вариант _if опирается на предоставленный предикат (строка 7).

Хотя у remove нет прямой ленивой версии, мы часто можем заменить ее на std::views::filter.

std::vector<int> data{1, 2, 3, 4, 5};
auto is_odd = [](int v) { return v % 2 != 0; };
for (int v : data | std::ranges::views::filter(is_odd)) {
    // проходимся через 1, 3, 5
}

Существенное отличие заключается в том, что views::filter изменяет способ итерации по диапазону, но не изменяет фактическое содержимое диапазона.

replace, replace_if

Мы можем использовать алгоритм replace для замены значений вместо их удаления.

Следуя той же схеме именования, std::replace заменяет элементы, соответствующие заданному значению, тогда как std::replace_if заменяет элементы на основе предиката.

std::vector<int> data{1, 2, 3, 4, 5, 6, 7};
std::ranges::replace(data, 4, 0);
// data={1, 2, 3, 0, 5, 6, 7}

auto is_odd = [](int v) { return v % 2 != 0; };
std::ranges::replace_if(data, is_odd, -1);
// data={-1, 2, -1, 0, -1, 6, -1}

reverse, rotate, shuffle

Алгоритм reverse обеспечивает простое реверсирование заданного двунаправленного диапазона на основе перестановки значений (swap).

Хотя только C++20 представил версию reverse для представления, каждый двунаправленный диапазон изначально поддерживает обратную итерацию через варианты rbegin() и rend() итераторов begin() и end().

std::vector<int> data{1, 2, 3, 4, 5, 6, 7};
std::reverse(data.begin(), data.end());
// data = {7, 6, 5, 4, 3, 2, 1}

for (auto it = data.rbegin(); it != data.rend(); ++it) {
    // проходим через: 1, 2, 3, 4, 5, 6, 7
}

for (auto v : data | std::views::reverse) {
    // проходим через: 1, 2, 3, 4, 5, 6, 7
}

При работе с устаревшими типами, такими как массивы C или строки в стиле C, обратная итерация может быть неудобной. Однако мы можем опираться на std::span (начиная с C++20) и std::string_view (начиная с C++17), которые обеспечивают двунаправленную поддержку.

int c_array[] = {1, 2, 3, 4, 5, 6, 7};
auto arr_view = std::span(c_array, sizeof(c_array)/sizeof(int));

for (auto it = arr_view.rbegin(); it != arr_view.rend(); ++it) {
    // проходим через: {7, 6, 5, 4, 3, 2, 1}
}

const char* c_string = "No lemon, no melon";
auto str_view = std::string_view(c_string);

for (auto it = str_view.rbegin(); it != str_view.rend(); ++it) {
    // проходим через: "nolem on ,nomel oN"
}

Алгоритм reverse также дает нам прекрасную возможность продемонстрировать более сложную композицию представлений. Например, следующее представление trim пропускает начальные и конечные пробелы:

const char* c_string = "  No lemon, no melon.     ";
auto str_view = std::string_view(c_string);

auto is_ws = [](char c) { return isspace(c); };
auto skip_ws = std::views::drop_while(is_ws);
auto skip_trailing_ws = std::views::reverse | skip_ws | std::views::reverse;
auto trim = skip_trailing_ws | skip_ws;

std::string out;
std::ranges::copy(str_view | trim, std::back_inserter(out));
// out = "No lemon, no melon."

Как и в предыдущих примерах, в строках 4–7 не выполняются вычисления во время выполнения, а обработка выполняется по запросу, поскольку алгоритм std::copy перебирает составленное представление (строка 10).

Мы начинаем с предиката, который возвращает true для пробельных символов (строка 4). Затем мы используем представление drop_while, которое пропускает элементы до тех пор, пока предикат не вернет false (строка 5). Это уже обрезка с одной стороны.

Чтобы построить обратную обрезку, мы переворачиваем диапазон, обрезаем теперь начальные пробелы, а затем снова переворачиваем диапазон (строка 6). Наконец, полная обрезка – это просто комбинация двух операций частичных обрезок.

Алгоритм rotate делает именно то, что подразумевает его название, и вращает элементы в диапазоне таким образом, что указанный элемент становится первым элементом диапазона.

std::vector<int> data{1, 2, 3, 4, 5, 6, 7};
std::rotate(data.begin(), data.begin()+3, data.end());
// data=4, 5, 6, 7, 1, 2, 3

Алгоритм shuffle (перемешивание) является преемником ныне несуществующего алгоритма random_shuffle (указан устаревшим в C++14, удален в C++17) и опирается на новые средства случайного выбора, добавленные в C++11.

Средства рандомизации выходят за рамки этой статьи. Однако shuffle будет работать с любым универсальным генератором случайных битов.

struct Card {
    unsigned index;
    
    friend std::ostream& operator << (std::ostream& s, const Card& card) {
        static constexpr std::array<const char*, 13> ranks = {"Ace", "Two", "Three", 
          "Four", "Five", "Six", "Seven", "Eight", 
          "Nine", "Ten", "Jack", "Queen", "King"};
        static constexpr std::array<const char*, 4> suits = {"Hearts", "Diamonds", 
                                                             "Clubs", "Spades"};

        if (card.index >= 52)
            throw std::domain_error("Card index has to be in the range 0..51");

        s << ranks[card.index%13] << " of " << suits[card.index/13];

        return s;
    }
};

std::vector<Card> deck(52, Card{});
std::ranges::generate(deck, [i = 0u]() mutable { return Card{i++}; });
// deck = {Ace of Hearts, Two of Hearts, Three of Hearts, Four of Hearts...}

std::random_device rd;
std::mt19937 gen{rd()};

std::ranges::shuffle(deck, gen);
// deck = { случайный порядок }

Мы используем алгоритм std::generate, который мы обсудим в следующей статье, для создания 52 уникальных карт (строка 21). После генерации эти карты будут отсортированы.

Затем мы используем универсальный битовый генератор вихрь Мерсенна (в его 32-битном предопределенном псевдониме), который мы передаем алгоритму shuffle, в результате чего диапазон перемешивается случайным образом.

Перегрузка оператора выходного потока в строках 4–17 обеспечивает перевод из индекса в текстовое представление, например, «Jack of Clubs».

next_permutation, prev_permutation, is_permutation

Алгоритмы перестановки будут генерировать либо следующую, либо предыдущую перестановку в лексикографическом порядке.

Строго говоря, вызов next_permutation отрегулирует порядок элементов таким образом, чтобы следующее значение было более высоким в соответствии с std::lexicographical_compare (с использованием того же функтора). Если такого диапазона нет, next_permutation вернется к наименьшему значению и вернет false.

std::vector<int> data{1, 2, 3};
do {
    // проходим через:
    // 1, 2, 3
    // 1, 3, 2
    // 2, 1, 3
    // 2, 3, 1
    // 3, 1, 2
    // 3, 2, 1
} while (std::next_permutation(data.begin(), data.end()));
// data = {1, 2, 3}

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

std::vector<std::string> data{"apple", "avocado", "banana", 
  "cherry", "lemon", "mango", 
  "orange", "plums", "watermelon"};

std::vector<char> pick(data.size(), false);
std::fill_n(pick.begin(), 3, true);

do {
    for (size_t i = 0; i < pick.size(); ++i) {
        if (pick[i])
            std::cout << data[i] << ", ";
    }
    std::cout << "\n";
} while (std::prev_permutation(pick.begin(), pick.end(), std::less<bool>()));  

Мы начинаем с диапазона, заполненного значениями false, установив для первых трех элементов значение true (строка 6). Затем мы распечатываем элементы, соответствующие значениям true (строка 10). Наконец, prev_permutation вернет false, как только мы вернемся к начальному диапазону с первыми тремя элементами, установленными в true (строка 14).

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

Полезность is_permutation в основном появляется при тестировании, где нам часто нужно проверять, являются ли два диапазона кусочно равными, но не обязательно в одном и том же порядке.

std::vector<int> data = { 8, 1, 7, 3, 4, 6, 2, 5};
for (size_t i = 0; i < data.size()-1; ++i)
    for (size_t j = i+1; j < data.size(); ++j)
        if (data[i] > data[j])
            std::swap(data[i], data[j]);

assert(std::ranges::is_sorted(data));
assert(std::ranges::is_permutation(data, 
                                   std::vector<int>{1, 2, 3, 4, 5, 6, 7, 8}));

Спасибо за чтение

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

Теги