Re: Collections of derived objects
Michael Doubez wrote:
std::deque is significantly faster than std::list with most operations
(for the simple reason that it executes significantly less allocations
and deallocations),
Insertion/deletion near the middle incurs N/2 moves.
With a list you have to traverse N/2 elements before you get to the
middle, if you want to insert something there. Admittedly traversal may
be faster than copying the equivalent amount of elements (although this
depends heavily on how fast the copying is, and how randomized the list
traversal is in physical memory, which affects cache misses).
There are some algorithms which benefit from the O(1) insertion at the
location of an iterator, but they aren't really frequently needed or
used in practice.
The biggest advantage of std::list might be that pointers/iterators
pointing to individual elements never get invalidated (unless the
element gets removed, of course). This is actually the most useful
feature of std::list, which might play an important role in some cases.
It the OP must hold distinct instances and order of insertion is not
important, a std::set<> is also a good choice.
std::set<> is only good if you need to find elements fast. Otherwise
it's quite inefficient (lots of memory allocations, consumes even more
memory than std::list...)
--- news://freenews.netfront.net/ - complaints: news@netfront.net ---