为什么std :: for_each迭代器需要一个可复制的构造迭代器 [英] why does std::for_each iterator need a copy constructable iterator

问题描述

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

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

 错误：使用已删除的函数'some_iterator :: some_iterator（const some_iterator&）'
  

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

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

  #include <&的iostream GT; 
 #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<< 复制建设; } 
 
 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需要复制构造迭代器，何时完成？这不是非常低效吗？

注意：我在谈论迭代器的cc，而不是它的元素，如下所示：在地图上使用foreach的预期副本

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

解决方案

您只是成为规范的牺牲品几十年来一直在发展。 InputIterator 的概念是在移动类型或可移动类型的概念被设想之前发明的。

<事后我很乐意声明 InputIterator 不需要是可复制的。这将与其单程行为完美地啮合。但我也担心这样的改变会产生压倒性的向后兼容性问题。

除了标准中规定的有缺陷的迭代器概念，大约十年前，尝试提供帮助，gcc std :: lib（libstdc ++）开始在std-algorithms中对 InputIterator 之类的东西强加概念。即因为标准说：

需要： InputIterator 应满足输入迭代器（24.2.3）的要求。

然后将概念检查插入到std算法中require InputIterator 以满足输入迭代器的所有要求，无论算法是否实际使用了所有这些要求。在这种情况下，它是概念检查，而不是实际的算法，要求你的迭代器 CopyConstructible 。

< sigh>

如果你编写自己的 for_each 算法，这样做很简单，不需要你的迭代器 CopyConstructible 或 CopyAssignable （如果提供rvalue迭代器参数）：

  template< class InputIterator，class Function> 
 inline 
函数
 for_each（InputIterator first，InputIterator last，Function f）
 {
 for（; first！= last; ++ first）
f （*第一）; 
返回f; 
} 
  

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

I noticed that std::for_each requires it's iterators to meet the requirement InputIterator, which in turn requires Iterator and then Copy{Contructable,Assignable}.

That's not the only thing, std::for_each actually uses the copy constructor (cc) (not assignment as far as my configuration goes). That is, deleting the cc from the iterator will result in:

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

Why does std::for_each need a cc? I found this particularly inconvenient, since I created an iterator which recursively iterates through files in a folder, keeping track of the files and folders on a queue. This means that the iterator has a queue data member, which would also have to be copied if the cc is used: that is unnecessarily inefficient.

The strange thing is that the cc is not called in this simple example:

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

source: http://ideone.com/YVHph8

It however is needed compile time. Why does std::for_each need to copy construct the iterator, and when is this done? Isn't this extremely inefficient?

NOTE: I'm talking about the cc of the iterator, not of it's elements, as is done here: unexpected copies with foreach over a map

EDIT: Note that the standard does not state the copy-constructor is called at all, it just expresses the amount of times f is called. May I then assume that the cc is not called at all? Why is the use of operator++ and operator* and cc not specified, but the use of f is?

解决方案

You have simply fallen victim to a specification that has evolved in bits and pieces over decades. The concept of InputIterator was invented a long time before the notion of move-only types, or movable types was conceived.

In hindsight I would love to declare that InputIterator need not be copyable. This would mesh perfectly with its single-pass behavior. But I also fear that such a change would have overwhelming backwards compatibility problems.

In addition to the flawed iterator concepts as specified in the standard, about a decade ago, in an attempt to be helpful, the gcc std::lib (libstdc++) started imposing "concepts" on things like InputIterator in the std-algorithms. I.e. because the standard says:

Requires: InputIterator shall satisfy the requirements of an input iterator (24.2.3).

then "concept checks" were inserted into the std-algorithms that require InputIterator to meet all of the requirements of input iterator whether or not the algorithm actually used all of those requirements. And in this case, it is the concept check, not the actual algorithm, that is requiring your iterator to be CopyConstructible.

<sigh>

If you write your own for_each algorithm, it is trivial to do so without requiring your iterators to be CopyConstructible or CopyAssignable (if supplied with rvalue iterator arguments):

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

And for your use case I recommend either doing that, or simply writing your own loop.

这篇关于为什么std :: for_each迭代器需要一个可复制的构造迭代器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！