Алгоритмы диапазонов C++20 — 11 модифицирующих операций / forpes.ru

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

Алгоритмы диапазонов C++20 — 11 модифицирующих операций +2

29.12.2022 22:01

honyaki 1 1800 Источник

В предыдущей статье серии «Диапазоны» я рассмотрел основы и некоторые немодифицирующие операции. Сегодня пришло время таких алгоритмов, как transform, copy, generate, shuffle и многих других… даже rotate. Подробности — к старту курса по разработке на С++.

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

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

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

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

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

Это вторая часть из серии статей про алгоритмы диапазонов. Читать:

Первая статья о «7 немодифицирующих операциях»

`copy_if`

У основного алгоритма copy много вариантов: copy_if, copy_n и даже copy_backward.

В простой форме copy_if определяется так:

// skipping all concept/templates declaration
constexpr copy_if_result<ranges::borrowed_iterator_t<R>, O>
          copy_if( R&& r, O result, Pred pred, Proj proj = {} );

Посмотрим на пример:

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

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

std::ostream& operator<<(std::ostream& os, const Product& p) {
    os << p.name_ << ", " << p.value_;
    return os;
}

int main() {
    const std::vector<Product> prods {
        { "box", 10.0 }, {"tv", 100.0}, {"rocket", 10000.0},
        { "car", 1000.0 }, {"toy", 40.0}, {"none", 0.0}
    };

    // standard version:  
    std::copy_if(begin(prods), end(prods),
              std::ostream_iterator<Product>(std::cout, "; "),
              [](const Product& p){
        return !p.name_.starts_with("none");
    });
    std::cout << '\n';

    // ranges version:
    std::ranges::copy_if(prods,
              std::ostream_iterator<Product>(std::cout, "; "),
              [](const Product& p){
        return !p.name_.starts_with("none");
    });
}

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

В примере я копирую элементы из вектора в выходной поток. Кроме того, на этапе фильтрации я выбираю только товары не "none". Поскольку в поток копируются целые элементы, мне пришлось реализовать operator< для класса Product.

Благодаря проекциям я также мог написать такой вариант кода:

std::ranges::copy_if(prods,
          std::ostream_iterator<Product>(std::cout, "; "),
          [](const std::string& name){
              return !name.starts_with("none");
          },
          &Product::name_);

Этот код немного длиннее, но теперь предикат принимает string, а не весь объект Product.

Читать подробнее на ranges::copy, ranges::copy_if @Cppreference.

`fill`

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

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

    Product& operator=(int i) { name_ += std::to_string(i); return *this; }
};

std::ostream& operator<<(std::ostream& os, const Product& p) {
    os << p.name_ << ", " << p.value_;
    return os;
}

int main() {
    std::vector<Product> prods{7, {"Box ", 1.0}};

    // standard version:  
    std::fill(begin(prods), end(prods), 4);
    std::ranges::copy(prods, std::ostream_iterator<Product>(std::cout, "; "));
    std::cout << '\n';

    // ranges version:  
    std::ranges::fill(prods, 2);
    std::ranges::copy(prods, std::ostream_iterator<Product>(std::cout, "; "));
}

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

Алгоритм fill проходит по диапазону, а затем выполняет присвоение с переданным вами value. Тип value может отличаться от типа элементов в контейнере.

while (first != last)
    *first++ = value;

В примере я использовал класс с пользовательским оператором преобразования, им можно воспользоваться для изменения члена данных name_ на основе интегрального входного значения.

Читать подробнее на ranges::fill @Cppreference.

`generate`

В то время как fill() использует одно и то же значение для присвоения всем элементам, generate() использует функциональный объект для генерации значения. В этом примере можно смоделировать генерацию iota:

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

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

    Product& operator=(int i) { name_ += std::to_string(i); return *this; }
};

std::ostream& operator<<(std::ostream& os, const Product& p) {
    os << p.name_ << ", " << p.value_;
    return os;
}

int main() {
    std::vector<Product> prods{7, {"Box ", 1.0}};

    // standard version:  
    std::generate(begin(prods), end(prods), [v = 0]() mutable {
        return v++;
    });
    std::ranges::copy(prods, std::ostream_iterator<Product>(std::cout, "; "));
    std::cout << '\n';

    // ranges version:  
    std::ranges::generate(prods, [v = 0]() mutable {
        return ++v;
    });
    std::ranges::copy(prods, std::ostream_iterator<Product>(std::cout, "; "));
}

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

Вывод:

Box 0, 1; Box 1, 1; Box 2, 1; Box 3, 1; Box 4, 1; Box 5, 1; Box 6, 1;
Box 01, 1; Box 12, 1; Box 23, 1; Box 34, 1; Box 45, 1; Box 56, 1; Box 67, 1;

