Professional C__ - Marc Gregoire [188]
The STL provides 17 containers, divided into five categories.
Sequential containers: vector (dynamic array)
list
deque
array
forward_list
Associative containers: map
multimap
set
multiset
Unordered associative containers or hash tables: unordered_map
unordered_multimap
unordered_set
unordered_multiset
Container adapters: queue
priority_queue
stack
bitset
Additionally, C++ strings, and streams can also be used as STL containers to a certain degree.
Everything in the STL is in the std namespace. The examples in this book usually use the blanket using namespace std; statement in source files (never use this in header files!), but you can be more selective in your own programs about which symbols from std to use.
Requirements on Elements
STL containers use value semantics on elements. That is, they store a copy of the element that they are given, and return copies of elements when requested. They also assign to elements with the assignment operator and destroy elements with the destructor. Thus, when you write classes that you intend to use with the STL, make sure that it’s okay to have multiple copies of an object in the program at the same time.
If you prefer reference semantics, you must implement them yourself by storing pointers to elements instead of the elements themselves. When the containers copy a pointer, the result still refers to the same element.
If you store pointers in containers, we recommend using reference-counted smart pointers in order to handle the memory management properly. If you use C++11, you can use the new shared_ptr reference counted smart pointer. It’s more difficult if your compiler does not yet support shared_ptr. You cannot use the C++ auto_ptr class in containers because it does not implement copying correctly (as far as the STL is concerned). See Chapter 21 for a SuperSmartPointer class that you can use in the STL containers without C++11 support.
The specific requirements on elements in containers are shown in the following table:
METHOD DESCRIPTION NOTES
Copy Constructor Creates a new element that is “equal” to the old one, but that can safely be destructed without affecting the old one Used every time you insert an element
Move Constructor Creates a new element by moving all content from a source element to the new element Used when the source element will be destroyed after the construction of the new element
Assignment Operator Replaces the contents of an element with a copy of the source element Used every time you modify an element
Move Assignment Operator Replaces the contents of an element by moving all content from a source element Used when the source element will be destroyed after the assignment operation
Destructor Cleans up an element Used every time you remove an element
Default Constructor Constructs an element without any arguments Required only for certain operations, such as the vector resize() method and the map operator[] access
operator== Compares two elements for equality Required only for certain operations, such as operator== on two containers
operator< Determines if one element is less than another Required for keys in associative containers and for certain operations, such as operator< on two containers
Chapter 7 shows you how to write these methods. C++11 move semantics is discussed in Chapter 9.
The STL containers call the copy constructor and assignment operator for elements often, so make those operations efficient. With C++11 it can be made much more efficient by implementing move semantics for your elements, as described in Chapter 9.
Exceptions and Error Checking
The STL containers provide limited error checking. Clients are expected to ensure that their uses are valid. However, some container methods and functions throw exceptions in certain conditions such as out-of-bounds indexing. This chapter mentions exceptions where appropriate. The Standard Library Reference resource on the website attempts to catalog the possible exceptions thrown from each method. However, it is