honyaki 30 дек 2022 в 22:52

Алгоритмы диапазонов C++20 — сортировка, множества, обновления C++23 и прочее

9 мин

5.3K

Блог компании SkillfactoryC++*Алгоритмы*Программирование*

Обзор

Перевод

Эта статья — третья и последняя в мини-серии об алгоритмах диапазонов. Мы рассмотрим некоторые алгоритмы сортировки, поиска и другие, а также познакомимся с готовящимися крутыми улучшениями этих алгоритмов в версии C++23. Поехали! Подробности — к старту курса по разработке на С++.

Прежде чем мы начнём

Ключевые наблюдения для алгоритмов std::ranges:

Алгоритмы диапазонов определяются в заголовке <algorithm>, а инфраструктура диапазонов и основные типы определяются в заголовке <ranges>.
Существует как минимум две перегрузки алгоритмов диапазона: с парой итераторов и перегрузка с одним аргументом диапазона.
Версия, которая возвращает поддиапазон или итератор и принимает диапазон, возвращает заимствованный диапазон или заимствованный итератор. Это помогает обнаруживать итераторы для временных диапазонов.
Версии диапазона имеют проекции, что обеспечивает большую гибкость; например, вы можете выполнить сортировку по некоторым выбранным элементам или выполнить дополнительные преобразования перед сравнением.
В версии с диапазонами нет опции параллельного выполнения (вы не можете передать политику std::execution).
Алгоритмы диапазонов, как и стандартные алгоритмы C++20, также являются constexpr.
Начиная с версии C++20, не существует алгоритмов числовых диапазонов, соответствующих заголовку <numeric>.

Ниже вы можете найти примеры, демонстрирующие стандартный алгоритм и альтернативную версию с диапазонами. В них мы иллюстрируем некоторые основные концепции, стараясь не использовать расширенную композицию диапазонов или представления. Мы пойдём в порядке, указанном в cppreference/algorithms.

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

Это третья статья об алгоритмах диапазонов. Смотрите также:

первая статья: «Алгоритмы диапазонов C++20 — 7 немодифицирующих операций»;

вторая статья: «Алгоритмы диапазонов C++20 — 11 модифицирующих операций»;

Разбиение на разделы и сортировка

`sort` и `is_sorted`

Алгоритм сортировки часто используют для объявления диапазонов. Если у вас есть контейнер, то благодаря диапазонам вы можете написать:

std::ranges::sort(myContainer);

Вот пример для лучшего понимания:

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

struct Product {
    std::string name;
    double value { 0.0 };
};

void print(std::string_view intro, const std::vector<Product>& container) {
    std::cout << intro << '\n';
    for (const auto &elem : container)
        std::cout << elem.name << ", " << elem.value << '\n';
}

int main() {
    const std::vector<Product> prods {
        { "box", 10.0 }, {"tv", 100.0}, {"ball", 30.0},
        { "car", 1000.0 }, {"toy", 40.0}, {"cake", 15.0},
        { "book", 45.0}, {"pc game", 35.0}, {"wine", 25}
    };

    print("input", prods);

    // the standard version:
    std::vector<Product> copy = prods;   
    std::sort(begin(copy), end(copy), [](const Product& a, const Product& b)
        { return a.name < b.name; }
    );

    print("after sorting by name", copy);

    // the ranges version:
    copy = prods;   
    std::ranges::sort(copy, {}, &Product::name);    
    print("after sorting by name", copy);           
    std::ranges::sort(copy, {}, &Product::value);    
    print("after sorting by value", copy);     
    auto sorted = std::ranges::is_sorted(copy, {}, &Product::value);
    std::cout << "is sorted by value: " << sorted << '\n';
}

Запустить @Compiler Explorer

Во многих реализациях используется интросортировка (см. Википедию). Это гибридное решение, обычно с быстрой сортировкой/сортировкой кучей, а затем сортировкой вставками для небольших (под)диапазонов.

Другие версии алгоритмов сортировки:

partial_sort — сортирует первые N элементов диапазона.
stable_sort — порядок эквивалентных элементов гарантированно сохраняется.

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

Подробнее: ranges::sort @Cppreference.

`partition`

Разбиение — неотъемлемая часть быстрой сортировки. Для данного предиката операция перемещает элементы, соответствующие предикату, в первую часть контейнера, а не соответствующие — во вторую. Иногда можно разделить контейнер, а не выполнять полную операцию сортировки:

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

void print(std::string_view intro, const std::vector<auto>& container) {
    std::cout << intro << '\n';
    for (const auto &elem : container)
        std::cout << elem << ", ";
    std::cout << '\n';
}

int main() {
    const std::vector vec { 11, 2, 3, 9, 5, 4, 3, 8, 4, 1, 11, 12, 10, 4};

    print("input", vec);

    // the standard version:
    auto copy = vec;   
    auto it = std::partition(begin(copy), end(copy), [](int a)
        { return a < 7; }
    );

    print("partition till 7", copy);
    std::cout << "pivot at " << std::distance(begin(copy), it) << '\n';

    // ranges version:
    copy = vec;   
    auto sub = std::ranges::partition(copy, [](int a)
        { return a < 7; }
    );

    print("partition till 7", copy);
    std::cout << "pivot at " << std::distance(begin(copy), sub.begin()) << '\n';
}

