C++ Primer Plus

In addition to being a sequence, a vector container is also a model of the reversible container concept. This adds two more class methods: rbegin() returns an iterator to the first element of the reversed sequence, and rend() returns a past-the-end iterator for the reversed sequence. So if dice is a vector container and Show(int) is a function that displays an integer, the following code displays the contents of dice first in forward order and then in reverse order:

for_each(dice.begin(), dice.end(), Show);    // display in order

cout << endl;

for_each(dice.rbegin(), dice.rend(), Show);  // display in reversed order

cout << endl;

The iterator returned by the two methods is of a class scope type reverse_iterator. Recall that incrementing such an iterator causes it to move through a reversible container in reverse order.

The vector template class is the simplest of the sequence types and is considered the type that should be used by default unless the program requirements are better satisfied by the particular virtues of the other types.

deque

The deque template class (declared in the deque header file) represents a double-ended queue, a type often called a deque (pronounced “deck”), for short. As implemented in the STL, it’s a lot like a vector container, supporting random access. The main difference is that inserting and removing items from the beginning of a deque object are constant-time operations instead of being linear-time operations the way they are for vector. So if most operations take place at the beginning and ends of a sequence, you should consider using a deque data structure.

The goal of constant-time insertion and removal at both ends of a deque makes the design of a deque object more complex than that of a vector object. Thus, although both offer random access to elements and linear-time insertion and removal from the middle of a sequence, the vector container should allow faster execution of these operations.

list

The list template class (declared in the list header file) represents a doubly linked list. Each element, other than the first and last, is linked to the item before it and the item following it, implying that a list can be traversed in both directions. The crucial difference between list and vector is that list provides for constant-time insertion and removal of elements at any location in the list. (Recall that the vector template provides linear-time insertion and removal except at the end, where it provides constant-time insertion and removal.) Thus, vector emphasizes rapid access via random access, whereas list emphasizes rapid insertion and removal of elements.

Like vector, list is a reversible container. Unlike vector, list does not support array notation and random access. Unlike a vector iterator, a list iterator remains pointing to the same element even after items are inserted into or removed from a container. For example, suppose you have an iterator pointing to the fifth element of a vector container. Then suppose you insert an element at the beginning of the container. All the other elements have to be moved to make room, so after the insertion, the fifth element now contains the value that used to be in the fourth element. Thus, the iterator points to the same location but to different data. Inserting a new element into a list, however, doesn’t move the existing elements; it just alters the link information. An iterator pointing to a certain item still points to the same item, but it may be linked to different items than before.

The list template class has some list-oriented member functions in addition to those that come with sequences and reversible containers. Table 16.9 lists many of them. (For a complete list of STL methods and functions, see Appendix G.) The Alloc template parameter is one you normally don’t have to worry about because it has a default value.

Table 16.9. Some list Member Functions

Listing 16.12 illustrates these methods, along with the insert() method, which comes with all STL classes that model sequences.

Listing 16.12. list.cpp

// list.cpp -- using a list

#include

#include

#include

#include

void outint(int n) {std::cout << n << " ";}

int main()

{

    using namespace std;

    list one(5, 2); // list of 5 2s

    int stuff[5] = {1,2,4,8, 6};

    list two;

    two.insert(two.begin(),stuff, stuff + 5 );

    int more[6] = {6, 4, 2, 4, 6, 5};

    list three(two);

    three.insert(three.end(), more, more + 6);

    cout << "List one: ";

    for_each(one.begin(),one.end(), outint);

    cout << endl << "List two: ";

    for_each(two.begin(), two.end(), outint);

    cout << endl << "List three: ";

    for_each(three.begin(), three.end(), outint);

    three.remove(2);

    cout << endl << "List three minus 2s: ";

    for_each(three.begin(), three.end(), outint);