Читать подробнее на странице ranges::generate @Cppreference. Есть версия с _n: ranges::generate_n.

`transform`

transform() — надёжный алгоритм, имеющий множество вариаций.

В простой форме он выглядит так:

transform( R&& r, O result, F op, Proj proj = {} );

Он принимает диапазон r, а затем использует op для преобразования элементов из этого диапазона и вывода в result, который является итератором.

Вот простой пример:

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

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

int main() {
    std::vector<Product> prods{7, {"Box ", 1.0}};

    // standard version:  
    std::transform(begin(prods), end(prods), begin(prods), [v = 0](const Product &p) mutable {
        return Product { p.name_ + std::to_string(v++), 1.0};
    });
    for (auto &p : prods) std::cout << p.name_ << ", ";
    std::cout << '\n';

    // ranges version:  
    std::ranges::transform(prods, begin(prods), [v = 0](const std::string &n) mutable {
        return Product { n + std::to_string(v++), 1.0};
    }, &Product::name_);
    for (auto &p : prods) std::cout << p.name_ << ", ";
}

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

Вывод:

Box 0, Box 1, Box 2, Box 3, Box 4, Box 5, Box 6,
Box 00, Box 11, Box 22, Box 33, Box 44, Box 55, Box 66,

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

Также есть версия, которая берет два диапазона и объединяет их с помощью бинарной операции:

transform( R1&& r1, R2&& r2, O result, F binary_op, Proj1 proj1 = {}, Proj2 proj2 = {} );

Этой версией можно воспользоваться для «объединения» двух контейнеров и получения одного значения:

std::vector<Product> prods{7, {"Box ", 1.0}};
std::vector<int> numbers{1, 2, 3, 4, 5, 6, 7};

std::ranges::transform(prods, numbers, begin(prods),
[](const Product& p, int v) {
    return Product { p.name_ + std::to_string(v), 1.0};
});
for (auto &p : prods) std::cout << p.name_ << ", ";

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

Читать подробнее на ranges::transform.

`remove`

В C++20 есть способ удаления и стирания элементов из различных контейнеров эффективнее. Смотрите std::erase_if, набор перегруженных функций для согласованного удаления контейнера. Подробности — в моей статье: 20 небольших, но удобных функций C++20 — согласованное удаление контейнеров.

Для полноты картины сравним все три версии:

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

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

int main() {
    const std::vector<Product> prods {
        { "box", 10.0 }, {"tv", 100.0}, {"rocket", 10000.0},
        {"no prod", 0.0}, { "car", 1000.0 }, {"toy", 40.0}, {"none", 0.0}
    };

    auto printCont = [](const std::vector<Product>& cont) {
        for (auto &p : cont) std::cout << p.name_ << ", ";
        std::cout << '\n';
    };
    std::cout << "removing products starting with \"no\"\n";
    printCont(prods);

    auto checkNoPrefix = [&](const Product& p) { return p.name_.starts_with("no"); };

    // standard version:
    auto tempProds = prods;
    tempProds.erase(std::remove_if(tempProds.begin(), tempProds.end(),
        checkNoPrefix), tempProds.end());
    printCont(tempProds);

    // ranges version:
    tempProds = prods;
    tempProds.erase(std::ranges::remove_if(tempProds, checkNoPrefix).begin(), tempProds.end());
    printCont(tempProds);

    // C++20 version:  
    tempProds = prods;
    std::erase_if(tempProds, checkNoPrefix);
    printCont(tempProds);
}

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

Версия ranges сокращает этот вызов:

tempProds.erase(std::remove_if(tempProds.begin(), tempProds.end(),
        checkNoPrefix), tempProds.end());

в такой:

tempProds.erase(std::ranges::remove_if(tempProds, checkNoPrefix).begin(), tempProds.end());

Но, на мой взгляд, это выглядит не намного лучше. ranges::remove_if возвращает поддиапазон, поэтому всё равно нужно прописать его begin() и, возможно, end().

Гораздо проще написать так:

std::erase_if(tempProds, checkNoPrefix);

Подробности здесь: ranges::removeranges::remove_if @Cppreference, а также std::erase, std::erase_if (std::vector) @Cppreference (каждый контейнер имеет свою перегрузку для std::erase).

`replace`

Как заменить элементы внутри контейнера:

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

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

    friend bool operator==(const Product& a, const Product& b) {
        return a.name_ == b.name_ && abs(a.value_ - b.value_) < 0.0001;
    }
};

std::ostream& operator<<(std::ostream& os, const Product& p) {
    os << p.name_ << ", " << p.value_;
    return os;
}

