C++ "group where" 算法

Question

STL中是否有一个函数，可以将一个序列分成连续的子序列，其中某些谓词是有效的？

例如，以下序列：

1 1 1 0 1 1 0 0 1 1 1 1

给定一个谓词 v == 1，应该返回三个子序列：

1 1 1
1 1
1 1 1 1

组的顺序以及组内元素的顺序应该被保留。

我可以写一个O(N)的循环来实现，但我正在尝试学习更多关于STL，并避免使用循环来完成这种事情。Sean Parent的精彩演讲C++ Seasoning是我的动力。

浏览<algorithm>，没有什么特别引人注目的。

- Drew Noakes

---

也许这个问题可以表达为一种更通用的分词形式？在你的例子中，分隔符满足v！=1。 - user2672165

可能可以使用 std::partition_point 和 std::stable_partition 来实现。 - P0W

我不是很清楚：“应该返回三个子序列”，那么这些子序列应该如何被返回呢？是数组视图的向量？迭代器？还是容器中的迭代器？亦或是范围的向量？ - Ali

我会投票支持“范围集合”作为最符合STL的选择。 - user2672165

@TemplateRex，感谢您的解释和回答。我已经使用了相当多的C#，其中有一个IEnumerable<T>类型来表示序列，并且它可以在运算符/算法之间很好地组合。我仍在学习如何组合STL算法。对于某些类型的操作，似乎拥有一个begin/end对使得代码变得更冗长，但它确实更灵活。 - Drew Noakes

Answer 1

标准库中没有这样的算法。您可以手动编写一个，使用std::find_if和std::find_if_not来查找每个出现序列的开始和结束迭代器。我认为输出应该是一个std::pair<FwdIt，FwdIt>范围。该算法在其输入上具有O(N)复杂度。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <utility>

template<class FwdIt, class OutIt, class UnaryPred>
auto find_all_if(FwdIt first, FwdIt last, OutIt dst, UnaryPred pred)
{   
    while (first != last) {
        // start of next occurance
        auto next_b = std::find_if(first, last, pred);
        if (next_b == last) break;

        // end of next occurance
        auto next_e = std::find_if_not(next_b, last, pred);
        *dst++ = make_pair(next_b, next_e);

        first = next_e;
    }
    return dst;
}

int main()
{
    auto const v = std::vector<int> { 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1 };
    using It = decltype(v.begin());
    std::vector<std::pair<It, It>> r; // "range of ranges" 

    find_all_if(begin(v), end(v), std::back_inserter(r), 
        [](auto e) { return e == 1; }
    );

    for (auto&& e : r) {
        std::cout << "[";
        std::cout << std::distance(begin(v), e.first) << ", ";
        std::cout << std::distance(begin(v), e.second) << "), ";
    }
}

在C++14风格下的实时示例（使用手动类型定义和函数对象来支持老旧的C++98），可根据输入打印[0, 3), [4, 6), [8, 12)。

- TemplateRex

---

我想这已经是最好的了。有哪些算法可以获得多个范围呢？ - user2672165

@user2672165 不，当前的标准算法和容器成员函数返回的要么是空值、计数、迭代器或者是迭代器和布尔值的一对（例如 map::insert）。当然，将迭代器返回到一个迭代器对的输出范围中，可以模拟您所请求的范围。 - TemplateRex

好的。谢谢信息。此外，人们可以反思这样一个事实：尽管范围在STL中非常核心，但没有官方的范围类型（def）。在您的情况下，您不得不创建一个pair。 - user2672165

@user2672165 请查看标准范围研究小组，这里正在讨论这些主题。最近有很多基于此的讨论。 - TemplateRex

Answer 2

算法应该返回什么？一组范围（迭代器对）的向量吗？还是它只是留下一个修改后的容器，其中不满足条件的元素应该被删除？

对于第一种情况，您可以“半手动”地使用交替 std::find_if()和std::find_if_not() 直到到达容器的末尾。

对于第二种情况，应用remove-erase-idiom。

container.erase( std::remove_if(
        std::begin( container ), std::end( container ), 
        []( int i ){ return i != 1; } ), 
    std::end( container ) );

- Ralph Tandetzky

---

第二个解决方案不符合要求。 - user2672165

@user2672165 为什么不呢？ - Ralph Tandetzky

现在可能已经太晚了，但是你只会得到一个范围吗？ - user2672165

这是正确的。从问题中，我不清楚计算的确切结果应该是什么。这是一个更简单的选择。 - Ralph Tandetzky