Professional C__ - Marc Gregoire [181]
Use a vector instead of an array whenever possible.
There is a template specialization available for vector list An STL list is a doubly linked list structure. Like an array or vector, it stores a sequence of elements. However, unlike an array or vector, the elements of a list are not necessarily in contiguous memory. Instead, each element in the list specifies where to find the next and previous elements in the list (usually via pointers), hence the name doubly linked list. The performance characteristics of a list are the exact opposite of a vector. They provide slow (linear time) element lookup and access, but quick (constant time) insertion and deletion of elements once the relevant position has been found. Thus, you should use a list when you plan to insert and remove many elements, but do not require quick lookup. deque The name deque is an abbreviation for a double-ended queue, although it behaves more like a vector instead of a queue which is discussed later. A deque provides quick (constant time) element access. It also provides fast (amortized constant time) insertion and deletion at both ends of the sequence, but it provides slow (linear time) insertion and deletion in the middle of the sequence. You should use a deque instead of a vector when you need to insert or remove elements from either end of the sequence but still need fast access to all elements. However, this requirement does not apply to many programming problems; in most cases a vector or list should suffice. array C++11 introduces a new type of sequential container called std::array. This is a replacement for the standard C-style arrays. Sometimes you know the exact number of elements in your container upfront and you don’t need the flexibility of a vector or a list, which are able to grow dynamically to accommodate new elements. The C++11 std::array is perfect for such fixed-sized collections and it does not have the same overhead as vector; it’s basically a thin wrapper around standard C-style arrays. There are a number of advantages in using std::arrays instead of standard C-style arrays; they always know their own size, do not automatically get cast to a pointer to avoid certain types of bugs, and have iterators to easily loop over the elements. std::arrays do not provide insertion or deletion. They have a fixed size. Access to elements is very fast (constant time), just as with vectors. forward_list The forward_list, introduced in C++11, is a singly linked list, compared to the list container, which is doubly linked. The forward_list supports forward iteration only. They require less memory than a list; allow constant time insertion and deletion anywhere; and like lists, there is no fast random access to elements. The vector, list, deque, array, and forward_list containers are called sequential containers because they store a sequence of elements. queue The name queue comes directly from the definition of the English word queue, which means a line of people or objects. The queue container provides standard first in, first out (or FIFO) semantics. A queue is a container in which you insert elements at one end and take them out at the other end. Both insertion (amortized constant time) and removal (constant time) of elements is quick. You should use a queue structure when you want to model real-life “first-come, first-served” semantics. For example, consider a bank. As customers arrive at the bank, they get in line. As tellers become available, they serve the next customer in line, thus providing “first-come, first-served”