# Comparison Algorithms

An introduction to the 8 main comparison algorithms in the C++ 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
Edited

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:

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

int main(){
std::vector A{1, 2, 3};
std::vector B{1, 2, 3};

if (std::ranges::equal(A, B)) {
std::cout << "Ranges are equal";
}
}
Ranges 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:

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

int main(){
std::vector A{1, -2, 3};
std::vector B{-1, 2, -3};

auto absEqual{
[](int x, int y){
return std::abs(x) == std::abs(y);
}};

if (std::ranges::equal(A, B, absEqual)) {
std::cout << "Ranges are equal";
}
}
Ranges 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.

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

int main(){
std::vector A{1, -2, 3};
std::vector B{-1, 2, -3};

auto P{[](int x){ return std::abs(x); }};

if (std::ranges::equal(A, B, {}, P, P)) {
std::cout << "Ranges are equal";
}
}
Ranges 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:

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

class Character {
public:
Character(std::string Name) : Name{Name}{}
std::string GetName() const{ return Name; }

private:
std::string Name;
};

int main(){
using namespace std::string_literals;
std::vector<Character> A{
"Anna"s, "Roderick"s};
std::vector<Character> B{
"Anna"s, "Roderick"s};

if (std::ranges::equal(A, B, {},
&Character::GetName,
&Character::GetName)) {
std::cout << "Ranges are equal";
}
}
Ranges 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:

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

int main(){
std::vector A{1, 2, 3};
std::vector B{0, 1, 2, 3, 4};

if (std::ranges::equal(A.begin(), A.end(),
B.begin() + 1,
B.end() - 1)) {
std::cout << "A is in the middle of B";
}
}
A 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:

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

int main(){
std::vector A{1, 2, 3};
std::vector B{3, 2, 1};

if (std::ranges::equal(
A, std::views::reverse(B))) {
std::cout << "Ranges are reversed";
}
}
Ranges 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:

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

int main(){
std::vector A{1, 2, 3};
std::vector B{2, 1, 3};

if (!std::ranges::equal(A, B)) {
std::cout << "Ranges are NOT equal";
}

if (std::ranges::is_permutation(A, B)) {
std::cout << "\nBut they ARE a permutation";
}
}
Ranges are NOT equal
But they ARE a permutation

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

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

int main(){
std::vector A{1, 2, 3};
std::vector B{1, 2, 3};

if (std::ranges::equal(A, B)) {
std::cout << "Ranges are equal";
}

if (std::ranges::is_permutation(A, B)) {
std::cout << "\nAnd also a permutation";
}
}
Ranges are equal
And also a permutation

### Identity Permutations

An unchanged collection being considered a permutation may be confusing. This behavior is based on nuance in how permutations are definedÂ mathematically.

A permutation that maintains the order of the objects in the collection is sometimes referred to as an identity 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:

#include <algorithm>
#include <vector>

int main() {
std::vector A{1, 2, 3};
std::vector B{1, 3, 4};

auto Result { std::ranges::mismatch(A, B) };
}

The mismatch() algorithm returns a std::ranges::mismatch_result. This is an alias for std::ranges::in_in_result - a simple struct that returns 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:

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

int main(){
std::vector A{1, 2, 3};
std::vector B{1, 3, 4};

auto [in1, in2]{std::ranges::mismatch(A, B)};

// Dangerous - see notes below
std::cout << "First mismatch - A: " << *in1;
std::cout << "\nFirst mismatch - B: " << *in2;
}
First mismatch - A: 2
First mismatch - B: 3

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

std::vector A{1, 2, 3};
std::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:

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

int main(){
std::vector A{1, 2, 3};
std::vector B{1, 2, 3, 4};

auto [in1, in2]{std::ranges::mismatch(A, B)};

if (in1 == A.end()) {
std::cout << "Reached the end of A";
}

if (in2 != B.end()) {
std::cout << "\nMismatch in B: " << *in2;
}
}
Reached the end of A
Mismatch 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.

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

