41

假设我有一个向量：

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

有没有用标准库解决这个问题的优雅方法？

4

6 回答 6

29

这基本上是 Range 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.
    }
});
于 2019-07-02T20:51:24.833 回答
26

您可以使用std::upper_bound将迭代器获取到“下一个”值。由于std::upper_bound返回大于所提供值的第一个元素的迭代器，如果您提供当前元素的值，它将为您提供一个迭代器，该迭代器将超过当前值的末尾。那会给你一个像

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
}
于 2019-07-02T20:48:19.763 回答
21

您正在寻找std::equal_range.

返回一个范围，其中包含与范围[first, last)中的 value 等效的所有元素。

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

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
}

备注：尽管这将是一种直观的方法，但在and的帮助下std::equal_range获得了它的第一个和第二个迭代器（即b和e），这使得这种方法效率略低。因为，对于 OP 的情况，第一个迭代器可以很容易地访问，只需要调用第二个迭代器（如@NathanOliver的回答所示）。std::lower_boundstd::upper_boundstd::upper_bound

于 2019-07-02T20:56:55.057 回答
9

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

    }
}

std::not_equal_to如果你愿意，你也可以用 lambda 代替。

于 2019-07-03T06:21:44.870 回答
7

但即使我们什么都不用 e，这个公式很方便，也更难出错。另一种方式（检查变化的值）更乏味（因为我们需要特别处理最后一个范围[...]）

取决于您如何解释“特别处理最后一个范围”：

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

最后一个范围没有特殊处理 - 只是，可能需要两次初始化代码......

嵌套循环方法：

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

现在终于，它看起来类似于 eg std::for_each，不是吗？

于 2019-07-02T21:34:17.593 回答
0 
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
    }
}
于 2019-07-10T08:45:10.830 回答