On Mar 15, 7:47 pm, tasjae...@gmail.com wrote:
> On Mar 14, 5:38 pm, "Chris Jefferson" <4zuma...@gmail.com> wrote:
> > In partice there are (I suspect) going to be three possible outcomes
> > from x = std::move(y)
>
> > a) y stays the same
> > b) y becomes the old value of x
> > c) y becomes the "default constructed" value.
>
> In paper N1858 (23.1/5), it specifies that container move assignment
> is constant time.
>
> Outcome b) is the only option that can be done in constant time (by
> calling swap). Option a) implies a linear number of assignments, c)
> implies a linear number of destructions (of the contents of x).

You are right. What I was talking about (and Howard was I think
replying to) is that in general, I suspect most type's move
constructors / assignments will be implemented in one of those three
ways.

Note that option c) is possible when you have a vector of pods, so no
need to run destructors. Would it necessarily be the most sensible
thing to do? Probably not, but it's allowed I think.

If I wanted to be even more warped, I could do option b) and then
randomly change a few values in the vector. Not that sensible but
still allowed.

One reason I wanted to try to pin down exactly what is going on here
is to decide exactly what debugging libraries can and can't do. It
seems to me it would be very sensible for a library to mark a
container as "moved from" and then flag a warning if a user then tries
to access the container which was moved from except to move / assign
something else to it. That wouldn't strictly be an error, but I
suspect in 99.9% of cases it would show up a mistake on the user's
part.


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

In article <1174034940.745881.17150@n59g2000hsh.googlegroups.com>,
 "Chris Jefferson" <4zumanga@gmail.com> wrote:

> One reason I wanted to try to pin down exactly what is going on here
> is to decide exactly what debugging libraries can and can't do. It
> seems to me it would be very sensible for a library to mark a
> container as "moved from" and then flag a warning if a user then tries
> to access the container which was moved from except to move / assign
> something else to it. That wouldn't strictly be an error, but I
> suspect in 99.9% of cases it would show up a mistake on the user's
> part.

<nod> Very interesting. :-)

-Howard

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Howard Hinnant wrote:
>
> d) can only assign or destruct y
>
> I don't think we need to do that for vector, and if somebody does it for
> their own type then...
>
>> However, I don't think it's the standard's job to specify that
>> behaviour.
>
> exactly. :-)

