Here are three fundamental issues and related questions for programming in general, and for choosing a container in particular:Item 6): Prefer to choose the container that will let you write the clearest code. Examples: If you need to insert at a specific position, use a sequence container (e.g.,
vector, list ). If you need random-access iterators, use
vector, deque , or
string . If you need dictionary-like lookups like
c[0] = 42; , use an associative container (e.g.,
set, map )but if you need an
ordered associative collection, you can't use hash-based (nonstandard
hash_… or standard
unordered_… ) containers.Item 8): If lookup speed is a proven critical consideration, based on actual performance data, prefer a hash-based (nonstandard
hash_… or standard
unordered_… ) containers, then a sorted
vector , then a
set or
map , usually in that order. Even then, big-Oh differences (e.g., linear-time vs. logarithmic-time; see Item 7) only matter if the containers are big enough to swamp the constant factor, which for containers of small objects like
double s frequently doesn't happen until after container sizes exceed several thousand elements.
Prefer to write transactional, strongly error-safe code where reasonably possible (see Item 71), and don't use invalid objects (see Item 99): If you need transactional semantics for inserting and erasing elements, or need to minimize iterator invalidations, prefer a node-based container (e.g.,
Otherwise, follow the Standard's advice: "
vector is the type of sequence that should be used by default." ([C++03] §23.1.1)
If you doubt this advice, ask yourself if you really have a compelling reason
not to use the only standard container that guarantees all of the following properties.
vector alone is:Items 77 and Chapter 78)
Guaranteed to have the most flexible iterators (random access iterators) of any container.
Almost certain to have the fastest iterators (pointers, or classes with comparable performance that often compile away to the same speed as pointers when not in debug mode), faster than those of all other containers.
Do you have a reason not to use that container by default? If you do have a reason, because of your answers to the first three question in this Item, that's just great and perfectly fineuse the other container knowing you did the right thing. If you don't, write
vector and keep going without breaking stride, again knowing you did the right thing.
Finally, prefer to use standard library containers and algorithms over vendor-specific or handcrafted code.