Heitor's log


std::adjacent_find


C++ standard library is insane. There are more data structures and algorithms and utilities than someone can possible remember. If you need to something, there’s a good chance that someone already made it. And if someone already made it, there’s a good chance someone submitted a proposal to add it to the C++ standard library.

Today I want to talk about std::adjacent_find, from the <algorithm> library. It returns an iterator to the first repeated element. So, if you have a list of numbers {1, 2, 2, 3, 3}, this function would return an iterator to the first 2. Let’s see it in practice:

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


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

	auto it = std::ranges::adjacent_find(numbers);
	std::cout << *it << " " << *(it+1) << std::endl;

	return 0;
}

I’m using ranges in there, so you need a C++20 compatible compiler. To compile it with gcc: g++ -Wall -Wextra -std=c++20 adj.cpp. I tested with g++ 10.2.0 and clang++ 11.0.0, and both have support for it 😎. But if you can’t (or don’t want to) use C++20, change the code to std::adjacent_find(numbers.begin(), numbers.end());

This code finds the repeated elements and return an iterator to the first one. It then prints it and the next:

$ ./a.out
2 2

But we can also hack std::adjacent_find with different predicates, and change how we compare equality between consecutive elements. The <functional> header contains some common arithmetic comparison operators, like equal, not equal, less, less equal, etc. Using the same numbers from before, we can find the first number that is less or equal the next one:

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


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

	auto it = std::ranges::adjacent_find(numbers, std::ranges::less_equal());
	std::cout << *it << " " << *(it+1) << std::endl;

	return 0;
}

This code returns 1 2.

Let’s see some more examples. From now on, I’ll omit the headers for brevity.

You want to find the first number that is greater the next one:

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

	auto it = std::ranges::adjacent_find(numbers, std::ranges::greater());

	if (it != numbers.end())
		std::cout << *it << " " << *(it+1) << std::endl;
	else
		std::cout << "Found nothing" << std::endl;

	return 0;
}

This code returns Found nothing, because no two consecutive numbers in {1, 2, 2, 3, 3, 4, 5} satisfies \( a > b \). When std::adjacent_find does not find anything, it returns an iterator to the end of the range.

Now you want to find the first number that does not follow the pattern \( x_{i+1} = x_i + 1 \):

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

	auto it = std::ranges::adjacent_find(numbers,
	                                     [](int a, int b){
	                                             return a != b - 1 ;
	                                     });

	if (it != numbers.end())
		std::cout << *it << " " << *(it+1) << std::endl;
	else
		std::cout << "Found nothing" << std::endl;

	return 0;
}

This returns, as expected, 2 2. This happens because 2 != 2-1, so the lambda returns true and the function returns the iterator to this number. By this number I mean, std::adjacent_find loops over the objects and compares this object with the next one. If the sequence was {1, 2, 3, 4, 5}, std::adjacent_find would return an iterator to the element after the last one in there, that is, numbers.end()).

Can you find the first pair (a, b) of numbers such that \(0.78 < a/b < 1 \)? Of course you can:

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

	auto it = std::ranges::adjacent_find(numbers,
	                                     [](float a, float b) {
	                                             return (0.78 < a/b) && (a/b < 1);
	                                     });

	if (it != numbers.end())
		std::cout << *it << " " << *(it+1) << std::endl;
	else
		std::cout << "Found nothing" << std::endl;

	return 0;
}

This code returns 4 5, because \(0.78 < 4/5 = 0.8 < 1\).

What I like about this function is that it gives to you an iterator to the first object matching any rule. If have a vector/list/range of objects, and you need to find the first one that has some relation to the next, std::adjacent_find is the way to go.