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 2 of 2 — ← Prev page 1 [2]

#7119

On Jun 24, 11:29 am, Werner <wer...@gmail.com> wrote:
> 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

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

#7229

On Jun 23, 4: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. 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.

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

#7233

On Wed, 2011-06-29, hanukas wrote:
> On Jun 23, 4: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. 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,

"Might get lucky" is too pessimistic. All standard containers I know of
have a fast, non-throwing swap.  "ittium" should read the
documentation for whatever container he or she is using.

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .  .
\X/     snipabacken.se>   O  o   .

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

#7320

On Jun 29, 6:45 pm, Jorgen Grahn <grahn+n...@snipabacken.se> wrote:
> On Wed, 2011-06-29, hanukas wrote:
> > On Jun 23, 4: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. 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,
>
> "Might get lucky" is too pessimistic. All standard containers I know of
> have a fast, non-throwing swap.  "ittium" should read the
> documentation for whatever container he or she is using.

Probably don't have to go there in that case; it won't turn up as
performance bottleneck in that case in most likely twist of events. I
was commenting for scenario where it would/might be as the poster
seemed overly concerned. ;)

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web