cppdraft_translate/cppdraft/list/ops.md

[list.ops]

# 23 Containers library [[containers]](./#containers)

## 23.3 Sequence containers [[sequences]](sequences#list.ops)

### 23.3.11 Class template list [[list]](list#ops)

#### 23.3.11.5 Operations [list.ops]

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9427)

Since lists allow fast insertion and erasing from the middle of a list, certain
operations are provided specifically for them[.](#1.sentence-1)[196](#footnote-196 "As specified in [allocator.requirements], the requirements in this Clause apply only to lists whose allocators compare equal.")

In this subclause,
arguments for a template parameter
named Predicate or BinaryPredicate shall meet the corresponding requirements in [[algorithms.requirements]](algorithms.requirements "26.2 Algorithms requirements")[.](#1.sentence-2)

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[.](#1.sentence-3)

For merge and sort,
the definitions and requirements in [[alg.sorting]](alg.sorting "26.8 Sorting and related operations") apply[.](#1.sentence-4)

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9446)

list provides three splice operations that destructively move elements from one list to
another[.](#2.sentence-1)

The behavior of splice operations is undefined if get_allocator() != x.get_allocator()[.](#2.sentence-2)

[🔗](#lib:splice,list)

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

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9458)

*Preconditions*: addressof(x) != this is true[.](#3.sentence-1)

[4](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9462)

*Effects*: Inserts the contents ofx beforeposition andx becomes empty[.](#4.sentence-1)

Pointers and references to the moved elements ofx now refer to those same elements but as members of*this[.](#4.sentence-2)

Iterators referring to the moved elements will continue to refer to their
elements, but they now behave as iterators into*this,
not intox[.](#4.sentence-3)

[5](#5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9481)

*Throws*: Nothing[.](#5.sentence-1)

[6](#6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9485)

*Complexity*: Constant time[.](#6.sentence-1)

[🔗](#lib:splice,list_)

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

[7](#7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9497)

*Preconditions*: i is a valid dereferenceable iterator of x[.](#7.sentence-1)

[8](#8)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9501)

*Effects*: Inserts an element pointed to byi from listx before position and removes the element fromx[.](#8.sentence-1)

The result is unchanged ifposition == i orposition == ++i[.](#8.sentence-2)

Pointers and references to*i continue to refer to this same element but as a member of*this[.](#8.sentence-3)

Iterators
to*i (includingi itself) continue to refer to the same element, but now behave as iterators into*this,
not intox[.](#8.sentence-4)

[9](#9)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9527)

*Throws*: Nothing[.](#9.sentence-1)

[10](#10)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9531)

*Complexity*: Constant time[.](#10.sentence-1)

[🔗](#lib:splice,list__)

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

[11](#11)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9545)

*Preconditions*: [first, last) is a valid range in x[.](#11.sentence-1)

position is not an iterator in the range [first, last)[.](#11.sentence-2)

[12](#12)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9550)

*Effects*: Inserts elements in the range
[first, last)
beforeposition and removes the elements fromx[.](#12.sentence-1)

Pointers and references to the moved elements ofx now refer to those same elements but as members of*this[.](#12.sentence-2)

Iterators referring to the moved elements will continue to refer to their
elements, but they now behave as iterators into*this,
not intox[.](#12.sentence-3)

[13](#13)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9568)

*Throws*: Nothing[.](#13.sentence-1)

[14](#14)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9572)

*Complexity*: Constant time ifaddressof(x) == this;
otherwise, linear time[.](#14.sentence-1)

[🔗](#lib:remove,list)

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

[15](#15)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9586)

*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[.](#15.sentence-1)

Invalidates only the iterators and references to the erased elements[.](#15.sentence-2)

[16](#16)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9592)

*Returns*: The number of elements erased[.](#16.sentence-1)

[17](#17)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9596)

*Throws*: Nothing unless an exception is thrown by*i == value orpred(*i) != false[.](#17.sentence-1)

[18](#18)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9603)

*Complexity*: Exactlysize() applications of the corresponding predicate[.](#18.sentence-1)

[19](#19)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9609)

*Remarks*: [Stable](algorithm.stable "16.4.6.8 Requirements for stable algorithms [algorithm.stable]")[.](#19.sentence-1)

[🔗](#lib:unique,list)

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

[20](#20)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9621)

Let binary_pred be equal_to<>{} for the first overload[.](#20.sentence-1)

[21](#21)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9624)

*Preconditions*: binary_pred is an equivalence relation[.](#21.sentence-1)

[22](#22)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9628)

*Effects*: Erases all but the first element from every
consecutive group of equivalent elements[.](#22.sentence-1)

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[.](#22.sentence-2)

Invalidates only the iterators and references to the erased elements[.](#22.sentence-3)

[23](#23)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9637)

*Returns*: The number of elements erased[.](#23.sentence-1)

[24](#24)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9641)

*Throws*: Nothing unless an exception is thrown by the predicate[.](#24.sentence-1)

[25](#25)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9645)

*Complexity*: If empty() is false,
exactly size() - 1 applications of the corresponding predicate,
otherwise no applications of the predicate[.](#25.sentence-1)

[🔗](#lib:merge,list)

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

[26](#26)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9661)

Let comp be less<> for the first two overloads[.](#26.sentence-1)

[27](#27)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9664)

*Preconditions*: *this and x are both sorted
with respect to the comparator comp, andget_allocator() == x.get_allocator() is true[.](#27.sentence-1)

[28](#28)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9670)

*Effects*: If addressof(x) == this, there are no effects[.](#28.sentence-1)

Otherwise, merges
the two sorted ranges [begin(), end()) and [x.begin(), x.end())[.](#28.sentence-2)

The result is a range
that is sorted with respect to the comparator comp[.](#28.sentence-3)

Pointers and references to the moved elements of x now refer to those same elements
but as members of *this[.](#28.sentence-4)

Iterators referring to the moved elements will continue to
refer to their elements, but they now behave as iterators into *this, not intox[.](#28.sentence-5)

[29](#29)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9682)

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

[30](#30)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9688)

*Remarks*: Stable ([[algorithm.stable]](algorithm.stable "16.4.6.8 Requirements for stable algorithms"))[.](#30.sentence-1)

If addressof(x) != this, x is empty after the merge[.](#30.sentence-2)

No elements are copied by this operation[.](#30.sentence-3)

If an exception is thrown other than by a comparison, there are no effects[.](#30.sentence-4)

[🔗](#lib:reverse,list)

`constexpr void reverse() noexcept;
`

[31](#31)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9702)

*Effects*: Reverses the order of the elements in the list[.](#31.sentence-1)

Does not affect the validity of iterators and references[.](#31.sentence-2)

[32](#32)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9707)

*Complexity*: Linear time[.](#32.sentence-1)

[🔗](#lib:sort,list)

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

[33](#33)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9719)

*Effects*: Sorts the list according to the operator< or a Compare function object[.](#33.sentence-1)

If an exception is thrown,
the order of the elements in *this is unspecified[.](#33.sentence-2)

Does not affect the validity of iterators and references[.](#33.sentence-3)

[34](#34)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9726)

*Complexity*: ApproximatelyNlogN comparisons, where N is size()[.](#34.sentence-1)

[35](#35)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/containers.tex#L9732)

*Remarks*: [Stable](algorithm.stable "16.4.6.8 Requirements for stable algorithms [algorithm.stable]")[.](#35.sentence-1)

[196)](#footnote-196)[196)](#footnoteref-196)

As specified
in [[allocator.requirements]](allocator.requirements "16.4.4.6 Cpp17Allocator requirements"), the requirements in this Clause apply only to
lists whose allocators compare equal[.](#footnote-196.sentence-1)