list of objects

[mataus]

Hello all.

I have a custom object that i have made. I need to store many of these in a
list, and add and delete these objects when i ned them or have finished with
them.

What is the best solution for holding a dynamic list of objects? Are STL
containers best?

Thank you - mataus

[Giuliano]

Post by mataus
Hello all.
I have a custom object that i have made. I need to store many of these in a
list, and add and delete these objects when i ned them or have finished with
them.
What is the best solution for holding a dynamic list of objects? Are STL
containers best?
Thank you - mataus

Generally speaking, standard containers are ok...

If the scenario implies a non-polymorphic list you can use
a container that holds copies or pointers to the real objects.

If you need a polymorphic list, in order to avoid the slicing
of the objects, the items of the container have to be pointers.
However, if you choose to use smart pointers instead of bald
pointers, you have to avoid the use of auto_ptr because it has
copy semantics that not is suitable to use with standard algorithms
used with standard containers.

Ragards.

Giuliano

[Chris Uzdavinis (TeamB)]

Post by mataus
Hello all.
I have a custom object that i have made. I need to store many of these in a
list, and add and delete these objects when i ned them or have finished with
them.
What is the best solution for holding a dynamic list of objects? Are STL
containers best?

When you say "list", do you mean you would like a linked list data
structure, or do you mean something more generic like "some kind of
sequence" of things?

The STL has a linked list implementation, (std::list) which is about
as good as it gets if you want a doubly-linked list. That has fast
insertions and removals, but you can only quickly access elements at
the ends (and must walk item-by-item to find something that is
somewhere in between. In the worst case you must examine everything
in the list before you find what you are looking for, as you cannot
jump to any arbitrary element without already having an iterator to
it.)

If you need random access to an arbitrary element, consider using a
std::vector. It's more like a dynamically sized array. Insertions are
amortized constant time if you add to the end, but are linear if you
add to the beginning (because it must shift all of the existing
elements to make room for the new.) Access to any element is constant
time.

If you need associative access (find an object based on some kind of
key) then consider std::map. That has logarithmic time for
insertions, removals, and lookups. If you have strict performance
issues, you might want a hash table, but that is not yet part of the
standard library. (It will be however, in the near future.)

[Alan Bellingham]

Post by Chris Uzdavinis (TeamB)
If you need random access to an arbitrary element, consider using a
std::vector. It's more like a dynamically sized array. Insertions are
amortized constant time if you add to the end, but are linear if you
add to the beginning (because it must shift all of the existing
elements to make room for the new.) Access to any element is constant
time.

And if you do want to add to or remove from the start, consider
std::vector<>'s close relative, std::deque<>.

Alan Bellingham