C++20 Ranges Algorithms - sorting, sets, other and C++23 updates

Table of Contents

This article is the third and the last one in the mini-series about ranges algorithms. We’ll look at some sorting, searching, and remaining algorithms. We’ll also have a glimpse of cool C++23 improvements in this area.

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 sorting algorithms, partitioning, binary search, and some other functions.

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

the first article on “7 Non-modifying Operations”.

the second article on “11 Modifying Operations”

Partitioning & Sorting

`sort` and `is_sorted`

The Sorting algorithm often comes as an advertisement for ranges. If you have a container, then thanks to ranges, you can write:

std::ranges::sort(myContainer);

See the example for a bettwer overview:

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

Play @Compiler Explorer

In many implementations, the Introsort (see Wikipedia) is used. It’s a hybrid solution with usually a quick sort/heap sort and then insertion sort for small (sub)ranges.

Other versions of sorting algorithms:

partial_sort - sorts the first N elements of a range.
stable_sort - the order of equivalent elements is stable, i.e. guaranteed to be preserved.

As you can see, with the ranges version, it’s straightforward to pass a projection and sort by a given sub-part of the element. In the regular version, you need a separate lambda…

Read more at ranges::sort @Cppreference.

`partition`

Partitioning is an essential part of quick sort. For a given predicate, the operation moves elements matching the predicate to the first part of the container and non-matching to the second part. Sometimes, you might partition a container rather than perform the full sorting operation. Have a look at the following example:

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

Play @Compiler Explorer

The output:

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

As you can see, we could easily divide the container into two groups: the first part contains elements smaller than 7, and the second part with elements >= 7. The relative order between elements might be altered (you need stable_partition to keep that order).

The interface for partition is relatively simple. The ranges version additionally takes a projection, but the example didn’t use it. One difference is that ranges::partition returns a subrange rather than an iterator (as with the std:: version).

See more about the algorithms at ranges::is_partitioned and ranges::partition @C++Reference.

Binary Search operations

If your container is already sorted, then you can perform logarithmic binary search operations.

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

Run @Compiler Explorer

See more at ranges::binary_search @C++Reference.

Additionally you can use related algorithms:

std::ranges::lower_bound - cppreference.com - returns an iterator to the first element not less than the given value
std::ranges::upper_bound - cppreference.com - returns an iterator to the first element greater than a certain value

Set operations

There are many set-related functions in the library some of them:

ranges::merge - merges two sorted ranges
ranges::inplace_merge - merges two ordered ranges in-place
ranges::includes - returns true if one sorted sequence is a subsequence of another sorted sequence
ranges::set_difference - computes the difference between two sets
ranges::set_intersection - computes the intersection of two sets
ranges::set_symmetric_difference - computes the symmetric difference between two sets
ranges::set_union - computes the union of two sets

As an example let’s have a look at one case with includes:

`includes`

Returns true if the sorted range is a subsequence of another sorted range.

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

Play @Compiler Explorer

The ranges version is simpler and offers a way to check against different containers. With the std:: approach, the iterator needs to be dereferenced and then implicitly converted to both input container element types.

See more at std::includes @cppreference.com.

Other

`max_element`

Searching for the max element in a container (unsorted):

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

Play @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';
}

Play @Compiler Explorer

See more at ranges::equal @C++Reference.

Even more

My list of algorithms is not complete. Almost all standard algorithms have their std::ranges:: alternative. Have a look at the following interesting algorithms that haven’t been mentioned in the series:

Heap operations:

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

Permutations:

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

Uninitialized memory algorithms:

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

As of C++20, we have most of the corresponding ranges algorithms from the <algorithm> header, but the <numeric> header is missing.

Soon in C++23

C++23 specification is almost complete and in the feature-freeze mode. So far I’m aware of the following algorithms that we’ll land in the new C++ version:

ranges::starts_with and ranges::ends_with (as of June 2022 available in the MSVC compiler)
ranges::contains (P2302)
ranges::shift_left and ranges::shift_right,
ranges::iota
ranges::fold - as an alternative for std::accumulate

Summary

This article completes our journey through most C++ algorithms available in the Standard Library (except for numerics). Most of the algorithms have their ranges:: counterparts, and in C++23, we’ll have even more additions.

Would you like to see more?
I packed all three articles in a nice-looking and updated PDF (31-pages!), get it here "An Overview of C++20 Ranges Algorithms, all parts". It's available for all C++ Stories Premium/Patreon members. See all Premium benefits here.

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.

C++20 Ranges Algorithms - sorting, sets, other and C++23 updates

Before we start

Partitioning & Sorting

sort and is_sorted

partition

Binary Search operations

binary_search

Set operations

includes

Other

max_element

equal

Even more

Numeric

Soon in C++23

Summary

Back to you

Similar Articles:

`sort` and `is_sorted`

`partition`

`binary_search`

`includes`

`max_element`

`equal`