Where are iterators for rvalue containers?

[Gene Bushuyev]

I was looking at the C++11 standard docs and didn't see iterators for
rvalue containers. For example, std::vector has only these begin()
member functions:

iterator begin();
const_iterator begin() const;

Where is "iterator begin() &&;" ?

Say, I want to construct my container by moving from a vector,

MyContainer::MyContainer(vector<Object>&& v)
{
reserve(v.size());
uninitialized_copy(move(v).begin(), move(v).end(), data);
size = v.size();
}

But that would copy instead of moving, because containers have no
rvalue iterators. Am I missing something or the standard missed them?


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Daniel Krügler]

On 2012-03-02 11:41, Gene Bushuyev wrote:
> I was looking at the C++11 standard docs and didn't see iterators for
> rvalue containers.

There exist a general adapter for any forward iterator to a "moving
iterator", namely std::move_iterator.

> For example, std::vector has only these begin()
> member functions:
>
> iterator begin();
> const_iterator begin() const;
>
> Where is "iterator begin()&&;" ?

It does not exist, for good reasons:

1) You cannot overload ref-qualified and non-ref-qualified member
functions, so simply adding begin() &&; would make instantiating vector
for these functions ill-formed.

2) They are not needed, because you can call a non-ref-qualified from an
rvalue.

3) It would not help solving your problem to provide begin()&& returning
an iterator, because the root of your problem is that the iterator's
indirection operator returns an lvalue, but you need one with an rvalue.

> Say, I want to construct my container by moving from a vector,
>
> MyContainer::MyContainer(vector<Object>&& v)
> {
> reserve(v.size());
> uninitialized_copy(move(v).begin(), move(v).end(), data);
> size = v.size();
> }
>
> But that would copy instead of moving, because containers have no
> rvalue iterators. Am I missing something or the standard missed them?

The standard did not miss to add them. It would be possible to follow
your suggestion with the cost of

a) replacing all container begin/end pairs by a double-pair each one
&-ref-qualified and &&-ref-qualified

b) doubling the number of iterators with in each container:
&-ref-qualified begin/end functions return the normal one,
&&-ref-qualified returning a moving iterator instead.

Instead the standard chose a more economic and useful feature:
std::move_iterator. Just replace your code above by

MyContainer::MyContainer(vector<Object>&& v)
{
reserve(v.size());

uninitialized_copy(std::make_move_iterator(v.begin()),
std::make_move_iterator(v.end()), data);
size = v.size();
}

HTH & Greetings from Bremen,

Daniel Krügler

[Dave Abrahams]

on Fri Mar 02 2012, Gene Bushuyev <publicfilter-AT-gbresearch.com> wrote:

> I was looking at the C++11 standard docs and didn't see iterators for
> rvalue containers. For example, std::vector has only these begin()
> member functions:
>
> iterator begin();
> const_iterator begin() const;
>
> Where is "iterator begin() &&;" ?
>
> Say, I want to construct my container by moving from a vector,
>
> MyContainer::MyContainer(vector<Object>&& v)
> {
> reserve(v.size());
> uninitialized_copy(move(v).begin(), move(v).end(), data);
> size = v.size();
> }
>
> But that would copy instead of moving, because containers have no
> rvalue iterators. Am I missing something or the standard missed them?

I don't think you really want implicit move iterators for container
rvalues. Move iterators only work for single-read traversals. Replace
with some algorithm that makes multiple passes over the input data and
you could have a disaster on your hands.

Just use move_iterator when you're sure it's safe.

Cheers,

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

[Gene Bushuyev]

On Mar 2, 1:42 pm, Daniel Krügler <daniel.krueg...@googlemail.com>
wrote:

> On 2012-03-02 11:41, Gene Bushuyev wrote:
>
> > I was looking at the C++11 standard docs and didn't see iterators for
> > rvalue containers.

...

> The standard did not miss to add them. It would be possible to follow
> your suggestion with the cost of
>
> a) replacing all container begin/end pairs by a double-pair each one
> &-ref-qualified and &&-ref-qualified
>
> b) doubling the number of iterators with in each container:
> &-ref-qualified begin/end functions return the normal one,
> &&-ref-qualified returning a moving iterator instead.
>
> Instead the standard chose a more economic and useful feature:
> std::move_iterator. Just replace your code above by
>
> MyContainer::MyContainer(vector<Object>&& v)
> {
> reserve(v.size());
> uninitialized_copy(std::make_move_iterator(v.begin()),
> std::make_move_iterator(v.end()), data);
> size = v.size();
>
> }

