Find second (or n) highest value of a field in a vector of object c++

Question

In a related question, I asked how to get the value of the max element in a vector of objects in c++ based o some field of said objects. I extended the algorithm to get the index of that max element so I could later just pop it from the vector of object.

Here is the code that I use right now and it works fine:

vector<MyOwnClass> scoretracker // MyOwnClass has a ".score" field

// Some code filling scoretracker

auto max = std::max_element(scoretracker.begin(), scoretracker.end(),
    [] (const MyOwnClass &a, const MyOwnClass &b )
{
    return a.score < b.score; // I am not sure how this line works
});

int index = distance(scoretracker.begin(), max);

So, I tried to modify this to get the second highest (or n-th value) instead of the max but so far my attempts failed.

It makes me realize that I don't really understand why "return a.score < b.score" returns the highest value.

By looking at how max_element works, I am not sure if it could ever be used to find the 2nd largest.

Oh, finally, I would rather not pop_back the highest value from the vector, find the new max (the 2nd highest value in the original vector) and add some logic to restore the original version. Well if I have to, I'll do it but there might be some iterator property or something else I don't know...

Answer 1

If you need the index of only once (and not for all values), you may use:

std::size_t get_index_of_nth_greatest(const std::vector<MyOwnClass>& v, std::size_t k)
{
    std::vector<std::size_t> indexes(v.size());
    std::iota(indexes.begin(), indexes.end(), 0);

    std::nth_element(indexes.begin(), indexes.begin() + k, indexes.end(),
        [&](int lhs, int rhs)
        {
            return v[lhs].score > v[rhs].score;
        }
    );
    return indexes[k];
}

Live example.

Note: As Vlad from Moscow points out, with duplicate inputs, there is no guaranty of the order of the duplicates, and so you may have identical indexes for different k.

Answer 2

try this:

auto max = std::sort(scoretracker.begin(), scoretracker.end(),
    [] (const MyOwnClass &a, const MyOwnClass &b )
{
    return a.score < b.score;
});

then

scoretracker.back().score;

would give you last element

scoretracker.at(position).score;

would return element of the position where position can be any number

Answer 3

If you want a more sophisticated approach you can look at the std::partition function.

std::partition takes a container and divides it into two parts.

std::vector<MyOwnClass> v(100);
// fill vector with stuff. Find n-th element.
auto mid = v[somwhere_in_the_middle];
auto p = std::partition(v.begin(), v.end(), 
                [mid](MyOwnClass v){ return v.score < mid.score; } );

Every element bigger than p is to the right of p. The smaller ones are to the left. If you are looking for the second biggest, you go to the right as long as the distance of v.end() - p is large enough.

This method is called quick-select, based on the ideas of quicksort, and is detailed here How to find the kth largest element in an unsorted array of length n in O(n)?.

And this is of course already implemented as std::nth_element and can be used as

std::nth_element(v.begin(), v.begin()+5, v.end(), std::greater<int>());

To get the 6th largest element at the 6th position.

Answer 4

You can do it by taking the max element you already have and looking for the std::max_element() either side of it and getting the std::max() of those two values:

struct MyOwnClass
{
    int score = 0;
    MyOwnClass(int s): score(s) {}
};

vector<MyOwnClass> scores = {{4}, {2}, {7}, {9}, {3}}; 

int main()
{
    // we need this more than once
    auto compare = [] (const MyOwnClass &a, const MyOwnClass &b)
    {
        return a.score < b.score; // I am not sure how this line works
    };

    auto max = std::max_element(scores.begin(), scores.end(), compare);

    std::cout << "max: " << max->score << '\n';

    // call std::max_element() twice with ranges either side of the max element
    // and get the std::max() of those values
    auto next_max = std::max(std::max_element(scores.begin(), max, compare)->score
        , std::max_element(max + 1, scores.end(), compare)->score);

    std::cout << "next max: " << next_max << '\n';
}

NOTE: If you want to get the third or fourth elements this technique is a technique of diminishing returns, probably better to do a std::sort().