I have read alot of C++-books the past two years but the following
idiom has never been introduced to me earlier.
Is this nonsense or does it makes sense? Any pros and cons?
I think it could be applicable when this kind off runtime information
about all living objects of some class is needed.

class Widget {
public:
	static vector<Widget*> everyone;

	Widget() {
		everyone.push_back(this);
	}

	~Widget() {
		everyone.erase(find(everyone.begin(), everyone.end(), this));
	}
};
vector<Widget*> Widget::everyone;

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

d04rp@student.lth.se wrote:
> I have read alot of C++-books the past two years but the following
> idiom has never been introduced to me earlier.
> Is this nonsense or does it makes sense? Any pros and cons?
> I think it could be applicable when this kind off runtime information
> about all living objects of some class is needed.
> 
> class Widget {
> public:
> 	static vector<Widget*> everyone;
> 
> 	Widget() {
> 		everyone.push_back(this);
> 	}
> 
> 	~Widget() {
> 		everyone.erase(find(everyone.begin(), everyone.end(), this));
> 	}
> };
> vector<Widget*> Widget::everyone;

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 ;-)

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

* d04rp@student.lth.se:
> I have read alot of C++-books the past two years but the following
> idiom has never been introduced to me earlier.
> Is this nonsense or does it makes sense? Any pros and cons?

Biggest con that this scheme adds O(n^2) behavior for destruction of a set of 
Widget instances.

One might almost suspect that this is code from unmentionable company X...

Second con, that in theory you might run into the static initialization fiasco 
problem (see the FAQ).



> I think it could be applicable when this kind off runtime information
> about all living objects of some class is needed.
> 
> class Widget {
> public:
> 	static vector<Widget*> everyone;
> 
> 	Widget() {
> 		everyone.push_back(this);
> 	}
> 
> 	~Widget() {
> 		everyone.erase(find(everyone.begin(), everyone.end(), this));
> 	}
> };
> vector<Widget*> Widget::everyone;

Try this instead:

<code>
#include <set>

class Widget
{
public:
     static std::set<Widget*> all;

     Widget() { all.insert( this ); }
     ~Widget() { all.erase( this ); }
};

std::set<Widget*> Widget::all;

#include <iostream>
#include <iterator>
#include <algorithm>
int main()
{
     using namespace std;
     {
         Widget  a, b, c;
         ostream_iterator<Widget*> oi( cout, "\n" );
         copy( Widget::all.begin(), Widget::all.end(), oi );
     }
}
</code>

Note that here the ease() operation is guaranteed O(log n).

By the way, please don't post tab characters, but instead convert tabs to spaces 
  before posting.


Cheers, & hth.,

- Alf

-- 
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

<d04rp@student.lth.se> wrote in message 

news:7f610cc2-d0a0-4eb9-9e9d-1de301825652@i12g2000prf.googlegroups.com...

:I have read alot of C++-books the past two years but the following

: idiom has never been introduced to me earlier.



The idiom is not unrelated to the Counted base class described by

Scott Meyers in MEC++, item 26.  I'm sure other refs can be found.



: Is this nonsense or does it makes sense? Any pros and cons?



pros?

  Well, only if you have a need to access all instances of a class.

  For detecting object leaks, you may want more than a count,

and extend in this way the Count template of MEC++ #26.

  The idiom will mainly be found as a back-end to a factory function

that implements re-use of existing object instances (you'll

see this in some networking layers or various object caches,

more usually in the form of a static map<pathOrId,Object*>.



cons?

  As with all gobal/static data, beware of multithreading...



Regards --Ivan

-- 

http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

Brainbench MVP for C++ <> http://www.brainbench.com 





      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 21 Mar, 08:37, David Abrahams <d...@boost-consulting.com> wrote:
> d0...@student.lth.se 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 ;-)

Depends. Big-O is mainly useful when talking about infinities. Real
programs usually work in a ranges that are closer to zero and there
constant factors can have more to say on the subject.
Hint: vector is much more cache-friendly and can also use less
allocations, which tend to be expensive.

It is possible to write a benchmark that will "prove" either case, so
I would not dismiss the original solution just based on O(something).

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

<d04rp@student.lth.se> wrote in message
news:7f610cc2-d0a0-4eb9-9e9d-1de301825652@i12g2000prf.googlegroups.com...

[8<8<8<]
> Is this nonsense or does it makes sense?

It makes perfectly sense.

> Any pros and cons?

If there are any Widget objects created as global object (non local, static
storage duration) the "everyone" container may or may not be constructor
when the Widget constructor is executed.
In that case

