Is there an algorithm like std::max_element for the second largest element?

Question

The standard library provides std::max_element to find the largest element in an iterable, e.g.:

std::vector<float>::const_iterator max = 
  std::max_element(obj.pt()->begin(), obj.pt()->end());
return std::distance(obj.pt()->begin(), max);

Is there also something to get an iterator for the n-th largest element?

(Note that max_element returns an iterator and this is actually important: Rather than for the value itself, I am looking for the position of the n-th largest element within the iterable.)

Answer 1

Mutating

You can use std::rangs::nth_element if you are allowed to modify the original vector:

std::vector<int> v{4, 2, 1, 3};

// C++20
std::ranges::nth_element(v, v.begin() + 1, std::ranges::greater{});
// C++11
std::nth_element(v.begin(), v.begin() + 1, v.end(), std::greater<int>{});

std::cout << "Second greatest: " << v[1];

Non-mutating

If you are not allowed to modify the original, you can create an extra buffer and use std::ranges::partial_sort_copy:

const std::vector<int> v{4, 2, 1, 3};
std::array<int, 2> buffer{};

// C++20
std::ranges::partial_sort_copy(v, buffer, std::ranges::greater{});
// C++11
std::partial_sort_copy(v.begin(), v.end(), buffer.begin(), buffer.end(), std::greater<int>{});

std::cout << "Second greatest: " << buffer[1];

Position within the original

In either case, you don't obtain the position of the element in the original vector. To do that, you would have to create a std::vector<std::size_t> of indices and sort that instead.

const std::vector<int> v{4, 2, 1, 3};
// The following is a C++23 way to do = {0, 1, 2, 3}.
// There are obviously ways to do that prior to C++23 too, e.g. with std::iota.
std::vector<std::size_t> indices(std::from_range, std::views::iota(0, v.size());

// C++20
std::ranges::nth_element(
    indices, indices.begin() + 1,       // input range and nth
    std::ranges::greater{},             // comparison
    [&v](std::size_t i) { return v[i]; } // projection
);
// C++11
std::nth_element(
    indices.begin(), indices.begin() + 1, indices.end(),
    [&v](std::size_t i, std::size_t j) {
        return v[i] > v[j];
    }
);

// Second greatest element is located at index indices[1]
std::cout << "Second greatest: " << v[indices[1]];

Answer 2

As Dyp mentioned in comment, if you are fine to alter the order of elements within your vector you can use std::nth_element as follows. On top if you use find again over vector you will get original position of the nth element from vector. Since nth_element modifies the positions, you have to keep a local copy of it before doing nth_element operation over vector.

2nd largest element:

std::vector<float> vf{1.1f, 2.2f, 3.3f, 4.4f};
std::vector<float> orig_vec = vf;

std::nth_element(vf.begin(), vf.begin()+1, vf.end(), std::greater<float>{});
float second = *(vf.begin()+1);
auto it = std::find(orig_vec.begin(), orig_vec.end(), second);

nth largest element:

std::nth_element(vf.begin(), vf.begin()+n-1, vf.end(), std::greater<float>{});
float nth = *(vf.begin()+n-1);
auto it = std::find(orig_vec.begin(), orig_vec.end(), nth)

Answer 3

max_element() method can be used to get second largest element by passing lambda function which compares the element with the previously found largest element and if it is equal to the largest element then it'll simply skip that element.

    auto largest = max_element(vec.begin(), vec.end());
    auto secondLargest = max_element(vec.begin(), vec.end(),
                                     [&largest](unsigned long &a, unsigned long &b) {
                                         if (a == *largest) return true;
                                         if (b == *largest) return false;                                         
                                         return a < b;
                                     });

Answer 4

It took me a while to find a solution, because I worked with const vector (so I can't use nth_element) and copy would be just wasting (especially, when vector is holding a bigger structures). So I came with this:

// Find 1st max
auto max1 = max_element(vec.begin(), vec.end());
if (max1 != vec.end())
    // Use max1

// Find 2nd max. Split the vector into 2 parts, find max and merge results
auto max2Beg = max_element(vec.begin(), max1);
auto max2End = max_element(max1 + 1, vec.end());
auto max2 = max2Beg == max1 ? max2End :
            max2End == vec.end() ? max2Beg : max(max2Beg, max2End);
if (max2 != max1 && max2 != vec.end())
    // Use max2

Answer 5

If you are specifically interested in the second-largest element, you can do a simple scan of the array in which most elements require a single comparison:

float second_largest_element(std::vector<float> vec) {
  float m2, m1;
  /* Check to make sure that vec has at least 2 elements!! */
  std::tie(m2, m1) = std::minmax(vec[0], vec[1]);
  for (auto it = vec.begin() + 2, limit = vec.end();
       it != limit;
       ++it)
    if (*it > m2) std::tie(m2, m1) = std::minmax(*it, m1);
  return m2;
}

Getting the index of (or an iterator to) the second largest element is very similar, although std::minmax is less useful. Here's a very sloppy example:

template<typename T>
typename T::iterator second_largest(T& container) {
  using iterator = typename T::iterator;
  iterator limit = container.end();
  iterator it = container.begin();
  if (it != limit) {
    iterator first = it++;
    if (it != limit) {
      iterator second = it++;
      if (*first < *second) std::swap(first, second);
      for (; it != limit; ++it) {
        if (*second < *it) {
          if (*first < *it) { second = first; first = it; }
          else              { second = it; }
        }
      }
      return second;
    }
    return first;
  }
  return it;
}

You could also consider using std::accumulate to scan the array, although the explicit for loop is not complicated.

Answer 6

This is a trivial algorithm to implement in linear time. The naive approach would be to compare the first two values, and select them as the max and second largest values. Then you need to iterate over the other elements comparing each new element with both of them and adjusting your current max and second largest values. For most use cases that is probably more than enough. If you really care about performance (as in you care a lot) you will need to think what values you want to compare to minimize the number of comparisons.

Also note that float (floating point in general) have quirks... you might get funny values if your input contains NaN or infinite values.