Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library User's Guide

6.2 list Operations

In this section, each of the member functions provided by the list datatype are described in more detail. These member functions provide the basic operations for lists. They can be greatly extended through the generic algorithms described in Chapter 13.

6.2.1 Declaration and Initialization of lists

A list may contain elements of a primitive language type, such as an int or double, a pointer type, or a user-defined type. A user-defined type must implement a copy constructor, as this constructor is used to initialize newly created elements.

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 list will maintain. A list declared in this fashion initially contains no elements:


NOTE -- If you declare a container as holding pointers, you are responsible for managing the memory for the objects pointed to. The container classes will not automatically free memory for these objects when an item is erased from the container.

An alternative form of declaration creates a collection that initially contains some number of equal elements. The constructor takes two arguments, a size and an initial value. The second argument is optional if the contained type has a default constructor. If only the number of initial elements to be created is given, these values are initialized with the default constructor; otherwise the elements are initialized with the value of the second argument:

lists can also be initialized using elements from another collection, with 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 C++ Standard Library that support iterators.

The insert() operation can also be used to place values denoted by an iterator into a list (Section 6.2.3). Insert iterators can be used to initialize a list with a sequence of values produced by a generator (Section 13.2.3). This is illustrated by the following:

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.

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 is invoked for the elements being removed. There are two forms of assign():

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

6.2.2 Type Definitions

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

In addition to iterator, list defines the following types:

Table 11: Type definitions for class list

Type Definition

value_type

The type of the elements maintained by the list.

const_iterator

An iterator that does not allow modification of the underlying sequence.

reverse_iterator

An iterator that moves in a backward direction.

const_reverse_iterator

A combination constant and reverse iterator.

reference

A reference to an underlying element.

const_reference

A reference to an underlying element that will not permit the element to be modified.

pointer

A pointer to an underlying element

const_pointer

A constant pointer to an underlying element.

size_type

An unsigned integer type, used to refer to the size of containers.

difference_type

A signed integer type, used to describe distances between iterators.

allocator_type

The allocator type used for all storage management by the list.

6.2.3 Placing Elements into a list

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:

In Section 6.2.1 we noted how values can be placed into a list at a location denoted by an iterator with the aid of an insert iterator and the std::copy() or std::generate() generic algorithm. 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:

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 Section 13.3, such as an invocation of the find() generic algorithm:

Here 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.


NOTE -- Unlike a vector or deque, insertions or removals from the middle of a list will not invalidate references or pointers to other elements in the container. This property can be important if two or more iterators are being used to refer to the same container.

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:

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

6.2.3.1 Splicing

There are several 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 source list. For this reason, a splice can be performed 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 sub-sequence of a list (denoted by a pair of iterators).

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 (Section 14.5), two forms are supported. The first form uses the operator<() defined for the contained type. The second form uses the binary function supplied as argument to order values, but not all compilers suppor 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:

6.2.4 Removing Elements

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. If a destructor is defined for the element type, it is invoked as the element is removed. These member functions simply remove the given element, and do not themselves yield a result. To retrieve 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 sub-sequence 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:

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 either of these are the remove() or remove_if() generic algorithms (Section 13.5.1). 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.

The member function unique() erases duplicate elements from a list. To do this, the function iterates over the list and removes every element that is equal to the preceeding element. An alternative version takes a binary function and compares adjacent elements using the function, removing the second value in those situations where the function yields a true value. The more general unique() generic algorithm can also be used (Section 13.5.2). In the following example, the binary function is the greater-than operator, which removes all elements smaller than a preceding element:

6.2.5 Extent and Size-Changing Operations

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

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:

6.2.6 Access and Iteration

The member functions front() and back() return, but do not remove, the first and last items in the container, respectively. A list does not provide random access. Access to elements other than the first and last elements is possible only by removing elements until the desired element becomes the front or back element, or by using 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 datatype, 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.

6.2.7 Test for Inclusion

The list datatypes do not directly provide any method that can be used to determine if a specific value is contained in the collection. However, either of the generic algorithms std::find() or std::count() can be used for this purpose (Section 13.3.1 and Section 13.6.1). For example, to test whether an integer list contains the element 17:

If your compiler does not support partial specialization, then you must use the following interface instead:

6.2.8 Sorting and Sorted list Operations

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

Once a list has been sorted, a number of the generic algorithms for ordered collections can be used with lists (Chapter 14).

6.2.9 Searching Operations

The various forms of searching functions described in Chapter 13.3, namely std::find(), std::find_if(), std::adjacent_find(), std::mismatch(), std::max_element(), std::min_element(), or std::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.


NOTE -- The searching algorithms in the C++ Standard Library always return the end of range iterator if no element matching the search condition is found. Unless the result is guaranteed to be valid, it is a good idea to check for the end of range condition.

6.2.10 In-Place Transformations

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:

The generic algorithm std::transform() can be used to modify every value in a container by simply using the same container as both input and result for the operation (Section 13.7.1). For example, the following code 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 1 using the bind1st function adapter (Section 3.5). The version of std::transform() that manipulates two parallel sequences can also be used this way.

Similarly, the functions std::replace() and std::replace_if() can be used to replace elements of a list with specific values (Section 13.4.2). Rotations and partitions can also be performed with lists (Section 13.4.3 and Section 13.4.4):

The functions std::next_permutation() and std::prev_permutation() can be used to generate the next permutation (or previous permutation) of a collection of values (Section 13.4.5):

6.2.11 Other Operations

The algorithm std::for_each() applies a function to every element of a collection (Section 13.8). An illustration of this use is given in the radix sort example program in the section on the deque data structure (Section 7.3).

The std::accumulate() generic algorithm reduces a collection to a scalar value (Chapter 13.6.2). This can be used, for example, to compute the sum of a list of numbers. A more unusual use of std::accumulate() is illustrated in the radix sort example from Section 7.3:

Two lists can be compared against each other using the std::lexicographical_compare() algorithm (Section 13.6.5). The lists 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.



Previous fileTop of DocumentContentsIndex pageNext file