2106. move_iterator wrapping iterators returning prvalues

Section: 24.5.4 [move.iterators] Status: C++17 Submitter: Dave Abrahams Opened: 2011-11-30 Last modified: 2017-07-30

Priority: 3

View all other issues in [move.iterators].

View all issues with C++17 status.

Discussion:

Shouldn't move_iterator be specialized so that if the iterator it wraps returns a prvalue when dereferenced, the move_iterator also returns by value? Otherwise, it creates a dangling reference.

Howard: I believe just changing move_iterator<I>::reference would do. A direction might be testing on is_reference<iterator_traits<I>::reference>, or is_reference<decltype(*declval<I>())>.

Daniel: I would prefer to use a consistent style among the iterator adaptors, so I suggest to keep with the iterator_traits typedefs if possible.

using reference = typename conditional<
  is_reference<typename iterator_traits<Iterator>::reference>::value,
  value_type&&,
  value_type
>::type;

We might also want to ensure that if Iterator's reference type is a reference, the referent is equal to value_type (after removal of cv-qualifiers). In general we have no such guarantee.

Marc: In the default case where we don't return value_type&&, should we use value_type or should we keep the reference type of the wrapped iterator?

Daniel: This suggestion looks appealing at first, but the problem here is that using this typedef can make it impossible for move_iterator to satisfy its contract, which means returning an rvalue of the value type (Currently it says rvalue-reference, but this must be fixed as of this issue anyway). I think that user-code can reasonably expect that when it has constructed an object m of move_iterator<It>, where It is a valid mutable iterator type, the expression

It::value_type&& rv = *m;

is well-formed.

Let's set R equal to iterator_traits<Iterator>::reference in the following. We can discuss the following situations:

1. R is a reference type: We can only return the corresponding xvalue of R, if value_type is reference-related to the referent type, else this is presumably no forward iterator and we cannot say much about it, except that it must be convertible to value_type, so it better should return a prvalue.
2. R is not a reference type: In this case we can rely on a conversion to value_type again, but not much more. Assume we would return R directly, this might turn out to have a conversion to an lvalue-reference type of the value type (for example). If that is the case, this would indirectly violate the contract of move_iterator.

In regard to the first scenario I suggest that implementations are simply required to check that V2 = remove_cv<remove_reference<R>::type>::type is equal to the value type V1 as a criterion to return this reference as an xvalue, in all other cases it should return the value type directly as prvalue.

The additional advantage of this strategy is, that we always ensure that reference has the correct cv-qualification, if R is a real reference.

It is possible to improve this a bit by indeed supporting reference-related types, this would require to test is_same<V1, V2>::value || is_base_of<V1, V2>::value instead. I'm unsure whether (a) this additional effort is worth it and (b) a strict reading of the forward iterator requirements seems not to allow to return a reference-related type (Whether this is a defect or not is another question).

[2011-12-05: Marc Glisse comments and splits into two resolution alternatives]

I guess I am looking at the speed of:

value_type x;
x = *m;

(copy construction would likely trigger copy elision and thus be neutral) instead of the validity of:

value_type&& x = *m;

