Group: comp.lang.c++.moderated · Group Profile
Author: Roman.PerepelitsaRoman.Perepelitsa Date: Mar 26, 2008 09:30
On 26 Mar, 11:42, Carl Barron adelphia.net> wrote:> In article
> i7g2000prf.googlegroups.com>,
>
> <"Roman.Perepeli...@gmail.com"> wrote:>> On 21 Mar, 08:37, David Abrahams boost-consulting.com> wrote:>>> It's not a new idea, but please use a std::set instead of a vector to
>>> avoid O(n^2) explosions. A linear search through all Widgets every time
>>> one is destroyed won't be very healthy for your program ;-)
>
>> Using std::list might be even better idea because it's O(1) complexity
>> to add and remove widgets (I think it should be not slower than
>> std::set
>> even for small number of widgets). And on typical implementation it
>> will use the same amount of memory.
>
> But a set will find the entry to erase on a dtor call in O(log N) time
> not O(N) time. Further if a list was the solution then a vector would
> probably be better due to better caching of infromation,unless there
> are a huge number of pointers to store. Use a set. Note the container
> is holding pointers and these are typically very cheap to copy....
For this particular problem std::set is not faster than std::list in
all
cases and uses the same amount of memory. Why would you recommend
it?
I would use std::vector if there are only a few widgets expected to
exist
at any given time (less than 500) and use std::list otherwise. If I
don't
know how many widgets to expect then I would use std::list because
it's
more scalable.
Roman Perepelitsa.
| 
