Comparison Algorithms

In this lesson, we cover all of the main standard library algorithms that are used to compare two collections:

• equal(): Determine if two collections contain the same objects, in the same order
• is_permutation(): Determine if two collections contain the same objects, in any order
• mismatch(): Find the first position where two collections deviate from each other
• lexicographical_compare(): Determine if one collection is "less than" another collection.
• lexicographical_compare_three_way(): Determine if one collection is less than, greater than or equal to another collection
• starts_with(): Check if the objects in one collection match the objects at the start of another collection
• ends_with(): Check if the objects in one collection match the objects at the end of another collection
• includes(): Check if one collection contains another collection - that is, if one is a subset or superset of the other

std::ranges::equal()

The equal() algorithm receives two input collections and returns true if they are equal. Collections are considered equal if they have the same objects, in the same order:

1#include <algorithm>
2#include <vector>
3#include <iostream>
4
5int main(){
6  std::vector A{1, 2, 3};
7  std::vector B{1, 2, 3};
8
9  if (std::ranges::equal(A, B)) {
10    std::cout << "Ranges are equal";
11  }
12}

1Ranges are equal

Overview of Algorithm Techniques

The algorithms in this lesson support all the usual techniques we’ve covered in the previous chapters. Below, we provide some examples using std::equal(), but the same techniques are available for all the other algorithms in this lesson too.

Custom Comparers

The algorithms in this lesson all rely on the ability to compare objects within collections. They all provide default behavior - for example, the equal() algorithm compares objects using the == operator.

But, we can customize this behavior by passing an additional argument to our algorithm calls. This argument is a function that will receive two objects from our collection, and return true if those objects should be considered equal.

Below, we run the equal() algorithm, where objects should be considered equal if their absolute value is equal:

1#include <algorithm>
2#include <vector>
3#include <iostream>
4#include <cmath> // For std::abs
5
6int main(){
7  std::vector A{1, -2, 3};
8  std::vector B{-1, 2, -3};
9
10  auto absEqual{
11    [](int x, int y){
12      return std::abs(x) == std::abs(y);
13    }};
14
15  if (std::ranges::equal(A, B, absEqual)) {
16    std::cout << "Ranges are equal";
17  }
18}

1Ranges are equal

Projection Functions

Projection functions receive objects from our collections, and return "projections" - different objects that are based on those inputs. The algorithm then uses those projections for their comparisons, rather than the original objects.

Below, we rewrite our previous example to use projection instead of a custom comparison.

We pass {} as our third argument, as we want to use the algorithm's default comparison operation.

We then pass our projection function as the fourth and fifth arguments. We pass it twice as the algorithm receives two input collections, and allows us to specify different projection functions for each collection.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, -2, 3};
7  std::vector B{-1, 2, -3};
8
9  auto P{[](int x){ return std::abs(x); }};
10
11  if (std::ranges::equal(A, B, {}, P, P)) {
12    std::cout << "Ranges are equal";
13  }
14}

1Ranges are equal

Projection functions do not need to return the same type as the original objects.

Below, our collections contain Character objects, whilst our projection functions ensure the comparison is done using the Name member of each Character, which is a std::string:

1#include <algorithm>
2#include <vector>
3#include <iostream>
4
5class Character {
6public:
7  Character(std::string Name) : Name{Name}{}
8  std::string GetName() const{ return Name; }
9
10private:
11  std::string Name;
12};
13
14int main(){
15  using namespace std::string_literals;
16  std::vector<Character> A{
17    "Anna"s, "Roderick"s};
18  std::vector<Character> B{
19    "Anna"s, "Roderick"s};
20
21  if (std::ranges::equal(A, B, {},
22                         &Character::GetName,
23                         &Character::GetName)) {
24    std::cout << "Ranges are equal";
25  }
26}

1Ranges are equal

Iterators / Sentinels

In most of the examples in this lesson, we pass our input ranges as a single argument. But, we have the option to provide our ranges as two arguments - an iterator and sentinel pair:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, 2, 3};
7  std::vector B{0, 1, 2, 3, 4};
8
9  if (std::ranges::equal(A.begin(), A.end(),
10                         B.begin() + 1,
11                         B.end() - 1)) {
12    std::cout << "A is in the middle of B";
13  }
14}

