Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #7080 > unrolled thread

Fast swapping of STL containers

Back to article view | Back to comp.lang.c++

Contents

  Fast swapping of STL containers ittium <ittium@gmail.com> - 2011-06-23 06:45 -0700
    Re: Fast swapping of STL containers Victor Bazarov <v.bazarov@comcast.invalid> - 2011-06-23 10:05 -0400
      Re: Fast swapping of STL containers gwowen <gwowen@gmail.com> - 2011-06-23 08:07 -0700
        Re: Fast swapping of STL containers Rune Allnor <allnor@tele.ntnu.no> - 2011-06-23 22:49 -0700
          Re: Fast swapping of STL containers ittium <ittium@gmail.com> - 2011-06-24 02:16 -0700
            Re: Fast swapping of STL containers Ian Collins <ian-news@hotmail.com> - 2011-06-24 21:27 +1200
              Re: Fast swapping of STL containers ittium <ittium@gmail.com> - 2011-06-24 02:58 -0700
                Re: Fast swapping of STL containers Ian Collins <ian-news@hotmail.com> - 2011-06-24 22:09 +1200
                  Re: Fast swapping of STL containers ittium <ittium@gmail.com> - 2011-06-24 03:29 -0700
                    Re: Fast swapping of STL containers Ian Collins <ian-news@hotmail.com> - 2011-06-24 22:44 +1200
                      Re: Fast swapping of STL containers Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-06-24 13:25 +0200
                        Re: Fast swapping of STL containers Ian Collins <ian-news@hotmail.com> - 2011-06-24 23:35 +1200
                  Re: Fast swapping of STL containers Pete Becker <pete@versatilecoding.com> - 2011-06-24 07:34 -0400
            Re: Fast swapping of STL containers Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-06-24 13:34 +0200
          Re: Fast swapping of STL containers gwowen <gwowen@gmail.com> - 2011-06-24 03:26 -0700
            Re: Fast swapping of STL containers ittium <ittium@gmail.com> - 2011-06-24 03:30 -0700
              Re: Fast swapping of STL containers gwowen <gwowen@gmail.com> - 2011-06-24 04:01 -0700
                Re: Fast swapping of STL containers Pete Becker <pete@versatilecoding.com> - 2011-06-24 07:37 -0400
                  Re: Fast swapping of STL containers gwowen <gwowen@gmail.com> - 2011-06-24 06:11 -0700
    Re: Fast swapping of STL containers Werner <werasm@gmail.com> - 2011-06-24 02:29 -0700
      Re: Fast swapping of STL containers Werner <werasm@gmail.com> - 2011-06-24 04:51 -0700
    Re: Fast swapping of STL containers hanukas <jukka@liimatta.org> - 2011-06-29 05:29 -0700
      Re: Fast swapping of STL containers Jorgen Grahn <grahn+nntp@snipabacken.se> - 2011-06-29 15:45 +0000
        Re: Fast swapping of STL containers hanukas <jukka@liimatta.org> - 2011-06-30 23:46 -0700

Page 1 of 2  [1] 2  Next page →

#7080 — Fast swapping of STL containers

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

[toc] | [next] | [standalone]

#7082

On 6/23/2011 9:45 AM, ittium wrote:
> 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
-- 
I do not respond to top-posted replies, please don't ask

[toc] | [prev] | [next] | [standalone]

#7085

On Jun 23, 3:05 pm, Victor Bazarov <v.baza...@comcast.invalid> wrote:

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

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

[toc] | [prev] | [next] | [standalone]

#7093

On Jun 23, 5:07 pm, gwowen <gwo...@gmail.com> wrote:
> On Jun 23, 3:05 pm, Victor Bazarov <v.baza...@comcast.invalid> wrote:
>
> > Homework again?  Read about 'std::swap'.
>
> ... and stay away from std::tr1::array<>

Why? For this particular task or in general?

Rune

[toc] | [prev] | [next] | [standalone]

#7100

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

[toc] | [prev] | [next] | [standalone]

#7101

On 06/24/11 09:16 PM, ittium wrote:
> 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.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#7104

> 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.

[toc] | [prev] | [next] | [standalone]

#7105

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

Please don't snip attributions!

 > On 06/24/11 09:27 PM, Ian Collins wrote:
>
>> 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.

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

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#7110

> 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.

[toc] | [prev] | [next] | [standalone]

#7111

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

Please stop snipping attributions, it's rude!

>> 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.

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!

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#7113

Ian Collins wrote:

> On 06/24/11 10:29 PM, ittium wrote:
> 
> Please stop snipping attributions, it's rude!
> 
>>> 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.
> 
> 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

[toc] | [prev] | [next] | [standalone]

#7116

On 06/24/11 11:25 PM, Kai-Uwe Bux wrote:
> Ian Collins wrote:
>
>> On 06/24/11 10:29 PM, ittium wrote:
>>
>> Please stop snipping attributions, it's rude!
>>
>>>> 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.
>>
>> 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!
>
<snip>
>
> 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.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#7115

On 2011-06-24 06:09:10 -0400, Ian Collins said:

> On 06/24/11 09:58 PM, ittium wrote:
> 
> Please don't snip attributions!
> 
>  > On 06/24/11 09:27 PM, Ian Collins wrote:
>> 
>>> 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.
> 
> What difference does the number of calls make?  The operation is either 
> efficient, or it isn't.

The more it's called, the more likely it is to be a bottleneck. If I 
only call a function once, it doesn't matter whether it takes 1 ms or 2 
ms.

-- 
  Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The 
Standard C++ Library Extensions: a Tutorial and Reference 
(www.petebecker.com/tr1book)

[toc] | [prev] | [next] | [standalone]

#7114

ittium wrote:

> 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

[toc] | [prev] | [next] | [standalone]

#7108

On Jun 24, 6:49 am, Rune Allnor <all...@tele.ntnu.no> wrote:

> 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

[toc] | [prev] | [next] | [standalone]

#7109

On Jun 24, 3:26 pm, gwowen <gwo...@gmail.com> wrote:
> On Jun 24, 6:49 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > Why? For this particular task or in general?
>
> Because you can't guarantee an O(1) std::swap.

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

[toc] | [prev] | [next] | [standalone]

#7112

On Jun 24, 11:30 am, ittium <itt...@gmail.com> wrote:
> On Jun 24, 3:26 pm, gwowen <gwo...@gmail.com> wrote:
>
> > On Jun 24, 6:49 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>
> > > Why? For this particular task or in general?
>
> > Because you can't guarantee an O(1) std::swap.
>
> 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).

[toc] | [prev] | [next] | [standalone]

#7117

On 2011-06-24 07:01:48 -0400, gwowen said:

> On Jun 24, 11:30 am, ittium <itt...@gmail.com> wrote:
>> On Jun 24, 3:26 pm, gwowen <gwo...@gmail.com> wrote:
>> 
>>> On Jun 24, 6:49 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>> 
>>>> Why? For this particular task or in general?
>> 
>>> Because you can't guarantee an O(1) std::swap.
>> 
>> 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).

I don't see where this mentions *amortized* O(1). There's nothing to 
amortize; swap for containers other than array is O(1).

-- 
  Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The 
Standard C++ Library Extensions: a Tutorial and Reference 
(www.petebecker.com/tr1book)

[toc] | [prev] | [next] | [standalone]

#7118

On Jun 24, 12:37 pm, Pete Becker <p...@versatilecoding.com> wrote:

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

[toc] | [prev] | [next] | [standalone]

#7102

On Jun 23, 3:45 pm, ittium <itt...@gmail.com> wrote:
> 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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c++

csiph-web