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.<\/p>\n\n\n\n\n\n\n\n
Before going forward, I want to add some more requirements:<\/p>\n\n\n\n
You could argue whether these make sense or not but I will start with these premises.<\/p>\n\n\n\n
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:<\/p>\n\n\n\n There are two possible solutions for this: a user-defined search and using We can write and explicit iteration of the range and compare elements to find the 2nd largest. The algorithm is as follows:<\/p>\n\n\n\n This can be implemented as follows using a function template that takes iterators to the first and last elements of a range:<\/p>\n\n\n\n Notice that the first two checks are meant to ensure the first two requirements defined in the beginning are properly handled.<\/p>\n\n\n\n A second alternative is to use the 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:<\/p>\n\n\n\n Assuming you can modify the original range there are additional solutions to the problem using partial sorting algorithms from the standard library. <\/p>\n\n\n\n (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.)<\/p>\n\n\n\n The std::nth_element<\/a> 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:<\/p>\n\n\n\n We can partially sort the range using the 2nd element as the pivot, and using operator Here is the implementation:<\/p>\n\n\n\n This is even less code than with The std::partial_sort<\/a> function is a general purpose algorithm that rearranges elements in a range based on a pivot so that the Again, the default behavior is to sort using operator 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.<\/p>\n\n\n\n To put these implementations to test, we can write the following simple tests to ensure they always return the expected value:<\/p>\n\n\n\n If we run this, we get the following output:<\/p>\n\n\n\n An exclamation mark here indicates the result is not what was expected. <\/p>\n\n\n\n Let’s first look at We can notice here that the maximum element is always the first. There is a bug on this line:<\/p>\n\n\n\n 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:<\/p>\n\n\n\n With this change, The second problem is related to The last but not least thing to check is how do they perform against each other. For this, I have written another simple test. <\/p>\n\n\n\n Run with optimizations enabled (a release build) I get the following numbers (of course, these vary slightly with each run):<\/p>\n\n\n\n There are several thing to notice here:<\/p>\n\n\n\n The reason std::max_element<\/code>. Let’s see them both.<\/p>\n\n\n\nUser-defined search function<\/h3>\n\n\n\n
template <typename Iter>\nIter find_2nd_largest_1(Iter begin, Iter end)\n{\n if (begin == end) return end;\n if (std::distance(begin, end) == 1) return begin;\n\n auto max1 = begin++;\n auto max2 = begin++;\n if (*max1 < *max2) std::swap(max1, max2);\n\n for (auto it = begin; it != end; ++it)\n {\n if (*it > *max1)\n {\n max2 = max1;\n max1 = it;\n }\n else if (*it > *max2 && *it < *max1)\n {\n max2 = it;\n }\n }\n\n return max2;\n}<\/pre>\n\n\n\nUsing std::max_element<\/h3>\n\n\n\n
std::max_element<\/code> general purpose algorithm. However, we need to use this twice:<\/p>\n\n\n\ntemplate <typename Iter>\nIter find_2nd_largest_2(Iter begin, Iter end)\n{\n if (begin == end) return end;\n if (std::distance(begin, end) == 1) return begin;\n\n auto m = std::max_element(begin, end);\n\n auto m2 = std::max_element(\n begin, end, [m](auto const& e1, auto const& e2) { return e2 < *m && e1 < e2; });\n\n return m2;\n}<\/pre>\n\n\n\nScenario 2: the range can be modified<\/h2>\n\n\n\n
Using std::nth_element<\/h3>\n\n\n\n
><\/code> instead of the default operator <<\/code> for comparison (in other words we would sort descending, not ascending).<\/p>\n\n\n\ntemplate <typename Iter>\nIter find_2nd_largest_3(Iter begin, Iter end)\n{\n if (begin == end) return end;\n if (std::distance(begin, end) == 1) return begin;\n\n std::nth_element(begin, begin + 1, end, std::greater<>());\n\n return begin + 1;\n}<\/pre>\n\n\n\nstd::max_element<\/code> although remember, the range is modified.<\/p>\n\n\n\nUsing std::partial_sort<\/h3>\n\n\n\n
pivot - first<\/code> smallest elements come first followed by the other elements in an specified order.<\/p>\n\n\n\n<<\/code> so we need to change this and sort using operator ><\/code>. We only need to sort the largest two elements of the range, so the pivot would be begin + 2<\/code>. Here is how the implementation would look:<\/p>\n\n\n\ntemplate <typename Iter>\nIter find_2nd_largest_4(Iter begin, Iter end)\n{\n if (begin == end) return end;\n if (std::distance(begin, end) == 1) return begin;\n\n std::partial_sort(begin, begin + 2, end, std::greater<>());\n\n return begin + 1;\n}<\/pre>\n\n\n\nTesting the implementations<\/h2>\n\n\n\n
void basic_tests()\n{\n std::vector<std::pair<std::optional<int>, std::vector<int>>> data = {\n {{}, { }},\n {1, { 1}},\n {1, { 1, 2}},\n {1, { 2, 1}},\n {2, { 2, 3, 1}},\n {2, { 3, 2, 1}},\n {1, { 1, 1, 1 }},\n {1, { 1, 2, 1 }},\n {1, { 1, 2, 2 }},\n {4, { 1, 2, 3, 4, 5 }},\n {5, { 1, 2, 3, 4, 5, 6 }},\n {4, { 5, 4, 3, 2, 1 }},\n {5, { 6, 5, 4, 3, 2, 1 }},\n {8, { 4, 2, 1, 5, 8, 6, 9, 3, 7 }},\n };\n\n std::cout << std::format(\"{:<10} {:<10} {:<10} {:<10} {:<10}\\n\", \n \"expected\", \"manual\", \"max\", \"nthelem\", \"partsort\");\n\n for (auto const & [e, v] : data)\n {\n auto m1 = find_2nd_largest_1(v.begin(), v.end());\n auto m2 = find_2nd_largest_2(v.begin(), v.end());\n auto v3 = v;\n auto m3 = find_2nd_largest_3(v3.begin(), v3.end());\n auto v4 = v;\n auto m4 = find_2nd_largest_4(v4.begin(), v4.end());\n\n std::cout << std::format(\"{:<10} {:<10} {:<10} {:<10} {:<10}\\n\",\n (bool)e ? std::to_string(e.value()) : \"N\/A\",\n m1 != v.end() ? std::to_string(*m1) : \"N\/A\",\n m2 != v.end() ? std::to_string(*m2) : \"N\/A\",\n m3 != v3.end() ? std::to_string(*m3) : \"N\/A\",\n m4 != v4.end() ? std::to_string(*m4) : \"N\/A\");\n }\n}<\/pre>\n\n\n\nexpected manual max nthelem partsort\nN\/A N\/A N\/A N\/A N\/A\n1 1 1 1 1\n1 1 1 1 1\n1 1 2 [!] 1 1\n2 2 2 2 2\n2 2 3 [!] 2 2\n1 1 1 1 1\n1 1 1 1 1\n1 1 1 2 [!] 2 [!]\n4 4 4 4 4\n5 5 5 5 5\n4 4 5 4 4\n5 5 6 [!] 5 5\n8 8 8 8 8<\/pre>\n\n\n\n
std::max_element<\/code>. It got the wrong results for the following test cases:<\/p>\n\n\n\n{ 2, 1}\n{ 3, 2, 1}\n{ 6, 5, 4, 3, 2, 1 }<\/pre>\n\n\n\nauto m2 = std::max_element(begin, end, [m](auto const& e1, auto const& e2) { return e2 < *m&& e1 < e2; });<\/pre>\n\n\n\ntemplate <typename Iter>\nIter find_2nd_largest_2(Iter begin, Iter end)\n{\n if (begin == end) return end;\n if (std::distance(begin, end) == 1) return begin;\n\n auto m = std::max_element(begin, end);\n\n auto m2 = std::max_element(\n m == begin ? begin + 1 : begin, end, [m](auto const& e1, auto const& e2) { return e2 < *m&& e1 < e2; });\n\n return m2;\n}<\/pre>\n\n\n\nfind_2nd_largest_2<\/code> always returns the expected value.<\/p>\n\n\n\nstd::nth_element<\/code> and std::partial_sort<\/code>. They both fail for the range { 1, 2, 2 }<\/code>. 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.<\/p>\n\n\n\nComparing performance<\/h2>\n\n\n\n
void benchmark()\n{\n std::cout << std::format(\"{:>10} {:>10} {:>10} {:>10} {:>10}\\n\",\n \"size\", \"manual\", \"max\", \"nthelem\", \"partsort\");\n\n std::vector<size_t> sizes{ 1000, 10000, 100000, 1000000, 10000000 };\n for (auto size : sizes)\n {\n std::vector<int> data;\n generate(data, size);\n\n auto d3 = data;\n auto d4 = data;\n\n auto t1 = std::chrono::steady_clock::now();\n\n auto m1 = find_2nd_largest_1(data.begin(), data.end());\n\n auto t2 = std::chrono::steady_clock::now();\n\n auto m2 = find_2nd_largest_2(data.begin(), data.end());\n\n auto t3 = std::chrono::steady_clock::now();\n\n auto m3 = find_2nd_largest_3(d3.begin(), d3.end());\n\n auto t4 = std::chrono::steady_clock::now();\n\n auto m4 = find_2nd_largest_4(d4.begin(), d4.end());\n\n auto t5 = std::chrono::steady_clock::now();\n\n if (*m1 == *m2 || *m1 == *m3 || *m1 == *m4) \/\/ this is just to ensure calls are not remove because of optimizations\n {\n std::cout << std::format(\n \"{:>10} {:>10} {:>10} {:>10} {:>10}\\n\",\n size,\n std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count(),\n std::chrono::duration_cast<std::chrono::microseconds>(t3 - t2).count(),\n std::chrono::duration_cast<std::chrono::microseconds>(t4 - t3).count(),\n std::chrono::duration_cast<std::chrono::microseconds>(t5 - t4).count()\n );\n }\n }\n}<\/pre>\n\n\n\n size manual max nthelem partsort\n 1000 1 3 11 1\n 10000 11 28 112 6\n 100000 104 293 1306 107\n 1000000 4044 8083 10364 4020\n 10000000 25980 34281 66386 5834<\/pre>\n\n\n\n
std::max_element<\/code> is always less performant than the manual search (about twice as much time to find the 2nd largest)<\/li>std::nth_element<\/code> is the least performant of them all<\/li>std::partial_sort<\/code> is comparable to the manual search and several times faster when there are 10 million elements in the range<\/li><\/ul>\n\n\n\nstd::partial_sort<\/code> is much faster than std::nth_element<\/code> 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<\/a>.<\/p>\n\n\n\n