Thank you for pointing move_iterator template to me, but it doesn't
look like a better solution. I would rather see all containers having
defined all functions:

using iterator = <implementation_defined>
using const_iterator = <implementation_defined>
using move_iterator = <implementation_defined>

iterator begin() & ;
const_iterator begin() const &;
move_iterator begin() &&;

Because, it might be unknown, whether a container comes as an lvalue
or rvalue, and thus one need a duck-typing way of addressing it, for
example:

template<class V>
auto unique(V&& v) -> set<typename
remove_reference<V>::type::value_type>
{
return set<typename remove_reference<V>::type::value_type>
(forward<V>(v).begin(), forward<V>(v).end());
}

The same way it would have been better if std::begin and std::end
templates were using perfect forwarding, instead of const and non-
const lvalue versions.

[Gene Bushuyev]

On Mar 2, 2:01 pm, Dave Abrahams <d...@boostpro.com> wrote:
> on Fri Mar 02 2012, Gene Bushuyev <publicfilter-AT-gbresearch.com> wrote:
> > I was looking at the C++11 standard docs and didn't see iterators for
> > rvalue containers. For example, std::vector has only these begin()
> > member functions:
>
> > iterator begin();
> > const_iterator begin() const;
>
> > Where is "iterator begin() &&;" ?
>
> > Say, I want to construct my container by moving from a vector,
>
> > MyContainer::MyContainer(vector<Object>&& v)
> > {
> > reserve(v.size());
> > uninitialized_copy(move(v).begin(), move(v).end(), data);
> > size = v.size();
> > }
>
> > But that would copy instead of moving, because containers have no
> > rvalue iterators. Am I missing something or the standard missed them?
>
> I don't think you really want implicit move iterators for container
> rvalues. Move iterators only work for single-read traversals. Replace
> with some algorithm that makes multiple passes over the input data and
> you could have a disaster on your hands.
>

Yes, I would like move iterators for rvalue containers, because the
perfect forwarding would work. And if algorithms makes multiple passes
it shouldn't take container by r-value reference, or at least know
when to move.


--

[Daniel Krügler]

Am 14.03.2012 22:31, schrieb Gene Bushuyev:
> On Mar 2, 1:42 pm, Daniel Krügler<daniel.krueg...@googlemail.com>
> wrote:
>> On 2012-03-02 11:41, Gene Bushuyev wrote:
>>
>>> I was looking at the C++11 standard docs and didn't see iterators for
>>> rvalue containers.
> ...
>> The standard did not miss to add them. It would be possible to follow
>> your suggestion with the cost of
>>
>> a) replacing all container begin/end pairs by a double-pair each one
>> &-ref-qualified and&&-ref-qualified
>>
>> b) doubling the number of iterators with in each container:
>> &-ref-qualified begin/end functions return the normal one,
>> &&-ref-qualified returning a moving iterator instead.
>>
>> Instead the standard chose a more economic and useful feature:
>> std::move_iterator. Just replace your code above by
>>
>> MyContainer::MyContainer(vector<Object>&& v)
>> {
>> reserve(v.size());
>> uninitialized_copy(std::make_move_iterator(v.begin()),
>> std::make_move_iterator(v.end()), data);
>> size = v.size();
>>
>> }
>
> Thank you for pointing move_iterator template to me, but it doesn't
> look like a better solution.

That depends on the weights used for the measure. make_move_iterator
solves the problem and *not* adding all these overloads plus one further
iterator type is much easier to learn or to teach. It is also much
easier to specifier. I consider all these arguments as relevant.

> I would rather see all containers having
> defined all functions:
>
> using iterator =<implementation_defined>
> using const_iterator =<implementation_defined>
> using move_iterator =<implementation_defined>
>
> iterator begin()& ;
> const_iterator begin() const&;
> move_iterator begin()&&;

As I said before, this would have considerably increased the number of
all iterator-returning functions and it would not make C++03 containers
move-aware via the iterator. Further, the story has not yet ended:
(r)(c)begin()/(r)(c)end() are not the only iterator-returning functions,
just look for all remaining iterator-returning functions in the string
clause or the container clause. In addition, any user-code that wants to
create a C++11 container has to create all the boiler-code to satisfy
the requirements. IMO two instead of three function for each such
iterator function is more than enough!

Please refer to some real arguments, because from what you write so far
I really cannot deduce the overall advantage of such a change.

> Because, it might be unknown, whether a container comes as an lvalue
> or rvalue, and thus one need a duck-typing way of addressing it, for
> example:
>
> template<class V>
> auto unique(V&& v) -> set<typename
> remove_reference<V>::type::value_type>
> {
> return set<typename remove_reference<V>::type::value_type>
> (forward<V>(v).begin(), forward<V>(v).end());
> }