Запустить @Compiler Explorer

Вывод:

input
11, 2, 3, 9, 5, 4, 3, 8, 4, 1, 11, 12, 10, 4,
partition till 7
4, 2, 3, 1, 5, 4, 3, 4, 8, 9, 11, 12, 10, 11,
pivot at 8
partition till 7
4, 2, 3, 1, 5, 4, 3, 4, 8, 9, 11, 12, 10, 11,
pivot at 8

Как видите, мы легко можем разделить контейнер на две группы: первая часть содержит элементы меньше 7, а вторая часть — элементы >= 7. Относительный порядок между элементами может быть изменен (для сохранения этого порядка нужно использовать stable_partition).

Интерфейс для partition относительно прост. Версия алгоритма дополнительно принимает проекцию, но в примере она не использовалась. Отличие состоит в том, что ranges::partition возвращает поддиапазон, а не итератор (как в версии std::).

Подробнее об алгоритмах: ranges::is_partitioned и ranges::partition @C++Reference.

Операции бинарного поиска

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

`binary_search`

#include <iostream>
#include <algorithm>
#include <ranges>
#include <vector>
#include <numeric>

void print(std::string_view intro, const auto& container) {
    std::cout << intro << '\n';
    for (const auto &elem : container)
        std::cout << elem << ", ";
    std::cout << '\n';
}

int main() {
    std::vector<int> vec(100, 0);
    std::iota(begin(vec), end(vec), 0);

    print("first ten elements of input", vec | std::views::take(10));

    // the standard version:
    auto copy = vec;   
    auto found = std::binary_search(begin(copy), end(copy), 13);
    std::cout << "found 13: " << found << '\n';

    // ranges version:
    copy = vec;   
    found = std::ranges::binary_search(copy, 13);
    std::cout << "found 13: " << found << '\n';
}

Запустить @Compiler Explorer

Читать подробнее:ranges::binary_search @C++Reference.

Кроме того, можно использовать связанные алгоритмы:

std::ranges::lower_bound — cppreference.com возвращает итератор к первому элементу не меньше заданного значения;
std::ranges::upper_bound — cppreference.com — возвращает итератор к первому элементу больше заданного значения;

Операции с множествами

В библиотеке есть много функций, связанных с множествами, вот некоторые из них:

ranges::merge — объединяет два отсортированных диапазона
ranges::inplace_merge — объединяет два упорядоченных диапазона in-place
ranges::includes — возвращает true, если одна отсортированная последовательность является подпоследовательностью другой отсортированной последовательности
ranges::set_difference — вычисляет разницу между двумя множествами
ranges::set_intersection — вычисляет пересечение двух множеств
ranges::set_symmetric_difference — вычисляет симметричную разность двух множеств
ranges::set_union — вычисляет объединение двух множеств

Рассмотрим один пример с includes:

`includes`

Возвращает true, если отсортированный диапазон является подпоследовательностью другого отсортированного диапазона.

#include <iostream>
#include <algorithm>
#include <ranges>
#include <vector>
#include <string>

struct Product {
    std::string name;
    double value { 0.0 };
};

void print(std::string_view intro, const std::vector<Product>& container) {
    std::cout << intro << '\n';
    for (const auto &elem : container)
        std::cout << elem.name << ", " << elem.value << '\n';
}

int main() {
    std::vector<Product> prods {
        { "box", 10.0 }, {"tv", 100.0}, {"ball", 30.0},
        { "car", 1000.0 }, {"toy", 40.0}, {"cake", 15.0},
        { "book", 45.0}, {"pc game", 35.0}, {"wine", 25}
    };
    std::vector<Product> vecToCheck {
        {"ball", 30.0}, { "box", 10.0 }, {"wine", 25}
    };
    std::ranges::sort(prods, {}, &Product::name);
    std::vector<std::string> namesToCheck {"ball", "box", "wine"};

    print("input", prods);

    // the standard version:      
    auto ret = std::includes(begin(prods), end(prods),
                            begin(vecToCheck), end(vecToCheck),
                            [](const Product& a, const Product& b)
        { return a.name < b.name; }
    );
    std::cout << "contains the name set: " << ret << '\n';

    // the ranges version:
    ret = std::ranges::includes(prods, namesToCheck, {}, &Product::name);
    std::cout << "contains the name set: " << ret << '\n';
}

Запустить @Compiler Explorer

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

Дополнительную информацию см.: std::includes @cppreference.com.

Прочее

`max_element`

Поиск наибольшего элемента в контейнере (без сортировки):

#include <iostream>
#include <random>
#include <iterator>
#include <algorithm>
#include <ranges>

struct Product {
    std::string name_;
    double value_ { 0.0 };
};

