ADTlist and the STL list Container Class
The list is probably the abstract data type most useful to humans in general in their daily lives, and is extremely useful to programmers as well. The usual ADT interface for a list as found in most textbooks on data structures is further enhanced by additional operations found in the STL list implementation. As befits an "industrial strength" container class, the STL list provides many variations on the usual operations in the standard list interface, for maximal flexibility.
| list Operations | |
|---|---|
| Generic (ADT) | Specific (STL) |
| Construct a list |
list<T> lst; list<T> lst(num); list<T> lst(num, someValueOfTypeT); list<T> lst(otherList); list<T> lst(inputIter1, inputIter2); |
| Test for emptiness | empty() |
| Add one or more values | |
| Add value to back | push_back(val) |
| Add value to front | push_front(val) |
| Insert values |
insert(iter, val) insert(iter, num, val) insert(iter, startIter, endIter) |
| Assign values |
assign(num, val) assign(startIter, endIter) |
| Remove one or more values | |
| Remove all values | clear() |
| Remove value pointed to | erase(iter) |
| Remove a range of values | erase(startIter, endIter) |
| Remove value from back | pop_back() |
| Remove value from front | pop_front() |
| Remove all copies of one value | remove(val) |
| Remove all values satisfying a criterion | remove_if(booleanFunction) |
| Remove consecutive duplicate elements | unique(startIter, endIter) |
| Retrieve a value from a list (without removing it) | |
| Get value at front | front() |
| Get value at back | back() |
| Retrieve size | |
| Get current size | size() |
| Get maximum size | max_size() |
| Miscellaneous operations affecting the entire container | |
| Change size |
resize(num) resize(num, val) |
| Exchange contents of self with another list | swap(otherList) |
| Reverse the order of the values | reverse(startIter, endIter) |
| Sort the values | sort(startIter, endIter) |
| Combining part or all of one list with another | |
| Merge self with another list | merge(otherList) |
| Splice elements from another list into self |
splice(iter, otherList) splice(iter, otherList, otherIter) splice(iter, otherList, otherStartIter, otherEndIter) |
The following STL "best practice" applies to use of the list container: For those operations whose names are identical to the names of general STL algorithms (merge, remove, remove_if, reverse, sort, swap, and unique), the list-specific versions are to be preferred when working with lists. And, by the way, similar advice applies as well to other STL containers when a choice can be made between using a member function and using an algorithm.
The list<T>::iterator and list<T>::reverse_iterator iterators are bidirectional access iterators, the second-most powerful kind of STL iterator. The member function begin() returns an iterator pointing at the first element of the list, while end() is a member function returning an iterator pointing at the position "one past the end" of the list. Analogously, rbegin() and rend() return iterators pointing at the last and "one before the first" positions, respectively.
Note that the at() member function and index access via [ ] are not supported, but the bidirectional iterators supported by the list container do permit a different kind of access to any element in a list.
A list is useful when the order of the components and fast insertion and deletion at arbitrary locations are important. If insertion and deletion only take place at the ends, lists are not as efficient as deques.
The list class is one of the three "sequential" container classes in the STL (the vector and the deque are the other two). Lists provide many of the same operations as vectors and deques. However, the list class also provides a number of "high-powered" list operations like "splice" and "merge" that are not found in the other sequence containers.