How can I find the index of the highest value in a vector, defaulting to the greater index if there are two "greatest" indices?

Question

I have been using std::max_element(vec), but from what I can tell, it returns the smallest index if two "greatest" indices are equal.

Example:

vector<int> v = {1, 2, 3, 4, 5, 3, 3, 2, 5};

std::max_element(v) would reference v[4], but for the purposes of my project I need it to reference v[8] instead. What would be the best way to do this?

Solution 1

You can use this

max_element(v.rbegin(), v.rend());

to refer to the greatest index of the greatest value.

For example,

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

int main()
{
    vector<int> v = {1, 2, 3, 4, 5, 3, 3, 2, 5};
    *max_element(v.rbegin(), v.rend())=-1;
    for (auto i: v) cout << i << ' ';
}

produces output

1 2 3 4 5 3 3 2 -1 

The method mentioned above returns a reverse iterator, as pointed out by @BoBTFish. To get a forward iterator, you could do this:

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

int main()
{
    vector <int> v = {1, 2, 3, 4, 5, 3, 3, 2, 5};
    reverse_iterator < vector <int> :: iterator > x (max_element(v.rbegin(), v.rend()));
    vector <int> :: iterator it=--x.base(); // x.base() points to the element next to that pointed by x. 
    *it=-1; 
    *--it=0; // marked to verify 
    for (auto i: v) cout << i << ' ';
}

produces output

1 2 3 4 5 3 3 0 -1 
              ^

It can be seen that the iterator it is a forward iterator.

Solution 2

It's very easy to make your own function:

/* Finds the greatest element in the range [first, last). Uses `<=` for comparison.
*
* Returns iterator to the greatest element in the range [first, last).
* If several elements in the range are equivalent to the greatest element,
* returns the iterator to the last such element. Returns last if the range is empty.
*/

template <class It>
auto max_last(It first, It last) -> It
{
    auto max = first;
    for(; first != last; ++first) {
        if (*max <= *first) {
            max = first;
        }
    }
    return max;
}

Comments

[BoBTFish]

Bear in mind this gives you a reverse_iterator to the element, which you may want to convert back to the "proper" iterator type (std::vector::iterator). I think it would improve your answer if you show how to do this.

[BoBTFish]

You could make this follow the style of the standard algorithms by taking a Comparator that follows a strict weak ordering, then using if(!cmp(*first, *max)) { max = first; }. Although the standard algorithms typically have a version not taking a comparator, and defaulting to < (which is not quite the same as defaulting to std::less<T>, which may be specialised).

[Christian Hackl]

A type is more likely to support < than <=. And <= can be implemented in terms of <: a <= b is equal to (a < b) || (!(a < b) && !(b < a)). So you don't necessarily need to require <=.