C++ Primer Plus

    three.splice(three.begin(), one);

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

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

    cout << endl << "List one: ";

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

    three.unique();

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

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

    three.sort();

    three.unique();

    cout << endl << "List three after sort & unique: ";

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

    two.sort();

    three.merge(two);

    cout << endl << "Sorted two merged into three: ";

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

    cout << endl;

    return 0;

}

Here is the output of the program in Listing 16.12:

List one: 2 2 2 2 2

List two: 1 2 4 8 6

List three: 1 2 4 8 6 6 4 2 4 6 5

List three minus 2s: 1 4 8 6 6 4 4 6 5

List three after splice: 2 2 2 2 2 1 4 8 6 6 4 4 6 5

List one:

List three after unique: 2 1 4 8 6 4 6 5

List three after sort & unique: 1 2 4 5 6 8

Sorted two merged into three: 1 1 2 2 4 4 5 6 6 8 8

Program Notes

The program in Listing 16.12 uses the for_each() algorithm and an outint() function to display the lists. With C++11, you could use the range-based for loop instead:

for (auto x : three) cout << x << " ";

The main difference between insert() and splice() is that insert() inserts a copy of the original range into the destination, whereas splice() moves the original range into the destination. Thus, after the contents of one are spliced to three, one is left empty. (The splice() method has additional prototypes for moving single elements and a range of elements.) The splice() method leaves iterators valid. That is, if you set a particular iterator to point to an element in one, that iterator still points to the same element after splice() relocates it in three.

Notice that unique() only reduces adjacent equal values to a single value. After the program executes three.unique(), three still contains two fours and two sixes that weren’t adjacent. But applying sort() and then unique() does limit each value to a single appearance.

There is a nonmember sort() function (Listing 16.9), but it requires random access iterators. Because the trade-off for rapid insertion is to give up random access, you can’t use the nonmember sort() function with a list. Therefore, the class includes a member version that works within the restrictions of the class.

The list Toolbox

The list methods form a handy toolbox. Suppose, for example, that you have two mailing lists to organize. You could sort each list, merge them, and then use unique() to remove multiple entries.

The sort(), merge(), and unique() methods also each have a version that accepts an additional argument to specify an alternative function to be used for comparing elements. Similarly, the remove() method has a version with an additional argument that specifies a function used to determine whether an element is removed. These arguments are examples of predicate functions, a topic to which we’ll return later.

forward_list (C++11)

C++11 adds forward_list as a container class. This class implements a singly linked list. In this kind of list, each item is linked just to the next item, but not to the preceding item. Therefore, the class requires just a forward iterator, not a bidirectional one. Thus, unlike vector and list, forward_list isn’t a reversible container. Compared to list, forward_list is simpler, more compact, but with fewer features.

queue

The queue template class (declared in the queue—formerly queue.h—header file) is an adapter class. Recall that the ostream_iterator template is an adapter that allows an output stream to use the iterator interface. Similarly, the queue template allows an underlying class (deque, by default) to exhibit the typical queue interface.

The queue template is more restrictive than deque. Not only does it not permit random access to elements of a queue, the queue class doesn’t even allow you to iterate through a queue. Instead, it limits you to the basic operations that define a queue. You can add an element to the rear of a queue, remove an element from the front of a queue, view the values of the front and rear elements, check the number of elements, and test to see if a queue is empty. Table 16.10 lists these operations.

Note that pop() is a data removal method, not a data retrieval method. If you want to use a value from a queue, you first use front() to retrieve the value and then use pop() to remove it from the queue.

Table 16.10. queue Operations

priority_queue