Boost logo

Boost :

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"
( 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

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


Boost list run by bdawes at, gregod at, cpdaniel at, john at