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

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

您可以使用 std::upper_bound 将迭代器获取到 "next" 值。由于 std::upper_bound returns 指向第一个大于所提供值的元素的迭代器，如果您提供当前元素的值，它将为您提供一个迭代器，该迭代器将是当前值末尾的迭代器.那会给你一个像

这样的循环

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 2

这基本上是范围 v3 的 group_by：group_by(v, std::equal_to{})。它不存在于 C++17 标准库中，但我们可以编写自己的粗略等效项：

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

用法：

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 3

您正在寻找 std::equal_range。

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

像下面这样的东西应该可以工作。

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
}

^{备注：虽然这是一种直观的方法，但 std::equal_range 会先获得它的和 second 迭代器（即 b 和 e）在 std::lower_bound and std::upper_bound, which makes this approche slightly inefficient 的帮助下。因为，对于 OP 的情况，first 迭代器可以很容易地访问，调用 std::upper_bound 只需要 second 迭代器（如 @NathanOliver 的回答).}

Answer 4

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 [...])

取决于你如何解读'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
    }
}

没有对最后一个范围进行特殊处理——仅此而已，可能需要两次初始化代码...

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

更优雅？承认，我自己也有疑问……不过，这两种方法都避免在同一范围内迭代两次（首先是为了找到结束，然后是实际迭代）。如果我们从以下位置创建自己的库函数：

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

然后我们可以像这样使用它：

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

现在终于和e很像了。 G。 std::for_each，不是吗？

Answer 5

如果您的等值范围很短，那么 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 6

for(auto b=v.begin(), i=b, e=v.end(); i!=e; b=i) {
    // initialise the 'Do something' code for another range
    for(; i!=e && *i==*b; ++i) {
        // Do something with i
    }
}

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

How do I iterate equal values with the standard library?

c++

algorithm

c++-standard-library

iterator-range

c++17