Furthermore often there is no need to have "everyone" as part of the
declaration of Widget (it's a bad idea to have it publicly accessable
anyway), but instead have it as a global variable in unnamed namespace in
the cpp-file. This increases encapsulation.

Combined this means something like (not test compiled and a few details
missing):
HPP-file:

class Widget
{
public:
   Widget();
   ~Widget()

   // ... whatever

private:
   Widget(const Widget);  // prohibit copy-construction
};

CPP-file:
namespace
{  // start of unnamed namespace

// vector or set - depending on needs
vector<Widget*>*   everyoneWidget;

Widget::Widget()
{
   if(!everyoneWidget)
     everyoneWidget = new vector<Widget*>;

  assert(everyoneWidget);
  assert(everyoneWidget->end() == find(everyoneWidget->begin(),
everyoneWidget->end(), this));
  everyoneWidget->push_back(this);
}

Widget::~Widget()
{
  assert(everyoneWidget);
  assert(everyoneWidget->end() != find(everyoneWidget->begin(),
everyoneWidget->end(), this));
  everyoneWidget->erase(find(everyoneWidget->begin(), everyoneWidget->end(),
this));
  if(everyoneWidget->empty())    {
    delete everyoneWidget;
    everyoneWidget = 0;
  }
}

}  // end of unnamed namespace




--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

d04rp@student.lth.se () wrote (abridged):
> Is this nonsense or does it makes sense? Any pros and cons?
> I think it could be applicable when this kind off runtime 
> information about all living objects of some class is needed.

I have used a similar idiom in real programs. It is a scary thing to do.
As with any singleton, you have a potential covert channel of
communication between different parts of the program. Widgets created by
different modules for different reasons will end up in the same
collection. You have to be careful about losing modularity. I would see
it as a kind of metaprogramming, so you also have to be careful about
mixing levels of abstraction.

In your particular implementation, you need to be aware that if some
class inherits from Widget, its instances will be added to the collection
before they are fully constructed. From the collection they can be
accessed from anywhere, still in their incomplete state. This may not be
a problem in any particular use, but it is an example of the kind of
scariness I mentioned. It gives me the willies, anyway.

-- Dave Harris, Nottingham, UK.

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 21 Mar, 08:37, David Abrahams <d...@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.

<code>
#include <list>

class Widget;
typedef std::list<Widget*> Widgets;

class Widget
{
public:
   static Widgets all;

   Widget()
   {
     all.push_back(this);
     self = all.end();
     --self;
   }
   ~Widget() { all.erase(self); }

private:
   Widgets::iterator self;
};

Widgets Widget::all;
</code>

Roman Perepelitsa.

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

In article
<f0f6435f-cf6a-4e33-ab47-e03aa7391be7@i7g2000prf.googlegroups.com>,
<"Roman.Perepelitsa@gmail.com"> wrote:

> On 21 Mar, 08:37, David Abrahams <d...@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....

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

David Abrahams wrote:
> d04rp@student.lth.se wrote:
>> class Widget {
[...]
>> };
>> vector<Widget*> Widget::everyone;
> 
> 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 ;-)

Hmmm, I would actually use a vector, but differently and for different
reasons:
1. It's simple, with few allocations for typical programs (I'd expect less
than one thousand widget in a UI).
2. Due to the hierarchical nature of widgets, you actually have a high
likelihood that the widget you want to remove is near the end of the
vector, so I would start searching at the end.
3. I wouldn't erase that pointer but first swap it with the last one and
then pop that off the vector.
4. I wouldn't use std::list, because it requires allocation of a node which
contains two pointers in addition to the content. Even with an optimised
allocator, this would still disturb caching, in particular when you always
search linearly.
5. Adding and removing elements here is probably dwarfed by the overhead of
the GUI in general, so I'd opt for the method that at least preserves
memory, i.e. std::vector still.


Uli

-- 
Sator Laser GmbH
Gesch�ftsf�hrer: Michael W�hrmann, Amtsgericht Hamburg HR B62 932


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

David Abrahams wrote:
> d04rp@student.lth.se wrote:
>> I have read alot of C++-books the past two years but the following
>> idiom has never been introduced to me earlier.
>> Is this nonsense or does it makes sense? Any pros and cons?
>> I think it could be applicable when this kind off runtime information
>> about all living objects of some class is needed.
>>

[...]

>> 	~Widget() {
>> 		everyone.erase(find(everyone.begin(), everyone.end(), this));
>> 	}
>> };