1A is in the middle of B

Views

Standard library views are also valid ranges, so they can be passed to these algorithms. Below, we use std::views::reverse with std::equal to determine if one collection is the reverse of another:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4#include <ranges>
5
6int main(){
7  std::vector A{1, 2, 3};
8  std::vector B{3, 2, 1};
9
10  if (std::ranges::equal(
11    A, std::views::reverse(B))) {
12    std::cout << "Ranges are reversed";
13  }
14}

1Ranges are reversed

std::ranges::is_permutation()

The is_permutation() algorithm determines whether the objects in two collections are equal, regardless of how the containers are ordered.

For example, 1, 2, 3 is not equal to 2, 1, 3, but it is a permutation:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, 2, 3};
7  std::vector B{2, 1, 3};
8
9  if (!std::ranges::equal(A, B)) {
10    std::cout << "Ranges are NOT equal";
11  }
12
13  if (std::ranges::is_permutation(A, B)) {
14    std::cout << "\nBut they ARE a permutation";
15  }
16}

1Ranges are NOT equal
2But they ARE a permutation

If two collections are equal to each other, is_permutation() also returns true.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, 2, 3};
7  std::vector B{1, 2, 3};
8
9  if (std::ranges::equal(A, B)) {
10    std::cout << "Ranges are equal";
11  }
12
13  if (std::ranges::is_permutation(A, B)) {
14    std::cout << "\nAnd also a permutation";
15  }
16}

1Ranges are equal
2And also a permutation

std::ranges::mismatch()

The mismatch() algorithm compares two input collections, and lets us determine where they deviate. That is, it lets us return the first position in the collections where their respective objects fail an equality check.

In the following example, the first mismatch occurs when comparing the 2 within A to the 3 within B:

1#include <algorithm>
2#include <vector>
3
4int main() {
5  std::vector A{1, 2, 3};
6  std::vector B{1, 3, 4};
7
8  auto Result { std::ranges::mismatch(A, B) };
9}

The mismatch() algorithm returns a std::ranges::mismatch_result. This is an alias for std::ranges::in_in_result – a simple struct that contains iterators corresponding to the two input ranges.

For the mismatch() algorithm, the two data members contain:

• in1 - an iterator for where the mismatch was found, within the context of the first input range
• in2 - an iterator for where the mismatch was found, within the context of the second input range

Below, we show an example using these iterators:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, 2, 3};
7  std::vector B{1, 3, 4};
8
9  auto [in1, in2]{std::ranges::mismatch(A, B)};
10
11  // Dangerous - see notes below
12  std::cout << "First mismatch - A: " << *in1;
13  std::cout << "\nFirst mismatch - B: " << *in2;
14}

1First mismatch - A: 2
2First mismatch - B: 3

One (or both) of these iterators may point beyond the end of the input ranges. For example, consider the following collections:

1std::vector A{1, 2, 3};
2std::vector B{1, 2, 3, 4};

Comparing these, the mismatch() would return a past-the-end iterator for A (equivalent to A.end()) and an iterator pointing to the 4 within B

If a scenario like this is possible for our inputs, we should test for it before dereferencing the iterators:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, 2, 3};
7  std::vector B{1, 2, 3, 4};
8
9  auto [in1, in2]{std::ranges::mismatch(A, B)};
10
11  if (in1 == A.end()) {
12    std::cout << "Reached the end of A";
13  }
14
15  if (in2 != B.end()) {
16    std::cout << "\nMismatch in B: " << *in2;
17  }
18}

1Reached the end of A
2Mismatch in B: 4

If no mismatch is found - ie the ranges are equal - both iterators returned by mismatch() will be past-the-end iterators for their respective inputs.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, 2, 3};
7  std::vector B{1, 2, 3};
8
9  auto [in1, in2]{std::ranges::mismatch(A, B)};
10
11  if (in1 == A.end() && in2 == B.end()) {
12    std::cout << "Ranges are Equal";
13  }
14}

1Ranges are Equal

This allows the mismatch() algorithm to be used to determine equality similar to the equal() algorithm.

The advantage of mismatch() in this scenario is that, if the ranges are not equal and our program needs to understand why, the richer return type of mismatch() can help us.

