The workhorse: std::vector<T>

std::vector represents a contiguous array of data elements, but allocated on the heap instead of on the stack. This improves on std::array in two ways: First, it allows us to create a really gigantic array without blowing our stack. Second, it allows us to resize the underlying array dynamically--unlike std::array<int, 3> where the size of the array is an immutable part of the type, a std::vector<int> has no intrinsic size. A vector's .size() method actually yields useful information about the current state of the vector.

A std::vector has one other salient attribute: its capacity. The capacity of a vector is always at least as large as its size, and represents the number of elements that the vector currently could hold, before it would need to reallocate its underlying array:

Other than its resizeability, vector behaves similarly to array. Like arrays, vectors are copyable (copying all their data elements, in linear time) and comparable (std::vector<T>::operator< will report the lexicographical order of the operands by delegating to T::operator<).

Generally speaking, std::vector is the most commonly used container in the entire standard library. Any time you need to store a "lot" of elements (or "I'm not sure how many elements I have"), your first thought should always be to use a vector. Why? Because vector gives you all the flexibility of a resizeable container, with all the simplicity and efficiency of a contiguous array.

Contiguous arrays are the most efficient data structures (on typical hardware) because they provide good locality, also known as cache-friendliness. When you're traversing a vector in order from its .begin() to its .end(), you're also traversing memory in order, which means that the computer's hardware can predict with very high accuracy the next piece of memory you're going to look at. Compare this to a linked list, in which traversing from .begin() to .end() might well involve following pointers all over the address space, and accessing memory locations in no sensible order. With a linked list, pretty much every address you hit will be unrelated to the previous one, and so none of them will be in the CPU's cache. With a vector (or array), the opposite is true: every address you hit will be related to the previous one by a simple linear relationship, and the CPU will be able to have the values all ready and waiting for you by the time you need them.

Even if your data is "more structured" than a simple list of values, you can often get away with using a vector to store it. We'll see near the end of this chapter how you can use vector to simulate a stack or a priority queue.