# Iterator and Range-Based Algorithms

An introduction to iterator and range-based algorithms, using examples from the standard library
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
###### Ryan McCombe
Updated

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

By doing so, we gain the benefit of being able to use or create algorithms that work across any of thoseÂ containers.

The standard library's <algorithm> header includes over a hundred generally useful algorithms based on iterators andÂ ranges.

## Example: Sorting Using Iterators

Once weâ€™ve included the <algorithm> header, we can pass an iterator pair to std::sort(). The algorithm will traverse between those two iterators, putting all of the elements inÂ order:

#include <vector>
#include <iostream>
#include <algorithm>

int main() {
std::vector Numbers { 3, 1, 2 };
std::sort(Numbers.begin(), Numbers.end());
for (auto Num : Numbers) {
std::cout << Num << ", ";
}
}
1, 2, 3,

## Example: Sorting Using Ranges

Almost all of the iterator-based algorithms in the standard library have a variation that works with ranges. These are available within the std::ranges namespace. For example, the range-based variation of std::sort() is std::ranges::sort().

Rather than an iterator pair, we can call it with a single argument - the range we want to run the algorithmÂ on:

#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 << ", ";
}
}
1, 2, 3,

## Applying an Algorithm to a Subrange

Our previous examples sorted our entire container, but we can apply an algorithm to only part of aÂ container.

With iterator-based algorithms, we can do this by passing different iterators as arguments. Below, we sort the middle three elements of ourÂ container:

#include <vector>
#include <iostream>
#include <algorithm>

int main() {
std::vector Numbers { 3, 5, 1, 2, 4 };

std::sort(
std::next(Numbers.begin(), 1),
std::prev(Numbers.end(), 1)
);

for (auto Num : Numbers) {
std::cout << Num << ", ";
}
}
3, 1, 2, 5, 4,

We can do the same thing using the overload of range-based algorithms by defining the range using an iterator and a sentinel. In this case, the sentinel is another iterator but, as we covered in the previous lesson, it doesnâ€™t need toÂ be:

#include <vector>
#include <iostream>
#include <algorithm>

int main() {
std::vector Numbers { 3, 5, 1, 2, 4 };

std::ranges::sort(
std::next(Numbers.begin(), 1),
std::prev(Numbers.end(), 1)
);

for (auto Num : Numbers) {
std::cout << Num << ", ";
}
}
3, 1, 2, 5, 4,

There are many more ways of generating subranges from a range, which weâ€™ll explore through the rest of thisÂ chapter.

## Algorithm Container Requirements

Fixing "the constraint was not satisfied" errors

As we covered earlier in the chapter, not all ranges and iterators have the same capabilities. For example, some ranges might support random access, whilst others may only support forwardÂ access.

Many algorithms have specific requirements for the ranges and iterators passed toÂ them.

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:

#include <forward_list>
#include <algorithm>

int main() {
std::forward_list Numbers { 3, 1, 2 };
std::ranges::sort(Numbers);
}

We can check the requirements of any algorithm from theÂ documentation.

We may often also get useful error messages from the compiler if our container does not meet theÂ requirements.

Below, we see std::ranges::sort() requires the std::ranges::random_access_range concept to be satisfied, but std::forward_list does not meet theÂ requirements:

error: the concept 'std::ranges::random_access_range<std::forward_list<int>>' evaluated to false - the constraint was not satisfied

Just because a container isnâ€™t compatible with a generic algorithm, that doesnâ€™t necessarily mean we canâ€™t perform the task some otherÂ way.

Perhaps thereâ€™s a different algorithm we could use, or we could create ourÂ own.

For example, even though std::forward_list doesnâ€™t generate iterators compatible with std::sort(), it has its own native sort()Â method:

#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 << ", ";
}
}
1, 2, 3, 4, 5,

## Algorithm Element Requirements

Beyond container requirements, algorithms may additionally have expectations of the type of objects stored within ourÂ container.

For example, using std::ranges::sort() or std::sort() on a collection only makes sense when the type of data within that collection isÂ orderable.

If we create an arbitrary type, and attempt to sort a container of them, the algorithm is not going to know how to doÂ it:

#include <vector>
#include <algorithm>

struct SomeType {
SomeType(int x) : Value{x} {}
int Value;
};

int main() {
std::vector<SomeType> Numbers { 3, 1, 2 };
std::ranges::sort(Numbers);
}
the associated constraints are not satisfied
the concept 'std::sortable' evaluated to false

We cover ordering in more detail in a later chapter, but we can make a type compatible with std::sort() by implementing the == and <=>Â operators:

#include <vector>
#include <algorithm>
#include <iostream>

struct SomeType {
SomeType(int x) : Value{x} {}
auto operator<=>(const SomeType& Other) const {
return Value <=> Other.Value;
}
bool operator==(const SomeType& Other) const {
return Value == Other.Value;
}

int Value;
};