If this pattern occurs often for you, it could be useful to introduce
once and for all a helper function that maps rvalue containers to a
moving iterator range, else a normal iterator range. This is easy to
realize, e.g.

#include <type_traits>
#include <iterator>
#include <utility>

template<class C>
inline auto make_iterator_range(C&& c) ->
typename std::enable_if<std::is_lvalue_reference<C>::value,
std::pair<decltype(c.begin()), decltype(c.end())>
>::type
{
return {c.begin(), c.end()};
}

template<class C>
inline auto make_iterator_range(C&& c) ->
typename std::enable_if<!std::is_lvalue_reference<C>::value,
std::pair<
decltype(std::make_move_iterator(c.begin())),
decltype(std::make_move_iterator(c.end()))
>
>::type
{
return {std::make_move_iterator(c.begin()),
std::make_move_iterator(c.end())};
}

#include <vector>

int main() {
using C = std::vector<int>;
C c1{};
auto r1 = make_iterator_range(c1);
static_assert(std::is_same<decltype(r1), std::pair<C::iterator,
C::iterator>>::value, "");
const C c2{};
auto r2 = make_iterator_range(c2);
static_assert(std::is_same<decltype(r2),
std::pair<C::const_iterator, C::const_iterator>>::value, "");
auto r3 = make_iterator_range(C{});
static_assert(std::is_same<decltype(r3),
std::pair<std::move_iterator<C::iterator>,
std::move_iterator<C::iterator>>>::value, "");
}

This has no intrusive effects on the container specification.

I would like to point out that the last example is a typical mis-usage,
because the life-time of the C temporary has ended after the
construction of r3, but I added it anyway just to demonstrate that the
expected return type corresponds to the obtained one.

Now you can easily implement your suggested function like so:

template<class V>
auto unique(V&& v) -> set<typename
remove_reference<V>::type::value_type>
{

auto r = make_iterator_range(forward<V>(v));

return set<typename remove_reference<V>::type::value_type>

(r.first, r.second);

}

> The same way it would have been better if std::begin and std::end
> templates were using perfect forwarding, instead of const and non-
> const lvalue versions.

There is no fundamental reason why the standard could not be extended in
the future to realize that. You could write-up a proposal for this, for
example.

HTH & Greetings from Bremen,

Daniel Krügler

[Dave Abrahams]

on Wed Mar 14 2012, Gene Bushuyev <publicfilter-AT-gbresearch.com> wrote:

> On Mar 2, 2:01 pm, Dave Abrahams <d...@boostpro.com> wrote:
>> on Fri Mar 02 2012, Gene Bushuyev <publicfilter-AT-gbresearch.com> wrote:
>> > I was looking at the C++11 standard docs and didn't see iterators for
>> > rvalue containers. For example, std::vector has only these begin()
>> > member functions:
>>
>
>> > iterator begin();
>> > const_iterator begin() const;
>>
>> > Where is "iterator begin() &&;" ?
>>
>> > Say, I want to construct my container by moving from a vector,
>>
>> > MyContainer::MyContainer(vector<Object>&& v)
>> > {
>> > reserve(v.size());
>> > uninitialized_copy(move(v).begin(), move(v).end(), data);
>> > size = v.size();
>> > }
>>
>> > But that would copy instead of moving, because containers have no
>> > rvalue iterators. Am I missing something or the standard missed them?
>>
>> I don't think you really want implicit move iterators for container
>> rvalues. Move iterators only work for single-read traversals. Replace
>> with some algorithm that makes multiple passes over the input data and
>> you could have a disaster on your hands.
>>
>
> Yes, I would like move iterators for rvalue containers,

Trust me, you really don't want that :-)

> because the perfect forwarding would work.

The problem is that too many other things would "work" (until runtime)
as well.

> And if algorithms makes multiple passes it shouldn't take container by
> r-value reference, or at least know when to move.

The standard library algorithms don't operate on containers; they
operate on iterators. You'd have to, /at least/, make sure the "rvalue
iterators" were classified no more refined-ly than InputIterator to
avoid them being used in multiple-read situations. And even that isn't
right; you can read an input iterator multiple times. We really don't
have a proper concept for read-once, random-access iterators like
move_iterator, and until we do, you're better off being really explicit
about it when you want one. move_iterator is best thought of as a
low-level convenience adaptor for implementing various moving algorithms
in terms of their non-moving cousins.

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com