Implementations of count_until and accumulate_until?

Question

Given an input sequence, the standard algorithms std::count and std::accumulate count the number of occurances of a specific value (or predicate matches for std::count_if) and the accumulation of a given associative operation (sum, product, Boolean or/and, min/max, string concatenation, etc.), respectively.

What if one wants to know whether an input sequence contains exactly/at least/at most n occurances/matches, or accumulates to a sum of exactly/at least/at most n? The brute-force way would be to compare the result of std::count or std::accumulate against the target n, but that would miss out on an early exit opportunity when the count or accumulation exceeds the target already halfway through the input sequence.

One could e.g. make a count_until as

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    
}

and from which one could test for equality/at least/at most by using a suitable predicate and comparison against the returned count.

Questions:

• is it possible to write count_until (and similarly for accumulate_until) using a combination existing standard algorithms, possibly in combination with a suitable Boost.Iterator?
• In particular, I was thinking of a find_if over an accumulate_iterator where the predicate would extract the count or sum from the iterator.
• Or do count_until and accumulate_until warrant inclusion as standalone primitives in a future version of the Standard Library?

Edit: I think the most useful formulation is to return a std::pair of an iterator and the count at the point where the predicate is first satisfied. This enables users to continue iterating.

Answer 1

I was thinking of a combination of std::find_if with a state predicate: (Pred is normal user predicate.)

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;
}