why does std::for_each iterator need a copy constructable iterator

Question

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?

Answer 1

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.