From: dgregor_at_[hidden]
Date: 2008-05-16 11:46:01
Author: dgregor
Date: 2008-05-16 11:46:01 EDT (Fri, 16 May 2008)
New Revision: 45427
URL: http://svn.boost.org/trac/boost/changeset/45427
Log:
Conceptualize list
Text files modified:
sandbox/committee/concepts/stdlib/clib-containers.tex | 760 +++++++++++++++++++++++++++++++++++++++
1 files changed, 750 insertions(+), 10 deletions(-)
Modified: sandbox/committee/concepts/stdlib/clib-containers.tex
==============================================================================
--- sandbox/committee/concepts/stdlib/clib-containers.tex (original)
+++ sandbox/committee/concepts/stdlib/clib-containers.tex 2008-05-16 11:46:01 EDT (Fri, 16 May 2008)
@@ -1223,24 +1223,26 @@
\begin{codeblock}
namespace std {
- template <class T, class Allocator = allocator<T> > class list;
- template <class T, class Allocator>
+ template <@\changedConcepts{class}{ObjectType}@ T, class Allocator = allocator<T> >
+ @\addedConcepts{requires Destructible<T>}@
+ class list;
+ template <@\changedConcepts{class}{EqualityComparable}@ T, class Allocator>
bool operator==(const list<T,Allocator>& x, const list<T,Allocator>& y);
- template <class T, class Allocator>
+ template <@\changedConcepts{class}{LessThanComparable}@ T, class Allocator>
bool operator< (const list<T,Allocator>& x, const list<T,Allocator>& y);
- template <class T, class Allocator>
+ template <@\changedConcepts{class}{EqualityComparable}@ T, class Allocator>
bool operator!=(const list<T,Allocator>& x, const list<T,Allocator>& y);
- template <class T, class Allocator>
+ template <@\changedConcepts{class}{LessThanComparable}@ T, class Allocator>
bool operator> (const list<T,Allocator>& x, const list<T,Allocator>& y);
- template <class T, class Allocator>
+ template <@\changedConcepts{class}{LessThanComparable}@ T, class Allocator>
bool operator>=(const list<T,Allocator>& x, const list<T,Allocator>& y);
- template <class T, class Allocator>
+ template <@\changedConcepts{class}{LessThanComparable}@ T, class Allocator>
bool operator<=(const list<T,Allocator>& x, const list<T,Allocator>& y);
- template <class T, class Allocator>
+ template <@\changedConcepts{class}{ObjectType}@ T, class Allocator>
void swap(list<T,Allocator>& x, list<T,Allocator>& y);
- template <class T, class Allocator>
+ template <@\changedConcepts{class}{ObjectType}@ T, class Allocator>
void swap(list<T,Allocator>&& x, list<T,Allocator>& y);
- template <class T, class Allocator>
+ template <@\changedConcepts{class}{ObjectType}@ T, class Allocator>
void swap(list<T,Allocator>& x, list<T,Allocator>&& y);
}
\end{codeblock}
@@ -2514,6 +2516,744 @@
\effects \tcode{x.swap(y)}
\end{itemdescr}
+\rSec2[list]{Class template \tcode{list}}
+
+\pnum
+\index{list@\tcode{list}}%
+A
+\tcode{list}\
+is a sequence container that supports
+bidirectional iterators and allows constant time insert and erase
+operations anywhere within the sequence, with storage management handled
+automatically. Unlike vectors (\ref{vector}) and deques (\ref{deque}),
+fast random access to list elements is not supported, but many
+algorithms only need sequential access anyway.
+
+\pnum
+A \tcode{list}\ satisfies all of the requirements of a container, of
+a reversible container (given in two tables in
+\ref{container.requirements}), of a sequence container,
+including most of the the optional sequence container
+requirements (\ref{sequence.reqmts}), and of an allocator-aware container (Table~\ref{tab:containers.allocatoraware}).
+The exceptions are the
+\tcode{operator[]}\
+and
+\tcode{at}\
+member functions, which are not provided.%
+\footnote{
+These member functions are only provided by containers whose iterators
+are random access iterators.
+}
+Descriptions are provided here only for operations on
+\tcode{list}\
+that are not described in one of these tables
+or for operations where there is additional semantic information.
+
+\begin{codeblock}
+namespace std {
+ template <@\changedConcepts{class}{ObjectType}@ T, class Allocator = allocator<T> >
+ @\addedConcepts{requires Destructible<T>}@
+ class list {
+ public:
+ // types:
+ typedef typename Allocator::reference reference;
+ typedef typename Allocator::const_reference const_reference;
+ typedef @\impdef@ iterator; // See \ref{container.requirements}
+ typedef @\impdef@ const_iterator; // See \ref{container.requirements}
+ typedef @\impdef@ size_type; // See \ref{container.requirements}
+ typedef @\impdef@ difference_type;// See \ref{container.requirements}
+ typedef T value_type;
+ typedef Allocator allocator_type;
+ typedef typename Allocator::pointer pointer;
+ typedef typename Allocator::const_pointer const_pointer;
+ typedef std::reverse_iterator<iterator> reverse_iterator;
+ typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+
+ // \ref{list.cons} construct/copy/destroy:
+ explicit list(const Allocator& = Allocator());
+ @\addedConcepts{requires DefaultConstructible<T>}@ explicit list(size_type n);
+ @\addedConcepts{requires CopyConstructible<T>}@
+ list(size_type @\farg{n}@, const T& @\farg{value}@, const Allocator& = Allocator());
+ template <@\changedConcepts{class InputIterator}{InputIterator Iter}@>
+ @\addedConcepts{requires HasConstructor<T, Iter::reference>}@
+ list(@\changedConcepts{InputIterator}{Iter}@ @\farg{first}@, @\changedConcepts{InputIterator}{Iter}@ @\farg{last}@, const Allocator& = Allocator());
+ @\addedConcepts{requires CopyConstructible<T>}@ list(const list<T,Allocator>& @\farg{x}@);
+ list(list&& x);
+ @\addedConcepts{requires CopyConstructible<T>}@ list(const list&, const Allocator&);
+ list(list&&, const Allocator&);
+ ~list();
+ @\addedConcepts{requires CopyAssignable<T>}@ list<T,Allocator>& operator=(const list<T,Allocator>& @\farg{x}@);
+ list<T,Allocator>& operator=(list<T,Allocator>&& x);
+ template <@\changedConcepts{class InputIterator}{InputIterator Iter}@>
+ @\addedConcepts{requires HasCopyAssign<T, Iter::reference> \&\& HasConstructor<T, Iter::reference>}@
+ void assign(@\changedConcepts{InputIterator}{Iter}@ first, @\changedConcepts{InputIterator}{Iter}@ last);
+ @\addedConcepts{requires CopyAssignable<T> \&\& CopyConstructible<T>}@ void assign(size_type n, const T& t);
+ allocator_type get_allocator() const;
+
+ // iterators:
+ iterator begin();
+ const_iterator begin() const;
+ iterator end();
+ const_iterator end() const;
+ reverse_iterator rbegin();
+ const_reverse_iterator rbegin() const;
+ reverse_iterator rend();
+ const_reverse_iterator rend() const;
+
+ const_iterator cbegin() const;
+ const_iterator cend() const;
+ const_reverse_iterator crbegin() const;
+ const_reverse_iterator crend() const;
+
+ // \ref{list.capacity} capacity:
+ bool empty() const;
+ size_type size() const;
+ size_type max_size() const;
+ @\addedConcepts{requires DefaultConstructible<T>}@ void resize(size_type sz);
+ @\addedConcepts{requires CopyConstructible<T>}@ void resize(size_type sz, const T& c);
+
+ // element access:
+ reference front();
+ const_reference front() const;
+ reference back();
+ const_reference back() const;
+
+ // \ref{list.modifiers} modifiers:
+ template <class... Args>
+ @\addedConcepts{requires HasConstructor<T, Args\&\&...>}@
+ void push_front(Args&&... args);
+ void pop_front();
+ template <class... Args>
+ @\addedConcepts{requires HasConstructor<T, Args\&\&...>}@
+ void push_back(Args&&... args);
+ void pop_back();
+
+ template <class... Args>
+ @\addedConcepts{requires HasConstructor<T, Args\&\&...>}@
+ iterator emplace(const_iterator position, Args&&... args);
+ @\addedConcepts{requires CopyConstructible<T>}@ iterator insert(const_iterator @\farg{position}@, const T& @\farg{x}@);
+ @\addedConcepts{requires MoveConstructible<T>}@ iterator insert(const_iterator position, T&& x);
+ @\addedConcepts{requires CopyConstructible<T>}@
+ void insert(const_iterator @\farg{position}@, size_type @\farg{n}@, const T& @\farg{x}@);
+ template <@\changedConcepts{class InputIterator}{InputIterator Iter}@>
+ @\addedConcepts{requires HasConstructor<T, Iter::reference>}@
+ void insert(const_iterator @\farg{position}@, @\changedConcepts{InputIterator}{Iter}@ @\farg{first}@,
+ @\changedConcepts{InputIterator}{Iter}@ @\farg{last}@);
+
+ iterator erase(const_iterator @\farg{position}@);
+ iterator erase(const_iterator @\farg{position}@, const_iterator @\farg{last}@);
+ void swap(list<T,Allocator>&&);
+ void clear();
+
+ // \ref{list.ops} list operations:
+ void splice(const_iterator @\farg{position}@, list<T,Allocator>&& @\farg{x}@);
+ void splice(const_iterator @\farg{position}@, list<T,Allocator>&& @\farg{x}@, const_iterator @\farg{i}@);
+ void splice(const_iterator @\farg{position}@, list<T,Allocator>&& @\farg{x}@,
+ const_iterator @\farg{first}@, const_iterator @\farg{last}@);
+
+ @\addedConcepts{requires EqualityComparable<T>}@ void remove(const T& @\farg{value}@);
+ template <@\changedConcepts{class}{Predicate<auto, T>}@ Pred@\removedConcepts{icate}@> void remove_if(Pred@\removedConcepts{icate}@ @\farg{pred}@);
+
+ @\addedConcepts{requires EqualityComparable<T>}@ void unique();
+ template <@\changedConcepts{class}{Predicate<auto, T, T>}@ BinaryPredicate>
+ void unique(BinaryPredicate @\farg{binary_pred}@);
+
+ @\addedConcepts{requires LessThanComparable<T>}@ void merge(list<T,Allocator>&& @\farg{x}@);
+ template <@\changedConcepts{class}{BinaryPredicate<auto, T, T>}@ Compare>
+ void merge(list<T,Allocator>&& @\farg{x}@, Compare @\farg{comp}@);
+
+ @\addedConcepts{requires LessThanComparable<T>}@ void sort();
+ template <@\changedConcepts{class}{BinaryPredicate<auto, T, T>}@ Compare> void sort(Compare @\farg{comp}@);
+
+ void reverse();
+ };
+
+ template <@\changedConcepts{class}{EqualityComparable}@ T, class Allocator>
+ bool operator==(const list<T,Allocator>& @\farg{x}@, const list<T,Allocator>& @\farg{y}@);
+ template <@\changedConcepts{class}{LessThanComparable}@ T, class Allocator>
+ bool operator< (const list<T,Allocator>& @\farg{x}@, const list<T,Allocator>& @\farg{y}@);
+ template <@\changedConcepts{class}{EqualityComparable}@ T, class Allocator>
+ bool operator!=(const list<T,Allocator>& @\farg{x}@, const list<T,Allocator>& @\farg{y}@);
+ template <@\changedConcepts{class}{LessThanComparable}@ T, class Allocator>
+ bool operator> (const list<T,Allocator>& @\farg{x}@, const list<T,Allocator>& @\farg{y}@);
+ template <@\changedConcepts{class}{LessThanComparable}@ T, class Allocator>
+ bool operator>=(const list<T,Allocator>& @\farg{x}@, const list<T,Allocator>& @\farg{y}@);
+ template <@\changedConcepts{class}{LessThanComparable}@ T, class Allocator>
+ bool operator<=(const list<T,Allocator>& @\farg{x}@, const list<T,Allocator>& @\farg{y}@);
+
+ // specialized algorithms:
+ template <@\changedConcepts{class}{ObjectType}@ T, class Allocator>
+ void swap(list<T,Allocator>& x, list<T,Allocator>& y);
+ template <@\changedConcepts{class}{ObjectType}@ T, class Allocator>
+ void swap(list<T,Allocator>&& x, list<T,Allocator>& y);
+ template <@\changedConcepts{class}{ObjectType}@ T, class Allocator>
+ void swap(list<T,Allocator>& x, list<T,Allocator>&& y);
+
+ template <class T, class Alloc>
+ struct constructible_with_allocator_suffix<list<T, Alloc> >
+ : true_type { };
+}
+\end{codeblock}
+
+\rSec3[list.cons]{\tcode{list}\ constructors, copy, and assignment}
+
+\begin{itemdecl}
+explicit list(const Allocator& = Allocator());
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Constructs an empty list, using the specified allocator.
+
+\pnum
+\complexity\
+Constant.
+\end{itemdescr}
+
+\begin{itemdecl}
+@\addedConcepts{requires DefaultConstructible<T>}@ explicit list(size_type n);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects Constructs a \tcode{list} with
+\tcode{n} default constructed elements.
+
+\pnum
+\removedConcepts{\mbox{\requires} \mbox{\tcode{T}} shall be \mbox{\tcode{DefaultConstructible}}.}
+
+\pnum
+\complexity
+Linear in
+\tcode{n}.
+\end{itemdescr}
+
+\begin{itemdecl}
+@\addedConcepts{requires CopyConstructible<T>}@
+ list(size_type @\farg{n}@, const T& @\farg{value}@,
+ const Allocator& = Allocator());
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Constructs a
+\tcode{list}\
+with
+\tcode{n}\
+copies of
+\tcode{value},
+using the specified allocator.
+
+\pnum
+\removedConcepts{\mbox{\requires} \mbox{\tcode{T}} shall be \mbox{\tcode{CopyConstructible}}.}
+
+\pnum
+\complexity\
+Linear in
+\tcode{n}.
+\end{itemdescr}
+
+\begin{itemdecl}
+template <@\changedConcepts{class InputIterator}{InputIterator Iter}@>
+ @\addedConcepts{requires HasConstructor<T, Iter::reference>}@
+ list(@\changedConcepts{InputIterator}{Iter}@ @\farg{first}@, @\changedConcepts{InputIterator}{Iter}@ @\farg{last}@, const Allocator& = Allocator());
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Constructs a
+\tcode{list}\
+equal to the range
+\range{\farg{first}}{\farg{last}}.
+
+\pnum
+\complexity\
+Linear in
+\tcode{distance(\farg{first}, \farg{last})}.
+\end{itemdescr}
+
+\index{assign@\tcode{assign}!\tcode{list}}%
+\begin{itemdecl}
+template <@\changedConcepts{class InputIterator}{InputIterator Iter}@>
+ @\addedConcepts{requires HasCopyAssign<T, Iter::reference> \&\& HasConstructor<T, Iter::reference>}@
+ void assign(@\changedConcepts{InputIterator}{Iter}@ first, @\changedConcepts{InputIterator}{Iter}@ last);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Replaces the contents of the list with the range
+\tcode{[first, last)}.
+
+\begin{codeblock}
+erase(begin(), end());
+insert(begin(), n, t);
+\end{codeblock}
+
+\end{itemdescr}
+
+\begin{itemdecl}
+@\addedConcepts{requires CopyAssignable<T> \&\& CopyConstructible<T>}@ void assign(size_type n, const T& t);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Replaces the contents of the list with \farg{n}\ copies of \farg{t}.
+\end{itemdescr}
+
+\rSec3[list.capacity]{\tcode{list}\ capacity}
+
+\index{resize@\tcode{resize}!\tcode{list}}%
+\begin{itemdecl}
+@\addedConcepts{requires DefaultConstructible<T>}@ void resize(size_type sz);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects If \tcode{sz < size()}, equivalent to
+\tcode{list<T>::iterator it = begin();}
+\tcode{advance(it, sz);}
+\tcode{erase(it, end());}. If \tcode{size() < sz},
+appends \tcode{sz - size()} default constructed elements to the
+sequence.
+
+\pnum
+\removedConcepts{\mbox{\requires} \mbox{\tcode{T}} shall be
+\mbox{\tcode{DefaultConstructible}}.}
+\end{itemdescr}
+
+\index{resize@\tcode{resize}!\tcode{list}}%
+\begin{itemdecl}
+@\addedConcepts{requires CopyConstructible<T>}@ void resize(size_type sz, const T& c);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+\begin{codeblock}
+if (sz > size())
+ insert(end(), sz-size(), c);
+else if (sz < size()) {
+ iterator i = begin();
+ advance(i, sz);
+ erase(i, end());
+}
+else
+ ; // do nothing
+\end{codeblock}
+
+\pnum
+\removedConcepts{\mbox{\requires} \mbox{\tcode{T}} shall be \mbox{\tcode{CopyConstructible}}.}
+\end{itemdescr}
+
+\rSec3[list.modifiers]{\tcode{list}\ modifiers}
+
+\index{insert@\tcode{insert}!\tcode{list}}%
+\begin{itemdecl}
+@\addedConcepts{requires CopyConstructible<T>}@ iterator insert(const_iterator position, const T& x);
+@\addedConcepts{requires MoveConstructible<T>}@ iterator insert(const_iterator position, T&& x);
+@\addedConcepts{requires CopyConstructible<T>}@
+ void insert(const_iterator @\farg{position}@, size_type @\farg{n}@, const T& @\farg{x}@);
+template <@\changedConcepts{class InputIterator}{InputIterator Iter}@>
+ @\addedConcepts{requires HasConstructor<T, Iter::reference>}@
+ void insert(const_iterator @\farg{position}@, @\changedConcepts{InputIterator}{Iter}@ @\farg{first}@,
+ @\changedConcepts{InputIterator}{Iter}@ @\farg{last}@);
+
+template <class... Args>
+ @\addedConcepts{requires HasConstructor<T, Args\&\&...>}@
+ void push_front(Args&&... args);
+template <class... Args>
+ @\addedConcepts{requires HasConstructor<T, Args\&\&...>}@
+ void push_back(Args&&... args);
+template <class... Args>
+ @\addedConcepts{requires HasConstructor<T, Args\&\&...>}@
+ iterator emplace(const_iterator position, Args&&... args);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\notes\
+Does not affect the validity of iterators and references.
+If an exception is thrown there are no effects.
+
+\pnum
+\complexity\
+Insertion of a single element into a list takes constant time and
+exactly one call to a constructor of
+\tcode{T}. Insertion of multiple elements into a list is linear in the
+number of elements inserted, and the number of calls to the copy
+constructor or move constructor of \tcode{T}\ is exactly equal
+to the number of elements inserted.
+\end{itemdescr}
+
+\index{erase@\tcode{erase}!\tcode{list}}%
+\begin{itemdecl}
+iterator erase(const_iterator position);
+iterator erase(const_iterator first, const_iterator last);
+
+void pop_front();
+void pop_back();
+void clear();
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Invalidates only the iterators and references to the erased elements.
+
+\pnum
+\throws\
+Nothing.
+
+\pnum
+\complexity\
+Erasing a single element is a constant time operation with a single call to the destructor of
+\tcode{T}.
+Erasing a range in a list is linear time in the
+size of the range and the number of calls to the destructor of type
+\tcode{T}\
+is exactly equal to the size of the range.
+\end{itemdescr}
+
+\rSec3[list.ops]{\tcode{list}\ operations}
+
+\pnum
+Since lists allow fast insertion and erasing from the middle of a list, certain operations are provided
+specifically for them.%
+\footnote{As specified in~\ref{allocator.requirements}, the requirements
+in this clause apply only to lists whose allocators compare equal.
+}
+
+\pnum
+\tcode{list}\
+provides three splice operations that destructively move elements from one list to another. The behavior of splice operations is undefined if \tcode{get_allocator() != x.get_allocator()}.
+
+\index{splice@\tcode{splice}!\tcode{list}}%
+\begin{itemdecl}
+void splice(const_iterator @\farg{position}@, list<T,Allocator>&& @\farg{x}@);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\requires\
+\tcode{\&\farg{x} != this}.
+
+\pnum
+\effects\
+Inserts the contents of
+\tcode{x}
+before
+\tcode{position}
+and
+\tcode{x}
+becomes empty.
+Pointers and references to the moved elements of
+\tcode{x}\
+now refer to those same elements but as members of
+\tcode{*this}.
+Iterators referring to the moved elements will continue to refer to their
+elements, but they now behave as iterators into
+\tcode{*this},
+not into
+\tcode{x}.
+
+\pnum
+\throws\
+Nothing
+
+\pnum
+\complexity\
+Constant time.
+\end{itemdescr}
+
+\begin{itemdecl}
+void splice(const_iterator @\farg{position}@, list<T,Allocator>&& @\farg{x}@, iterator @\farg{i}@);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Inserts an element pointed to by
+\tcode{i}\
+from list
+\tcode{x}\
+before \tcode{position}\ and removes the element from
+\tcode{x}.
+The result is unchanged if
+\tcode{position == i}
+or
+\tcode{position == ++i}.
+Pointers and references to
+\tcode{*i}\
+continue to refer to this same element but as a member of
+\tcode{*this}.
+Iterators
+to
+\tcode{*i}\
+(including
+\tcode{i}\
+itself) continue to refer to the same element, but now behave as iterators into
+\tcode{*this},
+not into
+\tcode{x}.
+
+\pnum
+\throws\
+Nothing
+
+\pnum
+\requires\
+\tcode{i}\
+is a valid dereferenceable iterator of
+\tcode{x}.
+
+\pnum
+\complexity\
+Constant time.
+\end{itemdescr}
+
+\begin{itemdecl}
+void splice(const_iterator @\farg{position}@, list<T,Allocator>&& @\farg{x}@, iterator @\farg{first}@,
+ iterator @\farg{last}@);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Inserts elements in the range
+\range{first}{last}\
+before
+\tcode{position}
+and removes the elements from
+\tcode{x}.
+
+\pnum
+\requires\
+\tcode{[first, last)}
+is a valid range in
+\tcode{x}.
+The result is undefined if
+\tcode{position}
+is an iterator in the range
+\range{first}{last}.
+Pointers and references to the moved elements of
+\tcode{x}\
+now refer to those same elements but as members of
+\tcode{*this}.
+Iterators referring to the moved elements will continue to refer to their
+elements, but they now behave as iterators into
+\tcode{*this},
+not into
+\tcode{x}.
+
+\pnum
+\throws\
+Nothing
+
+\pnum
+\complexity\
+Constant time if
+\tcode{\&\farg{x} == this};
+otherwise, linear time.
+\end{itemdescr}
+
+\index{remove@\tcode{remove}!\tcode{list}}%
+\begin{itemdecl}
+@\addedConcepts{requires EqualityComparable<T>}@ void remove(const T& @\farg{value}@);
+template <@\changedConcepts{class}{Predicate<auto, T>}@ Pred@\removedConcepts{icate}@> void remove_if(Pred@\removedConcepts{icate}@ @\farg{pred}@);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Erases all the elements in the list referred by a list iterator
+\tcode{i}
+for which the following conditions hold:
+\tcode{*i == value, pred(*i) != false}.
+
+\pnum
+\throws\
+Nothing unless an exception is thrown by
+\tcode{*i == value}
+or
+\tcode{\farg{pred}(*i) != false}.
+
+\pnum
+\notes\
+Stable.
+
+\pnum
+\complexity\
+Exactly
+\tcode{size()}
+applications of the corresponding predicate.
+\end{itemdescr}
+
+\index{unique@\tcode{unique}!\tcode{list}}%
+\begin{itemdecl}
+@\addedConcepts{requires EqualityComparable<T>}@ void unique();
+template <@\changedConcepts{class}{Predicate<auto, T, T>}@ BinaryPredicate> void unique(BinaryPredicate @\farg{binary_pred}@);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Eliminates all but the first element from every
+consecutive group of equal elements referred to by the
+iterator
+\tcode{i}\
+in the range
+\range{\farg{first} + 1}{\farg{last}}\
+for which
+\tcode{*i == *(i-1)}
+(for the version of
+\tcode{unique}\
+with no arguments) or
+\tcode{\farg{pred}(*i, *(i - 1))}\
+(for the version of
+\tcode{unique}
+with a predicate argument)
+holds.
+
+\pnum
+\throws\
+Nothing unless an exception in thrown by
+\tcode{*i == *(i-1)}\
+or
+\tcode{\farg{pred}(*i, *(i - 1))}\
+
+\pnum
+\complexity\
+If the range
+\tcode{[\farg{first}, \farg{last})}\
+is not empty, exactly
+\tcode{(\farg{last} - \farg{first}) - 1}
+applications of the corresponding predicate,
+otherwise no applications of the predicate.
+\end{itemdescr}
+
+\index{merge@\tcode{merge}!\tcode{list}}%
+\begin{itemdecl}
+@\addedConcepts{requires LessThanComparable<T>}@ void merge(list<T,Allocator>&& @\farg{x}@);
+template <@\changedConcepts{class}{Predicate<auto, T, T>}@ Compare> void merge(list<T,Allocator>&& @\farg{x}@, Compare @\farg{comp}@);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\requires\
+\farg{comp}\ shall define a strict weak ordering
+(\ref{alg.sorting}), and both the list and the argument list shall be
+sorted according to this ordering.
+
+\pnum
+\effects\
+If
+\tcode{(\&x == this)}\
+does nothing; otherwise, merges the two sorted ranges
+\tcode{[begin(), end())}\
+and
+\tcode{[x.\brk{}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 \tcode{comp};
+that is, for every iterator \tcode{i}, in the range other than the first,
+the condition
+\tcode{comp(*i, *(i - 1)}\
+will be false.
+
+\pnum
+\notes\
+Stable. If \tcode{(\&x != this)}\ the range \tcode{[x.begin(), x.end())}\
+is empty after the merge.
+
+\pnum
+\complexity\
+At most
+\tcode{size() + x.size() - 1}\
+applications of \tcode{comp}\ if
+\tcode{(\&x != this)};
+otherwise, no applications of \tcode{comp}\ are performed.
+If an exception is thrown other than by a comparison there are no effects.
+\end{itemdescr}
+
+\index{reverse@\tcode{reverse}!\tcode{list}}%
+\begin{itemdecl}
+void reverse();
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Reverses the order of the elements in the list.
+
+\pnum
+\throws\
+Nothing.
+
+\pnum
+\complexity\
+Linear time.
+\end{itemdescr}
+
+\index{sort@\tcode{sort}!\tcode{list}}%
+\begin{itemdecl}
+@\addedConcepts{requires LessThanComparable<T>}@ void sort();
+template <@\changedConcepts{class}{BinaryPredicate<auto, T, T>}@ Compare> void sort(Compare @\farg{comp}@);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\requires\
+\tcode{operator<}\
+(for the first
+version)
+or
+\farg{comp}\
+(for the second version)
+shall define a strict weak ordering (\ref{alg.sorting}).
+
+\pnum
+\effects\
+Sorts the list according to the
+\tcode{operator<}\
+or a
+\tcode{Compare}\
+function object.
+
+\pnum
+\notes\
+Stable.
+
+\pnum
+\complexity\
+Approximately
+$N \log(N)$
+comparisons, where
+\tcode{N == size()}.
+\end{itemdescr}
+
+\rSec3[list.special]{\tcode{list}\ specialized algorithms}
+
+\begin{itemdecl}
+template <@\changedConcepts{class}{ObjectType}@ T, class Allocator>
+ void swap(list<T,Allocator>& x, list<T,Allocator>& y);
+template <@\changedConcepts{class}{ObjectType}@ T, class Allocator>
+ void swap(list<T,Allocator>&& x, list<T,Allocator>& y);
+template <@\changedConcepts{class}{ObjectType}@ T, class Allocator>
+ void swap(list<T,Allocator>& x, list<T,Allocator>&& y);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+\begin{codeblock}
+x.swap(y);
+\end{codeblock}
+\end{itemdescr}
+
\setcounter{subsection}{3}
\rSec2[lib.container.adaptors]{Container adaptors}