I think, if you both try to consider requirements in essence of moveable
data type (you can  start from http://grizlyk1.narod.ru/cpp_new#11 ), you
will see, that there is concrete standard's job to control that behaviour.

But unfortunatelly, the problem is destroing sweet idea to create moveable
data type from nothing (as alias of RVO of copyable), so all unsuitable
questions treated as "non-asked", "non-existing", "non-coherent",
"metaphysical" and "heretical" in order to save clear Idea.


--
Maksim A. Polyanin
http://grizlyk1.narod.ru/cpp_new




---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Mar 15, 11:19 pm, Howard Hinnant <howard.hinn...@gmail.com> wrote:
>
> Personally I'd rather have a guaranteed O(1) move assignment for vector
> (which amounts to a swap, as you correctly point out).  Rationale:
>
> vector<A> v1(1000);
> vector<A> v2(1000);
> vector<A> v3(1000);
> .
> v2 = move(v1);
> v1 = v3;
>
> If move assignment for vector is a swap, then the two statements above
> never go to the heap.  The first is O(1) and the second is O(1000) but
> doesn't need allocation.
>
> If move assignment is equivalent to (dump resources, steal resources) as
> opposed to (swap resources), then both statements above go to the heap:
> the first deallocates and the second allocates.
>

It's an interesting perspective I hadn't considered. I was imagining
move assignment would be implemented as a clear then a swap. Your
example with vector would not require any additional allocations
(assuming the capacity is transfered in the swap). It does result in
destructions and constructions rather than just assignments.

Implementing node-based containers' move assignment as clear then
swap, however, would indeed require the additional allocations.

OTOH, I can't think of any cases where the code would *automatically*
benefit from a capacity-maintaining operator. The code is explicitly
using std::move; wouldn't an explicit swap be clearer?

James

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Mar 15, 11:19 pm, Howard Hinnant <howard.hinn...@gmail.com> wrote:
>
> For some types, swap is the wrong implementation for move assignment.
> For example unique_ptr shouldn't use swap for move assign.
>

Do you mean this implementation would do the wrong thing or just that
there's no advantage using swap?

If assignment using swap is wrong for unique_ptr, I suspect it is also
wrong for vector<unique_ptr>.

I don't currently consider it wrong, necessarily. I'd just be much
more comfortable with guaranteed timely destruction; it seems far more
intuitive.


James

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

In article <1174137070.190697.258940@l75g2000hse.googlegroups.com>,
 tasjaevan@gmail.com wrote:

> If assignment using swap is wrong for unique_ptr, I suspect it is also
> wrong for vector<unique_ptr>.

That's an interesting point.  I'll have to give that one more thought.
Perhaps (clear(), swap()) would be more appropriate?  This does the O(N)
destruction, but retains capacity.  Though see below...

> On Mar 15, 11:19 pm, Howard Hinnant <howard.hinn...@gmail.com> wrote:
> >
> > Personally I'd rather have a guaranteed O(1) move assignment for vector
> > (which amounts to a swap, as you correctly point out).  Rationale:
> >
> > vector<A> v1(1000);
> > vector<A> v2(1000);
> > vector<A> v3(1000);
> > .
> > v2 = move(v1);
> > v1 = v3;
> >
> > If move assignment for vector is a swap, then the two statements above
> > never go to the heap.  The first is O(1) and the second is O(1000) but
> > doesn't need allocation.
> >
> > If move assignment is equivalent to (dump resources, steal resources) as
> > opposed to (swap resources), then both statements above go to the heap:
> > the first deallocates and the second allocates.
> >
>
> It's an interesting perspective I hadn't considered. I was imagining
> move assignment would be implemented as a clear then a swap. Your
> example with vector would not require any additional allocations
> (assuming the capacity is transfered in the swap). It does result in
> destructions and constructions rather than just assignments.
>
> Implementing node-based containers' move assignment as clear then
> swap, however, would indeed require the additional allocations.
>
> OTOH, I can't think of any cases where the code would *automatically*
> benefit from a capacity-maintaining operator. The code is explicitly
> using std::move; wouldn't an explicit swap be clearer?

I started thinking about real world use cases which include:

deque/vector::insert
deque/vector::erase

And just about all of the sequence modifying algorithms in <algorithm>.

For deque/vector::insert the procedure will begin with a move
construction (assuming not inserting on the end) which leaves the moved
from element with zero capacity (assuming the value_type of this
container is vector).  And from then on you are move assigning to a
zero-capacity vector.  So it wouldn't make any difference whether move
assign is a swap, or a (dump resources, steal resources).

deque/vector::erase is just like insert, only opposite.  You start with
move assigning (source and target have capacity), but you end up
destructing one value_type.  If the move assign is a swap, then all move
assigns are O(1), but you have one heap access and O(N) destruction at
the end.  If move assign is a steal/destruct then the first move assign
during the erase is O(N) and deallocates, but from then on the move
assigns are O(1) since the target of the move is always a 0 capacity
element.  And when the final element is destructed, it is a 0 capacity
element.  So again the cost looks identical either way.

Sequence modifying algorithms will either use swap (no issue) or they
move construct to a local temporary, move assign one sequence element to
another, and then move assign that local back into the sequence.  Again
assuming the value_type is vector, there are never any heap accesses no
matter how move assign is defined.  All move assigns are always working
with a zero-capacity target.

So perhaps my example is an outlier.  I will work on coming up with
further motivation for my example, or abandon it, and consider (clear(),
swap()).

Thanks,
Howard

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Mar 13, 5:15 pm, howard.hinn...@gmail.com (Howard Hinnant) wrote:
> In article <1173789845.345163.318...@64g2000cwx.googlegroups.com>,
>  "Chris Jefferson" <4zuma...@gmail.com> wrote:
>
> > Hello, I've been reading N1771 (rvalue references) again, and have a
> > question.
>
> > Consider the following code snippet:
>
> > vector<int> x, y;
> > x = std::move(y);
>
> > After this code snippet, what can I do with y? Does y have to be a
> > valid vector?
>
> > I assume as no condition is placed on y, that y is intended to be a
> > valid vector but it's exact value is unspecified?
>
> Yes, that's a fair summary.  You should be able to inspect y, assign y
> another value, and destruct y.  But you shouldn't depend upon it having
> a specific value after the move and prior to you assigning it another
> value.

This sounds sensible. I did have a go at seeing if I could get greater
performance by assuming that y was left in a state when the only valid
operations on it were assign or destruct rather than just "an
unspecified but valid vector" but decided any possible gains were
swamped by the added complexity.

In partice there are (I suspect) going to be three possible outcomes
from x = std::move(y)

a) y stays the same
b) y becomes the old value of x
c) y becomes the "default constructed" value.