> 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 ;-)
> 

Maybe I'm not seeing this, but is there a good reason that each Widget
doesn't just store the iterator that it refers to in the container?

This way there is no lookup required when erasing the current object
from the container.

Regards,

Richard



-- 
Richard Corden

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 26 Mar, 11:42, Carl Barron <cbarron...@adelphia.net> wrote:
> In article
> <f0f6435f-cf6a-4e33-ab47-e03aa7391...@i7g2000prf.googlegroups.com>,
>
> <"Roman.Perepeli...@gmail.com"> wrote:
> > On 21 Mar, 08:37, David Abrahams <d...@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.

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Carl Barron wrote:

> In article
> <f0f6435f-cf6a-4e33-ab47-e03aa7391be7@i7g2000prf.googlegroups.com>,
> <"Roman.Perepelitsa@gmail.com"> wrote:
> 
>> On 21 Mar, 08:37, David Abrahams <d...@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.

And a list in O(1) time, which is less.

If you traverse (eg. read or find) the list of widget more than once (or
O(1) times) per each insert/delete, use a vector, because the quadratic
complexity is already there in the traversal. If you use it for eg. finding
if a given pointer is a pointer to a widget, use a set. If you do not
traverse the list often (that is less than O(1) times per insert/delete),
and do not search it for a given pointer often (less than O(log n/n) times
per insert/delete), use a list. A hash_set might be even better in the last
two cases.

BTW, if you think it is rare to have a thousand widgets in a real world
program, it is not so uncommon. For example, in Gtk, every label is a
widget, and if you have a listbox with text entries, these entries are
labels. That means a listbox with a thousand entries will create a thousand
widgets.

Regards
     Jiri Palecek


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

In article <fsdfm9$2ijp$1@ns.felk.cvut.cz>, Jiri Palecek
<jpalecek@web.de> wrote:

> Carl Barron wrote:
> 
> > In article
> > <f0f6435f-cf6a-4e33-ab47-e03aa7391be7@i7g2000prf.googlegroups.com>,
> > <"Roman.Perepelitsa@gmail.com"> wrote:
> > 
> >> On 21 Mar, 08:37, David Abrahams <d...@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.
> 
> And a list in O(1) time, which is less.
> 
> If you traverse (eg. read or find) the list of widget more than once (or
> O(1) times) per each insert/delete, use a vector, because the quadratic
> complexity is already there in the traversal. If you use it for eg. finding
> if a given pointer is a pointer to a widget, use a set. If you do not
> traverse the list often (that is less than O(1) times per insert/delete),
> and do not search it for a given pointer often (less than O(log n/n) times
> per insert/delete), use a list. A hash_set might be even better in the last
> two cases.
> 
> BTW, if you think it is rare to have a thousand widgets in a real world
> program, it is not so uncommon. For example, in Gtk, every label is a
> widget, and if you have a listbox with text entries, these entries are
> labels. That means a listbox with a thousand entries will create a thousand
> widgets.
> 
     I just picked 1000 as an example the point is a list is allocates
memory once per node and a vector can allocate lots of them at once for
pointers, in my example allocating 1000 ptrs at once is going to be
faster than 1000 allocations of int *. [most likely]  so I don't see
list as better here, but it is a heuristic its not cast in stone,
Further each dtor call of Widget must find its entry in the container
when the dtor is called, and with a list or vector its O(N) with a set
its O(log N).  so unless you never destruct widgets you need to find
this in the static container in the dtor and remove the entry for this
from the container.  That is linear for a list/vector and logaritmic
for
set and that is const time on average but could be linear for an
unsorted_set<int *>.

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On Mar 21, 8:37 am, David Abrahams <d...@boost-consulting.com> wrote:
> d0...@student.lth.se wrote:
> > I have read alot of C++-books the past two years but the following
> > idiom has never been introduced to me earlier.
> > Is this nonsense or does it makes sense? Any pros and cons?
> > I think it could be applicable when this kind off runtime information
> > about all living objects of some class is needed.
>
> > class Widget {
> > public:
> >    static vector<Widget*> everyone;
>
> >    Widget() {
> >            everyone.push_back(this);
> >    }
>
> >    ~Widget() {
> >            everyone.erase(find(everyone.begin(), everyone.end(), this));
> >    }
> > };
> > vector<Widget*> Widget::everyone;
>
> 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 ;-)

