Re: [boost] move semantics

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2002-02-05 21:44:38

On Tuesday, February 5, 2002, at 07:09  PM, Howard Hinnant wrote:

> They are not close to optimal at all if T is a light weight class with 
> move semantics (like auto_ptr).  In this case your alternatives are 2 
> and 3 times slower.

On Tuesday, February 5, 2002, at 08:43  PM, Rainer Deyke wrote:

> No: the time needed to move 'x' is likely to be dominated by the time
> needed to make room for 'x'.

"Likely" is subject to debate.  We were discussing this method:

vector::insert(iterator position, size_type n, const value_type& x);

The minimum time needed to make room for x is O(end()-position).  The 
minimum time needed to move x is O(n).  It all depends on the input 
parameters to insert.

But very well.  Let's review:

> There are three ways of dealing with this specific problem:
>
> 1. If any exceptions are thrown by the copy operation, catch it, move
> all elements back into their original position, and rethrow.

Still has code size larger than necessary, and complexity that is more 
than necessary.  Without going into all the gory details, section E.3.2 
of Stroustrup's "The C++ Programming Language" 
(http://www.research.att.com/~bs/3rd_safe0.html) says it much better 
than I could ever hope to.

> 2. Copy 'x' first, then move the elements, then move the copy of 'x'
> into place.

Still requires an auxillary buffer to copy x into first.  The "make 
room" O(end()-position) part is as optimal as possible.  The O(n) part 
is twice as expensive as the minimum.

The auxillary buffer blows this option out of the water.  If the copy 
constructor and assignment operator of x are no-throw, and if the 
capacity of the vector can handle the insert (as is the assumption for 
this particular discussion) then insert does not throw.  So obtaining 
the auxillary buffer becomes problematic.

> 3. push_back 'x' and use 'std::swap' to fix the order of the vector
> elements.  This requires no move operation.

There is an O(n) expense to copy the x into the vector.  This is as 
optimal as possible.  The next step is an inplace rotate which the 
standard says will take at most end()-position + n swaps (25.2.10/4).  
Each swap consumes 3 assignments.

Compare these alternatives to "option 4":  Move elements out of the way 
leaving constructed elements in their path.  Copy assign the x into 
place:

O(end()-position) move out of the way.  O(n) copy assign into place.

-Howard