However, I don't think it's the standard's job to specify that
behaviour.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

In article <1173882506.367812.257420@l77g2000hsb.googlegroups.com>,
 "Chris Jefferson" <4zumanga@gmail.com> wrote:

> On Mar 13, 5:15 pm, howard.hinn...@gmail.com (Howard Hinnant) wrote:
> > In article <1173789845.345163.318...@64g2000cwx.googlegroups.com>,
> >  "Chris Jefferson" <4zuma...@gmail.com> wrote:
> >
> > > Hello, I've been reading N1771 (rvalue references) again, and have a
> > > question.
> >
> > > Consider the following code snippet:
> >
> > > vector<int> x, y;
> > > x = std::move(y);
> >
> > > After this code snippet, what can I do with y? Does y have to be a
> > > valid vector?
> >
> > > I assume as no condition is placed on y, that y is intended to be a
> > > valid vector but it's exact value is unspecified?
> >
> > Yes, that's a fair summary.  You should be able to inspect y, assign y
> > another value, and destruct y.  But you shouldn't depend upon it having
> > a specific value after the move and prior to you assigning it another
> > value.
>
> This sounds sensible. I did have a go at seeing if I could get greater
> performance by assuming that y was left in a state when the only valid
> operations on it were assign or destruct rather than just "an
> unspecified but valid vector" but decided any possible gains were
> swamped by the added complexity.
>
> In partice there are (I suspect) going to be three possible outcomes
> from x = std::move(y)
>
> a) y stays the same
> b) y becomes the old value of x
> c) y becomes the "default constructed" value.

<nod> Agreed, and nicely summarized.  There may be some type someone
makes where it makes sense to do:

d) can only assign or destruct y

I don't think we need to do that for vector, and if somebody does it for
their own type then...

> However, I don't think it's the standard's job to specify that
> behaviour.

exactly. :-)

-Howard

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Mar 14, 5:38 pm, "Chris Jefferson" <4zuma...@gmail.com> wrote:
>
> In partice there are (I suspect) going to be three possible outcomes
> from x = std::move(y)
>
> a) y stays the same
> b) y becomes the old value of x
> c) y becomes the "default constructed" value.
>

In paper N1858 (23.1/5), it specifies that container move assignment
is constant time.

Outcome b) is the only option that can be done in constant time (by
calling swap). Option a) implies a linear number of assignments, c)
implies a linear number of destructions (of the contents of x).

I don't think that was the intention, though, since Howard agrees with
your analysis.

My suggestion is that the complexity of move assignment, for
expression a=rv, should be stated as O(a.size()).

Perhaps it should also specify that the destructors of a's objects are
called.

James


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On 2007-03-15 06:47:55 -0700, tasjaevan@gmail.com said:

