This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Resolved status.

### 1211. Move iterators should be restricted as input iterators

Section: 23.5.3.2 [move.iterator] Status: Resolved Submitter: Alisdair Meredith Opened: 2009-09-18 Last modified: 2016-05-14

Priority: Not Prioritized

View all other issues in [move.iterator].

View all issues with Resolved status.

Discussion:

I contend that while we can support both bidirectional and random access traversal, the category of a move iterator should never be better than `input_iterator_tag`.

The contentious point is that you cannot truly have a multipass property when values are moved from a range. This is contentious if you view a moved-from object as still holding a valid value within the range.

The second reason comes from the Forward Iterator requirements table:

> Forward iterators 23.3.5.5 [forward.iterators]

> Table 102 — Forward iterator requirements

> > For expression `*a` the return type is: "`T&` if `X` is mutable, otherwise `const T&`"

There is a similar constraint on `a->m`.

There is no support for rvalue references, nor do I believe their should be. Again, opinions may vary but either this table or the definition of `move_iterator` need updating.

Note: this requirement probably need updating anyway if we wish to support proxy iterators but I am waiting to see a new working paper before filing that issue.

[ 2009-10 post-Santa Cruz: ]

> Move to Open. Howard to put his rationale mentioned above into the issue as a note.

[ 2009-10-26 Howard adds: ]

> `vector::insert(pos, iter, iter)` is significantly more effcient when `iter` is a random access iterator, as compared to when it is an input iterator.

> When `iter` is an input iterator, the best algorithm is to append the inserted range to the end of the `vector` using `push_back`. This may involve several reallocations before the input range is exhausted. After the append, then one can use `std::rotate` to place the inserted range into the correct position in the vector.

> But when `iter` is a random access iterator, the best algorithm is to first compute the size of the range to be inserted (`last - first`), do a buffer reallocation if necessary, scoot existing elements in the `vector` down to make the "hole", and then insert the new elements directly to their correct place.

> > The insert-with-random-access-iterators algorithm is considerably more efficient than the insert-with-input-iterators algorithm

> Now consider:

> >     vector<A> v;
> >     //  ... build up a large vector of A ...
> >     vector<A> temp;
> >     //  ... build up a large temporary vector of A to later be inserted ...
> >     typedef move_iterator<vector<A>::iterator> MI;
> >     //  Now insert the temporary elements:
> >     v.insert(v.begin() + N, MI(temp.begin()), MI(temp.end()));

> A major motivation for using `move_iterator` in the above example is the expectation that `A` is cheap to move but expensive to copy. I.e. the customer is looking for high performance. If we allow `vector::insert` to subtract two `MI`'s to get the distance between them, the customer enjoys substantially better performance, compared to if we say that `vector::insert` can not subtract two `MI`'s.

> I can find no rationale for not giving this performance boost to our customers. Therefore I am strongly against restricting `move_iterator` to the `input_iterator_tag` category.

> I believe that the requirement that forward iterators have a dereference that returns an lvalue reference to cause unacceptable pessimization. For example `vector<bool>::iterator` also does not return a `bool&` on dereference. Yet I am not aware of a single vendor that is willing to ship `vector<bool>::iterator` as an input iterator. Everyone classifies it as a random access iterator. Not only does this not cause any problems, it prevents significant performance problems.

Previous resolution [SUPERSEDED]:

> Class template move_iterator 23.5.3.2 [move.iterator]

> >     namespace std {
> >     template <class Iterator>
> >     class move_iterator {
> >     public:
> >      ...
> >      typedef typename iterator_traits<Iterator>::iterator_category input_iterator_tag iterator_category;

[ 2010 Pittsburgh: Moved to NAD Editorial Resolved. Rationale added below. ]

Rationale:

Solved by N3066.

Proposed resolution:

See N3066.