C++ "group where" algorithm

Question

Is there a function in the STL that will divide a sequence into contiguous subsequences where some predicate is valid?

For example the following sequence:

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

Given a predicate v == 1, should return three subsequences:

1 1 1
1 1
1 1 1 1

The order of groups, and elements within those groups, should be preserved.

I can write a loop to do this in O(N) but I'm trying to learn more about the STL and avoid loops for this kind of thing. Sean Parent's great talk, C++ Seasoning, is my motivation.

Looking through <algorithm>, nothing jumped out at me.

Answer 1

There is no such algorithm already in the Standard Library. You can write one by hand using std::find_if and std::find_if_not to find the beginning and end iterators of each occuring sequence. I think the output should be a range of std::pair<FwdIt, FwdIt>. The algorithm has O(N) complexity over its input.

#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 in C++14 style (use manual type definitions and function objects for the good ole C++98) that prints [0, 3), [4, 6), [8, 12) for your input.