Fast swapping of STL containers

[ittium]

Group,
I have two containers (same type). Element are getting inserted in the
first container continuously. while second container is empty. At some
point of processing I want to swap the container so that first
container is now empty. What is the efficient container for this
operation. Swapping should involve, adjusting few pointers/parameter,
no element by element processing should take place. I will highly
appreciate a sample code.
thanks
Ittium

 

[Victor Bazarov]

I have two containers (same type). Element are getting inserted in the
first container continuously. while second container is empty. At some
point of processing I want to swap the container so that first
container is now empty. What is the efficient container for this
operation.

All containers are efficient for this operation.

Swapping should involve, adjusting few pointers/parameter,
no element by element processing should take place. I will highly
appreciate a sample code.

Homework again? Read about 'std::swap'.

V

 

[gwowen]

Homework again?  Read about 'std::swap'.

.... and stay away from std::tr1::array<>

 

[Rune Allnor]

... and stay away from std::tr1::array<>

Why? For this particular task or in general?

Rune

 

[ittium]

Thanks guys for your valuable time. I was actually thinking of writing
my own routines to solve this problem.

I checked STL map documentation it actually contain swap routine. I
did some googling, I could not find any information regarding
performance of such an operation.

From the discussion, it seems swap of standard container should be
fairly fast operation.
A standard link regarding this will help me convince other designers
in my group, to take this approach.
thanks
Ittium

 

[Ian Collins]

Thanks guys for your valuable time. I was actually thinking of writing
my own routines to solve this problem.

I checked STL map documentation it actually contain swap routine. I
did some googling, I could not find any information regarding
performance of such an operation.

From the discussion, it seems swap of standard container should be
fairly fast operation.
A standard link regarding this will help me convince other designers
in my group, to take this approach.

Well come on, it's the library author's job to write efficient code. If
they didn't, users would soon complain. They have implementation
specific short cuts available to them that we users do not.

 

[Werner]

Group,
I have two containers (same type). Element are getting inserted in the
first container continuously. while second container is empty. At some
point of processing I want to swap the container so that first
container is now empty.

As other posters already said, all containers are sufficient.
Container
choices are made on other criteria, like for instance:

- Where is the element inserted.
- Does the data get added in sorted order.
- Does the data need to be contiguous.
- etc.

What is the efficient container for this
operation.  Swapping should involve, adjusting few pointers/parameter,
no element by element processing should take place.

Element processing never takes place during container swap
(to my knowledge).

I will highly appreciate a sample code.

It can be noted when one uses vectors, you may want to
reserve enough space in the destination vector so that no
reallocation is necessary after the swap when writes
are performed on the source vector (now containing
internals of the destination vector).

Kind regards,

Werner

 

[ittium]

Well come on, it's the library author's job to write efficient code.  If
they didn't, users would soon complain.  They have implementation
specific short cuts available to them that we users do not.

For most of the cases, You are right. When a operation is likely to
take place large number of times per second than exact processing
complexity becomes very important.

 

[Ian Collins]

On 06/24/11 09:58 PM, ittium wrote:

Please don't snip attributions!

For most of the cases, You are right. When a operation is likely to
take place large number of times per second than exact processing
complexity becomes very important.

What difference does the number of calls make? The operation is either
efficient, or it isn't.

 

[gwowen]

Why? For this particular task or in general?

Because you can't guarantee an O(1) std::swap.

With other containers the stored objects themselves are on the free-
store, so you can (usually) swap by exchanging a few pointers and misc
variables. With tr1::array the stored objects themselves are on the
stack, and so the objects themselves have to be moved (because there's
no guarantee that the arrays have the same lifetime).

cf: The remark in http://msdn.microsoft.com/en-us/library/bb981972.aspx

 

[ittium]

What difference does the number of calls make?  The operation is either
efficient, or it isn't.

thanks Ian for quick response.
If operation is called limited number of times (e.g. only during
initialization of a process) you can live with it. But if it is called
large number of times and fast response time is required, complexity
is an important criteria before using a routine.

 

[ittium]

Because you can't guarantee an O(1) std::swap.

For other containers can you guarantee O(1) swap.

 

[Ian Collins]

On 06/24/11 10:29 PM, ittium wrote:

Please stop snipping attributions, it's rude!

thanks Ian for quick response.
If operation is called limited number of times (e.g. only during
initialization of a process) you can live with it. But if it is called
large number of times and fast response time is required, complexity
is an important criteria before using a routine.

How is the library designer to no how often a routine will be called?
They will strive to get the best performance and that will be much
better than a user will ever get!

 

[gwowen]

For other containers can you guarantee O(1) swap.

Amortized O(1), yes. See http://www.sgi.com/tech/stl/Container.html
(footnote [9] in particular).

 