int main() {
    std::vector<Product> prods {
        { "box", 10.0 }, {"tv", 100.0}, {"rocket", 10000.0},
        { "car", 1000.0 }, {"toy", 40.0}, {"none", 0.0},
        {"invalid", 0.0}, { "invalid", -10.0 }
    };

    std::ostream_iterator<Product> out_iter(std::cout, "; ");

    // standard version:  
    std::cout << "before: \n";
    std::copy(begin(prods), end(prods), out_iter);
    std::replace(begin(prods), end(prods), Product{"none", 0.0}, Product{"default", 10.0});
    std::cout << "\nafter: \n";
    std::copy(begin(prods), end(prods), out_iter);
    std::cout << '\n';

    // ranges version:
    std::cout << "before: \n";
    std::ranges::copy(prods, out_iter);
    std::ranges::replace(prods, "invalid", Product{"default", 10.0}, &Product::name_);
    std::cout << "\nafter: \n";
    std::ranges::copy(prods, out_iter);
    std::cout << '\n';    
}

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

Вывод:

before:
box, 10; tv, 100; rocket, 10000; car, 1000; toy, 40; none, 0; invalid, 0; invalid, -10;
after:
box, 10; tv, 100; rocket, 10000; car, 1000; toy, 40; default, 10; invalid, 0; invalid, -10;
before:
box, 10; tv, 100; rocket, 10000; car, 1000; toy, 40; default, 10; invalid, 0; invalid, -10;
after:
box, 10; tv, 100; rocket, 10000; car, 1000; toy, 40; default, 10; default, 10; default, 10;

Интересно, что в стандартной версии значение сравнивается с объектами в контейнере:

for (; first != last; ++first) {
    if (*first == old_value) {
        *first = new_value;
    }
}

Вот почему мне пришлось определить оператор сравнения == (или "космический корабль" <=> для большей гибкости).

Сравнение немного отличается, поэтому в версии с диапазонами можно использовать проекцию:

for (; first != last; ++first) {
    if (old_value == std::invoke(proj, *first)) {
        *first = new_value;
    }
}

В этом примере необходимости в операторе == нет, ведь строки можно сравнивать напрямую. Это даёт больше гибкости, поскольку так можно найти больше недопустимых значений (значение value_ теперь не проверяется, чтобы найти и исправить — 0.0 или -10.0).

Читать подробнее на ranges::replaceranges::replace_if @Cppreference.

`reverse`

Попробуем вариант с reverse-копией с выводом в поток:

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

int main() {
    const std::vector numbers {
        "one", "two", "three", "four", "five", "six"
    };

    auto outStream = std::ostream_iterator<std::string>(std::cout, "; ");

    // standard version:
    std::copy(begin(numbers), end(numbers), outStream);
    std::cout << '\n';
    std::reverse_copy(begin(numbers), end(numbers), outStream);

    // ranges version:
    std::cout << "\nRanges\n";
    std::ranges::copy(numbers, outStream);
    std::cout << '\n';
    std::ranges::reverse_copy(numbers, outStream);
}

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

Вывод:

one; two; three; four; five; six;
six; five; four; three; two; one;
Ranges
one; two; three; four; five; six;
six; five; four; three; two; one;

Как видите, работать с этой версией очень просто.

Подробности на @Cppreference — ranges::reverse и @Cppreference — ranges::reverse_copy.

`rotate`

На этот раз давайте поработаем со словами и попробуем развернуть их:

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

int main() {
    std::vector<std::string> words { "hello", "in", "the",
        "wonderful", "world", "of", "c++", "programming",
    };

    std::ostream_iterator<std::string> out(std::cout, " ");

    // standard version:
    std::ranges::copy(words, out);
    std::cout <<'\n';
    auto firstWord = words[0];
    auto newPos = std::rotate(begin(words), std::next(begin(words), 1), end(words));
    std::ranges::copy(words, out);
    std::cout <<'\n';
    std::cout << std::quoted(firstWord) << " is now at pos "
              << std::distance(begin(words), newPos) << '\n';

    // ranges version:
    auto helloPos = std::ranges::find(words, "hello");
    if (helloPos != end(words)) {
        auto firstWord = words[0];
        auto ret = std::ranges::rotate(words, helloPos);
        std::ranges::copy(words, out);
        std::cout <<'\n';
        std::cout << std::quoted(firstWord) << " is now at pos "
                  << std::distance(begin(words), ret.begin()) << '\n';
    }
}

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

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

Вывод:

hello in the wonderful world of c++ programming
in the wonderful world of c++ programming hello
"hello" is now at pos 7
hello in the wonderful world of c++ programming
"in" is now at pos 1

Подробности на ranges::rotate @Cppreference.

`shuffle`

Напомню, что std::random_shuffle объявлен устаревшим и удалён в C++17. Начиная с C++11, лучше всего использовать std::shuffle или std::ranges::shuffle, которые принимают в качестве параметра объект случайного генератора, а не полагаются на rand().

