c++ - How do I iterate equal values with the standard library?

Question

Suppose that I have a vector of something:

std::vector<Foo> v;

This vector is sorted, so equal elements are next to each other.

What is the best way to get all iterator pairs representing ranges with equal elements (using the standard library)?

while (v-is-not-processed) {
    iterator b = <begin-of-next-range-of-equal-elements>;
    iterator e = <end-of-next-range-of-equal-elements>;

    for (iterator i=b; i!=e; ++i) {
        // Do something with i
    }
}

I'd like to know how to get values of b and e in the code above.

So, for example, if v contains these numbers:

 index 0 1 2 3 4 5 6 7 8 9
 value 2 2 2 4 6 6 7 7 7 8

Then I'd like to have b and e point to elements in the loop:

 iteration  b  e
 1st        0  3
 2nd        3  4
 3rd        4  6
 4th        6  9
 5th        9 10

Is there an elegant way to solve this with the standard library?

question from:https://stackoverflow.com/questions/56859749/how-do-i-iterate-equal-values-with-the-standard-library

Answer 1

This is basically Range v3's group_by: group_by(v, std::equal_to{}). It doesn't exist in the C++17 standard library, but we can write our own rough equivalent:

template <typename FwdIter, typename BinaryPred, typename ForEach>
void for_each_equal_range(FwdIter first, FwdIter last, BinaryPred is_equal, ForEach f) {
    while (first != last) {
        auto next_unequal = std::find_if_not(std::next(first), last,
            [&] (auto const& element) { return is_equal(*first, element); });

        f(first, next_unequal);
        first = next_unequal;
    }
}

Usage:

for_each_equal_range(v.begin(), v.end(), std::equal_to{}, [&] (auto first, auto last) {
    for (; first != last; ++first) {
        // Do something with each element.
    }
});