Mfcttrf

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?

You can use std::upper_bound to get the iterator to the "next" value. Since std::upper_bound returns an iterator to the first element greater than that value provided, if you provide the value of the current element, it will give you an iterator that will be one past the end of the current value. That would give you a loop like

iterator it = v.begin();
while (it != v.end()) 
 iterator b = it;
 iterator e = std::upper_bound(it, v.end(), *it);

 for (iterator i=b; i!=e; ++i) 
 // do something with i
 
 it = e; // need this so the loop starts on the next value

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.
 
);

You are looking for std::equal_range.

Returns a range containing all elements equivalent to value in the
range [first, last).

Something like the following should work. (Untested)

iterator it = v.begin();
while (it != v.end()) 

 auto[b, e] = std::equal_range(it, v.end(), *it);
 // do something with [b, e)
 it = e; // need for the beginning of next std::equal_range

But even if we don't use e for anything, this formulation is convenient, it's harder to make an error. The other way (to check for changing values) is more tedious (as we need to handle the last range specially [...])

Depends on how you interpret 'handling last range specially':

auto begin = v.begin();
// we might need some initialization for whatever on *begin...
for(Iterator i = begin + 1; ; ++i)

No special handling for last range – solely, possibly needing the initialization code twice...

Nested-loop-approach:

auto begin = v.begin();
for(;;)

 // initialize first/next range using *begin
 for(Iterator i = begin + 1; ; ++i)
 

LOOP_EXIT:
// go on
// if nothing left to do in function, we might prefer returning over going to...

More elegant? Admitted, I'm in doubt myself... Both approaches avoid iterating over the same range twice (first for finding the end, then the actual iteration), though. And if we make our own library function from:

template <typename Iterator, typename RangeInitializer, typename ElementHandler>
void iterateOverEqualRanges
(
 Iterator begin, Iterator end,
 RangeInitializer ri, ElementHandler eh
)

 // the one of the two approaches you like better
 // or your own variation of...

we could then use it like:

std::vector<...> v;
iterateOverEqualRanges
(
 v.begin(), v.end(),
 [] (auto begin) /* ... */ ,
 [] (auto current) /* ... */ 
);

Now finally, it looks similiar to e. g. std::for_each, doesn't it?