Разделить диапазон на диапазон перекрывающихся диапазонов

Я пытаюсь использовать библиотеку Ranges-V3, чтобы разделить контейнер значений на диапазон диапазонов, чтобы соседние диапазоны имели общие граничные элементы.

Учтите следующее:

using namespace ranges;

std::vector<int> v = { 1, 2, 3, 0, 4, 0, 5, 0, 6, 7, 8, 0, 0, 9 };
auto myRanges = v | /* something like adjacent split */
for_each( myRanges, []( auto&& range ){ std::cout << range << std::endl;} );

Я хотел бы разделить диапазон на перекрывающиеся поддиапазоны в зависимости от того, соответствует ли регион двум критериям:

  1. имеет ли элемент нулевое значение
  2. или находится рядом с одним или несколькими элементами с нулевым значением

Желаемый результат:

[1,2,3]
[3,0,4,0,5,0,6]
[6,7,8]
[8,0,0,9]

моя попытка:

auto degenerate =
  []( auto&& arg ){
    return distance( arg ) < 2;  
  };

auto myRanges = v | view::split(0) | view::remove_if( degenerate );
for_each( myRanges, []( auto&& range ){ std::cout << range << std::endl;} );

Выход:

[1,2,3]
[6,7,8]

Я не понимаю, как я могу

  1. "вставить" диапазон от 3 до 6
  2. "добавить" диапазон от 8 до 9

person apmccartney    schedule 01.03.2017    source источник
comment
почему вы передаете движущуюся ссылку? это испортит ваши данные   -  person Sugar    schedule 01.03.2017
comment
@Sugar Полагаю, вы имеете в виду использование auto&& и впечатление, что && подразумевает ссылку на rvalue. В данном случае эта сигилла подразумевает не ссылку rvalue, а то, что Скотт Мейер называет универсальными ссылками. См. Дополнительную информацию (здесь) [isocpp.org/blog / 2012/11 /   -  person apmccartney    schedule 01.03.2017
comment
Вот рабочая версия ссылки apmccartney .   -  person Justin Time - Reinstate Monica    schedule 02.03.2017


Ответы (1)


Если я правильно понимаю ваши требования, вы можете реализовать генератор в терминах adjacent_find:

namespace detail {
    template<typename IterT, typename SentT>
    struct seg_gen_fn {
        IterT it_;
        SentT end_;
        bool parity_ = true;

        ranges::iterator_range<IterT> operator ()() {
            if (it_ == end_) {
                return {it_, it_};
            }

            auto n = ranges::adjacent_find(
                it_, end_,
                [p = std::exchange(parity_, !parity_)](auto const a, auto const b) {
                    return a && !b == p;
                }
            );
            return {
                std::exchange(it_, n),
                n != end_ ? ranges::next(std::move(n)) : std::move(n)
            };
        }
    };

    template<typename RngT>
    constexpr auto seg_gen(RngT&& rng)
     -> seg_gen_fn<ranges::iterator_t<RngT>, ranges::sentinel_t<RngT>>
    { return {ranges::begin(rng), ranges::end(rng)}; }
} // namespace detail

auto const segmented_view = [](auto&& rng) {
    return ranges::view::generate(detail::seg_gen(decltype(rng)(rng)))
         | ranges::view::take_while([](auto const& seg) { return !seg.empty(); });
};

int main() {
    auto const ns = {1, 2, 3, 0, 4, 0, 5, 0, 6, 7, 8, 0, 0, 9};
    ranges::copy(segmented_view(ns), ranges::ostream_iterator<>{std::cout, "\n"});
}

Интернет-демонстрация
Не так кратко, как можно было бы надеяться ...: - [


Это, вероятно, подходит для одноразового кода, но нужно немного поработать, и его можно будет использовать повторно:

namespace detail {
    namespace tag = ranges::tag;

    template<
        typename RngT, typename PredT, typename IterT = ranges::iterator_t<RngT>,
        typename StateT = ranges::tagged_compressed_tuple<
            tag::begin(IterT), tag::end(ranges::sentinel_t<RngT>),
            tag::current(bool), tag::fun(ranges::semiregular_t<PredT>)
        >
    >
    struct seg_gen_fn : private StateT {
        constexpr seg_gen_fn(RngT&& rng, PredT pred)
          : StateT{ranges::begin(rng), ranges::end(rng), true, std::move(pred)}
        { }

        ranges::iterator_range<IterT> operator ()() {
            StateT& state = *this;
            auto& it = state.begin();
            if (it == state.end()) {
                return {it, it};
            }

            auto& parity = state.current();
            auto n = ranges::adjacent_find(
                it, state.end(),
                [p = std::exchange(parity, !parity), &pred = state.fun()]
                (auto const& a, auto const& b) {
                    return !pred(a) && pred(b) == p;
                }
            );
            return {
                std::exchange(it, n),
                n != state.end() ? ranges::next(std::move(n)) : std::move(n)
            };
        }
    };

    template<typename RngT, typename PredT>
    constexpr seg_gen_fn<RngT, PredT> seg_gen(RngT&& rng, PredT pred) {
        return {std::forward<RngT>(rng), std::move(pred)};
    }
} // namespace detail

auto const segmented_view = [](auto&& rng, auto pred) {
    return ranges::view::generate(detail::seg_gen(decltype(rng)(rng), std::move(pred)))
         | ranges::view::take_while([](auto const& seg) { return !seg.empty(); });
};

int main() {
    auto const ns = {1, 2, 3, 0, 4, 0, 5, 0, 6, 7, 8, 0, 0, 9};
    ranges::copy(
        segmented_view(ns, [](auto const n) { return n == 0; }),
        ranges::ostream_iterator<>{std::cout, "\n"}
    );
}

Интернет-демонстрация

Проверка концепций и прогнозы оставлены как упражнение.

person ildjarn    schedule 01.03.2017
comment
@ildjam Вау! Большое спасибо за многоразовую версию в вашей редакции. - person apmccartney; 21.04.2018
comment
@apmccartney: Пожалуйста. : -] Я вернулся к ответу после случайного положительного голоса и почувствовал себя обязанным обновить его, поскольку он слишком конкретен. Я не уверен, что он обрабатывает начальные нули должным образом, но их размещение в отдельном сегменте требует только изменения жестко запрограммированного true для контроля четности (или отсрочки инициализации четности до первого вызова). - person ildjarn; 22.04.2018