Issue 1211: Move iterators should be restricted as input iterators

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: 24.5.4.2 [move.iterator] Status: Resolved Submitter: Alisdair Meredith Opened: 2009-09-18 Last modified: 2016-05-14

Priority: Not Prioritized

View other active issues in [move.iterator].

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 24.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 24.5.4.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.