Discussion

Here are three fundamental issues and related questions for programming in general, and for choosing a container in particular:

• Write for correctness, simplicity, and clarity first (see 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.

• Write for efficiency only when and where necessary (see 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 doubles 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., list, set, map).

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:

• Guaranteed to have the lowest space overhead of any container (zero bytes per object).

• Guaranteed to have the fastest access speed to contained elements of any container.

• Guaranteed to have inherent locality of reference, meaning that objects near each other in the container are guaranteed to be near each other in memory, which is not guaranteed by any other standard container.

• Guaranteed to be layout-compatible with C, unlike any other standard container. (See 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.