template<class Predicate> void remove_if( Predicate p); [4] | Removes all elements *i such that p(*i) is true. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() applications of p. |
void unique(); | Removes all but the first element in every consecutive group of equal elements. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() – 1 comparisons for equality. |
template<class BinaryPredicate> void unique( BinaryPredicate p); [4] | Removes all but the first element in every consecutive group of equivalent elements, where two elements *i and *j are considered equivalent if p(*i, *j) is true. The relative order of elements that are not removed is unchanged, and iterators to elements that are not removed remain valid. This function is linear time: it performs exactly size() – 1 comparisons for equality. |
void merge(list<T, Alloc>& x); | Both *this and x must be sorted according to operator<, and they must be distinct. (That is, it is required that &x != this.) This function removes all of x's elements and inserts them in order into *this. The merge is stable; that is, if an element from *this is equivalent to one from x, then the element from *this will precede the one from x. All iterators to elements in *this and x remain valid. This function is linear time: it performs at most size() + x.size() – 1 comparisons. |
template<class BinaryPredicate> void merge(list<T, Alloc>& x, BinaryPredicate Comp); [4] | Comp must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements) on objects of type T, and both *this and x must be sorted according to that ordering. The lists x and *this must be distinct. (That is, it is required that &x != this.) This function removes all of x's elements and inserts them in order into *this. The merge is stable; that is, if an element from *this is equivalent to one from x, then the element from *this will precede the one from x. All iterators to elements in *this and x remain valid. This function is linear time: it performs at most size() + x.size() – 1 applications of Comp. |
void reverse(); | Reverses the order of elements in the list. All iterators remain valid and continue to point to the same elements. [5] This function is linear time. |
void sort(); | Sorts *this according to operator< . The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. [6] The number of comparisons is approximately N log N , where N is the list 's size. |
template<class BinaryPredicate> void sort(BinaryPredicate comp); [4] | Comp must be a comparison function that induces a strict weak ordering (as defined in the LessThan Comparable requirements on objects of type T. This function sorts the list *this according to Comp. The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. [6] The number of comparisons is approximately N log N, where N is the list's size. |
Notes [1] A comparison with vector is instructive. Suppose that i is a valid vector<T>::iterator. If an element is inserted or removed in a position that precedes i, then this operation will either result in i pointing to a different element than it did before, or else it will invalidate i entirely. (A vector<T>::iterator will be invalidated, for example, if an insertion requires a reallocation.) However, suppose that i and j are both iterators into a vector , and there exists some integer n such that i == j + n. In that case, even if elements are inserted into the vector and i and j point to different elements, the relation between the two iterators will still hold. A list is exactly the opposite: iterators will not be invalidated, and will not be made to point to different elements, but, for list iterators, the predecessor/successor relationship is not invariant.
[2] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. If your compiler supports member templates, you can call this function with any type of input iterator. If your compiler does not yet support member templates, though, then the arguments must either be of type const value_type* or of type list::const_iterator.
[3] A similar property holds for all versions of insert() and erase() . List<T, Alloc>::insert() never invalidates any iterators, and list<T, Alloc>::erase() only invalidates iterators pointing to the elements that are actually being erased.
[4] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. You can only use this member function if your compiler
