Professional C__ - Marc Gregoire [201]
The deque provides push_front() and pop_front(), which the vector omits.
The deque does not expose its memory management scheme via reserve() or capacity().
deques are rarely used, as opposed to vectors and lists. Thus, we leave the details of the deque methods to the Standard Library Reference resource on the website.
list
The STL list, defined in the Most of the list operations are identical to those of the vector, including the constructors, destructor, copying operations, assignment operations, and comparison operations. This section focuses on those methods that differ from those of vector. Consult the Standard Library Reference resource on the website for details on the list methods not discussed here. lists also support the C++11 uniform initialization mechanism as shown in the following example: list Code snippet from ListUniformInit\ListUniformInit.cpp Accessing Elements The only methods provided by the list to access elements are front() and back(), both of which run in constant time. These methods return a reference to the first and last element in the list. All other element access must be performed through iterators. A list supports begin(), returning an iterator referring to the first element in the list, and end(), returning an iterator referring to the last element in the list. Lists do not provide random access to elements. Iterators The list iterator is bidirectional, not random access like the vector iterator. That means that you cannot add and subtract list iterators from each other, or perform other pointer arithmetic on them. For example, if p is a list iterator, you can traverse through the elements of the list by doing ++p or --p, but you cannot use the addition or subtraction operator; p+n or p-n does not work. Adding and Removing Elements The list supports the same add element and remove element methods like the vector, including push_back(), pop_back(), the five forms of insert(), the two forms of erase(), and clear(). Like the deque, it also provides push_front() and pop_front(). The amazing thing about the list is that all these methods (except for clear()) run in constant time, once you’ve found the correct position. Thus, the list is appropriate for applications that perform many insertions and deletions from the data structure, but do not need quick index-based element access. list Size Like deques, and unlike vectors, lists do not expose their underlying memory model. Consequently, they support size(), empty()and resize(), but not reserve() or capacity(). Special list Operations The list provides several special operations that exploit its quick element insertion and deletion. This section provides an overview and examples. The Standard Library Reference resource on the website gives a thorough reference for all the methods. Splicing The linked-list characteristics of the list class allow it to splice, or insert, an entire list at any position in another list in constant time. The simplest version of this method works as follows: list // Add the a words. dictionary.push_back("aardvark"); dictionary.push_back("ambulance"); // Add the c words. dictionary.push_back("canticle"); dictionary.push_back("consumerism"); // Create another list, of the b words. bWords.push_back("bathos"); bWords.push_back("balderdash"); // splice the b words into the main dictionary. if (bWords.size() > 0) { // Get an iterator to the last b word. auto iterLastB = --(bWords.cend()); // Iterate up to the spot where we want to insert header file, is a standard doubly linked list. It supports constant-time insertion and deletion of elements at any point in the list, but provides slow (linear) time access to individual elements. In fact, the list does not even provide random access operations like operator[]. Only through iterators can you access individual elements.