List Operations

The member functions provided by the list data type are described in more detail below. Note that while member functions provide basic operations, the utility of the data structure is greatly extended through the use of the generic algorithms described in Chapters 13 and 14.

Memory Management

There are a variety of ways to declare a list. In the simplest form, a list is declared by simply stating the type of element the collection will maintain. This can be a primitive language type (such as integer or double), a pointer type, or a user-defined type. In the latter case, the user-defined type must implement a default constructor (a constructor with no arguments), as this constructor is in some cases used to initialize newly created elements. A collection declared in this fashion will initially not contain any elements.

   list <int> list_one;
    list <Widget *> list_two;
    list <Widget> list_three;
 

An alternative form of declaration creates a collection that initially contains some number of equal elements. The constructor for this form is declared as explicit, meaning it cannot be used as a conversion operator. This prevents integers from inadvertently being converted into lists. The constructor for this form takes two arguments, a size and an initial value. The second argument is optional. If only the number of initial elements to be created is given, these values will be initialized with the default constructor; otherwise the elements will be initialized with the value of the second argument:

   list <int> list_four (5);  // five elements, initialized to zero
    list <double> list_five (4, 3.14);   // 4 values, initially 3.14
    list <Widget> wlist_six (4);  // default constructor, 4 elements
    list <Widget> list_six (3, Widget(7));  // 3 copies of Widget(7)
 

Lists can also be initialized using elements from another collection, using a beginning and ending iterator pair. The arguments can be any form of iterator, thus collections can be initialized with values drawn from any of the container classes in the standard library that support iterators. Because this requires the ability to specialize a member function using a template, some compilers may not yet support this feature. In these cases an alternative technique using the copy() generic algorithm can be employed. When a list is initialized using copy(), an insert iterator must be constructed to convert the output operations performed by the copy operation into list insertions. (See Chapter 2: Insert Iterators.) The inserter requires two arguments; the list into which the value is to be inserted, and an iterator indicating the location at which values will be placed. Insert iterators can also be used to copy elements into an arbitrary location in an existing list.

   list <double> list_seven (aVector.begin(), aVector.end());
 
                   // the following is equivalent to the above
    list <double> list_eight;
    copy (aVector.begin(), aVector.end(), 
           inserter(list_eight, list_eight.begin()));
 

The insert() operation, to be described in Placing Elements into a List, can also be used to place values denoted by an iterator into a list. Insert iterators can be used to initialize a list with a sequence of values produced by a generator (see Chapter 13: Initialize a Sequence with Generated Values). This is illustrated by the following:

   list <int> list_nine;          
                                    // initialize list 1 2 3 ... 7
    generate_n (inserter(list_nine, list_nine.begin()), 
        7, iotaGen(1));
 

A copy constructor can be used to initialize a list with values drawn from another list. The assignment operator performs the same actions. In both cases the assignment operator for the element type is used to copy each new value.

   list <int> list_ten (list_nine);          // copy constructor
    list <Widget> list_eleven;
    list_eleven = list_six;        // values copied by assignment
 

The assign() member function is similar to the assignment operator, but is more versatile and, in some cases, requires more arguments. Like an assignment, the existing values in the container are deleted, and replaced with the values specified by the arguments. If a destructor is provided for the container element type, it will be invoked for the elements being removed. There are two forms of assign(). The first takes two iterator arguments that specify a subsequence of an existing container. The values from this subsequence then become the new elements in the receiver. The second version of assign takes a count and an optional value of the container element type. After the call the container will hold the number of elements specified by the count, which will be equal to either the default value for the container type or the initial value specified.

   list_six.assign(list_ten.begin(), list_ten.end());
    list_four.assign(3, 7);          // three copies of value seven
    list_five.assign(12);            // twelve copies of value zero
 

Finally, two lists can exchange their entire contents by means of the operation swap(). The argument container will take on the values of the receiver, while the receiver will assume those of the argument. A swap is very efficient, and should be used, where appropriate, in preference to an explicit element-by-element transfer.

   list_ten.swap(list_nine);        // exchange lists nine and ten
 

The class list includes a number of type definitions. The most common use for these is in declaration statements. For example, an iterator for a list of integers can be declared as follows:

list<int>::iterator location;
 

In addition to iterator, the following types are defined:

Values can be inserted into a list in a variety of ways. Elements are most commonly added to the front or back of a list. These tasks are provided by the push_front() and push_back() operations, respectively. These operations are efficient (constant time) for both types of containers.

   list_seven.push_front(1.2);
    list_eleven.push_back (Widget(6));
 

In a previous discussion (Declaration and Initialization of Lists) we noted how, with the aid of an insert iterator and the copy() or generate() generic algorithm, values can be placed into a list at a location denoted by an iterator. There is also a member function, named insert(), that avoids the need to construct the inserter. As we will describe shortly, the values returned by the iterator generating functions begin() and end() denote the beginning and end of a list, respectively. An insert using one of these is equivalent to push_front() or push_back(), respectively. If we specify only one iterator, the default element value is inserted.

