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

C++ 14样式的实例(使用手动类型定义和good ole C++ 98的函数对象),[0, 3), [4, 6), [8, 12)为您的输入打印.