Давайте посмотрим на простой пример:

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

int main() {
    std::vector<std::string> words {
        "box", "tv", "car", "bricks", "game", "ball"
    };

    std::mt19937 rng{std::random_device{}()};

    auto print = [](std::string_view str, const auto& cont) {
        std::cout << str << ": ";
        for (const auto &w : cont)
            std::cout << w << ", ";
        std::cout << '\n';
    };

    print("before", words);

    // the standard version:   
    std::shuffle(begin(words), end(words), rng);    
    print("after ", words);

    // the ranges version:
    // the standard version:   
    std::ranges::shuffle(words, rng);
    print("after ", words);                
}

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

Подробности на ranges::shuffle @Cppreference.

`sample`

std::sample — относительно новый алгоритм, доступный с C++17. Он позволяет с равномерной вероятностью случайно выбрать n элементов из последовательности. Это не аналог constexpr. Давайте посмотрим на пример:

#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}
    };

    std::mt19937 rng{std::random_device{}()};
    const size_t firstRoundCount = 4;
    const size_t secondRoundCount = 2;

    // the standard version:
    std::vector<Product> selected;    
    std::sample(begin(prods), end(prods),
                std::back_inserter(selected),
                firstRoundCount,  rng);

    std::cout << firstRoundCount << " selected products: \n";
    for (const auto &elem : selected)
        std::cout << elem.name_ << '\n';

    // the ranges version:
    std::vector<Product> onlyTwo;
    std::ranges::sample(selected,
                std::back_inserter(onlyTwo),
                secondRoundCount,  rng);       

    std::cout << secondRoundCount << " winners: \n";
    for (const auto &elem : onlyTwo)
        std::cout << elem.name_ << '\n';                 
}

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

Читать подробнее на ranges::sample @Cppreference.

`unique`

Алгоритм unique() позволяет очистить последовательную группу эквивалентных элементов. Например, из {1, 1, 5, 5, 2, 2, 3, 3, 4, 4, 5, 5} вы можете удалить все дубликаты и получить {1 , 5, 2, 3, 4, 5}. Обратите внимание, что не все 5 были удалены, а только те, что были в той же «группе».

Давайте посмотрим на следующий пример, где я удаляю дубликаты слов:

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

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

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

    auto print = [](std::string_view str, const std::vector<Product>& cont) {
        std::cout << str << ": ";
        for (const auto &p : cont)
            std::cout << p.name_ << ", ";
        std::cout << '\n';
    };

    print("before:        ", prods);
    auto ret = std::ranges::unique(prods, {}, &Product::name_);
    prods.erase(ret.begin(), ret.end());
    print("after unique:  ", prods);                 
    std::ranges::sort(prods, {}, &Product::name_);
    print("after sort:    ", prods);          
    ret = std::ranges::unique(prods, {}, &Product::name_);
    prods.erase(ret.begin(), ret.end());
    print("another unique:", prods);                 
}

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

Вывод:

before:        : box, box, toy, box, tv, tv, car, box, toy, cake,
after unique:  : box, toy, box, tv, car, box, toy, cake,
after sort:    : box, box, box, cake, car, toy, toy, tv,
another unique:: box, cake, car, toy, tv,

Как видите, этот пример не охватывает стандартную версию, а фокусируется только на ranges::unique.

После первого запуска unique() вектор prods модифицируется таким образом, что удаляемые элементы передаются в конец контейнера. Более того, они имеют неопределённое значение. Вот почему я использовал erase, чтобы удалить эти элементы из контейнера. Объект ret содержит поддиапазон, указывающий на первый «удалённый» элемент и конец входного диапазона.

После первой «итерации» все еще есть некоторые повторяющиеся элементы, но они не принадлежат одной и той же «группе». Чтобы исправить это, можно отсортировать элементы (я использую проекцию, чтобы смотреть только на элемент данных name_). После сортировки элементов можно подчистить остальные дубликаты. Конечно, сортировку можно сделать перед всей очисткой.

Подробности на ranges::unique @Cppreference.

Заключение

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

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

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

Data Science и Machine Learning

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

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

Java и C#

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

А также

Комментарии (1)

sergio_nsk
30.12.2022 09:21
#25061998
Алгоритмы - это всё просто. Кто бы рассказал про view.

Алгоритмы диапазонов C++20 — 11 модифицирующих операций +2

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

copy_if

fill

generate

transform

remove

replace

reverse

rotate

shuffle

sample

unique

Заключение

Комментарии (1)

sergio_nsk

`copy_if`

`fill`

`generate`

`transform`

`remove`

`replace`

`reverse`

`rotate`

`shuffle`

`sample`

`unique`