std::copy_n对源迭代器的递增次数是否有C++标准明确规定？

实现的计数迭代器模板类 #

我实现了一个统计递增操作次数的迭代器模板类，可同时作为随机访问迭代器和输入迭代器使用：

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

特化与别名定义 #

该模板类的特化及别名定义如下：

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

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

测试程序及输出 #

测试示例程序：

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

该程序在libstdc和libc中的输出均为：

3
2

疑问 #

C++标准中是否提及std::copy_n对源迭代器的递增次数？是否可确定当源迭代器为非随机访问迭代器时，std::copy_n恰好执行n-1次递增；当为随机访问迭代器时执行n次递增？

解答 #

C++标准确实对std::copy_n的迭代器操作次数有明确规定：

• 对于非随机访问迭代器（输入迭代器范畴），std::copy_n必须执行恰好n-1次递增操作。因为这类迭代器不支持直接跳转，只能通过循环逐个复制元素：从起始位置开始，复制第1个元素后递增一次，直到复制完第n个元素，总共需要n-1次递增就能遍历完所有目标元素，这是标准强制要求的行为。
• 对于随机访问迭代器，标准允许实现进行优化，并没有强制固定递增次数。主流库（如libstdc++、libc++）会选择执行n次递增的实现方式，但理论上也可以直接通过起始迭代器 + n的方式跳转至结束位置，此时递增次数为0。不过从测试结果来看，n次递增是当前主流的实现选择。

总结：

• 非随机访问迭代器：递增次数固定为n-1，符合标准强制要求。
• 随机访问迭代器：递增次数不固定，但主流实现会执行n次递增。

内容的提问来源于stack exchange，提问作者Георгий Гуминов