{ edits: quoted banner removed please don't quote extranous material -mod }

Actually, in this case, the really optimal solution is to avoid using
container.

Just put Windget *prev, *next; member variables and create the linked
list of your own without using any memory to create nodes....

Mirek

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"Carl Barron" <cbarron413@adelphia.net> schreef in bericht
news:260320081729455664%cbarron413@adelphia.net...
> In article <fsdfm9$2ijp$1@ns.felk.cvut.cz>, Jiri Palecek
> <jpalecek@web.de> wrote:
>
> > Carl Barron wrote:
> >
>      I just picked 1000 as an example the point is a list is allocates
> memory once per node and a vector can allocate lots of them at once for
> pointers, in my example allocating 1000 ptrs at once is going to be
> faster than 1000 allocations of int *. [most likely]  so I don't see

Wouldn't a smart list allocator just reserve a block of memory and
use placement new for each node? That would make it (almost)
as fast as a vector.

Antoon

> list as better here, but it is a heuristic its not cast in stone,
> Further each dtor call of Widget must find its entry in the container
> when the dtor is called, and with a list or vector its O(N) with a set
> its O(log N).  so unless you never destruct widgets you need to find
> this in the static container in the dtor and remove the entry for this
> from the container.  That is linear for a list/vector and logaritmic
> for
> set and that is const time on average but could be linear for an
> unsorted_set<int *>.
>



-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

"Richard Corden" <richard.corden@gmail.com> schreef in bericht
news:64um9rF2dnb85U1@mid.individual.net...
> David Abrahams wrote:
> > d04rp@student.lth.se wrote:
> >> I have read alot of C++-books the past two years but the following
> >> idiom has never been introduced to me earlier.
> >> Is this nonsense or does it makes sense? Any pros and cons?
> >> I think it could be applicable when this kind off runtime information
> >> about all living objects of some class is needed.
> >>
>
> [...]
>
> >> ~Widget() {
> >> everyone.erase(find(everyone.begin(), everyone.end(), this));
> >> }
> >> };
>
> > 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 ;-)
> >
>
> Maybe I'm not seeing this, but is there a good reason that each Widget
> doesn't just store the iterator that it refers to in the container?
>
> This way there is no lookup required when erasing the current object
> from the container.
>

Because (depending on the type of container) when a Widget instance is
added or removed form the container some or all iterators are invalidated.
Your Widget probably ends up holding an iterator which can not be used.

Antoon

> Regards,
>
> Richard
>



-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Carl Barron wrote:

> In article <fsdfm9$2ijp$1@ns.felk.cvut.cz>, Jiri Palecek
> <jpalecek@web.de> wrote:
> 
>> Carl Barron wrote:
>> 
>> > In article
>> > <f0f6435f-cf6a-4e33-ab47-e03aa7391be7@i7g2000prf.googlegroups.com>,
>> > <"Roman.Perepelitsa@gmail.com"> wrote:
>> > 
>> >> On 21 Mar, 08:37, David Abrahams <d...@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.
>> 
>> And a list in O(1) time, which is less.
>> 
>> If you traverse (eg. read or find) the list of widget more than once (or
>> O(1) times) per each insert/delete, use a vector, because the quadratic
>> complexity is already there in the traversal. If you use it for eg.
>> finding if a given pointer is a pointer to a widget, use a set. If you do
>> not traverse the list often (that is less than O(1) times per
>> insert/delete), and do not search it for a given pointer often (less than
>> O(log n/n) times per insert/delete), use a list. A hash_set might be even
>> better in the last two cases.
>> 
>> BTW, if you think it is rare to have a thousand widgets in a real world
>> program, it is not so uncommon. For example, in Gtk, every label is a
>> widget, and if you have a listbox with text entries, these entries are
>> labels. That means a listbox with a thousand entries will create a
>> thousand widgets.
>> 

> Further each dtor call of Widget must find its entry in the container
> when the dtor is called, and with a list or vector its O(N)

No. You're missing the fundamental point about list, and that is, list
iterators can never be invalidated unless you touch them or the thing they
point to. This means you can store the iterator safely and need no search
at all. If allocations are a bottleneck for you, you can use custom
allocators.

