Limit STL algorithms to N elements

Question

(Inspired by a comment from nakiya)

Many STL algorithms take a range as a pair of iterators. For instance, for_each(begin, end, &foo);. Obviously, if distance(begin, end) >= N, and begin is a random-access iterator, then for_each(begin, begin+N, &foo); applies foo only to the first N elements.

Now is there a clean, generic alternative if either of these two conditions is not met?

Answer 1

There is no generic full solution without changing the iterator type.

Proof: suppose that the iterator type is only an InputIterator, so begin actually refers to (for example) a stream, and end is a special-case marker iterator, which will compare equal to the "real" iterator once the real iterator has read EOF.

Then any use of begin to try to work out a new value of end to pass to the algorithm, will "consume" the original value of begin, since that's how InputIterators work.

What you could do is write an iterator wrapper class, such that the iterator counts how many times it has been incremented, and compares equal to an "end" iterator once it has been incremented N times. N could be a template parameter, or a constructor parameter to one or other of the iterators.

Something like this. I've tested it compiles and works for me. Still to do - I'm currently only handling one of your two situations, "not a random-access iterator". I don't also handle the other, "distance < N".

#include <iterator>

template <typename It>
class FiniteIterator : public std::iterator<
  typename std::iterator_traits<It>::iterator_category,
  typename std::iterator_traits<It>::value_type> {
    typedef typename std::iterator_traits<It>::difference_type diff_type;
    typedef typename std::iterator_traits<It>::value_type val_type;
    It it;
    diff_type count;
  public:
    FiniteIterator(It it) : it(it), count(0) {}
    FiniteIterator(diff_type count, It it = It()) : it(it), count(count) {}
    FiniteIterator &operator++() {
        ++it;
        ++count;
        return *this;
    }
    FiniteIterator &operator--() {
        --it;
        --count;
        return *this;
    }
    val_type &operator*() const {
        return *it;
    }
    It operator->() const {
        return it;
    }
    bool operator==(const FiniteIterator &rhs) const {
        return count == rhs.count;
    }
    bool operator!=(const FiniteIterator &rhs) const {
        return !(*this == rhs);
    }
    FiniteIterator operator++(int) {
        FiniteIterator cp = *this;
        ++*this;
        return cp;
    }
    FiniteIterator operator--(int) {
        FiniteIterator cp = *this;
        --*this;
        return cp;
    }
};

Note that the second constructor only takes an iterator because the underlying type might not be default constructible (if it's only an InputIterator). In the case where the caller is creating an "end" iterator it doesn't use it, because it won't be valid once the other copy is incremented.

If the underlying iterator type is RandomAccess, then this wrapper isn't needed/wanted. So I provide a helper template function, that does the type deduction the same way back_inserter does for back_insert_iterator. However, in the case where its parameter type is an iterator of random-access category, the helper shouldn't return FiniteIterator<T>, but just T:

template <typename Iterator, typename Category>
struct finite_traits2 {
    typedef FiniteIterator<Iterator> ret_type;
    static ret_type plus(Iterator it, typename std::iterator_traits<Iterator>::difference_type d) {
        return ret_type(d, it);
    }
};

template <typename Iterator>
struct finite_traits2<Iterator, std::random_access_iterator_tag> {
    typedef Iterator ret_type;
    static ret_type plus(Iterator it, typename std::iterator_traits<Iterator>::difference_type d) {
        return it + d;
    }
};

template <typename Iterator>
struct finite_traits {
    typedef typename std::iterator_traits<Iterator>::iterator_category itcat;
    typedef typename finite_traits2<Iterator, itcat>::ret_type ret_type;
    static ret_type plus(Iterator it, typename std::iterator_traits<Iterator>::difference_type d) {
        return finite_traits2<Iterator, itcat>::plus(it, d);
    }
};

template <typename Iterator, typename Distance>
typename finite_traits<Iterator>::ret_type finite_iterator(Iterator it, Distance d) {
    return finite_traits<Iterator>::plus(it, d);
}

template <typename Iterator>
typename finite_traits<Iterator>::ret_type finite_iterator(Iterator it) {
    return finite_traits<Iterator>::plus(it, 0);
}

Example usage (and minimal test):

#include <iostream>
#include <typeinfo>
#include <list>

struct MyIterator : std::iterator<std::bidirectional_iterator_tag, int> {
    difference_type count;
};

int main() {
    std::cout << typeid(MyIterator::iterator_category).name() << "\n";
    std::cout << typeid(FiniteIterator<MyIterator>::iterator_category).name() << "\n";
    std::cout << typeid(MyIterator::difference_type).name() << "\n";
    std::cout << typeid(FiniteIterator<MyIterator>::difference_type).name() << "\n";

    int a[] = {1, 2, 3, 4, 5};
    std::copy(finite_iterator(a), finite_iterator(a,4), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
    std::list<int> al(finite_iterator(a), finite_iterator(a,4));
    std::cout << al.size() << "\n";
    std::copy(finite_iterator(al.begin()), finite_iterator(al.begin(),3), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}

Caution: finite_iterator(x, 1) == finite_iterator(++x, 0) is false, even for a forward iterator or better. Finite iterators are only comparable if they are created from the same starting point.

Also, this still isn't complete. For example std::reverse doesn't work, because for the purposes of accessing the referand, finite_iterator(x, 1) is "pointing at" x.

Currently the following happens to work:

std::list<int>::iterator e = al.begin();
std::advance(e,3);
std::reverse(finite_iterator(al.begin()), finite_iterator(e,3));

So I'm not far off, but that's not a good interface. I would need to think more about the case of Bidirectional iterators.

Answer 2

There is already fill_n and generate_n, there is no foreach_n (or for_n would probably be more appropriate) but it is easy enough to write one.

template< typename FwdIter, typename Op, typename SizeType >
void for_n( FwdIter begin, SizeType n, Op op )
{
   while( n-- )
   {
      op(*begin);
      ++begin;
   }
}

You could do op(*begin++) but although it is less typing it may generate more code to copy the iterator. size_type is numeric so doing post-increment is no less efficient and here is a case where it is useful.