为什么std :: for_each迭代器需要一个可复制的构造迭代器

我注意到std :: for_each要求它的迭代器满足InputIterator的要求,而后者又需要Iterator然后复制{Contructable,Assignable} .

这不是唯一的事情,std :: for_each实际上使用了复制构造函数(cc)(就我的配置而言,不是赋值) . 也就是说,从迭代器中删除cc将导致:

error: use of deleted function ‘some_iterator::some_iterator(const some_iterator&)’

为什么std :: for_each需要cc?我发现这特别不方便,因为我创建了一个迭代器,它递归地遍历文件夹中的文件,跟踪队列中的文件和文件夹 . 这意味着迭代器有一个队列数据成员,如果使用cc,也必须复制它:这是不必要的低效率 .

奇怪的是,在这个简单的例子中没有调用cc:

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


class infinite_5_iterator
:
public std::iterator<std::input_iterator_tag, int>
{
public:
  infinite_5_iterator() = default;
  infinite_5_iterator(infinite_5_iterator const &) {std::cout << "copy constr "; }

  infinite_5_iterator &operator=(infinite_5_iterator const &) = delete;


  int operator*() { return 5; }
  infinite_5_iterator &operator++() { return *this; }
  bool operator==(infinite_5_iterator const &) const { return false; }
  bool operator!=(infinite_5_iterator const &) const { return true; }
};

int main() {
  std::for_each(infinite_5_iterator(), infinite_5_iterator(),
    [](int v) {
      std::cout << v << ' ';
    }
  );
}

来源:http://ideone.com/YVHph8

然而,它需要编译时间 . 为什么std :: for_each需要复制构造迭代器,何时完成?这不是非常低效吗?

注意:我'm talking about the cc of the iterator, not of it'的元素,如下所示:unexpected copies with foreach over a map

编辑:请注意,标准并未声明复制构造函数完全被调用,它只表示调用f的次数 . 我可以假设cc根本没有被调用吗?为什么没有指定运算符和运算符*和cc的使用,但使用f是?

std::for_each documentation

回答(1)

3 years ago

你已经成为一个规范的牺牲品,这个规范已经发展了数十年的点点滴滴 . InputIterator 的概念是在移动类型或可移动类型的概念被设想之前很久才发明的 .

事后来说,我很想宣布 InputIterator 不需要复制 . 这将与其单程行为完美地啮合 . 但我也担心这样的改变会产生压倒性的向后兼容性问题 .

除了标准中规定的有缺陷的迭代器概念,大约十年前,为了有所帮助,gcc std :: lib(libstdc)开始在std算法中对 InputIterator 这样的东西强加"concepts" . 即因为标准说:

要求:InputIterator应满足输入迭代器(24.2.3)的要求 .

然后将"concept checks"插入到需要 InputIterator 的std算法中,以满足输入迭代器的所有要求,无论算法是否实际使用了所有这些要求 . 在这种情况下,要求迭代器为 CopyConstructible 的是概念检查,而不是实际算法 .

<感叹>

如果你编写自己的 for_each 算法,那么这样做是微不足道的,而不需要你的迭代器是 CopyConstructibleCopyAssignable (如果提供了rvalue迭代器参数):

template <class InputIterator, class Function>
inline
Function
for_each(InputIterator first, InputIterator last, Function f)
{
    for (; first != last; ++first)
        f(*first);
    return f;
}

对于您的用例,我建议您这样做,或者只是编写自己的循环 .