Nathan Myers <ncm@cantrip.org> wrote:

>Surely you realize that list<> doesn't operate on pointers to the
>contained objects, but rather pointers to list nodes.

Is your complaint about the fact in the HP STL, list_nodes have member
T's instead of pointer to T's? Well, I understand that, but that's an
implementation detail. The list_nodes could just as easily keep pointers
to T's in them.

In my own code here at work, I construct a hierarchy of objects that
contain other objects and so on. For example, in the code for creating a
list of "event groups", I create an event group based on some sort of
input. The event group then initializes its list of events based on some
sort of input. The events initialize a few lists of their own based on
the input. Then the event constructor comes back and the group inserts
the event into its list<event> using push_back.

Do you see the problem? I've already been copying all of the children
(in an ownership sense) of the events into the lists inside the event.
Now, I'm copying the event into the event group list, which means I am
creating an entirely new tree with an event as root, then throwing away
the old one. If I had a list::push_back_ptr(), then I could simply
insert the created event into the list without having to copy it and
then destroy the old event. If I've lost you, here's an example tree:

   class node {
      list<group> grouplist;
   }
   class group {
      list<event> eventlist;
   }
   class event {
      list<variable> varlist;
      list<pattern> patlist;
   }

Do you see the performance problem on creation of the tree?

>If you are moving objects from one list to another, you can
>use member splice() to avoid copying in that case.

Unfortunately, I can't do that. There's no "move" operation. The
push_back function *copies* the object you give it, and the only way to
make it otherwise would be to change the STL.

Now, I can use something like reference-counting STL-compatible
pointers, but it seems essentially like an ugly hack, given that it
would be so much nicer if the list has a fast insert function
(performance is supposed to be important to the STL, after all). Now,
I'm assuming that since the C++ committee has been fairly thorough, they
have already discussed a fast insert function and it was rejected for
some reason. It would be nice if I knew what that reason was, because I
can't think of any reasons why it shouldn't be done.


[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Steve Willer wrote:
>
> Nathan Myers <ncm@cantrip.org> wrote:
>
> >Surely you realize that list<> doesn't operate on pointers to the
> >contained objects, but rather pointers to list nodes.
>
> Is your complaint about the fact in the HP STL, list_nodes have member
> T's instead of pointer to T's? Well, I understand that, but that's an
> implementation detail. The list_nodes could just as easily keep pointers
> to T's in them.

I have no complaint.  list<T> operates on values of T.  list<T*>
operates on values of T*.  list<SmartPointer<T> > operates on values
of SmartPointer<T>.

> In my own code here at work, I construct a hierarchy of objects that
> contain other objects and so on. For example, in the code for creating a
> list of "event groups", I create an event group based on some sort of
> input. The event group then initializes its list of events based on some
> sort of input. The events initialize a few lists of their own based on
> the input. Then the event constructor comes back and the group inserts
> the event into its list<event> using push_back.
>
> Do you see the problem? I've already been copying all of the children
> (in an ownership sense) of the events into the lists inside the event.
> Now, I'm copying the event into the event group list, which means I am
> creating an entirely new tree with an event as root, then throwing away
> the old one. If I had a list::push_back_ptr(), then I could simply
> insert the created event into the list without having to copy it and
> then destroy the old event. If I've lost you, here's an example tree:
>
>    class node {
>       list<group> grouplist;
>    }
>    class group {
>       list<event> eventlist;
>    }
>    class event {
>       list<variable> varlist;
>       list<pattern> patlist;
>    }
>
> Do you see the performance problem on creation of the tree?

I see that you are using list<> in a way that involves a lot of
copying of objects, including list<> objects.  But there are many
ways to use list<>.

> >If you are moving objects from one list to another, you can
> >use member splice() to avoid copying in that case.
>
> Unfortunately, I can't do that. There's no "move" operation. The
> push_back function *copies* the object you give it, and the only way to
> make it otherwise would be to change the STL.

I recommend you not use push_back if it doesn't do what you want.
If it offends you that member "splice" is not called "move", you
can define your own global function, or derive from list<>.  Maybe
I don't understand your difficulty with splice().

> Now, I can use something like reference-counting STL-compatible
> pointers, but it seems essentially like an ugly hack, given that it
> would be so much nicer if the list has a fast insert function
> (performance is supposed to be important to the STL, after all). Now,
> I'm assuming that since the C++ committee has been fairly thorough, they
> have already discussed a fast insert function and it was rejected for
> some reason. It would be nice if I knew what that reason was, because I
> can't think of any reasons why it shouldn't be done.

A judicious use of pointers (counted or otherwise) seems called for in
this application.

list<> had to satisfy many, many requirements, and the result is that it
serves as a good basis for user types, but is not all things to all people.
Instead, it is simple enough to be useful to all people, and it is clear
which operations are fast and which are not.

I have directed followups to comp.lang.c++.moderated.  See you there.

Nathan Myers
ncm@cantrip.org
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]