Реализации count_until и accumulate_until?

Учитывая входную последовательность, стандартные алгоритмы std::count и std::accumulate подсчитывают количество событий определенного значения (или совпадение предикатов для std::count_if) и накопление данной ассоциативной операции (sum, product, Boolean или/и, min/max, конкатенация строк и т.д.), соответственно.

Что, если кто-то хочет знать, содержит ли входная последовательность ровно/по крайней мере/не более n встреча/совпадения или накапливается до суммы точно/не менее/не более n? Метод грубой силы - сравнить результат std::count или std::accumulate с целевым n, но это пропустит возможность раннего выхода, когда количество или накопление превысит цели уже на полпути через входную последовательность.

Можно, например, сделайте count_until как

template<class InputIt, class T, class Pred>
auto count_until(InputIt first, InputIt last, const T& value, Pred pred)
{
    auto res = 0;
    for (; first != last; ++first)
        if (*first == value && pred(++res))
            break; // early exit if predicate is satisfied
    return std::make_pair(first, res); // iterator and value to allow continuation    
}

и из которого можно было бы проверить равенство/по крайней мере/не более, используя подходящий предикат и сравнение с возвращаемым счетом.

Вопросы:

  • можно написать count_until (и аналогично для accumulate_until) с использованием комбинации существующих стандартных алгоритмов, возможно, в сочетании с подходящим Boost.Iterator?
  • В частности, я думал о find_if над accumulate_iterator, где предикат извлекал бы счет или сумму из итератора.
  • Или выполнить count_until и accumulate_until включение в качестве автономных примитивов в будущей версии стандартной библиотеки?

Изменить. Я считаю, что наиболее полезной формулировкой является возвращение std::pair итератора и счетчика в точке, где предикат сначала выполняется. Это позволяет пользователям продолжить итерацию.

Ответы

Ответ 1

Я думал о комбинации std:: find_if с предикатом состояния: (Pred - обычный пользовательский предикат.)

template<class InputIt, class T, class Pred>
typename iterator_traits<InputIterator>::difference_type
count_until(InputIt begin, InputIt end, const T& value, Pred pred)
{
    typename iterator_traits<InputIterator>::difference_type count = 0;
    auto internal_pred = [&count, &value, &pred](decltype(*begin) elem) {
        return elem == value && pred(++count);
    };

    std::find_if(begin, end, internal_pred);
    return count;
}

template<class InputIt, class T, class Pred>
T accumulate_until(InputIt begin, InputIt end, T value, Pred pred)
{
    auto internal_pred = [&value, &pred] (const T& t) {
        value += t;
        return pred(value);
    };
    std::find_if(begin, end, internal_pred);
    return value;
}