Table of Contents

In the previous article in the Ranges series, I covered some basics and non-modifying operations. Today it’s time for algorithms like transform, copy, generate, shuffle, and many more…. and there’s rotate as well :)

Let’s go.

Before we start  

Key observations for std::ranges algorithms:

  • Ranges algorithms are defined in the <algorithm> header, while the ranges infrastructure and core types are defined in the <ranges> header.
  • Usually, there are at least two overloads for range algorithms: with a pair of iterators and an overload with a single range argument.
  • The version that returns a subrange or an iterator and takes a range returns a borrowed range or a borrowed iterator. This helps detect iterators to temporary ranges.
  • The range versions take projections which allow more flexibility; for example, you can sort against some selected members or perform additional transformations before the comparison.
  • The ranges version doesn’t have a parallel execution option (you cannot pass the std::execution policy).
  • The ranges algorithms, similarly to standard algorithms as of C++20, are also constexpr.
  • As of C++20, there are no numerical ranges algorithms corresponding to the <numeric> header.

Below, you can find examples showing a standard algorithm and an alternative version with ranges. They illustrate some basic concepts and try not to use advanced ranges composition or views. We’ll go with the order found at cppreference/algorithms.

This part will cover some of the algorithms that allow changing the sequence, like copying, removing, transforming, or generating elements.

This is the second part of the on Ranges Algorithms. See:

copy_if  

There are many variations of this core algorithm: copy, copy_if, copy_n or even copy_backward.

In a basic form copy_if is defined as follows:

// 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 = {} );

Let’s try a basic example with:

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

Play @Compiler Explorer.

In the example, I copy elements from the vector into the output stream. Additionally, as a filter step, I want only products that are not “none”. Since we copy whole elements to the stream, I had to implement operator<< for the Product class.

Thanks to projections, I could also write a following version:

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

The code is a bit longer, but now the predicate takes a string rather than a whole Product object.

See more at 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, "; "));
}

Play @Compiler Explorer

The fill algorithm walks on the range and then performs the assignment with the value you pass. The value might have been of a different type than the elements in the container.

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

In the example, I used a class with a custom conversion operator, and that’s why we can use it to modify the name_ data member based on the integral input value.

See more at ranges::fill @Cppreference.

generate  

While fill() uses the same value to assign to all elements, generate() uses a function object to generate the value. In the example we can similate the iota generation:

#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, "; "));
}

Play @Compiler Explorer.

The output:

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;

See more at ranges::generate @Cppreference. And there’s also an alternative version with _n: ranges::generate_n.

transform  

transform() is a robust algorithm that has many variations.

In a basic form it looks as follows:

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

It takes a range r and then uses op to transform elements from that range and output it into the result, which is an iterator.

See the basic example:

#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_ << ", ";
}

Play @Compiler Explorer.

The output:

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,

The example transforms the same container but adds numbers - generated through a function - to each name.

There’s also a version that takes two ranges and combines them with a binary operation:

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

We can use this version to “join” two containers and produce a single value:

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_ << ", ";

Play @Compiler Explorer.

See more at [ ranges::transform @Cppreference.

This article started as a preview for Patrons, sometimes even months before the publication. If you want to get extra content, previews, free ebooks and access to our Discord server, join the C++ Stories Premium membership or see more information.

remove  

In C++20, we have a more efficient way to remove and erase elements from various containers. See std::erase_if, a set of overloaded functions for consistent container erasure. You can read more in my article: 20 Smaller yet Handy C++20 Features - Consistent Container Erasure.

For completeness, let’s compare all three versions:

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

Play @Compiler Explorer.

The ranges version can shorted the call to:

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

into:

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

But, in my opinion, this doesn’t look that much better. ranges::remove_if returns a subrange, so you need to get its begin() and possibly end() anyway.

It’s much easier to write:

std::erase_if(tempProds, checkNoPrefix);

See more at ranges::removeranges::remove_if @Cppreference and also std::erase, std::erase_if (std::vector) @Cppreference (each container has it’s own overload for std::erase).

replace  

How to replace elements inside a container:

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

Play @Compiler Explorer.

The output:

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;

The interesting part is that in the standard version we compare a value against objests stored in the container:

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

And that’s why I had to define a comparison operator == (or a spaceship <=> to be more flexible).

In the ranges version we can use projection as the comparison is a bit different:

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

And in the example, there’s no need to have the == operator, as we can compare strings directly. This gives us more flexibility, as we can find more “Invalid” values (the value of value_ is not checked now to catch both - 0.0 and -10.0 and fix them).

See more ranges::replaceranges::replace_if @Cppreference.

Would you like to see more?
To see more examples about projections and how to use them as a function argument, see this bonus article: "Utilities And Projections - C++17/C++20". It's available for C++ Stories Premium/Patreon members. See all Premium benefits here.

reverse  

Let’s try the version with a reverse copy that outputs to the stream:

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

Play @Compiler Explorer.

The output:

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;

As you can see, the ranges version is super simple to use

See more @Cppreference - ranges::reverse and @Cppreference - ranges::reverse_copy.

rotate  

This time let’s work with words and try to rotate them around:

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

Play @Compiler Explorer.

The example starts from a sentence and rotates it so that the word "the" is now the first word. Later in the ranges version, we try to find the first word of the initial sentence, and then we shift it again to get to the start.

The output:

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

See more ranges::rotate @Cppreference.

shuffle  

As a reminder, std::random_shuffle was deprecated and removed in C++17. Since C++11, it’s best to use std::shuffle or std::ranges::shuffle that takes a random generator object as a parameter rather than relying on rand().

Let’s have a look at the basic example:

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

Play @Compiler Explorer.

See more ranges::shuffle @Cppreference.

sample  

std::sample is a relatively new algorithm available since C++17. It allows you to select n items at random (uniform probabliity) from a sequence. It’s not constexpr. Let’s see an example:

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

Play @Compiler Explorer.

See more ranges::sample @Cppreference.

unique  

The unique() algorithm allows you to clean up a consecutive group of equivalent elements. For example, from {1, 1, 5, 5, 2, 2, 3, 3, 4, 4, 5, 5} you may want to remove all duplicates and get {1, 5, 2, 3, 4, 5}. Please note that not all 5’s were removed, only those in the same “group”.

Let’s have a look at the following sample where I want to remove such duplicates:

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

Play @Compiler Explorer.

The output:

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,

As you can see, this example didn’t cover the standard version and only focused on the ranges::unique.

After the first run to unique(), the prods vector is modified so that elements to be removed are passed to the end of the container. What’s more, they are of unspecified value. That’s why I used erase to remove those elements from the container. The ret object contains a sub-range pointing to the first “removed” element and the end of the input range.

After the first “iteration,” there are still some duplicated elements, but they don’t share the same “group”. To fix this, we can sort elements (I’m using a projection to look only at the name_ data member). After all, elements are sorted, we can clean up the rest of duplicates. Of course, you can do the sorting before the whole cleanup.

See more ranges::unique @Cppreference.

Summary  

Wow, we covered a lot of excellent algorithms!

As you can see, with the ranges versions, you can simplify code and pass the whole sequence, the entire container. In many cases, this results in a much easier-to-read code.

Stay tuned for the next part, where I’ll cover sorting algorithms, binary search, and others… and we’ll have a glace of what’s coming in C++23 regarding new algorithms.

Back to you

  • What’s your favorite aspect of ranges algorithms?
  • Have you tried them in your projects?

Share your opinion and experience in the comments below the article.