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> ，我什么也没想到。

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) << "), ";
    }
}

Live Example在 C++14 风格中(使用手动类型定义和函数对象来获得良好的 ole C++98)打印 [0, 3), [4, 6), [8, 12)征求意见。