[Kai-Uwe Bux]

On 06/24/11 10:29 PM, ittium wrote:

Please stop snipping attributions, it's rude!


How is the library designer to no how often a routine will be called?
They will strive to get the best performance and that will be much
better than a user will ever get!

Hm, that sounds too pessimistic and too optimistic at once. I remember a
discussion, which I think comes up ever so often on mailing lists for open
source implementations of the standard library: how to implement strstr() or
std::search(). There are many different possible implementations with
different asymptotic complexities. Moreover, which algorithm performs best
is very sensitive to the characteristics of the needle and haystack pairs
that are processed. It is somewhat likely that the library implementation
uses an implementation that is (a) asymptotically poor but (b) heavily
optimized. The rationale was, as I remember, that some measurements on the
use in open software projects exists which indicate that most of the time
the needle is rather short so that asymptotics will not enter the picture at
all and any preprocessing, as required by the asymptotically better
algorithms, will not pay off.

Lessons: (a) sometimes and with some effort, the library designer can not
only measure how many times the routine will be called but also get an idea
of the typical arguments; (b) if your particular use case differs from the
case for which the library was optimized, you can sometimes rather easily
beat the library implementation.


Best,

Kai-Uwe Bux

 

[Kai-Uwe Bux]

Thanks guys for your valuable time. I was actually thinking of writing
my own routines to solve this problem.

I checked STL map documentation it actually contain swap routine. I
did some googling, I could not find any information regarding
performance of such an operation.

From the discussion, it seems swap of standard container should be
fairly fast operation.
A standard link regarding this will help me convince other designers
in my group, to take this approach.

Table 65 in the C++03 standard, last line: a.swap(b) is marked with (Note A)
in the complexity column. That means:

Those entries marked ``(Note A)'' should have constant complexity.

BTW: a conforming implementation of the swap() method would have to be
rather contrived to take more than constant time; after there is clause
[23.1/10] which requires:

a) the swap() method must not invalidate pointers, references, or iterators
to elements of the containers being swapped.

b) the swap() method must not throw unless the copy constructor or
assignment operator of the _comparison_ objects might throw. That is, the
copy constructor or assignment operator of the container elements might
throw, but swap() is supposed to be unaffected by that.


Best,

Kai-Uwe Bux

 

[Ian Collins]

Lessons: (a) sometimes and with some effort, the library designer can not
only measure how many times the routine will be called but also get an idea
of the typical arguments; (b) if your particular use case differs from the
case for which the library was optimized, you can sometimes rather easily
beat the library implementation.

But not in the cast of an operation such as a container swap which can
typically be implemented by exchanging some pointers to the internal
data structure and a few other internal variables. The user would have
to perform a copy and erase.

 

[Werner]

Element processing never takes place during container swap
(to my knowledge).

Pardon me. I did not consider tr1::array and
unordered_*. It seems obvious that array content
swapping is not possible without swapping each
element (swap_ranges).

AFAICS all other container swaps have constant complexity.
This is supported by the standard (23.1.5: "Those entries
marked ("Note A") should have constant complexity".
I'd imagine that the swap member functions for unordered_*
would be constant (as for the other containers).

Kind regards,

Werner

 

[gwowen]

Amortized O(1), yes. See http://www.sgi.com/tech/stl/Container.html
(footnote [9] in particular).

I don't see where this mentions *amortized* O(1).

Did you consider searching for the word "amortized"?

Complexity guarantees: {elision}
swap() is amortized constant time. [9]

There's nothing to
amortize; swap for containers other than array is O(1).

You're quite correct. The standard just says "should have constant
complexity" - but the SGI docs do say "guaranteed amortized constant".

 

[hanukas]

Group,
I have two containers (same type). Element are getting inserted in the
first container continuously. while second container is empty. At some
point of processing I want to swap the container so that first
container is now empty. What is the efficient container for this
operation.  Swapping should involve, adjusting few pointers/parameter,
no element by element processing should take place. I will highly
appreciate a sample code.
thanks
Ittium

std::foo<bar> *a = ...;
std::foo<bar> *b = ...;

You don't have to swap the contents, you can swap pointers to the
containers:

std::swap(a, b); // O(1)

Regarding swapping actual containers or references to containers, you
might get lucky and the swap is optimized for the containers, in which
case it could be super light-weight (just swap some member data of the
container objects re-using the internal arrays and linked lists, trees
and what not).

The pointer-to-any-container swap is the safest bet (performance
wise), I guess, but I wouldn't necessarily use it myself if I know
more about the application. It might not be relevant at all, probably
not. When you identify bottleneck that drags the performance down
(rare) you do what you can, before that, not really.