24 Containers library [containers]

24.3 Sequence containers [sequences]

24.3.10 Class template list [list]

24.3.10.5 Operations [list.ops]

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

In this subclause, arguments for a template parameter named Predicate or BinaryPredicate shall meet the corresponding requirements in [algorithms.requirements].

The semantics of i + n and i - n, where i is an iterator into the list and n is an integer, are the same as those of next(i, n) and prev(i, n), respectively.

For merge and sort, the definitions and requirements in [alg.sorting] apply.

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);

Preconditions: addressof(x) != this is true.

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);

Preconditions: 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);

Preconditions: [first, last) is a valid range in x.

position is not 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 addressof(x) == this; otherwise, linear time.

🔗

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

Effects: Erases all the elements in the list referred to 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.

Returns: The number of elements erased.

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

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

Remarks: Stable ([algorithm.stable]).

🔗

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

Let binary_pred be equal_to<>{} for the first overload.

Preconditions: binary_pred is an equivalence relation.

Effects: Erases all but the first element from every consecutive group of equivalent elements.

That is, for a nonempty list, erases all elements referred to by the iterator i in the range [begin() + 1, end()) for which binary_pred(*i, *(i - 1)) is true.

Invalidates only the iterators and references to the erased elements.

Returns: The number of elements erased.

Throws: Nothing unless an exception is thrown by the predicate.

Complexity: If empty() is false, exactly size() - 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);

Let comp be less<> for the first two overloads.

Preconditions: *this and x are both sorted with respect to the comparator comp, and get_allocator() == x.get_allocator() is true.

Effects: If addressof(x) == this, there are no effects.

Otherwise, merges the two sorted ranges [begin(), end()) and [x.begin(), x.end()).

The result is a range that is sorted with respect to the comparator comp.

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.

Complexity: At most size() + x.size() - 1 comparisons if addressof(x) != this; otherwise, no comparisons are performed.

Remarks: Stable ([algorithm.stable]).

If addressof(x) != this, x is empty after the merge.

No elements are copied by this operation.

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);

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.

Complexity: Approximately

N log N

comparisons, where N == size().

Remarks: Stable ([algorithm.stable]).

209)209)

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