// insert default type at beginning of list
 list_eleven.insert(list_eleven.begin()); 
 // insert widget 8 at end of list
 list_eleven.insert(list_eleven.end(), Widget(8));
 

Iteration Invalidation

An iterator can denote a location in the middle of a list. There are several ways to produce this iterator. For example, we can use the result of any of the searching operations described in Chapter 13 (Searching Opertations), such as an invocation of the find() generic algorithm. The new value is inserted immediately prior to the location denoted by the iterator. The insert() operation itself returns an iterator denoting the location of the inserted value. This result value was ignored in the invocations shown above.

   //  find the location of the first occurrence of the 
    //     value 5 in list
    list<int>::iterator location = 
         find(list_nine.begin(), list_nine.end(), 5);
    // and insert an 11 immediate before it
    location = list_nine.insert(location, 11);
 

It is also possible to insert a fixed number of copies of an argument value. This form of insert() does not yield the location of the values.

   line_nine.insert (location, 5, 12);       // insert five twelves
 

Finally, an entire sequence denoted by an iterator pair can be inserted into a list. Again, no useful value is returned as a result of the insert().

     // insert entire contents of list_ten into list_nine
      list_nine.insert (location, list_ten.begin(), list_ten.end());
 

There are a variety of ways to splice one list into another. A splice differs from an insertion in that the item is simultaneously added to the receiver list and removed from the argument list. For this reason, a splice can be performed very efficiently, and should be used whenever appropriate. As with an insertion, the member function splice() uses an iterator to indicate the location in the receiver list where the splice should be made. The argument is either an entire list, a single element in a list (denoted by an iterator), or a subsequence of a list (denoted by a pair of iterators).

   // splice the last element of list ten
    list_nine.splice (location, list_ten, list_ten.end()); 
    // splice all of list ten
    list_nine.splice (location,  list_ten);
    // splice list 9 back into list 10
    list_ten.splice (list_ten.begin(), list_nine, 
       list_nine.begin(), location);
 

Two ordered lists can be combined into one using the merge() operation. Values from the argument list are merged into the ordered list, leaving the argument list empty. The merge is stable; that is, elements retain their relative ordering from the original lists. As with the generic algorithm of the same name (Chapter 14: Merge Ordered Sequences), two forms are supported. The second form uses the binary function supplied as argument to order values. Not all compilers support the second form. If the second form is desired and not supported, the more general generic algorithm can be used, although this is slightly less efficient.

   // merge with explicit compare function
    list_eleven.merge(list_six, widgetCompare);
 
    //the following is similar to the above
    list<Widget> list_twelve;
    merge (list_eleven.begin(), list_eleven.end(), 
       list_six.begin(), list_six.end(), 
       inserter(list_twelve, list_twelve.begin()), widgetCompare);
    list_eleven.swap(list_twelve);
 

Just as there are a number of different ways to insert an element into a list, there are a variety of ways to remove values from a list. The most common operations used to remove a value are pop_front() or pop_back(), which delete the single element from the front or the back of the list, respectively. These member functions simply remove the given element, and do not themselves yield any useful result. If a destructor is defined for the element type it will be invoked as the element is removed. To look at the values before deletion, use the member functions front() or back().

The erase() operation can be used to remove a value denoted by an iterator. For a list, the argument iterator, and any other iterators that denote the same location, become invalid after the removal, but iterators denoting other locations are unaffected. We can also use erase() to remove an entire subsequence, denoted by a pair of iterators. The values beginning at the initial iterator and up to, but not including, the final iterator are removed from the list. Erasing elements from the middle of a list is an efficient operation, unlike erasing elements from the middle of a vector or a deque.

   list_nine.erase (location);
 
    // erase values between the first occurrence of 5 
    // and the following occurrence of 7
 list<int>::iterator
    location = find(list_nine.begin(), list_nine.end(), 5);
    list<int>::iterator location2 = 
        find(location, list_nine.end(), 7);
    list_nine.erase (location, location2);
 

The remove() member function removes all occurrences of a given value from a list. A variation, remove_if(), removes all values that satisfy a given predicate. An alternative to the use of either of these is to use the remove() or remove_if() generic algorithms (Chapter 13: Remove Unwanted Elements). The generic algorithms do not reduce the size of the list, instead they move the elements to be retained to the front of the list, leave the remainder of the list unchanged, and return an iterator denoting the location of the first unmodified element. This value can be used in conjunction with the erase() member function to remove the remaining values.

   list_nine.remove(4);                         // remove all fours
    list_nine.remove_if(divisibleByThree);     //remove any div by 3
 
    // the following is equivalent to the above
    list<int>::iterator location3 = 
     remove_if(list_nine.begin(), list_nine.end(), 
               divisibleByThree);
    list_nine.erase(location3, list_nine.end());
 

