How calculation of std::distance works when multiple values with same value are part of the std::vector

Question

    vector<int> arr;

    max = *max_element(begin(arr), end(arr));
    min = *min_element(begin(arr), end(arr));

    auto it = find(arr.begin(), arr.end(), max);
    auto it2 = find(arr.begin(), arr.end(), min);

    dis1 = distance(arr.begin(), it);
    dis2 = distance(arr.begin(), it2);

I wanted to find the indexes of a max and min values in the vector, so I took iterator and used distance method to compute the value.

This works for some inputs but I came across an Input where there are two min values. Input : 10 10 58 31 63 40 76

So here 10 is minimum value but there are 2 10's but I want the distance calculated from the last occurrence of 10 not the first.

I can do this easily by holding a variable and check min values every iteration in a for a loop.

But, I would like to know if I can manipulate the std:: distance some way that program will take the distance from the last occurrence of 10.

Thanks.

Do you specifically want the 2nd occurrence, or the last occurrence? Also, why not just do `it = max_element`? — cigien, Sep 30 '20 at 12:08
sorry didn't frame correctly, yes I want the last occurrence. — heeat, Sep 30 '20 at 12:10
I framed it as per example but the main idea is I need the program to consider the last occurrences for both max and min values — heeat, Sep 30 '20 at 12:12
If you don't want using reverse iterators you can do: max = *max_element(begin(arr), end(arr), std::less_equal<>()); min = *min_element(begin(arr), end(arr), std::less_equal<>()); — Equod, Sep 30 '20 at 12:18
@Equod I'm happy to reopen the question if it can be solved without reverse iterators, but I don't see how your solution works. — cigien, Sep 30 '20 at 12:26
Simplify lines [3, 4, 6, 7] replacing with "auto it = max_element(begin(arr), end(arr), std::less_equal<>()); auto it2 = min_element(begin(arr), end(arr), std::less_equal<>());" — Equod, Sep 30 '20 at 12:32
@cigien using std::less_equal instead of default std::less allows you to get the last max (or min) occurrence — Equod, Sep 30 '20 at 12:35
@Equod Yes, you're right. I reopened the question, you can post an answer now. — cigien, Sep 30 '20 at 12:42

Equod · Accepted Answer · 2020-09-30T13:29:51.757

2

You can provide a custom compare operator for std::max_element and for std::min_element. Using std::less_equal instead of the default std::less allows you get the last occurrence instead of first:

auto it = max_element(begin(arr), end(arr), std::less_equal<>());
auto it2 = min_element(begin(arr), end(arr), std::less_equal<>());

Example here

edited Sep 30 '20 at 13:29

answered Sep 30 '20 at 12:47

Equod

556
3
13

Thanks, it works. Could you please explain how less_equal works? – heeat Sep 30 '20 at 13:00
2

less_equal is just an operator (like std::less). It returns if item1<=item2 and can be written as "auto less_equal = [](auto&& item1, auto&& item2){return item1<= item2;};". The main work here is done by max_element (and std::min_element). Take a look here: https://godbolt.org/z/5b77r1 – Equod Sep 30 '20 at 13:23

Surt · Answer 2 · 2020-09-30T12:24:12.877

0

Find the last occurrence

auto it = find(arr.rbegin(), arr.rend(), max);
auto it2 = find(arr.rbegin(), arr.rend(), min);

Using the reverse iterators should do what you want, finding the last occurrences.

dis1 = distance(arr.begin(), it.base())-1;
dis2 = distance(arr.begin(), it2.base())-1;

If I remember correctly, else test :)

edited Sep 30 '20 at 12:24

answered Sep 30 '20 at 12:13

Surt

15,501
3
23
39

Your usage of `find` will return a reverse iterator, which then can't be used with the OP's forward iterator usage of `distance` which is the question. – acraig5075 Sep 30 '20 at 12:17
Yes, but the `distance` calculation is non-obvious. You might want to mention that. – cigien Sep 30 '20 at 12:17

How calculation of std::distance works when multiple values with same value are part of the std::vector

2 Answers2