std::lexicographical_compare()

The lexicographical_compare() algorithm returns true if the first collection is "less than" the second collection.

Specifically, that means:

• The algorithm compares objects from each collection until it finds the first mismatch
• It then compares those mismatches using the < operator (customizable, by providing an additional argument as described earlier)
• If the object in the first collection is < the object in the second collection, the first collection is considered < the second collection, so the algorithm returns true

lexicographical_compare() is not yet available as a range-based algorithm. As such, there are no overloads that allow us to specify projection functions, and we need to provide our input collections using iterator pairs:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, 2, 3};
7  std::vector B{1, 2, 4};
8
9  if (std::lexicographical_compare(
10    A.begin(), A.end(), B.begin(), B.end())) {
11    std::cout << "A is less than B";
12  }
13}

1A is less than B

Additionally:

• If no mismatch is found (ie, the two collections are equal), lexicographical_compare() returns false
• If we reach the end of the first collection without finding a mismatch, but there are still objects in the second, the algorithm returns true. For example, the collection {1, 2, 3} is considered "less than" the collection {1, 2, 3, 4}

The main use case for this is determining the alphabetical ordering of strings. We can conceptualize strings simply as collections (or ranges) of characters.

For example, a std::string is a range of characters, so is compatible with range-based algorithms. It also has methods that return iterators, so we can use it with iterator-based algorithms like any other collection:

1#include <algorithm>
2#include <iostream>
3
4int main(){
5  std::string A{"Apple"};
6  std::string B{"Banana"};
7
8  if (std::lexicographical_compare(
9    A.begin(), A.end(), B.begin(), B.end())) {
10    std::cout << "Apple is before Banana";
11  }
12}

1Apple is before Banana

Many string types offer simplified ways to get this behavior, which makes the general algorithm unnecessary in those scenarios.

For example, if we’re using std::string, that class has overloaded the comparison operators, letting us write this code in a much simpler way:

1#include <iostream>
2
3int main(){
4  std::string A{"Apple"};
5  std::string B{"Banana"};
6
7  if (A < B) {
8    std::cout << "Apple is before Banana";
9  }
10}

1Apple is before Banana

Three-Way Lexicographical Comparison

The lexicographical_compare_three_way() algorithm is similar to lexicographical_compare(), but it doesn’t just check if a collection is "less than" another. Rather, it returns an object that lets us determine whether a collection is less than, equal to, or greater than another.

Similar to lexicographical_compare(), this algorithm is not yet available in a range-based form. Therefore, it doesn’t support projection functions, and we provide each input using an iterator pair:

1#include <algorithm>
2#include <iostream>
3
4int main(){
5  std::string A{"Apple"};
6  std::string B{"Banana"};
7
8  auto Result{
9    std::lexicographical_compare_three_way(
10      A.begin(), A.end(),
11      B.begin(), B.end())};
12}

This returns an object representing how our two ranges are ordered. We can pass this return value into one of several helper functions that return simple booleans.

For example, if we wanted to determine if A was "less than" B, we could pass what was returned from lexicographical_compare_three_way() into the std::is_lt() function:

1std::is_lt(Result)

The full suite of options are:

• std::is_lt(): Returns true if A was less than B
• std::is_lteq(): Returns true if A was less than or equal to B
• std::is_eq(): Returns true if A was equal to B
• std::is_neq(): Returns true if A was not equal to B
• std::is_gt(): Returns true if A was greater than B
• std::is_gteq(): Returns true if A was greater than or equal to B

Here are some examples:

1#include <algorithm>
2#include <iostream>
3
4int main(){
5  std::string A{"Apple"};
6  std::string B{"Banana"};
7
8  auto Result{
9    std::lexicographical_compare_three_way(
10      A.begin(), A.end(),
11      B.begin(), B.end())};
12
13  if (std::is_neq(Result)) {
14    std::cout << "Apple is not equal to Banana";
15  }
16  if (std::is_lt(Result)) {
17    std::cout << "\nApple is less than Banana";
18  }
19  if (std::is_lteq(Result)) {
20    std::cout <<
21      "\nApple is less than or equal to Banana";
22  }
23}

1Apple is not equal to Banana
2Apple is less than Banana
3Apple is less than or equal to Banana