int main() {
    const std::vector<Product> prods {
        { "box", 10.0 }, {"tv", 100.0}, {"ball", 30.0},
        { "car", 1000.0 }, {"toy", 40.0}, {"cake", 15.0},
        { "book", 45.0}, {"PC game", 35.0}, {"wine", 25}
    };

    // the standard version:   
    auto res = std::max_element(begin(prods), end(prods),
                [](const Product& a, const Product& b) {
                    return a.value_ < b.value_;
                });

    if (res != end(prods)) {
        const auto pos = std::distance(begin(prods), res);
        std::cout << "std::max_element at pos " << pos
                  << ", val " << res->value_ << '\n';
    }

    // the ranges version:
    auto it = std::ranges::max_element(prods, {}, &Product::value_);
    if (it != end(prods)) {
        const auto pos = std::distance(begin(prods), it);
        std::cout << "std::max_element at pos " << pos
                  << ", val " << res->value_ << '\n';
    }
}

Запустить @Compiler Explorer

`equal`

#include <iostream>
#include <random>
#include <iterator>
#include <algorithm>
#include <ranges>

struct Product {
    std::string name;
    double value { 0.0 };
};

int main() {
    const std::vector<Product> prods {
        { "box", 10.0 }, {"tv", 100.0}, {"ball", 30.0},
        { "car", 1000.0 }, {"toy", 40.0}, {"cake", 15.0},
    };

    const std::vector<Product> moreProds {
        { "box", 11.0 }, {"tv", 120.0}, {"ball", 30.0},
        { "car", 10.0 }, {"toy", 39.0}, {"cake", 15.0}
    };

    // the standard version:   
    auto res = std::equal(begin(prods), end(prods),
                          begin(moreProds), end(moreProds),
                [](const Product& a, const Product& b) {
                    return a.name == b.name;
                });

    std::cout << "equal: " << res << '\n';

    // the ranges version:
    res = std::ranges::equal(prods, moreProds, {}, &Product::name, &Product::name);
    std::cout << "equal: " << res << '\n';
}

Запустить @Compiler Explorer

Подробнее см.: ranges::equal @C++Reference.

Ещё больше

Мой список алгоритмов не полон. Почти у всех стандартных алгоритмов есть альтернатива std::ranges::. Взгляните на следующие интересные, не упомянутые мной алгоритмы:

Операции с кучей:

ranges::is_heap
ranges::is_heap_until
ranges::make_heap
ranges::push_heap
ranges::pop_heap
ranges::sort_heap

Перестановки:

ranges::is_permutation
ranges::next_permutation
ranges::prev_permutation

Алгоритмы неинициализированной памяти:

ranges::uninitialized_copy
ranges::uninitialized_copy_n
ranges::uninitialized_fill
ranges::uninitialized_fill_n
ranges::uninitialized_move
ranges::uninitialized_move_n
ranges::uninitialized_default_construct
ranges::uninitialized_default_construct_n
ranges::uninitialized_value_construct
ranges::uninitialized_value_construct_n
ranges::destroy
ranges::destroy_n
ranges::destroy_at
ranges::construct_at

Numeric

С версии C++20 у нас есть большинство соответствующих алгоритмов диапазонов из заголовка <algorithm>, но отсутствует заголовок <numeric>.

Скоро в C++23

Спецификация C++23 почти закончена и находится в режиме feature-freeze. На момент написания статьи мне известны следующие алгоритмы, которые появятся в новой версии C++:

ranges::starts_with и ranges::ends_with (по состоянию на июнь 2022 г. доступно в компиляторе MSVC)
ranges::contains (P2302)
ranges::shift_left и ranges::shift_right,
ranges::iota
ranges::fold в качестве альтернативы std::accumulate

Заключение

Эта статья завершает наше путешествие по алгоритмам C++, доступным в стандартной библиотеке (кроме числовых). У большинства алгоритмов есть аналоги ranges::, а в C++23 появится ещё больше дополнений.

А мы научим вас аккуратно работать с данными, чтобы вы прокачали карьеру и стали востребованным IT-специалистом.

Краткий каталог курсов

Data Science и Machine Learning

Python, веб-разработка

Мобильная разработка

Java и C#

От основ — в глубину

А также

Теги:

Хабы:

Алгоритмы диапазонов C++20 — сортировка, множества, обновления C++23 и прочее

Прежде чем мы начнём

Разбиение на разделы и сортировка

`sort` и `is_sorted`

`partition`

Операции бинарного поиска

`binary_search`

Операции с множествами

`includes`

Прочее

`max_element`

`equal`

Ещё больше

Numeric

Скоро в C++23

Заключение

Публикации

Информация

Алгоритмы диапазонов C++20 — сортировка, множества, обновления C++23 и прочее

Прежде чем мы начнём

Разбиение на разделы и сортировка

sort и is_sorted

partition

Операции бинарного поиска

binary_search

Операции с множествами

includes

Прочее

max_element

equal

Ещё больше

Numeric

Скоро в C++23

Заключение

`sort` и `is_sorted`

`partition`

`binary_search`

`includes`

`max_element`

`equal`