From: dgregor_at_[hidden]
Date: 2008-05-17 12:11:05
Author: dgregor
Date: 2008-05-17 12:11:04 EDT (Sat, 17 May 2008)
New Revision: 45454
URL: http://svn.boost.org/trac/boost/changeset/45454
Log:
Conceptualize set and multiset
Text files modified:
sandbox/committee/concepts/stdlib/clib-containers.tex | 560 ++++++++++++++++++++++++++++++++++++++-
1 files changed, 539 insertions(+), 21 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-17 12:11:04 EDT (Sat, 17 May 2008)
@@ -4456,65 +4456,67 @@
\begin{codeblock}
namespace std {
- template <class Key, class Compare = less<Key>,
+ template <@\changedConcepts{class}{ObjectType}@ Key, @\changedConcepts{class}{Predicate<auto, Key, Key>}@ Compare = less<Key>,
class Allocator = allocator<Key> >
+ @\addedConcepts{requires Destructible<Key> \&\& CopyConstructible<Compare>}@
class set;
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{EqualityComparable}@ Key, class Compare, class Allocator>
bool operator==(const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
bool operator< (const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{EqualityComparable}@ Key, class Compare, class Allocator>
bool operator!=(const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
bool operator> (const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
bool operator>=(const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
bool operator<=(const set<Key,Compare,Allocator>& x,
const set<Key,Compare,Allocator>& y);
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
void swap(set<Key,Compare,Allocator>& x,
set<Key,Compare,Allocator>& y);
- template <class Key, class T, class Compare, class Allocator>
+ template <@\changedConcepts{class}{ObjectType}@ Key, class T, class Compare, class Allocator>
void swap(set<Key,T,Compare,Allocator&& x,
set<Key,T,Compare,Allocator>& y);
- template <class Key, class T, class Compare, class Allocator>
+ template <@\changedConcepts{class}{ObjectType}@ Key, class T, class Compare, class Allocator>
void swap(set<Key,T,Compare,Allocator& x,
set<Key,T,Compare,Allocator>&& y);
- template <class Key, class Compare = less<Key>,
+ template <@\changedConcepts{class}{ObjectType}@ Key, @\changedConcepts{class}{Predicate<auto, Key, Key>}@ Compare = less<Key>,
class Allocator = allocator<Key> >
+ @\addedConcepts{requires Destructible<Key> \&\& CopyConstructible<Compare>}@
class multiset;
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{EqualityComparable}@ Key, class Compare, class Allocator>
bool operator==(const multiset<Key,Compare,Allocator>& x,
const multiset<Key,Compare,Allocator>& y);
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
bool operator< (const multiset<Key,Compare,Allocator>& x,
const multiset<Key,Compare,Allocator>& y);
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{EqualityComparable}@ Key, class Compare, class Allocator>
bool operator!=(const multiset<Key,Compare,Allocator>& x,
const multiset<Key,Compare,Allocator>& y);
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
bool operator> (const multiset<Key,Compare,Allocator>& x,
const multiset<Key,Compare,Allocator>& y);
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
bool operator>=(const multiset<Key,Compare,Allocator>& x,
const multiset<Key,Compare,Allocator>& y);
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
bool operator<=(const multiset<Key,Compare,Allocator>& x,
const multiset<Key,Compare,Allocator>& y);
- template <class Key, class Compare, class Allocator>
+ template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
void swap(multiset<Key,Compare,Allocator>& x,
multiset<Key,Compare,Allocator>& y);
- template <class Key, class T, class Compare, class Allocator>
+ template <@\changedConcepts{class}{ObjectType}@ Key, class T, class Compare, class Allocator>
void swap(multiset<Key,T,Compare,Allocator&& x,
multiset<Key,T,Compare,Allocator>& y);
- template <class Key, class T, class Compare, class Allocator>
+ template <@\changedConcepts{class}{ObjectType}@ Key, class T, class Compare, class Allocator>
void swap(multiset<Key,T,Compare,Allocator& x,
multiset<Key,T,Compare,Allocator>&& y);
}
@@ -5305,7 +5307,523 @@
\end{codeblock}
\end{itemdescr}
+\rSec2[set]{Class template \tcode{set}}
+
+\pnum
+\index{set@\tcode{set}}%
+A
+\tcode{set}\
+is an associative container that supports unique keys (contains at most one of each key value) and
+provides for fast retrieval of the keys themselves.
+Class
+\tcode{set}\
+supports bidirectional iterators.
+
+\pnum
+A
+\tcode{set}\
+satisfies all of the requirements of a container, of a reversible container
+(\ref{container.requirements}), of
+an associative container (\ref{associative.reqmts}), and of an allocator-aware container (Table~\ref{tab:containers.allocatoraware}).
+A
+\tcode{set}\
+also provides most operations described in (\ref{associative.reqmts})
+for unique keys.
+This means that a
+\tcode{set}\
+supports the
+\tcode{a_uniq}\
+operations in (\ref{associative.reqmts})
+but not the
+\tcode{a_eq}\
+operations.
+For a
+\tcode{set<Key>}\
+both the
+\tcode{key_type}\
+and
+\tcode{value_type}\
+are
+\tcode{Key}.
+Descriptions are provided here only for operations on
+\tcode{set}\
+that are not described in one of these tables
+and for operations where there is additional semantic information.
+
+\begin{codeblock}
+namespace std {
+ template <@\changedConcepts{class}{ObjectType}@ Key, @\changedConcepts{class}{Predicate<auto, Key, Key>}@ Compare = less<Key>,
+ class Allocator = allocator<Key> >
+ @\addedConcepts{requires Destructible<Key> \&\& CopyConstructible<Compare>}@
+ class set {
+ public:
+ // types:
+ typedef Key key_type;
+ typedef Key value_type;
+ typedef Compare key_compare;
+ typedef Compare value_compare;
+ typedef Allocator allocator_type;
+ 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 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{set.cons} construct/copy/destroy:
+ explicit set(const Compare& comp = Compare(),
+ const Allocator& = Allocator());
+ template <@\changedConcepts{class InputIterator}{InputIterator Iter}@>
+ @\addedConcepts{requires HasConstructor<value_type, Iter::reference>}@
+ set(@\changedConcepts{InputIterator}{Iter}@ first, @\changedConcepts{InputIterator}{Iter}@ last,
+ const Compare& comp = Compare(), const Allocator& = Allocator());
+ @\addedConcepts{requires CopyConstructible<value_type>}@ set(const set<Key,Compare,Allocator>& x);
+ set(set<Key,Compare,Allocator>&& x);
+ set(const Allocator&);
+ @\addedConcepts{requires CopyConstructible<value_type>}@ set(const set&, const Allocator&);
+ set(set&&, const Allocator&);
+ ~set();
+
+ @\addedConcepts{requires CopyConstructible<value_type> \&\& CopyAssignable<value_type>}@
+ set<Key,Compare,Allocator>& operator=(const set<Key,Compare,Allocator>& x);
+ set<Key,Compare,Allocator>& operator=(set<Key,Compare,Allocator>&& x);
+ 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;
+
+ // capacity:
+ bool empty() const;
+ size_type size() const;
+ size_type max_size() const;
+
+ // modifiers:
+ template <class... Args>
+ @\addedConcepts{requires HasConstructor<value_type, Args\&\&...>}@
+ pair<iterator, bool> emplace(Args&&... args);
+ template <class... Args>
+ @\addedConcepts{requires HasConstructor<value_type, Args\&\&...>}@
+ iterator emplace(const_iterator position, Args&&... args);
+ @\addedConcepts{requires CopyConstructible<value_type>}@ pair<iterator,bool> insert(const value_type& x);
+ @\addedConcepts{requires MoveConstructible<value_type>}@ pair<iterator,bool> insert(value_type&& x);
+ @\addedConcepts{requires CopyConstructible<value_type>}@ iterator insert(const_iterator position, const value_type& x);
+ @\addedConcepts{requires MoveConstructible<value_type>}@ iterator insert(const_iterator position, value_type&& x);
+ template <@\changedConcepts{class InputIterator}{InputIterator Iter}@>
+ @\addedConcepts{requires HasConstructor<value_type, Iter::reference>}@
+ void insert(@\changedConcepts{InputIterator}{Iter}@ first, @\changedConcepts{InputIterator}{Iter}@ last);
+
+ iterator erase(const_iterator position);
+ size_type erase(const key_type& x);
+ iterator erase(const_iterator first, const_iterator last);
+ void swap(set<Key,Compare,Allocator>&);
+ void clear();
+
+ // observers:
+ key_compare key_comp() const;
+ value_compare value_comp() const;
+
+ // set operations:
+ iterator find(const key_type& x);
+ const_iterator find(const key_type& x) const;
+
+ size_type count(const key_type& x) const;
+
+ iterator lower_bound(const key_type& x);
+ const_iterator lower_bound(const key_type& x) const;
+
+ iterator upper_bound(const key_type& x);
+ const_iterator upper_bound(const key_type& x) const;
+
+ pair<iterator,iterator> equal_range(const key_type& x);
+ pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
+ };
+
+ template <@\changedConcepts{class}{EqualityComparable}@ Key, class Compare, class Allocator>
+ bool operator==(const set<Key,Compare,Allocator>& x,
+ const set<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
+ bool operator< (const set<Key,Compare,Allocator>& x,
+ const set<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{EqualityComparable}@ Key, class Compare, class Allocator>
+ bool operator!=(const set<Key,Compare,Allocator>& x,
+ const set<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
+ bool operator> (const set<Key,Compare,Allocator>& x,
+ const set<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
+ bool operator>=(const set<Key,Compare,Allocator>& x,
+ const set<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
+ bool operator<=(const set<Key,Compare,Allocator>& x,
+ const set<Key,Compare,Allocator>& y);
+
+ // specialized algorithms:
+ template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
+ void swap(set<Key,Compare,Allocator>& x,
+ set<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
+ void swap(set<Key,Compare,Allocator&& x,
+ set<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
+ void swap(set<Key,Compare,Allocator& x,
+ set<Key,Compare,Allocator>&& y);
+
+ template <class Key, class Compare, class Alloc>
+ struct constructible_with_allocator_suffix<
+ set<Key, Compare, Alloc> >
+ : true_type { };
+}
+\end{codeblock}%
+\index{set@\tcode{set}!\tcode{operator==}}%
+\index{set@\tcode{set}!\tcode{operator<}}
+
+\rSec3[set.cons]{\tcode{set}\ constructors, copy, and assignment}
+
+\begin{itemdecl}
+explicit set(const Compare& comp = Compare(),
+ const Allocator& = Allocator());
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Constructs an empty set using the specified comparison objects and allocator.
+
+\pnum
+\complexity\
+Constant.
+\end{itemdescr}
+
+\begin{itemdecl}
+template <@\changedConcepts{class InputIterator}{InputIterator Iter}@>
+ @\addedConcepts{requires HasConstructor<value_type, Iter::reference>}@
+ set(@\changedConcepts{InputIterator}{Iter}@ @\farg{first}@, @\changedConcepts{InputIterator}{Iter}@ @\farg{last}@,
+ const Compare& @\farg{comp}@ = Compare(), const Allocator& = Allocator());
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Constructs an empty
+\tcode{set}\
+using the specified comparison object and allocator,
+and inserts elements from the range
+\range{\farg{first}}{\farg{last}}.
+
+\pnum
+@\removedConcepts{\mbox{\requires} If the iterator's dereference operator returns an lvalue or a
+non-const rvalue, then \mbox{\tcode{Key}} shall be
+\mbox{\tcode{CopyConstructible}}.}
+
+\pnum
+\complexity\
+Linear in $N$ if the range
+\range{\farg{first}}{\farg{last}}\
+is already sorted using \farg{comp}\
+and otherwise $N \log{N}$,
+where $N$\ is
+\tcode{\farg{last} - \farg{first}}.
+\end{itemdescr}
+
+\rSec3[set.special]{\tcode{set}\ specialized algorithms}
+
+\begin{itemdecl}
+template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
+ void swap(set<Key,Compare,Allocator>& x,
+ set<Key,Compare,Allocator>& y);
+template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
+ void swap(set<Key,Compare,Allocator>&& x,
+ set<Key,Compare,Allocator>& y);
+template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
+ void swap(set<Key,Compare,Allocator>& x,
+ set<Key,Compare,Allocator>&& y);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+\begin{codeblock}
+x.swap(y);
+\end{codeblock}
+\end{itemdescr}
+
+\rSec2[multiset]{Class template \tcode{multiset}}
+
+\pnum
+\index{multiset@\tcode{multiset}}%
+A
+\tcode{multiset}\
+is an associative container that supports equivalent keys (possibly contains multiple copies of
+the same key value) and provides for fast retrieval of the keys themselves.
+Class
+\tcode{multiset}\
+supports bidirectional iterators.
+
+\pnum
+A
+\tcode{multiset}\
+satisfies all of the requirements of a container, of a reversible container
+(\ref{container.requirements}), of
+an associative container (\ref{associative.reqmts}), and of an allocator-aware container (Table~\ref{tab:containers.allocatoraware}).
+\tcode{multiset}
+also provides most operations described in
+(\ref{associative.reqmts})
+for duplicate keys.
+This means that a
+\tcode{multiset}\
+supports the
+\tcode{a_eq}\
+operations in
+(\ref{associative.reqmts})
+but not the
+\tcode{a_uniq}\
+operations.
+For a
+\tcode{multiset<Key>}\
+both the
+\tcode{key_type}\
+and
+\tcode{value_type}\
+are
+\tcode{Key}.
+Descriptions are provided here only for operations on
+\tcode{multiset}\
+that are not described in one of these tables
+and for operations where there is additional semantic information.
+
+\begin{codeblock}
+namespace std {
+ template <@\changedConcepts{class}{ObjectType}@ Key, @\changedConcepts{class}{Predicate<auto, Key, Key>}@ Compare = less<Key>,
+ class Allocator = allocator<Key> >
+ @\addedConcepts{requires Destructible<Key> \&\& CopyConstructible<Compare>}@
+ class multiset {
+ public:
+ // types:
+ typedef Key key_type;
+ typedef Key value_type;
+ typedef Compare key_compare;
+ typedef Compare value_compare;
+ typedef Allocator allocator_type;
+ 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 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;
+
+ // construct/copy/destroy:
+ explicit multiset(const Compare& comp = Compare(),
+ const Allocator& = Allocator());
+ template <@\changedConcepts{class InputIterator}{InputIterator Iter}@>
+ @\addedConcepts{requires HasConstructor<value_type, Iter::reference>}@
+ multiset(@\changedConcepts{InputIterator}{Iter}@ first, @\changedConcepts{InputIterator}{Iter}@ last,
+ const Compare& comp = Compare(),
+ const Allocator& = Allocator());
+ @\addedConcepts{requires CopyConstructible<value_type>}@ multiset(const multiset<Key,Compare,Allocator>& x);
+ multiset(multiset<Key,Compare,Allocator>&& x);
+ multiset(const Allocator&);
+ @\addedConcepts{requires CopyConstructible<value_type>}@ multiset(const multiset&, const Allocator&);
+ multiset(multiset&&, const Allocator&);
+ ~multiset();
+ @\addedConcepts{requires CopyConstructible<value_type> \&\& CopyAssignable<value_type>}@
+ multiset<Key,Compare,Allocator>& operator=(const multiset<Key,Compare,Allocator>& x);
+ multiset<Key,Compare,Allocator>& operator=(multiset<Key,Compare,Allocator>&& x);
+ 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;
+
+ // capacity:
+ bool empty() const;
+ size_type size() const;
+ size_type max_size() const;
+
+ // modifiers:
+ template <class... Args>
+ @\addedConcepts{requires HasConstructor<value_type, Args\&\&...>}@
+ iterator emplace(Args&&... args);
+ template <class... Args>
+ @\addedConcepts{requires HasConstructor<value_type, Args\&\&...>}@
+ iterator emplace(const_iterator position, Args&&... args);
+ @\addedConcepts{requires CopyConstructible<value_type>}@ iterator insert(const value_type& x);
+ @\addedConcepts{requires MoveConstructible<value_type>}@ iterator insert(value_type&& x);
+ @\addedConcepts{requires CopyConstructible<value_type>}@ iterator insert(const_iterator position, const value_type& x);
+ @\addedConcepts{requires MoveConstructible<value_type>}@ iterator insert(const_iterator position, value_type&& x);
+ template <@\changedConcepts{class InputIterator}{InputIterator Iter}@>
+ @\addedConcepts{requires HasConstructor<value_type, Iter::reference>}@
+ void insert(@\changedConcepts{InputIterator}{Iter}@ first, @\changedConcepts{InputIterator}{Iter}@ last);
+
+ iterator erase(const_iterator position);
+ size_type erase(const key_type& x);
+ iterator erase(const_iterator first, const_iterator last);
+ void swap(multiset<Key,Compare,Allocator>&&);
+ void clear();
+
+ // observers:
+ key_compare key_comp() const;
+ value_compare value_comp() const;
+
+ // set operations:
+ iterator find(const key_type& x);
+ const_iterator find(const key_type& x) const;
+
+ size_type count(const key_type& x) const;
+
+ iterator lower_bound(const key_type& x);
+ const_iterator lower_bound(const key_type& x) const;
+
+ iterator upper_bound(const key_type& x);
+ const_iterator upper_bound(const key_type& x) const;
+
+ pair<iterator,iterator> equal_range(const key_type& x);
+ pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
+ };
+
+ template <@\changedConcepts{class}{EqualityComparable}@ Key, class Compare, class Allocator>
+ bool operator==(const multiset<Key,Compare,Allocator>& x,
+ const multiset<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
+ bool operator< (const multiset<Key,Compare,Allocator>& x,
+ const multiset<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{EqualityComparable}@ Key, class Compare, class Allocator>
+ bool operator!=(const multiset<Key,Compare,Allocator>& x,
+ const multiset<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
+ bool operator> (const multiset<Key,Compare,Allocator>& x,
+ const multiset<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
+ bool operator>=(const multiset<Key,Compare,Allocator>& x,
+ const multiset<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{LessThanComparable}@ Key, class Compare, class Allocator>
+ bool operator<=(const multiset<Key,Compare,Allocator>& x,
+ const multiset<Key,Compare,Allocator>& y);
+
+ // specialized algorithms:
+ template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
+ void swap(multiset<Key,Compare,Allocator>& x,
+ multiset<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
+ void swap(multiset<Key,Compare,Allocator&& x,
+ multiset<Key,Compare,Allocator>& y);
+ template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
+ void swap(multiset<Key,Compare,Allocator& x,
+ multiset<Key,Compare,Allocator>&& y);
+
+ template <class Key, class Compare, class Alloc>
+ struct constructible_with_allocator_suffix<
+ multiset<Key, Compare, Alloc> >
+ : true_type { };
+}
+\end{codeblock}%
+\index{multiset@\tcode{multiset}!\tcode{operator==}}%
+\index{multiset@\tcode{multiset}!\tcode{operator<}}
+
+\rSec3[multiset.cons]{\tcode{multiset}\ constructors}
+
+\begin{itemdecl}
+explicit multiset(const Compare& @\farg{comp}@ = Compare(),
+ const Allocator& = Allocator());
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+Constructs an empty set using the specified comparison object and allocator.
+
+\pnum
+\complexity\
+Constant.
+\end{itemdescr}
+
+\begin{itemdecl}
+template <@\changedConcepts{class InputIterator}{InputIterator Iter}@>
+ @\addedConcepts{requires HasConstructor<value_type, Iter::reference>}@
+ multiset(@\changedConcepts{InputIterator}{Iter}@ @\farg{first}@, @\changedConcepts{InputIterator}{Iter}@ @\farg{last}@,
+ const Compare& @\farg{comp}@ = Compare(),
+ const Allocator& = Allocator());
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\removedConcepts{\mbox{\requires} If the iterator's dereference operator returns an lvalue or a
+const rvalue, then \mbox{\tcode{Key}} shall be
+\mbox{\tcode{CopyConstructible}}.}
+
+\pnum
+\effects\
+Constructs an empty
+\tcode{multiset}\
+using the specified comparison object and allocator,
+and inserts elements from the range
+\range{\farg{first}}{\farg{last}}.
+
+\pnum
+\complexity\
+Linear in $N$
+if the range
+\range{\farg{first}}{\farg{last}}\
+is already sorted using \farg{comp}\ and otherwise $N \log{N}$,
+where $N$ is
+\tcode{\farg{last}\ - \farg{first}}.
+\end{itemdescr}
+
+\rSec3[multiset.special]{\tcode{multiset}\ specialized algorithms}
+
+\begin{itemdecl}
+template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
+ void swap(multiset<Key,Compare,Allocator>& x,
+ multiset<Key,Compare,Allocator>& y);
+template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
+ void swap(multiset<Key,Compare,Allocator>&& x,
+ multiset<Key,Compare,Allocator>& y);
+template <@\changedConcepts{class}{ObjectType}@ Key, class Compare, class Allocator>
+ void swap(multiset<Key,Compare,Allocator>& x,
+ multiset<Key,Compare,Allocator>&& y);
+\end{itemdecl}
+
+\begin{itemdescr}
+\pnum
+\effects\
+\begin{codeblock}
+x.swap(y);
+\end{codeblock}
+\end{itemdescr}
+
\bibliographystyle{plain}
-\bibliography{../local}
+\bibliography{local}
\end{document}
\ No newline at end of file