Which container to use?

[Frank]

Dear people,

I need to organize a list of elements, and I'm
not sure which STL container to use (they all have
their benefits and drawbacks) - or whether
to use some different method. Could someone,
from the required functionality, recommend something?

- the list should hold at least ca. 20,000 elements,
but 50-100 are much more typical
- the elements are complex (class type)
- all elements are unique, and a "less" predicate exists
- there will never a new element be inserted in the
sequence but frequently appended to the end of the list
- very often elements will be looked up, changed or
deleted from the list
- in case it matters: a unique element that has been
deleted will never appear again, so the elements are
unique "in eternity".

I thought of a plain vector; the only drawback
would be that on deletion the rest of the list
has to be shifted. Would a vector with a special
deletion function (marking deleted elements as
invalid and doing kind of a garbage collection
now and then) a good solution?

[David Lowndes]

Post by Frank
I need to organize a list of elements, and I'm
not sure which STL container to use (they all have
their benefits and drawbacks) - or whether
to use some different method. Could someone,
from the required functionality, recommend something?

The only way you'll know which best meets your need is to try them and
measure the results.

vector is probably the first and most likely candidate - even nowadays
in situations where traditionally linked lists may appear a better
text book choice because of CPU caches - keeping data together can be
a massive improvement.

Dave