如何使用标准库迭代相等的值？

Question

假设我有一个向量：

std::vector<Foo> v;

此向量已排序，因此相等的元素彼此相邻。

获得所有表示具有相等元素的范围的迭代器对的最佳方法是什么（使用标准库）？

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
    }
}

我想知道如何在上面的代码中获取b和的值e。

因此，例如，如果v包含以下数字：

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

然后，我想在循环中具有b并e指向元素：

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

使用标准库可以解决此问题吗？

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

Answer 2

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
}

Answer 3

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.

auto it = v.begin();
while (it != v.end())
{
    auto [b, e] = std::equal_range(it, v.end(), *it);
    for (; b != e; ++b) { /* do something in the range[b, e) */ }
    it = e;             // need for the beginning of next std::equal_range
}

^{Remark: Even though this will be an intuitive approach, the std::equal_range obtains its first and second iterators(i.e b and e) with the help of std::lower_bound and std::upper_bound, which makes this approche slightly inefficient. Since, the first iterator could be easily accessible for the OP's case, calling std::upper_bound for second iterator only neccesarry(as shown by @NathanOliver 's answer).}

Answer 4

如果您的相等值范围较短，则std::adjacent_find效果很好：

for (auto it = v.begin(); it != v.end();) {
    auto next = std::adjacent_find(it, v.end(), std::not_equal_to<Foo>());
    for(; it != next; ++it) {

    }
}

如果需要，也可以用lambda代替std::not_equal_to。

Answer 5

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)
{
    if(i == v.end() || *i != *begin)
    {
        // handle range single element of range [begin, ???);
        if(i == v.end())
            break;
        begin = i;
        // re-initialize next range
    }
}

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)
    {
        if(i == v.end() || *i != *begin)
        {
            // handle range single element of range [begin, ???);
            if(i == v.end())
                goto LOOP_EXIT;
            begin = i;
            break;
        }
    }
}
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?