lexicographical_compare_three_way() is a generic algorithm that works on all containers that implement iterators. Some container classes implement this functionality natively, usually by overloading the regular comparison operators like == and <=.

Where that is available, as it is with std::string, we should generally use that approach instead:

1#include <iostream>
2
3int main(){
4  std::string A{"Apple"};
5  std::string B{"Banana"};
6
7  if (A <= B) {
8    std::cout <<
9      "Apple is less than or equal to Banana";
10  }
11}

1Apple is less than or equal to Banana

We cover ordering in more detail later in the course when we introduce three-way comparisons.

The Spaceship Operator and Expression Rewriting

A guide to simplifying our comparison operators using C++20 features

std::ranges::starts_with()

The starts_with() algorithm accepts two collections, and will return true if the initial objects in the first argument pass an equality check with the objects in the second argument.

Below, we are asking if the range 1, 2, 3, 4, 5 starts with the range 1, 2, 3:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, 2, 3, 4, 5};
7  std::vector B{1, 2, 3};
8
9  if (std::ranges::starts_with(A, B)) {
10    std::cout << "A starts with B";
11  }
12}

1A starts with B

This algorithm is most often used when analyzing strings:

1#include <algorithm>
2#include <iostream>
3
4int main(){
5  std::string Name{"James Bond"};
6  std::string Target{"James"};
7
8  if (std::ranges::starts_with(Name, Target)) {
9    std::cout << "Hello James";
10  }
11}

1Hello James

Many string types have a dedicated method for this, which makes the general algorithm unnecessary for those use cases.

As of C++20, std::string has this functionality in the form of the starts_with() method. As such, we don’t need the generic range-based algorithm when our container is a standard library string:

1#include <iostream>
2
3int main(){
4  std::string Name{"James Bond"};
5  std::string Target{"James"};
6
7  if (Name.starts_with(Target)) {
8    std::cout << "Hello James";
9  }
10}

1Hello James

std::ranges::ends_with()

Predictably, the ends_with() algorithm returns true if our first collection ends with the elements in our second collection:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector A{1, 2, 3, 4, 5};
7  std::vector B      {3, 4, 5};
8
9  if (std::ranges::ends_with(A, B)) {
10    std::cout << "A ends with B";
11  }
12}

1A ends with B

Again, this is typically used when analyzing strings:

1#include <algorithm>
2#include <iostream>
3
4int main(){
5  std::string Name{"James Bond"};
6  std::string Target{"Bond"};
7
8  if (std::ranges::ends_with(Name, Target)) {
9    std::cout << "Hello Mr Bond";
10  }
11}

1Hello Mr Bond

As of C++20, std::string has this functionality in the form of the ends_with() method:

1#include <iostream>
2
3int main(){
4  std::string Name{"James Bond"};
5  std::string Target{"Bond"};
6
7  if (Name.ends_with(Target)) {
8    std::cout << "Hello Mr Bond";
9  }
10}

1Hello Mr Bond

std::ranges::includes()

The standard library includes an algorithm that lets us check if a collection contains another collection, in any position. This scenario is generally referred to as a collection being a subset or superset.

We covered this algorithm, and set-based algorithms in general, in an earlier lesson:

Set Algorithms

An introduction to set algorithms, and how to implement them using the C++ standard library

Summary

In this lesson, we explored the comparison algorithms provided by the standard library,

Main Points Learned

• Using std::ranges::equal() to check for equality between two ranges.
• Using std::ranges::is_permutation() to determine if one range is a permutation of another.
• Using std::ranges::mismatch() to find the first point of divergence between two ranges.
• Using std::lexicographical_compare() for comparing the lexicographical order of two ranges.
• Using std::lexicographical_compare_three_way() for detailed three-way comparison results.
• Using std::ranges::starts_with() and std::ranges::ends_with() to check if one range starts or ends with another.
• Using range based techniques, such as sentinels and views, to customise the algorithms’ input.
• Using custom comparers and projection functions to customise the algorithms’ behaviour.

Next Lesson

The Reduce and Accumulate Algorithms

A detailed guide to generating a single object from collections using the std::reduce() and std::accumulate() algorithms

ContinueView Course