int main() {
std::vector<SomeType> Container{3, 1, 2};
std::ranges::sort(Container);

for (const SomeType& Object : Container) {
std::cout << Object.Value << ", ";
}
}
1, 2, 3,

Other algorithms may have different requirements. Some algorithms might require our type to be default constructible or to implement an assignment operator forÂ example.

## Algorithm Preconditions

The final requirement that is worth considering is whether or not the algorithm weâ€™re using makes any assumptions that are not enforced by theÂ compiler.

For example, binary search is a very efficient algorithm for finding objects in a container, but it relies on the container beingÂ sorted.

As such, the standard libraryâ€™s implementation of binary search - std::binary_search has that sameÂ assumption.

When reading documentation, we must check for these types of requirements carefully, because theyâ€™re very difficult to enforce automatically. Instead of a compiler error, weâ€™ll typically just get incorrect behaviors at run timeÂ instead.

Below, we use binary search on a container that isnâ€™t sorted, causing our program to have an incorrectÂ output:

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
std::vector Container{3, 1, 4, 5, 2};

bool Found{
std::ranges::binary_search(Container, 2)};

if (!Found) {
std::cout << "The container doesn't have 2";
}
}
The container doesn't have 2

## Algorithm Customisations

Depending on the algorithm weâ€™re using, we can often pass additional arguments to customise theÂ behavior.

For example, most range-based algorithms allow us to modify their behavior by providing an additional projection function, which we cover in detail in the nextÂ lesson.

Other algorithms, such as std::sort and std::ranges::sort may offer additional parameters specific to their useÂ case.

### Example: Customizing the Sort Behaviour of std::sort()

By default, the std::sort() and std::ranges::sort() algorithms use our typeâ€™s < operator to determine the ordering. That is, if A < B, then A should come before B after the algorithmÂ completes.

However, these algorithms have overloads that allow us to provide a different comparison function as an additionalÂ argument.

This function is going to receive two objects from our collection and should return true if the first object should come before the secondÂ object.

Previously, our vector of numbers was arranged in ascending order. Let's provide a lambda that will instead cause the algorithm to sort the objects in descendingÂ order:

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
std::vector Container{3, 1, 4, 5, 2};

std::ranges::sort(Container, [](int a, int b) {
return a > b;
});

for (int x : Container) {
std::cout << x << ", ";
}
}
5, 4, 3, 2, 1,

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

Commonly, we need functions like these that simply invoke an operator, 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, so our previous code could have been written likeÂ this:

std::ranges::sort(Nums, 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 players by theirÂ level:

#include <vector>
#include <iostream>
#include <algorithm>

struct Player {
std::string Name;
int Level;
};

int main() {
std::vector Party {
Player {"Legolas", 49},
Player {"Gimli", 47},
Player {"Gandalf", 53}
};

std::ranges::sort(Party,
[](Player& a, Player& b){
return a.Level > b.Level;
}
);

for (const auto& Player : Party) {
std::cout << "[" << Player.Level << "] "
<< Player.Name << "\n";
}
}
[53] Gandalf
[49] Legolas
[47] Gimli

## Summary

In this lesson, we introduced the idea of iterator and range-based algorithms. We learned how these concepts enable standardized traversal and manipulation of data across various containerÂ types.

### Key Learnings

• The use of iterators and ranges for standardized container traversal.
• Implementing std::sort() with iterator pairs to order elements.
• Utilizing std::ranges::sort() for range-based sorting.
• Applying algorithms to subranges using both iterator-based and range-based methods.
• Understanding container requirements for different algorithms, like the need for random access in std::sort().
• Workarounds for performing tasks on non-compatible containers, such as using std::forward_list's native sort() method to sort a linked list.
• Algorithms may have additional requirements of the type stored within the containers - for example, sort algorithms only work on containers of types that can be ordered.
• The importance of algorithm preconditions, illustrated with std::binary_search.
• Customizing algorithms' behavior using additional arguments, like a custom comparison function in sorting.
• Utilization of standard library comparison functors for common operations.
• Sorting items of any type and order using custom comparison functions in algorithms.

Next Lesson

### Projection Functions

Learn how to use projection functions to apply range-based algorithms on derived data
New: AI-Powered AssistanceAI Assistance

### Questions and HelpNeed Help?

Get instant help using our free AI assistant, powered by state-of-the-art language models.

Updated
Lesson Contents

### Iterator and Range-Based Algorithms

An introduction to iterator and range-based algorithms, using examples from the standard library

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

###### Iterator and Range-Based Algorithms

An introduction to iterator and range-based algorithms, using examples from the standard library

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:

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

### Projection Functions

Learn how to use projection functions to apply range-based algorithms on derived data