С++ "группа где" алгоритм

Есть ли функция в 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 и избежать циклов для такого рода вещей. Шон Родитель большой разговор, С++ Seasoning, это моя мотивация.

Просматривая <algorithm>, я ничего не выскочил.

Ответ 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) << "), ";
    }
}

Живой пример в стиле С++ 14 (используйте определения ручного типа и объекты функций для хорошего ole С++ 98), который печатает [0, 3), [4, 6), [8, 12) для ввода.

Ответ 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 ) );