26 Containers library [containers]

26.3 Sequence containers [sequences]

26.3.10 Class template list [list]

26.3.10.5 list operations [list.ops]

Since lists allow fast insertion and erasing from the middle of a list, certain operations are provided specifically for them.259

list provides three splice operations that destructively move elements from one list to another. The behavior of splice operations is undefined if get_­allocator() != x.get_­allocator().

void splice(const_iterator position, list& x); void splice(const_iterator position, list&& x);

Requires: &x != this.

Effects: Inserts the contents of x before position and x becomes empty. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.

Throws: Nothing.

Complexity: Constant time.

void splice(const_iterator position, list& x, const_iterator i); void splice(const_iterator position, list&& x, const_iterator i);

Requires: i is a valid dereferenceable iterator of x.

Effects: Inserts an element pointed to by i from list x before position and removes the element from x. The result is unchanged if position == i or position == ++i. Pointers and references to *i continue to refer to this same element but as a member of *this. Iterators to *i (including i itself) continue to refer to the same element, but now behave as iterators into *this, not into x.

Throws: Nothing.

Complexity: Constant time.

void splice(const_iterator position, list& x, const_iterator first, const_iterator last); void splice(const_iterator position, list&& x, const_iterator first, const_iterator last);

Requires: [first, last) is a valid range in x. The program has undefined behavior if position is an iterator in the range [first, last).

Effects: Inserts elements in the range [first, last) before position and removes the elements from x. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.

Throws: Nothing.

Complexity: Constant time if &x == this; otherwise, linear time.

void remove(const T& value); template <class Predicate> void remove_if(Predicate pred);

Effects: Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value, pred(*i) != false. Invalidates only the iterators and references to the erased elements.

Throws: Nothing unless an exception is thrown by *i == value or pred(*i) != false.

Remarks: Stable.

Complexity: Exactly size() applications of the corresponding predicate.

void unique(); template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);

Effects: Erases all but the first element from every consecutive group of equal elements referred to by the iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version of unique with no arguments) or pred(*i, *(i - 1)) (for the version of unique with a predicate argument) holds. Invalidates only the iterators and references to the erased elements.

Throws: Nothing unless an exception is thrown by *i == *(i-1) or pred(*i, *(i - 1))

Complexity: If the range [first, last) is not empty, exactly (last - first) - 1 applications of the corresponding predicate, otherwise no applications of the predicate.

void merge(list& x); void merge(list&& x); template <class Compare> void merge(list& x, Compare comp); template <class Compare> void merge(list&& x, Compare comp);

Requires: comp shall define a strict weak ordering, and both the list and the argument list shall be sorted according to this ordering.

Effects: If (&x == this) does nothing; otherwise, merges the two sorted ranges [begin(), end()) and [x.​begin(), x.end()). The result is a range in which the elements will be sorted in non-decreasing order according to the ordering defined by comp; that is, for every iterator i, in the range other than the first, the condition comp(*i, *(i - 1)) will be false. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.

Remarks: Stable. If (&x != this) the range [x.begin(), x.end()) is empty after the merge. No elements are copied by this operation. The behavior is undefined if get_­allocator() != x.get_­allocator().

Complexity: At most size() + x.size() - 1 applications of comp if (&x != this); otherwise, no applications of comp are performed. If an exception is thrown other than by a comparison there are no effects.

void reverse() noexcept;

Effects: Reverses the order of the elements in the list. Does not affect the validity of iterators and references.

Complexity: Linear time.

void sort(); template <class Compare> void sort(Compare comp);

Requires: operator< (for the first version) or comp (for the second version) shall define a strict weak ordering.

Effects: Sorts the list according to the operator< or a Compare function object. If an exception is thrown, the order of the elements in *this is unspecified. Does not affect the validity of iterators and references.

Remarks: Stable.

Complexity: Approximately NlogN comparisons, where N == size().

As specified in [allocator.requirements], the requirements in this Clause apply only to lists whose allocators compare equal.