Daily bit(e) C++. std::partition, std::stable_partition

Daily bit(e) C++ #206. Алгоритмы разбиения: std::partition и std::stable_partition.

Алгоритм std::partition переупорядочивает элементы диапазона на основе предиката. Элементы, для которых предикат вычисляется как true, располагаются перед элементами, для которых предикат вычисляется как false.

Стабильная версия std::stable_partition также поддерживает относительный порядок элементов (внутри каждого раздела).

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> data1{1, 2, 3, 4, 5, 6, 7, 8, 9};

    auto pp1 = std::partition(data1.begin(), data1.end(), 
        [](int v) { return v % 2 == 0; }); // предикат для четных элементов

    // [begin, partition_point) - четные элементы
    for (auto it = data1.begin(); it != pp1; ++it)
        std::cout << *it << " ";
    std::cout << "\n";

    // [partition_point, end) - нечетные элементы
    for (auto it = pp1; it != data1.end(); ++it)
        std::cout << *it << " ";
    std::cout << "\n\n";

    std::vector<int> data2{1, 2, 3, 4, 5, 6, 7, 8, 9};

    auto odd = std::ranges::stable_partition(data2,
        [](int v) { return v % 2 == 0; }); // предикат для четных чисел

    // Версия для диапазонов возвращает поддиапазон {partition_point, end}
    // odd == {1, 3, 5, 7, 9} - гарантированный порядок
    for (auto v : odd)
        std::cout << v << " ";
    std::cout << "\n";

    // четные элементы
    auto even = std::ranges::subrange(data2.begin(), odd.begin());
    // even == {2, 4, 6, 8} - гарантированный порядок
    for (auto v : even)
        std::cout << v << " ";
    std::cout << "\n";
}

Открыть пример на Compiler Explorer.

Теги