Regards
     Jiri Palecek


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On Mar 27, 11:03 am, Mirek Fidler <c...@ntllib.org> wrote:
> On Mar 21, 8:37 am, David Abrahams <d...@boost-consulting.com> wrote:
>
>
>
>
>
> > d0...@student.lth.se wrote:
> > > I have read alot of C++-books the past two years but the following
> > > idiom has never been introduced to me earlier.
> > > Is this nonsense or does it makes sense? Any pros and cons?
> > > I think it could be applicable when this kind off runtime information
> > > about all living objects of some class is needed.
>
> > > class Widget {
> > > public:
> > >    static vector<Widget*> everyone;
>
> > >    Widget() {
> > >            everyone.push_back(this);
> > >    }
>
> > >    ~Widget() {
> > >            everyone.erase(find(everyone.begin(), everyone.end(), this));
> > >    }
> > > };
> > > vector<Widget*> Widget::everyone;
>
> > 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 ;-)
>
> { edits: quoted banner removed please don't quote extranous material -mod }
>
> Actually, in this case, the really optimal solution is to avoid using
> container.
>
> Just put Windget *prev, *next; member variables and create the linked
> list of your own without using any memory to create nodes....
>

I think Boost Intrusive would work well.
http://igaztanaga.drivehq.com/intrusive/intrusive/set_multiset.html

I don't like the way the library reuses names in std, though.

Brian Wood
Ebenezer Enterprises
www.webEbenezer.net


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

In article <fsga23$t6g$1@ns.felk.cvut.cz>, Jiri Palecek
<jpalecek@web.de> wrote:

> 
> No. You're missing the fundamental point about list, and that is, list
> iterators can never be invalidated unless you touch them or the thing they
> point to. This means you can store the iterator safely and need no search
> at all. If allocations are a bottleneck for you, you can use custom
> allocators.
> 
> Regards
>      Jiri Palecek
   True saving an iterator of a list reduces the lookup to O(1) but the
problem becomes things like instruction sequencing, localization of the
code etc.  the mileage varies but a simple use of a vector<Widget *> as
a dynamic array of Widget *'s is likely to produce more compact code,
fewer code cache loads etc.   you don't need even need a swap since the
Widget *'s are not owned by the container so a simple overwrite of the
last entry over the found entry and pop_back(). does the trick.  A
search for pointers in the backward direction is likely to be quick as
the items to be removed tend to be near the  back of the container, as
noted elsewhere in this thread.    Also if you save 10 micro seconds
and wait for input what do you really save??

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

> > Actually, in this case, the really optimal solution is to avoid using
> > container.
>
> > Just put Windget *prev, *next; member variables and create the linked
> > list of your own without using any memory to create nodes....
>
> I think Boost Intrusive would work well.http://igaztanaga.drivehq.com/intrusive/intrusive/set_multiset.html

Depends on what is the original goal. IMO, the real purpose is to have
a way how to iterate through all active 'widgets'. For this purpose,
even intrusive containers seems to be overkill (besides, what is
supposed to be the key? :)

Mirek

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On 27 Mar, 14:07, Carl Barron <cbarron...@adelphia.net> wrote:
>      I just picked 1000 as an example the point is a list is allocates
> memory once per node and a vector can allocate lots of them at once for
> pointers, in my example allocating 1000 ptrs at once is going to be
> faster than 1000 allocations of int *. [most likely]  so I don't see
> list as better here, but it is a heuristic its not cast in stone,
> Further each dtor call of Widget must find its entry in the container
> when the dtor is called, and with a list or vector its O(N) with a set
> its O(log N).  so unless you never destruct widgets you need to find
> this in the static container in the dtor and remove the entry for this
> from the container.  That is linear for a list/vector and logaritmic
> for
> set and that is const time on average but could be linear for an
> unsorted_set<int *>.

Erasing element from std::list is O(1), not O(N). All you have to do
is to store iterator to self inside of widget (see my previous post
with a code). That's why using list is faster than vector or set if
you have many widgets.

Roman Perepelitsa.

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Antoon wrote:
> "Richard Corden" <richard.corden@gmail.com> schreef in bericht
> news:64um9rF2dnb85U1@mid.individual.net...
>> David Abrahams wrote:
>>>
>> Maybe I'm not seeing this, but is there a good reason that each Widget
>> doesn't just store the iterator that it refers to in the container?
>>
>> This way there is no lookup required when erasing the current object
>> from the container.
>>
> 
> Because (depending on the type of container) when a Widget instance is
> added or removed form the container some or all iterators are invalidated.
> Your Widget probably ends up holding an iterator which can not be used.

What you say is true, but it doesn't really answer my question.

If you decide to store your "iterator" as per my suggestion then it only
makes sense to use a container which does not invalidate the other
iterators, eg: std::list.

So, given that your container is std::list, why wouldn't each widget
just store its iterator and delete that?  No lookup required by the
destructor.

Cheers,

Richard



-- 
Richard Corden

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]