The operation unique() will erase all but the first element from every consecutive group of equal elements in a list. The list need not be ordered. An alternative version takes a binary function, and compares adjacent elements using the function, removing the second value in those situations were the function yields a true value. As with remove_if(), not all compilers support the second form of unique(). In this case the more general unique() generic algorithm can be used (see Chapter 13: Remove Overruns of Similar Values). In the following example the binary function is the greater-than operator, which will remove all elements smaller than a preceding element.

   // remove first from consecutive equal elements
    list_nine.unique();
 
    // explicitly give comparison function
    list_nine.unique(greater<int>());
 
    // the following is equivalent to the above
    location3 = 
         unique(list_nine.begin(), list_nine.end(), greater<int>());
    list_nine.erase(location3, list_nine.end());
 

The member function size() will return the number of elements being held by a container. The function empty() will return true if the container is empty, and is more efficient than comparing the size against the value zero.

   cout << "Number of elements: " << list_nine.size () << endl;
    if ( list_nine.empty () )
       cout << "list is empty " << endl;
    else
       cout << "list is not empty " << endl;
 

The member function resize() changes the size of the list to the value specified by the argument. Values are either added or erased from the end of the collection as necessary. An optional second argument can be used to provide the initial value for any new elements added to the collection.

   // become size 12, adding values of 17 if necessary
    list_nine.resize (12, 17); 

The member functions front() and back() return, but do not remove, the first and last items in the container, respectively. For a list, access to other elements is possible only by removing elements (until the desired element becomes the front or back) or through the use of iterators.

There are three types of iterators that can be constructed for lists. The functions begin() and end() construct iterators that traverse the list in forward order. For the list data type begin() and end() create bidirectional iterators. The alternative functions rbegin() and rend() construct iterators that traverse in reverse order, moving from the end of the list to the front.

The list data types do not directly provide any method that can be used to determine if a specific value is contained in the collection. However, either the generic algorithms find() or count() (Chapter 13: Find an Element Satisfying a Condition and Count the Number of Elements that Satisfy a Condition) can be used for this purpose. The following statements, for example, test to see whether an integer list contains the element 17.

int num = 0;
 count(list_five.begin(), list_five.end(), 17, num);
 if (num > 0)
    cout << "contains a 17" << endl;
 else
    cout << "does not contain a 17" << endl;
 
 if (find(list_five.begin(), list_five.end(), 17) != list_five.end())
    cout << "contains a 17" << endl;
 else
    cout << "does not contain a 17" << endl;
 

The member function sort() places elements into ascending order. If a comparison operator other than < is desired, it can be supplied as an argument.

list_ten.sort ( );                  // place elements into sequence
 list_twelve.sort (widgetCompare);       // sort with widget compare
                                         // function
 

Once a list has been sorted, a number of the generic algorithms for ordered collections can be used with lists. These are described in detail in Chapter 14.

The various forms of searching functions described in Chapter 13, namely find(), find_if(), adjacent find(), mismatch(), max_element(), min_element() or search() can be applied to list. In all cases the result is an iterator, which can be dereferenced to discover the denoted element, or used as an argument in a subsequent operation.

Verify Search Results

A number of operations can be applied to lists in order to transform them in place. Some of these are provided as member functions. Others make use of some of the generic functions described in Chapter 13.

For a list, the member function reverse() reverses the order of elements in the list.

   list_ten.reverse();                 // elements are now reversed
 

The generic algorithm transform() (Chapter 13: Transform One or Two Sequences) can be used to modify every value in a container, by simply using the same container as both input and as result for the operation. The following, for example, increments each element of a list by one. To construct the necessary unary function, the first argument of the binary integer addition function is bound to the value one. The version of transform() that manipulates two parallel sequences can be used in a similar fashion.

   transform(list_ten.begin(), list_ten.end(), 
       list_ten.begin(), bind1st(plus<int>(), 1));
 

Similarly, the functions replace() and replace_if() (Section 12.4.2) can be used to replace elements of a list with specific values. Rotations ( Chapter 13: Rotate Elements Around a Midpoint) and partitions (Chapter 13: Partition a Sequence...), can also be performed with lists.

   // find the location of the value 5, and rotate around it
    location = find(list_ten.begin(), list_ten.end(), 5);
    rotate(list_ten.begin(), location, list_ten.end());
    // now partition using values greater than 7
    partition(list_ten.begin(), list_ten.end(), 
          bind2nd(greater<int>(), 7));
 

The functions next_permutation() and prev_permutation() (Chapter 13: Generate Permutations in Sequence) can be used to generate the next permutation (or previous permutation) of a collection of values.

   next_permutation (list_ten.begin(), list_ten.end());
 

The algorithm for_each() (Section 13: Apply a Function to All Elements...) will apply a function to every element of a collection. An illustration of this use will be given in the radix sort example program in the section on the deque data structure.

The accumulate() generic algorithm reduces a collection to a scalar value (see Chapter 13: Reduce Sequence to a Single Value). This can be used, for example, to compute the sum of a list of numbers. A more unusual use of accumulate() will be illustrated in the radix sort example.

   cout << "Sum of list is: " << 
          accumulate(list_ten.begin(), list_ten.end(), 0) << endl;
 

Two lists can be compared against each other. They are equal if they are the same size and all corresponding elements are equal. A list is less than another list if it is lexicographically smaller (see Chapter 13: Generalized Inner Product).