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:
Let's start simple, and build up our knowledge over the coming lessons.
We can sort a vector using std::ranges::sort
, which is available by including <algorithm>
#include <vector>
#include <iostream>
#include <algorithm>
int main() {
std::vector Numbers { 3, 1, 2 };
std::ranges::sort(Numbers);
for (auto Num : Numbers) {
std::cout << Num;
}
}
123
As the code above would suggest, we’re using an algorithm that relates to “ranges”. Ranges are an additional abstraction built on top of iterators. They allow us to use and create algorithms that work across different container classes.
Any container that supports begin()
and end()
is a “range”, and can therefore be used with range-based algorithms. All the algorithms we introduce in this chapter are range-based.
We’re using both containers and algorithms from the standard library in these examples, but we’re not restricted to the standard library. If a container is a range, and an algorithm works on ranges, they’re likely to be interoperable, even if their code came from totally different sources.
Note, however, just because a container is a valid range, that does not mean it will work with all range-based algorithms. Those algorithms may have additional requirements for the containers they operate on.
For example, the standard library’s ranges::sort
requires the container to support random access to elements in any position. So, it can be used with arrays and vectors, but not linked lists.
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:
std::vector Numbers { 3, 1, 2 };
std::ranges::sort(Numbers, [](int a, int b){
return a > b;
} );
for (auto Num : Numbers) {
std::cout << Num;
}
321
In the previous example, we created the following lambda to pass to std::ranges::sort
:
[](int a, int b){
return a > b;
}
This is a fairly common requirement, so the standard library has implemented helpers for this.
Rather than writing our own function, we could use a templated functor from the standard library’s <ranges>
 header.
The functor that calls >
is created from the std::ranges::greater
 struct:
std::ranges::sort(Numbers, std::ranges::greater{});
Functors that implement the other comparison operators are also available:
>
from std::ranges::greater
<
from std::ranges::less
>=
from std::ranges::greater_equal
<=
from std::ranges::less_equal
==
from std::ranges::equal_to
!=
from std::ranges::not_equal_to
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:
#include <vector>
#include <iostream>
#include <algorithm>
class Character {
public:
std::string Name;
int Level;
};
int main() {
std::vector Party {
Character {"Legolas", 49},
Character {"Gimli", 47},
Character {"Gandalf", 53}
};
std::ranges::sort(Party, [](Character& a, Character& b){
return a.Level > b.Level;
} );
for (const auto& Character : Party) {
std::cout << "[" << Character.Level << "] "
<< Character.Name << "\n";
}
}
[53] Gandalf
[49] Legolas
[47] Gimli
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:
#include <algorithm>
#include <ranges>
#include <vector>
int main() {
std::vector Numbers{3, 5, 2, 1, 4};
auto Subrange = std::ranges::subrange(
Numbers.begin(), Numbers.end()
);
for (auto Num : Subrange) {
std::cout << Num;
}
}
35214
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:
#include <algorithm>
#include <ranges>
#include <vector>
int main() {
std::vector Numbers{3, 1, 2, 5, 4};
auto Subrange = std::ranges::subrange(
std::next(Numbers.begin(), 1),
std::prev(Numbers.end(), 1)
);
for (auto Num : Subrange) {
std::cout << Num;
}
}
521
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:
#include <algorithm>
#include <ranges>
#include <vector>
int main() {
std::vector Numbers{3, 1, 2, 5, 4};
auto Subrange = std::ranges::subrange(
std::next(Numbers.begin(), 1),
std::prev(Numbers.end(), 1)
);
std::ranges::sort(Subrange)
for (auto Num : Numbers) {
std::cout << Num;
}
}
31254
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:
std::vector Numbers{3, 5, 2, 1, 4};
std::sort(Numbers.begin(), Numbers.end());
for (auto Num : Numbers) {
std::cout << Num;
}
12345
The following example uses the same technique to sort only the middle of the container, leaving the first and last elements in position:
std::vector Numbers{3, 5, 2, 1, 4};
std::sort(
std::next(Numbers.begin(), 1),
std::prev(Numbers.end(), 1)
);
for (auto Num : Numbers) {
std::cout << Num;
}
31254
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:
std::forward_list Numbers{3, 1, 2, 5, 4};
std::ranges::sort(Numbers);
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:
concept std::derived_from<std::random_access_iterator>
evaluated to false - the constraint was not satisfied
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:
#include <algorithm>
#include <forward_list>
#include <iostream>
int main() {
std::forward_list Numbers{3, 1, 2, 5, 4};
Numbers.sort();
for (auto Num : Numbers) {
std::cout << Num;
}
}
12345
Comprehensive course covering advanced concepts, and how to use them on large-scale projects.