In this sense, Daniels earlier proposition that ignored value_type and just did switch_lvalue_ref_to_rvalue_ref<reference> was easier to understand (and it didn't require thinking about reference related types).

The currently proposed resolution has been split into two alternatives.

[2012, Kona]

Move to Review.

Alisdair: This only applies to input iterators, so keep that in mind when thinking about this.

STL: I see what B is doing, but not A.

Howard: I agree.

Alisdair: Should we use add_rvalue_reference?

STL: No, we do not want reference collapsing.

STL: Re A, messing with the CV qualification scares me.

Alisdair: Agree. That would break my intent.

STL: Actually I don't think it's actually wrong, but I still don't see what it's doing.

Alisdair: A is picking the value type, B is picking the proxy type.

Howard: I like returning the proxy type.

STL: Returning a reference (B) seems right, because the requirements say "reference". I suspect that B works correctly if you have a move iterator wrapping a move iterator wrapping a thing. I think that A would mess up the type in the middle.

Considerable discussion about which version is correct, checking various examples.

STL: Still think B is right. Still don't understand A. In A we are losing the proxyness.

Howard: Agree 100%. We don't want to lose the proxy. If it's const, so be it.

STL: B is also understandable by mortals.

Howard: Remove to review, keep A but move it out of the proposed resolution area (but keep it for rational).

Alisdair: Adding an explanatory note might be a good idea, if someone wants to write one.

Walter: Concerned about losing the word "reference" in p.1.

Howard: move_iterator will return an xvalue or a prvalue, both of which are rvalues.

[Proposed resolution A, rejected in preference to the currently proposed resolution (B)

1. Change 24.5.4 [move.iterators] p1 as indicated:

   Class template move_iterator is an iterator adaptor with the same behavior as the underlying iterator except that its dereference operator implicitly converts the value returned by the underlying iterator's dereference operator to an rvalue referenceof the value type. Some generic algorithms can be called with move iterators to replace copying with moving.

2. Change 24.5.4.2 [move.iterator], class template move_iterator synopsis, as indicated:

   namespace std {
     template <class Iterator>
     class move_iterator {
     public:
       typedef Iterator iterator_type;
       typedef typename iterator_traits<Iterator>::difference_type difference_type;
       typedef Iterator pointer;
       typedef typename iterator_traits<Iterator>::value_type value_type;
       typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
       typedef value_type&&see below reference;
       […]
     };
   }
   

3. Immediately following the class template move_iterator synopsis in 24.5.4.2 [move.iterator] insert a new paragraph as indicated:

   -?- Let R be iterator_traits<Iterator>::reference and let V be iterator_traits<Iterator>::value_type. If is_reference<R>::value is true and if remove_cv<remove_reference<R>::type>::type is the same type as V, the template instantiation move_iterator<Iterator> shall define the nested type named reference as a synonym for remove_reference<R>::type&&, otherwise as a synonym for V.

[2012, Portland: Move to Tentatively Ready]

AJM wonders if the implied trait might be useful elsewhere, and worth adding to type traits as a transformation type trait.

Suspicion that the Range SG might find such a trait useful, but wait until there is clear additional use of such a trait before standardizing.

Minor wording tweak to use add_rvalue_reference rather than manually adding the &&, then move to Tentatively Ready.

[2013-01-09 Howard Hinnant comments]

I believe the P/R for LWG 2106 is incorrect (item 3). The way it currently reads, move_iterator<I>::reference is always an lvalue reference. I.e. if R is an lvalue reference type, then reference becomes add_rvalue_reference<R>::type which is just R. And if R is not a reference type, then reference becomes R (which is also just R ;-)).

I believe the correct wording is what was there previously:

-?- Let R be iterator_traits<Iterator>::reference. If is_reference<R>::value is true, the template instantiation move_iterator<Iterator> shall define the nested type named reference as a synonym for remove_reference<R>::type&&, otherwise as a synonym for R.

Additionally Marc Glisse points out that move_iterator<I>::operator*() should return static_cast<reference>(*current), not std::move(*current).

Previous resolution:

This wording is relative to the FDIS.

1. Change 24.5.4 [move.iterators] p1 as indicated:

   Class template move_iterator is an iterator adaptor with the same behavior as the underlying iterator except that its dereference operator implicitly converts the value returned by the underlying iterator's dereference operator to an rvalue reference. Some generic algorithms can be called with move iterators to replace copying with moving.

2. Change 24.5.4.2 [move.iterator], class template move_iterator synopsis, as indicated:

   namespace std {
     template <class Iterator>
     class move_iterator {
     public:
       typedef Iterator iterator_type;
       typedef typename iterator_traits<Iterator>::difference_type difference_type;
       typedef Iterator pointer;
       typedef typename iterator_traits<Iterator>::value_type value_type;
       typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
       typedef value_type&&see below reference;
       […]
     };
   }
   

3. Immediately following the class template move_iterator synopsis in 24.5.4.2 [move.iterator] insert a new paragraph as indicated:

   -?- Let R be iterator_traits<Iterator>::reference. If is_reference<R>::value is true, the template instantiation move_iterator<Iterator> shall define the nested type named reference as a synonym for add_rvalue_reference<R>::type, otherwise as a synonym for R.

[2014-05-19, Daniel comments]

The term instantiation has been changed to specialization in the newly added paragraph as suggested by STL and much preferred by myself.

[2014-05-19 Library reflector vote]

The issue has been identified as Tentatively Ready based on five votes in favour.

Proposed resolution:

This wording is relative to N3936.

1. Change 24.5.4 [move.iterators] p1 as indicated:

   Class template move_iterator is an iterator adaptor with the same behavior as the underlying iterator except that its indirection operator implicitly converts the value returned by the underlying iterator's indirection operator to an rvalue reference. Some generic algorithms can be called with move iterators to replace copying with moving.

2. Change 24.5.4.2 [move.iterator], class template move_iterator synopsis, as indicated:

   namespace std {
     template <class Iterator>
     class move_iterator {
     public:
       typedef Iterator iterator_type;
       typedef typename iterator_traits<Iterator>::difference_type difference_type;
       typedef Iterator pointer;
       typedef typename iterator_traits<Iterator>::value_type value_type;
       typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
       typedef value_type&&see below reference;
       […]
     };
   }
   

3. Immediately following the class template move_iterator synopsis in 24.5.4.2 [move.iterator] insert a new paragraph as indicated:

   -?- Let R be iterator_traits<Iterator>::reference. If is_reference<R>::value is true, the template specialization move_iterator<Iterator> shall define the nested type named reference as a synonym for remove_reference<R>::type&&, otherwise as a synonym for R.

4. Edit [move.iter.op.star] p1 as indicated:

   reference operator*() const;
   

   -1- Returns: std::movestatic_cast<reference>(*current).