int main(){
std::vector A{1, 2, 3};
std::vector B{1, 2, 3};

auto [in1, in2]{std::ranges::mismatch(A, B)};

if (in1 == A.end() && in2 == B.end()) {
std::cout << "Ranges are Equal";
}
}
Ranges 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:

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

int main(){
std::vector A{1, 2, 3};
std::vector B{1, 2, 4};

if (std::lexicographical_compare(
A.begin(), A.end(), B.begin(), B.end())) {
std::cout << "A is less than B";
}
}
A is less than B

• 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:

#include <algorithm>
#include <iostream>

int main(){
std::string A{"Apple"};
std::string B{"Banana"};

if (std::lexicographical_compare(
A.begin(), A.end(), B.begin(), B.end())) {
std::cout << "Apple is before Banana";
}
}
Apple 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:

#include <iostream>

int main(){
std::string A{"Apple"};
std::string B{"Banana"};

if (A < B) {
std::cout << "Apple is before Banana";
}
}
Apple 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:

#include <algorithm>
#include <iostream>

int main(){
std::string A{"Apple"};
std::string B{"Banana"};

auto Result{
std::lexicographical_compare_three_way(
A.begin(), A.end(),
B.begin(), B.end())};
}

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:

std::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:

#include <algorithm>
#include <iostream>

int main(){
std::string A{"Apple"};
std::string B{"Banana"};

auto Result{
std::lexicographical_compare_three_way(
A.begin(), A.end(),
B.begin(), B.end())};

if (std::is_neq(Result)) {
std::cout << "Apple is not equal to Banana";
}
if (std::is_lt(Result)) {
std::cout << "\nApple is less than Banana";
}
if (std::is_lteq(Result)) {
std::cout <<
"\nApple is less than or equal to Banana";
}
}
Apple is not equal to Banana
Apple is less than Banana
Apple 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:

#include <iostream>

int main(){
std::string A{"Apple"};
std::string B{"Banana"};

if (A <= B) {
std::cout <<
"Apple is less than or equal to Banana";
}
}
Apple is less than or equal to Banana

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

## 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:

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

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

if (std::ranges::starts_with(A, B)) {
std::cout << "A starts with B";
}
}
A starts with B

This algorithm is most often used when analyzingÂ strings:

#include <algorithm>
#include <iostream>

int main(){
std::string Name{"James Bond"};
std::string Target{"James"};

if (std::ranges::starts_with(Name, Target)) {
std::cout << "Hello James";
}
}
Hello 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:

#include <iostream>

int main(){
std::string Name{"James Bond"};
std::string Target{"James"};

if (Name.starts_with(Target)) {
std::cout << "Hello James";
}
}
Hello James

## std::ranges::ends_with()

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

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

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

if (std::ranges::ends_with(A, B)) {
std::cout << "A ends with B";
}
}
A ends with B

Again, this is typically used when analyzingÂ strings:

#include <algorithm>
#include <iostream>

int main(){
std::string Name{"James Bond"};
std::string Target{"Bond"};

if (std::ranges::ends_with(Name, Target)) {
std::cout << "Hello Mr Bond";
}
}
Hello Mr Bond

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

#include <iostream>

int main(){
std::string Name{"James Bond"};
std::string Target{"Bond"};

if (Name.ends_with(Target)) {
std::cout << "Hello Mr Bond";
}
}
Hello 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:

## 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.
• UJsing 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.

### Edit History

• â€” Refreshed Content

• â€” First Published

Edited
Lesson Contents

### Comparison Algorithms

An introduction to the 8 main comparison algorithms in the C++ 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

###### Comparison Algorithms

An introduction to the 8 main comparison algorithms in the C++ 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:

• 114 Lessons
• 550+ Code Samples
• 96% Positive Reviews
• Regularly Updated
• Help and FAQ
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