Range Based Algorithms and std::ranges::sort

In earlier lessons, we saw how we could standardize traversal through any type of container by using iterators.

Having done that, we gain the benefit of being able to use or create algorithms that work across any of those containers. For example, if we have a container representing a party of characters, we might need to create algorithms to do things like:

• Sort the characters by their name
• Find the highest-level character in the party
• Count how many healers are in the party
• Remove all the characters who are disconnected

Let's start simple, and build up our knowledge over the coming lessons.

Sorting a Vector

We can sort a vector using std::ranges::sort, which is available by including <algorithm>

1#include <vector>
2#include <iostream>
3#include <algorithm>
4
5int main() {
6  std::vector Numbers { 3, 1, 2 };
7  std::ranges::sort(Numbers);
8  for (auto Num : Numbers) {
9    std::cout << Num;
10  }
11}
12

1123
2

Customizing the Sort Behaviour

In order to sort the items in a collection, the compiler needs to know what it means to sort those items. Numbers can be compared with the < operator, so our vector of integers worked by default.

However, our custom types might not overload the comparison operators, and it might not make sense for them to do so.

Fortunately, we can pass a second argument to sort - an optional comparison function.

This function is going to receive the current and previous items and will then return true or false. That boolean value determines how the range will be sorted.

Previously, our vector of numbers was arranged in ascending order. But, we can control the sorting by providing our own comparison function.

Let's use a lambda that will sort the items in reverse order:

1std::vector Numbers { 3, 1, 2 };
2
3std::ranges::sort(Numbers, [](int a, int b){
4  return a > b;
5} );
6
7for (auto Num : Numbers) {
8  std::cout << Num;
9}
10

1321
2

1[](int a, int b){
2  return a > b;
3}
4

1std::ranges::sort(Numbers, std::ranges::greater{});
2

With the ability to pass a custom comparison function, we can now sort items of any type, in any order we desire. Let's sort a party of characters by their level:

1#include <vector>
2#include <iostream>
3#include <algorithm>
4
5class Character {
6public:
7  std::string Name;
8  int Level;
9};
10
11int main() {
12  std::vector Party {
13    Character {"Legolas", 49},
14    Character {"Gimli", 47},
15    Character {"Gandalf", 53}
16  };
17
18  std::ranges::sort(Party, [](Character& a, Character& b){
19    return a.Level > b.Level;
20  } );
21
22  for (const auto& Character : Party) {
23    std::cout << "[" << Character.Level << "] "
24              << Character.Name << "\n";
25  }
26}
27

1[53] Gandalf
2[49] Legolas
3[47] Gimli
4

Subranges

Sometimes, we only want an algorithm to apply to part of our range. By including <ranges> we get access to std::ranges::subrange, which allows us to create a subrange from a parent range. One way to specify a subrange is to specify starting and ending iterators. Here, we create a subrange that covers the entire container:

1#include <algorithm>
2#include <ranges>
3#include <vector>
4
5int main() {
6  std::vector Numbers{3, 5, 2, 1, 4};
7  auto Subrange = std::ranges::subrange(
8    Numbers.begin(), Numbers.end()
9  );
10
11  for (auto Num : Subrange) {
12    std::cout << Num;
13  }
14}
15

135214
2

In the next example, we use std::next and std::prev to traverse through our iterators, ultimately passing different starting and ending points to std::ranges::subrange. This has the effect that we create a subrange that omits the first and last element of the original range:

1#include <algorithm>
2#include <ranges>
3#include <vector>
4
5int main() {
6  std::vector Numbers{3, 1, 2, 5, 4};
7  auto Subrange = std::ranges::subrange(
8    std::next(Numbers.begin(), 1),
9    std::prev(Numbers.end(), 1)
10  );
11
12  for (auto Num : Subrange) {
13    std::cout << Num;
14  }
15}
16

1521
2

A subrange is an example of a view. We cover views in detail later in this chapter. For now, the key point is that a view maintains a connection to the container it was created from. One effect of this is that changes made to the view apply to the original container.

We see an example of this In the following code. Note that we’re passing the subrange to the std::ranges::sort algorithm, but we’re then logging out the contents of the original container. This demonstrates how sorting the subrange had the effect of sorting the middle three elements of the container:

1#include <algorithm>
2#include <ranges>
3#include <vector>
4
5int main() {
6  std::vector Numbers{3, 1, 2, 5, 4};
7  auto Subrange = std::ranges::subrange(
8    std::next(Numbers.begin(), 1),
9    std::prev(Numbers.end(), 1)
10  );
11
12  std::ranges::sort(Subrange)
13
14  for (auto Num : Numbers) {
15    std::cout << Num;
16  }
17}
18

131254
2

Using Iterators with Algorithms

The previous examples show us applying the algorithm to a range. However, sort and almost all of the other algorithms we’ll show in this chapter have a variant that works directly with iterators instead.

Whilst the range variant of sort is available under std::ranges::sort, the iterator variant is available as std::sort. The same pattern applies to most of the other algorithms we’ll cover in this chapter.

The following sorts the entire container, just like before, but it does so using std::sort instead:

1std::vector Numbers{3, 5, 2, 1, 4};
2std::sort(Numbers.begin(), Numbers.end());
3
4for (auto Num : Numbers) {
5  std::cout << Num;
6}
7

112345
2

The following example uses the same technique to sort only the middle of the container, leaving the first and last elements in position:

1std::vector Numbers{3, 5, 2, 1, 4};
2std::sort(
3  std::next(Numbers.begin(), 1),
4  std::prev(Numbers.end(), 1)
5);
6
7for (auto Num : Numbers) {
8  std::cout << Num;
9}
10

131254
2

Algorithm Requirements - Fixing the constraint was not satisfied errors

Many of the algorithms require the container or iterator passed to them to meet specific requirements. For example, the std::ranges::sort or std::sort algorithms require our range or iterators to support random access.

Therefore, it cannot be run on a container such as a linked list:

1std::forward_list Numbers{3, 1, 2, 5, 4};
2std::ranges::sort(Numbers);
3

When a container does not meet the requirements of an algorithm, we should get a somewhat useful error message from the compiler. In this case, it is telling us our iterator is not a random access iterator, or something that derives from it:

1concept std::derived_from<std::random_access_iterator>
2evaluated to false - the constraint was not satisfied
3

Just because a container isn’t compatible with an algorithm like sort, that doesn’t necessarily mean we can’t sort the container. We just need to find another way. For example, std::forward_list has a sort method.

So, even though it’s not compatible with the generic algorithm, we can just use the one that was specifically created for linked lists:

1#include <algorithm>
2#include <forward_list>
3#include <iostream>
4
5int main() {
6  std::forward_list Numbers{3, 1, 2, 5, 4};
7  Numbers.sort();
8
9  for (auto Num : Numbers) {
10    std::cout << Num;
11  }
12}
13

112345
2