c++c++17libstdc++libc++

Is std::copy_n source increment count mentioned in standard?


I've implemented an example of an iterator which counts every increment:

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

template <class IteratorCategory = std::vector<int>::iterator::iterator_category>
class DereferenceCountingIterator : public std::vector<int>::iterator {
  public:
    using iterator_category = IteratorCategory;
  public:
    static std::size_t increaseCnt;

    DereferenceCountingIterator(
        typename std::vector<int>::iterator iter)
            : std::vector<int>::iterator(iter) {}

    auto& operator++() {
      ++increaseCnt;
      return std::vector<int>::iterator::operator++();
    }

    DereferenceCountingIterator<IteratorCategory> operator+(difference_type diff) {
        return static_cast<std::vector<int>::iterator&>(*this).operator+(diff);
    }
};

This template class can work both as RandomAccess and as Input iterator:


template<class IteratorCategory>
std::size_t DereferenceCountingIterator<IteratorCategory>::increaseCnt = 0;

using RandomAccessDereferenceContingIterator = DereferenceCountingIterator<>;
using NonRandomAccessDereferenceContingIterator
    = DereferenceCountingIterator<std::input_iterator_tag>;

The app with an example:


int main() {
    auto vec = std::vector<int>{3, 4, 5};

    auto rAVecBegin = RandomAccessDereferenceContingIterator(vec.begin());
    auto nonRAVecBegin = NonRandomAccessDereferenceContingIterator(vec.begin());

    {
        const auto incBefore = RandomAccessDereferenceContingIterator::increaseCnt;
        auto out = std::vector<int>{};
        std::copy_n(rAVecBegin, 3, std::back_inserter(out));
        const auto incAfter = RandomAccessDereferenceContingIterator::increaseCnt;
        std::cout << incAfter - incBefore << std::endl;
    }

    {
        const auto incBefore = NonRandomAccessDereferenceContingIterator::increaseCnt;
        auto out = std::vector<int>{};
        std::copy_n(nonRAVecBegin, 3, std::back_inserter(out));
        const auto incAfter = NonRandomAccessDereferenceContingIterator::increaseCnt;
        std::cout << incAfter - incBefore << std::endl;
    }


    return 0;
}

The output of this program is the following (both in libstdc++ and libc++):

3
2

Can I be sure that copy_n does exactly n-1 increments on source iterator if it is not RandomAccessIterator and n increments if it is?


Solution

  • Can I be sure that copy_n does exactly n-1 increments on source iterator if it is not RandomAccessIterator and n increments if it is?

    No, there is no requirement on the number of increments.

    If the iterator is only an input iterator, not a forward iterator, then the implementation is forced to do exactly n or n-1 increments up to the last dereferenced iterator or the one after that which is not dereferenced but must be valid. An input iterator can't be iterated through the source sequence in any other way.

    If the iterator is a forward iterator or even random access iterator, there is no requirement on the number of increments and the implementation may also decrement or make larger steps than increments/decrements. If the iterator is contiguous it may use pointers instead of iterators to access elements of the sequence.

    There is also no requirement that the sequence is copied in order either.

    The only complexity requirement is that exactly n assignments are made.