In recent days, there’s been a question coming up on twitter: how do you find the second largest element in an array (container)? People are providing different answers. As usual, there are multiple solutions to this problem and they depend on the actual requirements: could this operation have side effect (change the original range) or should it be left untouched? In this post, I will discuss several solutions in C++ to this problem.
Before going forward, I want to add some more requirements:
- if the range is empty, the function must not return any value
- if the range has only one element, the function must return this element
- if all the range elements have the same value, the function must return this value
You could argue whether these make sense or not but I will start with these premises.
Scenario 1: the range must not be modified
Let’s first assume that the range must not be modified by this operation. I would guess that this should be the requirement in most cases when you need to find the second largest element. As someone put it on Twitter:
There are two possible solutions for this: a user-defined search and using std::max_element. Let’s see them both.
User-defined search function
We can write and explicit iteration of the range and compare elements to find the 2nd largest. The algorithm is as follows:
- define two variables to store the 1st and 2nd largest values and initialize them with the first two elements of the range
- iterate the range until the end doing the following:
- if the current element is greater than the largest, then assign 2nd largest to the value of 1st largest, and the 1st largest to the current element
- otherwise, if the current element is greater than the 2nd largest then assign its value to the 2nd largest
This can be implemented as follows using a function template that takes iterators to the first and last elements of a range:
template <typename Iter>
Iter find_2nd_largest_1(Iter begin, Iter end)
{
if (begin == end) return end;
if (std::distance(begin, end) == 1) return begin;
auto max1 = begin++;
auto max2 = begin++;
if (*max1 < *max2) std::swap(max1, max2);
for (auto it = begin; it != end; ++it)
{
if (*it > *max1)
{
max2 = max1;
max1 = it;
}
else if (*it > *max2 && *it < *max1)
{
max2 = it;
}
}
return max2;
}
Notice that the first two checks are meant to ensure the first two requirements defined in the beginning are properly handled.
Using std::max_element
A second alternative is to use the std::max_element general purpose algorithm. However, we need to use this twice:
- the first call would find the largest element in the range
- the second call would require a comparer to help find the largest element that is smaller than the element found with the first call
Of course, this means there are two passes through the range and this implies a degraded performance as the number of elements increases. But will see about this later. The following is a possible implementation:
template <typename Iter>
Iter find_2nd_largest_2(Iter begin, Iter end)
{
if (begin == end) return end;
if (std::distance(begin, end) == 1) return begin;
auto m = std::max_element(begin, end);
auto m2 = std::max_element(
begin, end, [m](auto const& e1, auto const& e2) { return e2 < *m && e1 < e2; });
return m2;
}
Scenario 2: the range can be modified
Assuming you can modify the original range there are additional solutions to the problem using partial sorting algorithms from the standard library.
(As a side note, I’d like to hear some use cases where modifying the range is OK, but that’s a side issue for now.)
Using std::nth_element
The std::nth_element function is a partial sorting algorithm that rearranges elements in a range. It takes two iterators that define the range (begin and last) and a pivot (the nth element) and sorts the range such that:
- the element pointed by the pivot is changed with the element that would occur in that position if the range was sorted
- all the elements before the pivot are changed so they are less or equal to the elements after the new pivot (nth element)
We can partially sort the range using the 2nd element as the pivot, and using operator > instead of the default operator < for comparison (in other words we would sort descending, not ascending).
Here is the implementation:
template <typename Iter>
Iter find_2nd_largest_3(Iter begin, Iter end)
{
if (begin == end) return end;
if (std::distance(begin, end) == 1) return begin;
std::nth_element(begin, begin + 1, end, std::greater<>());
return begin + 1;
}
This is even less code than with std::max_element although remember, the range is modified.
Using std::partial_sort
The std::partial_sort function is a general purpose algorithm that rearranges elements in a range based on a pivot so that the pivot - first smallest elements come first followed by the other elements in an specified order.
Again, the default behavior is to sort using operator < so we need to change this and sort using operator >. We only need to sort the largest two elements of the range, so the pivot would be begin + 2. Here is how the implementation would look:
template <typename Iter>
Iter find_2nd_largest_4(Iter begin, Iter end)
{
if (begin == end) return end;
if (std::distance(begin, end) == 1) return begin;
std::partial_sort(begin, begin + 2, end, std::greater<>());
return begin + 1;
}
This is very similar to the previous implementation. The question is, which is faster? But before answering that, let’s see if they actually do the right thing.
Testing the implementations
To put these implementations to test, we can write the following simple tests to ensure they always return the expected value:
void basic_tests()
{
std::vector<std::pair<std::optional<int>, std::vector<int>>> data = {
{{}, { }},
{1, { 1}},
{1, { 1, 2}},
{1, { 2, 1}},
{2, { 2, 3, 1}},
{2, { 3, 2, 1}},
{1, { 1, 1, 1 }},
{1, { 1, 2, 1 }},
{1, { 1, 2, 2 }},
{4, { 1, 2, 3, 4, 5 }},
{5, { 1, 2, 3, 4, 5, 6 }},
{4, { 5, 4, 3, 2, 1 }},
{5, { 6, 5, 4, 3, 2, 1 }},
{8, { 4, 2, 1, 5, 8, 6, 9, 3, 7 }},
};
std::cout << std::format("{:<10} {:<10} {:<10} {:<10} {:<10}\n",
"expected", "manual", "max", "nthelem", "partsort");
for (auto const & [e, v] : data)
{
auto m1 = find_2nd_largest_1(v.begin(), v.end());
auto m2 = find_2nd_largest_2(v.begin(), v.end());
auto v3 = v;
auto m3 = find_2nd_largest_3(v3.begin(), v3.end());
auto v4 = v;
auto m4 = find_2nd_largest_4(v4.begin(), v4.end());
std::cout << std::format("{:<10} {:<10} {:<10} {:<10} {:<10}\n",
(bool)e ? std::to_string(e.value()) : "N/A",
m1 != v.end() ? std::to_string(*m1) : "N/A",
m2 != v.end() ? std::to_string(*m2) : "N/A",
m3 != v3.end() ? std::to_string(*m3) : "N/A",
m4 != v4.end() ? std::to_string(*m4) : "N/A");
}
}
If we run this, we get the following output:
expected manual max nthelem partsort N/A N/A N/A N/A N/A 1 1 1 1 1 1 1 1 1 1 1 1 2 [!] 1 1 2 2 2 2 2 2 2 3 [!] 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 [!] 2 [!] 4 4 4 4 4 5 5 5 5 5 4 4 5 4 4 5 5 6 [!] 5 5 8 8 8 8 8
An exclamation mark here indicates the result is not what was expected.
Let’s first look at std::max_element. It got the wrong results for the following test cases:
{ 2, 1}
{ 3, 2, 1}
{ 6, 5, 4, 3, 2, 1 }
We can notice here that the maximum element is always the first. There is a bug on this line:
auto m2 = std::max_element(begin, end, [m](auto const& e1, auto const& e2) { return e2 < *m&& e1 < e2; });
It starts with the first element and compares it against each of the rest and the maximum but it will never find something larger. We need to modify this: when the largest is the first, then continue from the second element:
template <typename Iter>
Iter find_2nd_largest_2(Iter begin, Iter end)
{
if (begin == end) return end;
if (std::distance(begin, end) == 1) return begin;
auto m = std::max_element(begin, end);
auto m2 = std::max_element(
m == begin ? begin + 1 : begin, end, [m](auto const& e1, auto const& e2) { return e2 < *m&& e1 < e2; });
return m2;
}
With this change, find_2nd_largest_2 always returns the expected value.
The second problem is related to std::nth_element and std::partial_sort. They both fail for the range { 1, 2, 2 }. We can see here that the maximum element appears multiple times. There was an implicit assumption that this would not appear more than once. If that’s not true, then these two solutions do not work.
Comparing performance
The last but not least thing to check is how do they perform against each other. For this, I have written another simple test.
void benchmark()
{
std::cout << std::format("{:>10} {:>10} {:>10} {:>10} {:>10}\n",
"size", "manual", "max", "nthelem", "partsort");
std::vector<size_t> sizes{ 1000, 10000, 100000, 1000000, 10000000 };
for (auto size : sizes)
{
std::vector<int> data;
generate(data, size);
auto d3 = data;
auto d4 = data;
auto t1 = std::chrono::steady_clock::now();
auto m1 = find_2nd_largest_1(data.begin(), data.end());
auto t2 = std::chrono::steady_clock::now();
auto m2 = find_2nd_largest_2(data.begin(), data.end());
auto t3 = std::chrono::steady_clock::now();
auto m3 = find_2nd_largest_3(d3.begin(), d3.end());
auto t4 = std::chrono::steady_clock::now();
auto m4 = find_2nd_largest_4(d4.begin(), d4.end());
auto t5 = std::chrono::steady_clock::now();
if (*m1 == *m2 || *m1 == *m3 || *m1 == *m4) // this is just to ensure calls are not remove because of optimizations
{
std::cout << std::format(
"{:>10} {:>10} {:>10} {:>10} {:>10}\n",
size,
std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count(),
std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2).count(),
std::chrono::duration_cast<std::chrono::microseconds>(t4 - t3).count(),
std::chrono::duration_cast<std::chrono::microseconds>(t5 - t4).count()
);
}
}
}
Run with optimizations enabled (a release build) I get the following numbers (of course, these vary slightly with each run):
size manual max nthelem partsort
1000 1 3 11 1
10000 11 28 112 6
100000 104 293 1306 107
1000000 4044 8083 10364 4020
10000000 25980 34281 66386 5834
There are several thing to notice here:
- the implementation using two calls to
std::max_elementis always less performant than the manual search (about twice as much time to find the 2nd largest) - the implementation using the
std::nth_elementis the least performant of them all - the implementation using
std::partial_sortis comparable to the manual search and several times faster when there are 10 million elements in the range
The reason std::partial_sort is much faster than std::nth_element is that it does much fewer swaps. This is demonstrated in a cppcon talk by Marshall Clow: Down the Rabbit Hole: An Exploration of Stack Overflow Questions.
Conclusions
Problems usually have multiple solutions and finding the 2nd largest element in a range is no different. In my opinion, modifying the range is rarely an option, so, usually, you’d have to chose between the first two implementations. The manual search is faster but if you only have a small number of elements using std::max_element twice should not represent a performance problem.
You probably should not use std::distance, as this might have O(n) – e.g. for lists. It should be more efficient to check for end being reached after one begin++, which is O(1).