>
> On Mar 14, 5:38 pm, "Chris Jefferson" <4zuma...@gmail.com> wrote:
>>
>> In partice there are (I suspect) going to be three possible outcomes
>> from x = std::move(y)
>>
>> a) y stays the same
>> b) y becomes the old value of x
>> c) y becomes the "default constructed" value.
>>
>
> In paper N1858 (23.1/5), it specifies that container move assignment
> is constant time.
>
> Outcome b) is the only option that can be done in constant time (by
> calling swap). Option a) implies a linear number of assignments, c)
> implies a linear number of destructions (of the contents of x).
>
> I don't think that was the intention, though, since Howard agrees with
> your analysis.
>
> My suggestion is that the complexity of move assignment, for
> expression a=rv, should be stated as O(a.size()).

Agreed, as long as that's the worst case complexity, not the best case.

> Perhaps it should also specify that the destructors of a's objects are
> called.

Probably not a good idea, as this would make impossible an O(1) implementation.


--
Clark S. Cox III
clarkcox3@gmail.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

In article <1173982100.847321.61330@e65g2000hsc.googlegroups.com>,
 tasjaevan@gmail.com wrote:

> On Mar 14, 5:38 pm, "Chris Jefferson" <4zuma...@gmail.com> wrote:
> >
> > In partice there are (I suspect) going to be three possible outcomes
> > from x = std::move(y)
> >
> > a) y stays the same
> > b) y becomes the old value of x
> > c) y becomes the "default constructed" value.
> >
>
> In paper N1858 (23.1/5), it specifies that container move assignment
> is constant time.
>
> Outcome b) is the only option that can be done in constant time (by
> calling swap). Option a) implies a linear number of assignments, c)
> implies a linear number of destructions (of the contents of x).
>
> I don't think that was the intention, though, since Howard agrees with
> your analysis.
>
> My suggestion is that the complexity of move assignment, for
> expression a=rv, should be stated as O(a.size()).
>
> Perhaps it should also specify that the destructors of a's objects are
> called.

I'm guilty of trying to keep too much of the rvalue package in my head
and not looking up all the details before writing. :-\

We could do what you suggest for vector.  But would that be superior?

Personally I'd rather have a guaranteed O(1) move assignment for vector
(which amounts to a swap, as you correctly point out).  Rationale:

vector<A> v1(1000);
vector<A> v2(1000);
vector<A> v3(1000);
.
v2 = move(v1);
v1 = v3;

If move assignment for vector is a swap, then the two statements above
never go to the heap.  The first is O(1) and the second is O(1000) but
doesn't need allocation.

If move assignment is equivalent to (dump resources, steal resources) as
opposed to (swap resources), then both statements above go to the heap:
the first deallocates and the second allocates.

For some types, swap is the wrong implementation for move assignment.
For example unique_ptr shouldn't use swap for move assign.  But for
vector I think swap is a very good implementation - good enough to
require in the standard - never throw away capacity until you're
absolutely sure you don't need it anymore. :-)

-Howard

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Hello, I've been reading N1771 (rvalue references) again, and have a
question.

Consider the following code snippet:

vector<int> x, y;
x = std::move(y);

After this code snippet, what can I do with y? Does y have to be a
valid vector?

I assume as no condition is placed on y, that y is intended to be a
valid vector but it's exact value is unspecified?

Chris

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

In article <1173789845.345163.318630@64g2000cwx.googlegroups.com>,
 "Chris Jefferson" <4zumanga@gmail.com> wrote:

> Hello, I've been reading N1771 (rvalue references) again, and have a
> question.
>
> Consider the following code snippet:
>
> vector<int> x, y;
> x = std::move(y);
>
> After this code snippet, what can I do with y? Does y have to be a
> valid vector?
>
> I assume as no condition is placed on y, that y is intended to be a
> valid vector but it's exact value is unspecified?

Yes, that's a fair summary.  You should be able to inspect y, assign y
another value, and destruct y.  But you shouldn't depend upon it having
a specific value after the move and prior to you assigning it another
value.

-Howard

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]