Range Based Algorithms and std::ranges::sort

Learn how to efficiently work with collections of objects using range-based algorithms in C++
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

a72.jpg
Ryan McCombe
Ryan McCombe
Posted

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>

#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

Ranges

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.

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:

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

Standard Library Comparison Functors

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

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:

#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

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:

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

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:

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

Was this lesson useful?

Ryan McCombe
Ryan McCombe
Posted
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Iterators and Algorithms
7a.jpg
This lesson is part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access!

This course includes:

  • 106 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Next Lesson

Ranges and Sentinels

A practical guide to defining ranges using sentinel values, and why we sometimes need to
3D Character Concept Art
Contact|Privacy Policy|Terms of Use
Copyright © 2023 - All Rights Reserved