______________________________________________________________________

  23   Containers library                     [lib.containers]

  ______________________________________________________________________

1 This clause describes components that C++ programs may use to organize
  collections of information.

2 The  following  subclauses describe container requirements, and compo­
  nents for sequences and associative containers, as summarized in Table
  1:

                   Table 1--Containers library summary

         +------------------------------------------------------+
         |                Subclause                   Header(s) |
         +------------------------------------------------------+
         |_lib.container.requirements_ Requirements             |
         +------------------------------------------------------+
         |                                            <bitset>  |
         |                                            <deque>   |
         |_lib.sequences_ Sequences                   <list>    |
         |                                            <queue>   |
         |                                            <stack>   |
         |                                            <vector>  |
         +------------------------------------------------------+
         |_lib.associative_ Associative containers    <map>     |
         |                                            <set>     |
         +------------------------------------------------------+

  23.1  Container requirements              [lib.container.requirements]

1 Containers are objects that store other objects.  They control alloca­
  tion and deallocation of these objects through constructors,  destruc­
  tors, insert and erase operations.

2 The  type of objects stored in these components must meet the require­
  ments of CopyConstructible types  (_lib.copyconstructible_),  and  the
  additional requirements of Assignable types.

3 In  Table  2,  T is the type used to instantiate the container, t is a
  value of T, and u is a value of (possibly const) T.

                     Table 2--Assignable requirements

      +-------------------------------------------------------------+
      |expression   return type      post-condition      complexity |
      +-------------------------------------------------------------+
      |t = u        T&            t is equivalent to u   constant   |
      +-------------------------------------------------------------+

4 In Table 3, X denotes a container class containing objects of type  T,
  A  denotes the allocator type of X, a and b denote values of type X, u
  denotes an identifier and r denotes a value of X&.

                     Table 3--Container requirements

  --------------------------------------------------------------------------------------------------------
       expression               return type                   assertion/note              complexity
                                                            pre/post-condition
  --------------------------------------------------------------------------------------------------------
   X::value_type        T                             T is Assignable                  compile time
  --------------------------------------------------------------------------------------------------------
   X::reference         lvalue of T                                                    compile time
  --------------------------------------------------------------------------------------------------------
   X::const_reference   const lvalue of T                                              compile time
  --------------------------------------------------------------------------------------------------------
   X::iterator          iterator type pointing to T   any iterator category except     compile time
                                                      output iterator.
  --------------------------------------------------------------------------------------------------------
   X::const_iterator    iterator type pointing to     any iterator category except     compile time
                        const T                       output iterator.
  --------------------------------------------------------------------------------------------------------
   X::difference_type   signed integral type          is identical to the distance     compile time
                                                      type of X::iterator and
                                                      X::const_iterator
  --------------------------------------------------------------------------------------------------------
   X::size_type         unsigned integral type        size_type can represent any      compile time
                                                      non-negative value of differ­
                                                      ence_type
  --------------------------------------------------------------------------------------------------------
   X::allocator_type    const lvalue of A                                              compile time
  --------------------------------------------------------------------------------------------------------
   a.get_allocator()    allocator_type                returns the allocator object     constant
                                                      used to construct a
  --------------------------------------------------------------------------------------------------------
   X u;                                               post: u.size() == 0.             constant
  --------------------------------------------------------------------------------------------------------
   X();                                               X().size() == 0.                 constant
  --------------------------------------------------------------------------------------------------------
   X(a);                                              a == X(a).                       linear
  --------------------------------------------------------------------------------------------------------
   X u(a);                                            post: u == a.                    linear
   X u = a;                                           Equivalent to: X u; u = a;
  --------------------------------------------------------------------------------------------------------
   (&a)->~X();          void                          post: a.size() == 0.             linear
                                                      note: the destructor is ap­
                                                      plied to every element of a;
                                                      all the memory is returned.
  --------------------------------------------------------------------------------------------------------
   a.begin();           iterator;                                                      constant
                        const_iterator
                        for constant a
  --------------------------------------------------------------------------------------------------------
   a.end();             iterator;                                                      constant

  |                                                                                                      |
  |                                                                                                      |
  |                                                                                                      |
  |                                                                                                      |
  |                     const_iterator                                                                   |
  |                     for constant a                                                                   |
  +------------------------------------------------------------------------------------------------------+
  |a == b               convertible to bool           == is an equivalence relation.   linear            |
  |                                                   a.size()==b.size()                                 |
  |                                                   && equal(a.begin(),                                |
  |                                                   a.end(), b.begin())                                |
  +------------------------------------------------------------------------------------------------------+
  |a != b               convertible to bool           Equivalent to: !(a == b)         linear            |
  +------------------------------------------------------------------------------------------------------+
  |a.swap(b);           void                          swap(a,b)                        linear in gen­    |
  |                                                                                    eral,             |
  |                                                                                    constant if       |
  |                                                                                    a.get_allocator() |
  |                                                                                    ==                |
  |                                                                                    b.get_allocator() |
  +------------------------------------------------------------------------------------------------------+

  +----------------------------------------------------------------------------------+
  | expression      return type        operational       assertion/note   complexity |
  |                                     semantics      pre/post-condition            |
  +----------------------------------------------------------------------------------+
  |r = a        X&                  if (&r != &a) {    post: r == a.      linear     |
  |                                   (&r)->X::~X();                                 |
  |                                   new (&r) X(a);                                 |
  |                                 } return r;                                      |
  +----------------------------------------------------------------------------------+
  |a.size()     size_type           a.end()-a.begin()                     constant   |
  +----------------------------------------------------------------------------------+
  |a.max_size() size_type           size() of the                         constant   |
  |                                 largest possible                                 |
  |                                 container.                                       |
  +----------------------------------------------------------------------------------+
  |a.empty()    convertible to bool a.size() == 0                         constant   |
  +----------------------------------------------------------------------------------+
  |a < b        convertible to bool lexicographical_   pre: < is defined  linear     |
  |                                 com­               for values of T.              |
  |                                 pare(a.begin(),    < is a total or­              |
  |                                 a.end(),b.begin(), dering relation.              |
  |                                 b.end())                                         |
  +----------------------------------------------------------------------------------+
  |a > b        convertible to bool  b < a                                linear     |
  +----------------------------------------------------------------------------------+
  |a <= b       convertible to bool  !(a > b)                             linear     |
  +----------------------------------------------------------------------------------+
  |a >= b       convertible to bool  !(a < b)                             linear     |
  +----------------------------------------------------------------------------------+
  Notes:  the  algorithms  swap(), equal() and lexicographical_compare()
  are defined in Clause _lib.algorithms_.

5 The member function size() returns the number of elements in the  con­
  tainer.   Its  semantics  is  defined  by  the  rules of constructors,
  inserts, and erases.

6 begin() returns an iterator referring to the first element in the con­
  tainer.  end() returns an iterator which is the past-the-end value for
  the container.  If the container is empty, then begin() == end();

7 Copy constructors for all container types defined in this clause  copy
  the  allocator  argument  from their respective first parameters.  All
  other constructors for container types  take  an  Allocator&  argument
  (_lib.allocator.requirements_).   A  copy of this argument is used for
  any memory allocation performed, by these constructors and by all mem­
  ber functions, during the lifetime of each container object.

8 If  the  iterator  type of a container belongs to the bidirectional or
  random access iterator categories  (_lib.iterator.requirements_),  the
  container  is  called reversible and satisfies the additional require­
  ments in Table 4:

                Table 4--Reversible container requirements

  +-------------------------------------------------------------------------------------+
  |expression            return type                assertion/note          complexity  |
  |                                               pre/post-condition                    |
  +-------------------------------------------------------------------------------------+
  |X::reverse_   iterator type pointing to T   re­                         compile time |
  |iterator                                    verse_iterator<iterator,                 |
  |                                            value_type, reference,                   |
  |                                            difference_type> for ran­                |
  |                                            dom access iterator, re­                 |
  |                                            verse_bidirectional_ it­                 |
  |                                            erator<iterator, val­                    |
  |                                            ue_type, reference, dif­                 |
  |                                            ference_type> for bidi­                  |
  |                                            rectional iterator.                      |
  +-------------------------------------------------------------------------------------+
  |X::const_     iterator type pointing to     reverse_iterator< con­      compile time |
  |reverse_      const T                       st_iterator, value_type,                 |
  |iterator                                    const_reference, differ­                 |
  |                                            ence_type> for random ac­                |
  |                                            cess iterator, re­                       |
  |                                            verse_bidirectional_ it­                 |
  |                                            erator<const_iterator,                   |
  |                                            value_type, con­                         |
  |                                            st_reference, differ­                    |
  |                                            ence_type> for bidirec­                  |
  |                                            tional iterator.                         |
  +-------------------------------------------------------------------------------------+
  |a.rbegin()    reverse_iterator; con­        reverse_iterator(end())     constant     |
  |              st_reverse_ iterator for                                               |
  |              constant a                                                             |
  +-------------------------------------------------------------------------------------+
  |a.rend()      reverse_iterator; con­        reverse_iterator(begin())   constant     |
  |              st_reverse_ iterator for                                               |
  |              constant a                                                             |
  +-------------------------------------------------------------------------------------+

  23.1.1  Sequences                                [lib.sequence.reqmts]

1 A  sequence  is  a  kind  of  container that organizes a finite set of
  objects, all of the same type, into  a  strictly  linear  arrangement.
  The library provides three basic kinds of sequence containers: vector,
  list, and deque.  It also provides container  adaptors  that  make  it
  easy  to  construct abstract data types, such as stacks or queues, out
  of the basic sequence kinds (or out of other kinds of  sequences  that
  the user might define).

2 vector,  list,  and  deque  offer  the programmer different complexity
  trade-offs and should be used accordingly.   vector  is  the  type  of

  sequence  that  should  be  used by default.  list should be used when
  there are frequent insertions and deletions from  the  middle  of  the
  sequence.   deque is the data structure of choice when most insertions
  and deletions take place at  the  beginning  or  at  the  end  of  the
  sequence.

3 In Tables 5 and 6, X denotes a sequence class, a denotes value of X, i
  and j denote iterators satisfying input iterator requirements,

4 vector, list, and deque  offer  the  programmer  different  complexity
  trade-offs  and  should  be  used  accordingly.  vector is the type of
  sequence that should be used by default.  list  should  be  used  when
  there  are  frequent  insertions  and deletions from the middle of the
  sequence.  deque is the data structure of choice when most  insertions
  and  deletions  take  place  at  the  beginning  or  at the end of the
  sequence.

5 vector, list, and deque  offer  the  programmer  different  complexity
  trade-offs  and  should  be  used  accordingly.  vector is the type of
  sequence that should be used by default.  list  should  be  used  when
  there  are  frequent  insertions  and deletions from the middle of the
  sequence.  deque is the data structure of choice when most  insertions
  and  deletions  take  place  at  the  beginning  or  at the end of the
  sequence.  [i, j)  denotes  a  valid  range,  n  denotes  a  value  of
  X::size_type,  p  and  q2 denote valid iterators to a, q and q1 denote
  valid dereferenceable iterators to a, [q1, q2) denotes a valid  range,
  and t denotes a value of X::value_type.

6 The complexities of the expressions are sequence dependent.

        Table 5--Sequence requirements (in addition to container)

  +------------------------------------------------------------------------------------+
  |  expression      return type                   assertion/note                      |
  |                                               pre/post-condition                   |
  +------------------------------------------------------------------------------------+
  |X(n, t)                         post: size() == n.                                  |
  |X a(n, t);                      constructs a sequence with n copies of t.           |
  +------------------------------------------------------------------------------------+
  |X(i, j)                         post: size() == distance between i and j.           |
  |X a(i, j);                      constructs a sequence equal to the range [i,j).     |
  +------------------------------------------------------------------------------------+
  |a.insert(p,t)     iterator      inserts a copy of t before p.                       |
  +------------------------------------------------------------------------------------+
  |a.insert(p,n,t)   void          inserts n copies of t before p.                     |
  +------------------------------------------------------------------------------------+
  |a.insert(p,i,j)   void          inserts copies of elements in [i,j) before p.       |
  +------------------------------------------------------------------------------------+
  |a.erase(q)        iterator      erases the element pointed to by q.                 |
  +------------------------------------------------------------------------------------+
  |a.erase(q1,q2)    iterator      erases the elements in the range [q1,q2).           |
  +------------------------------------------------------------------------------------+
  |a.clear()         void          erase(s.begin(), s.end())                           |
  |                                post: size() == 0.                                  |
  +------------------------------------------------------------------------------------+

7 iterator  and  const_iterator  types for sequences must be at least of
  the forward iterator category.

8 The iterator returned from a.insert(p,t)  points  to  the  copy  of  t
  inserted into a.

9 The  iterator  returned  from a.erase(q) points to the element immedi­
  ately following q prior to the element being erased.  If no such  ele­
  ment exists, a.end() is returned.

10The  iterator returned by a.erase(q1,q2) points to the element pointed
  to by q2 prior to any elements  being  erased.   If  no  such  element
  exists, a.end() is returned.

11The  operations  in  Table  6 are provided only for the containers for
  which they take constant time:

                  Table 6--Optional sequence operations

  +-----------------------------------------------------------------------------+
  |  expression     return type          operational             container      |
  |                                       semantics                             |
  +-----------------------------------------------------------------------------+
  |a.front()       T&; const T&     *a.begin()              vector, list, deque |
  |                for constant a                                               |
  +-----------------------------------------------------------------------------+
  |a.back()        T&; const T&     *--a.end()              vector, list, deque |
  |                for constant a                                               |
  +-----------------------------------------------------------------------------+
  |a.push_front(x) void             a.insert(a.begin(),x)   list, deque         |
  +-----------------------------------------------------------------------------+
  |a.push_back(x)  void             a.insert(a.end(),x)     vector, list, deque |
  +-----------------------------------------------------------------------------+
  |a.pop_front()   void             a.erase(a.begin())      list, deque         |
  +-----------------------------------------------------------------------------+
  |a.pop_back()    void             a.erase(--a.end())      vector, list, deque |
  +-----------------------------------------------------------------------------+
  |a[n]            T&; const T&     *(a.begin() + n)        vector, deque       |
  |                for constant a                                               |
  +-----------------------------------------------------------------------------+
  |a.at(n)         T&; const T&     *(a.begin() + n)        vector, deque       |
  |                for constant a                                               |
  +-----------------------------------------------------------------------------+

12The member function at() provides bounds-checked access  to  container
  elements.  at() throws out_of_range if n >= a.size().

  23.1.2  Associative containers                [lib.associative.reqmts]

1 Associative  containers  provide an ability for fast retrieval of data
  based on keys.  The library provides four basic kinds  of  associative
  containers: set, multiset, map and multimap.

2 Each  associative  containers  is parameterized on Key and an ordering
  relation   Compare   that   induces    a    strict    weak    ordering
  (_lib.alg.sorting_) on elements of Key.  In addition, map and multimap
  associate an arbitrary type T with the Key.  The object of  type  Com­
  pare is called the comparison object of a container.

3 The  phrase  ``equivalence  of  keys''  means the equivalence relation
  imposed by the comparison and not the operator== on  keys.   That  is,
  two keys k1 and k2 are considered to be equivalent if for the compari­
  son object comp, comp(k1, k2) == false && comp(k2, k1) == false.

4 An associative container supports unique keys if  it  may  contain  at
  most  one  element  for  each  key.  Otherwise, it supports equivalent
  keys.  set and map support unique keys.  multiset and multimap support
  equal keys.

5 For  set and multiset the value type is the same as the key type.  For
  map and multimap it is equal to pair<const Key, T>.

6 iterator of an associative container is of the bidirectional  iterator
  category.

7 In  Table  7,  X is an associative container class, a is a value of X,
  a_uniq is a value of X when X supports unique  keys,  and  a_eq  is  a
  value of X when X supports multiple keys, i and j satisfy input itera­
  tor requirements and refer to elements of  value_type,  [i,  j)  is  a
  valid  range,  p  and  q2 are valid iterators to a, q and q1 are valid
  dereferenceable iterators to a, [q1, q2) is a  valid  range,  t  is  a
  value of X::value_type and k is a value of X::key_type.

  Table 7--Associative container requirements (in addition to container)

  +-----------------------------------------------------------------------------------+
  |  expression    return type              assertion/note               complexity   |
  |                                       pre/post-condition                          |
  +-----------------------------------------------------------------------------------+
  |X::key_type    Key            Key is Assignable                     compile time   |
  +-----------------------------------------------------------------------------------+
  |X::key_compare Compare        defaults to less<key_type>            compile time   |
  +-----------------------------------------------------------------------------------+
  |X:: val­       a binary pred­ is the same as key_compare for set    compile time   |
  |ue_compare     icate type     and multiset; is an ordering relation                |
  |                              on pairs induced by the first compo­                 |
  |                              nent (i.e. Key) for map and multimap.                |
  +-----------------------------------------------------------------------------------+
  |X(c)                          constructs an empty container;        constant       |
  |X a(c);                       uses c as a comparison object                        |
  +-----------------------------------------------------------------------------------+
  |X()                           constructs an empty container;        constant       |
  |X a;                          uses Compare() as a comparison object                |
  +-----------------------------------------------------------------------------------+
  |X(i,j,c);                     constructs an empty container and in­ NlogN in gen­  |
  |X a(i,j,c);                   serts elements from the range [i, j)  eral (N is the |
  |                              into it; uses c as a comparison ob­   distance from  |
  |                              ject                                  i to j);       |
  |                                                                    linear if [i,  |
  |                                                                    j) is sorted   |
  |                                                                    with val­      |
  |                                                                    ue_comp()      |
  +-----------------------------------------------------------------------------------+
  |X(i, j)                       same as above, but uses Compare() as  same as above  |
  |                              a comparison object.                                 |
  |X a(i, j);                                                                         |
  +-----------------------------------------------------------------------------------+
  |a.key_comp()   X::key_compare returns the comparison object out of  constant       |
  |                              which a was constructed.                             |
  +-----------------------------------------------------------------------------------+
  |a.value_comp() X:: val­       returns an object of value_compare    constant       |
  |               ue_compare     constructed out of the comparison ob­                |
  |                              ject                                                 |
  +-----------------------------------------------------------------------------------+
  |a_uniq.  in­   pair<iterator, inserts t if and only if there is no  logarithmic    |
  |sert(t)        bool>          element in the container with key                    |
  |                              equivalent to the key of t.  The bool                |
  |                              component of the returned pair indi­                 |
  |                              cates whether the insertion takes                    |
  |                              place and the iterator component of                  |
  |                              the pair points to the element with                  |
  |                              key equivalent to the key of t.                      |
  +-----------------------------------------------------------------------------------+

  -----------------------------------------------------------------------------------------
      expression     return type             assertion/note                complexity
                                           pre/post-condition
  -----------------------------------------------------------------------------------------
   a_eq.insert(t)   iterator       inserts t and returns the iterator  logarithmic
                                   pointing to the newly inserted ele­
                                   ment.
  -----------------------------------------------------------------------------------------
   a.insert(p,t)    iterator       inserts t if and only if there is   logarithmic in
                                   no element with key equivalent to   general, but amor­
                                   the key of t in containers with     tized constant if
                                   unique keys; always inserts t in    t is inserted
                                   containers with equivalent keys.    right after p.
                                   always returns the iterator point­
                                   ing to the element with key equiva­
                                   lent to the key of t.  iterator p
                                   is a hint pointing to where the in­
                                   sert should start to search.
  -----------------------------------------------------------------------------------------
   a.insert(i,j)    void           inserts the elements from the range Nlog(size()+N) (N
                                   [i, j) into the container.          is the distance
                                                                       from i to j) in
                                                                       general;
                                                                       linear if [i, j)
                                                                       is sorted accord­
                                                                       ing to val­
                                                                       ue_comp()
  -----------------------------------------------------------------------------------------
   a.erase(k)       size_type      erases all the elements in the con­ log(size()) +
                                   tainer with key equivalent to k.    count(k)
                                   returns the number of erased ele­
                                   ments.
  -----------------------------------------------------------------------------------------
   a.erase(q)       void           erases the element pointed to by q. amortized constant
  -----------------------------------------------------------------------------------------
   a.erase(q1,q2)   void           erases all the elements in the      log(size())+ N
                                   range [q1, q2).                     where N is the
                                                                       distance from q1
                                                                       to q2.
  -----------------------------------------------------------------------------------------
   a.clear()        void           erase(s.begin, s.end))              log(size()) + N
                                   post: size == 0
  -----------------------------------------------------------------------------------------
   a.find(k)        iterator; con­ returns an iterator pointing to an  logarithmic
                    st_iterator    element with the key equivalent to
                    for constant a k, or a.end() if such an element is
                                   not found.
  -----------------------------------------------------------------------------------------
   a.count(k)       size_type      returns the number of elements with log(size()) +
                                   key equivalent to k                 count(k)
  -----------------------------------------------------------------------------------------
   a.lower_bound(k) iterator; con­ returns an iterator pointing to the logarithmic
                    st_iterator    first element with key not less
                    for constant a than k.

  |                                                                                       |
  |                                                                                       |
  |                                                                                       |
  |                                                                                       |
  +---------------------------------------------------------------------------------------+
  |a.upper_bound(k) iterator; con­ returns an iterator pointing to the logarithmic        |
  |                 st_iterator    first element with key greater than                    |
  |                 for constant a k.                                                     |
  +---------------------------------------------------------------------------------------+
  |a.equal_range(k) pair< itera­   equivalent to make_pair(            logarithmic        |
  |                 tor,iterator>;     a.lower_bound(k),                                  |
  |                 pair< con­         a.upper_bound(k)).                                 |
  |                 st_iterator,                                                          |
  |                 con­                                                                  |
  |                 st_iterator>                                                          |
  |                 for constant a                                                        |
  +---------------------------------------------------------------------------------------+

8 The  fundamental  property  of  iterators of associative containers is
  that they iterate through the containers in the  non-descending  order
  of  keys  where  non-descending  is defined by the comparison that was
  used to construct them.  For any two dereferenceable iterators i and j
  such that distance from i to j is positive,
    value_comp(*j, *i) == false

9 For  associative  containers  with  unique keys the stronger condition
  holds,
    value_comp(*i, *j) == true.

  23.2  Sequences                                        [lib.sequences]

1 Headers <bitset>, <deque>, <list>, <queue>, <stack>, and <vector>.

  Header <bitset> synopsis

  #include <cstddef>      // for size_t
  #include <string>
  #include <stdexcept>    // for invalid_argument, out_of_range, overflow_error
  #include <iosfwd>       // for istream, ostream
  namespace std {
    template <size_t N> class bitset;
    // _lib.bitset.operators_ bitset operations:
    template <size_t N> bitset<N> operator&(const bitset<N>&, const bitset<N>&);
    template <size_t N> bitset<N> operator|(const bitset<N>&, const bitset<N>&);
    template <size_t N> bitset<N> operator^(const bitset<N>&, const bitset<N>&);
    template <class charT, class traits, size_t N>
      basic_istream<charT, traits>&
      operator>>(basic_istream<charT, traits>& is, bitset<N>& x);
    template <class charT, class traits, size_t N>
      basic_ostream<charT, traits>&
      operator<<(basic_ostream<charT, traits>& os, const bitset<N>& x);
  }

  Header <deque> synopsis

  #include <memory>       // for allocator
  namespace std {
    template <class T, class Allocator = allocator<T> > class deque;
    template <class T, class Allocator>
      bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
    template <class T, class Allocator>
      bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
    template <class T, class Allocator>
      void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);
  }

  Header <list> synopsis

  #include <memory>       // for allocator
  namespace std {
    template <class T, class Allocator = allocator<T> > class list;
    template <class T, class Allocator>
      bool operator==(const list<T,Allocator>& x, const list<T,Allocator>& y);
    template <class T, class Allocator>
      bool operator< (const list<T,Allocator>& x, const list<T,Allocator>& y);
    template <class T, class Allocator>
      void swap(list<T,Allocator>& x, list<T,Allocator>& y);
  }

  Header <queue> synopsis

  #include <functional>   // for less
  namespace std {
    template <class T, class Container = deque<T>,
              class Allocator = allocator<T> > class queue;
    template <class T, class Container, class Allocator>
      bool operator==(const queue<T, Container, Allocator>& x,
                      const queue<T, Container, Allocator>& y);
    template <class T, class Container, class Allocator>
      bool operator< (const queue<T, Container, Allocator>& x,
                      const queue<T, Container, Allocator>& y);
    template <class T, class Container = vector<T>,
              class Compare = less<Container::value_type>,
              class Allocator = allocator<T> > class priority_queue;
  }

  Header <stack> synopsis

  namespace std {
    template <class T, class Container = deque<T>,
              class Allocator = allocator<T> > class stack;
    template <class T, class Container, class Allocator>
      bool operator==(const stack<T, Container, Allocator>& x,
                      const stack<T, Container, Allocator>& y);
    template <class T, class Container, class Allocator>
      bool operator< (const stack<T, Container, Allocator>& x,
                      const stack<T, Container, Allocator>& y);
  }

  Header <vector> synopsis

  #include <memory>       // for allocator
  namespace std {
    template <class T, class Allocator = allocator<T> > class vector;
    template <class T, class Allocator>
      bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
    template <class T, class Allocator>
      bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
    template <class T, class Allocator>
      void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);

    template <class Allocator = allocator<T> > class vector<bool,Allocator>;
    template <class Allocator>
      bool operator==(const vector<bool,Allocator>& x,
                      const vector<bool,Allocator>& y);
    template <class Allocator>
      bool operator< (const vector<bool,Allocator>& x,
                      const vector<bool,Allocator>& y);
    template <class Allocator>
      void swap(vector<bool,Allocator>& x, vector<bool,Allocator>& y);
  }

  23.2.1  Template class bitset                    [lib.template.bitset]

1 The header <bitset> defines a template class and several related func­
  tions  for representing and manipulating fixed-size sequences of bits.
  namespace std {
    template<size_t N> class bitset {
    public:
    // bit reference:
      class reference {
        friend class bitset;
        reference();
      public:
       ~reference();
        reference& operator=(bool x);           // for b[i] = x;
        reference& operator=(const reference&); // for b[i] = b[j];
        bool operator~() const;                 // flips the bit
        operator bool() const;                  // for x = b[i];
        reference& flip();                      // for b[i].flip();
      };
    // _lib.bitset.cons_ constructors:
      bitset();
      bitset(unsigned long val);
      explicit bitset(const string& str, size_t pos = 0, size_t n = size_t(-1));

    // _lib.bitset.members_ bitset operations:
      bitset<N>& operator&=(const bitset<N>& rhs);
      bitset<N>& operator|=(const bitset<N>& rhs);
      bitset<N>& operator^=(const bitset<N>& rhs);
      bitset<N>& operator<<=(size_t pos);
      bitset<N>& operator>>=(size_t pos);
      bitset<N>& set();
      bitset<N>& set(size_t pos, int val = true);
      bitset<N>& reset();
      bitset<N>& reset(size_t pos);
      bitset<N>  operator~() const;
      bitset<N>& flip();
      bitset<N>& flip(size_t pos);
    // element access:
      reference operator[](size_t pos);   // for b[i];
      unsigned long  to_ulong() const;
      template <class charT, class traits, class Allocator>
        basic_string<charT, traits, Allocator> to_string() const;
      size_t count() const;
      size_t size()  const;
      bool operator==(const bitset<N>& rhs) const;
      bool operator!=(const bitset<N>& rhs) const;
      bool test(size_t pos) const;
      bool any() const;
      bool none() const;
      bitset<N> operator<<(size_t pos) const;
      bitset<N> operator>>(size_t pos) const;
    };
  }

2 The template class bitset<N> describes an  object  that  can  store  a
  sequence consisting of a fixed number of bits, N.

3 Each  bit  represents  either the value zero (reset) or one (set).  To
  toggle a bit is to change the value zero to one, or the value  one  to
  zero.   Each  bit  has  a  non-negative position pos.  When converting
  between an object of class bitset<N> and  a  value  of  some  integral
  type,  bit  position  pos  corresponds to the bit value 1 << pos.  The
  integral value corresponding to two or more bits is the sum  of  their
  bit values.

4 The  functions  described  in this subclause can report three kinds of
  errors, each associated with a distinct exception:

  --an invalid-argument error is  associated  with  exceptions  of  type
    invalid_argument (_lib.invalid.argument_);

  --an   out-of-range  error  is  associated  with  exceptions  of  type
    out_of_range (_lib.out.of.range_);

  --an overflow error  is  associated  with  exceptions  of  type  over­
    flow_error (_lib.overflow.error_).

  23.2.1.1  bitset constructors                        [lib.bitset.cons]

  bitset();

  Effects:
    Constructs  an  object  of class bitset<N>, initializing all bits to
    zero.

  bitset(unsigned long val);

  Effects:
    Constructs an object of class bitset<N>, initializing  the  first  M
    bit  positions  to  the  corresponding  bit values in val.  M is the
    smaller of N and the value CHAR_BIT * sizeof (unsigned long).1)
    If M < N, remaining bit positions are initialized to zero.

  template <class charT, class traits, class Allocator>
  explicit
  bitset(const basic_string<charT, traits, Allocator>& str,
         basic_string<charT, traits, Allocator>::size_type pos = 0,
         basic_string<charT, traits, Allocator>::size_type n =
           basic_string<charT, traits, Allocator>::npos);

  Requires:
    pos <= str.size().
  Throws:
    out_of_range if pos > str.size().
  Effects:
    Determines  the  effective length rlen of the initializing string as
    the smaller of n and str.size() - pos.
    The function then throws invalid_argument if any of the rlen charac­
    ters in str beginning at position pos is other than 0 or 1.
    Otherwise,  the  function  constructs  an object of class bitset<N>,
    initializing the first M bit positions to values determined from the
    corresponding  characters  in the string str.  M is the smaller of N
    and rlen.

1 An element of the constructed string has value zero if the correspond­
  ing character in str, beginning at position pos, is 0.  Otherwise, the
  element has the value one.  Character position pos + M - 1 corresponds
  to  bit position zero.  Subsequent decreasing character positions cor­
  respond to increasing bit positions.

2 If M < N, remaining bit positions are initialized to zero.

  _________________________
  1) The macro CHAR_BIT is defined in <climits>  (_lib.support.limits_).

  23.2.1.2  bitset members                          [lib.bitset.members]

  bitset<N>& operator&=(const bitset<N>& rhs);

  Effects:
    Clears each bit in *this for which the corresponding bit in  rhs  is
    clear, and leaves all other bits unchanged.
  Returns:
    *this.

  bitset<N>& operator|=(const bitset<N>& rhs);

  Effects:
    Sets  each  bit  in  *this for which the corresponding bit in rhs is
    set, and leaves all other bits unchanged.
  Returns:
    *this.

  bitset<N>& operator^=(const bitset<N>& rhs);

  Effects:
    Toggles each bit in *this for which the corresponding bit in rhs  is
    set, and leaves all other bits unchanged.
  Returns:
    *this.

  bitset<N>& operator<<=(size_t pos);

  Effects:
    Replaces  each bit at position I in *this with a value determined as
    follows:

  --If I < pos, the new value is zero;

  --If I >= pos, the new value is the previous value of the bit at posi­
    tion I - pos.
  Returns:
    *this.

  bitset<N>& operator>>=(size_t pos);

  Effects:
    Replaces  each bit at position I in *this with a value determined as
    follows:

  --If pos >= N - I, the new value is zero;

  --If pos < N - I, the new value is the previous value of  the  bit  at

    position I + pos.
  Returns:
    *this.

  bitset<N>& set();

  Effects:
    Sets all bits in *this.
  Returns:
    *this.

  bitset<N>& set(size_t pos, int val = 1);

  Requires:
    pos is valid
  Throws:
    out_of_range if pos does not correspond to a valid bit position.
  Effects:
    Stores  a  new value in the bit at position pos in *this.  If val is
    nonzero, the stored value is one, otherwise it is zero.
  Returns:
    *this.

  bitset<N>& reset();

  Effects:
    Resets all bits in *this.
  Returns:
    *this.

  bitset<N>& reset(size_t pos);

  Requires:
    pos is valid
  Throws:
    out_of_range if pos does not correspond to a valid bit position.
  Effects:
    Resets the bit at position pos in *this.
  Returns:
    *this.

  bitset<N> operator~() const;

  Effects:
    Constructs an object x of class bitset<N> and  initializes  it  with
    *this.
  Returns:
    x.flip().

  bitset<N>& flip();

  Effects:
    Toggles all bits in *this.
  Returns:
    *this.

  bitset<N>& flip(size_t pos);

  Requires:
    pos is valid
  Throws:
    out_of_range if pos does not correspond to a valid bit position.
  Effects:
    Toggles the bit at position pos in *this.
  Returns:
    *this.

  unsigned long to_ulong() const;

  Throws:
    overflow_error  if the integral value x corresponding to the bits in
    *this cannot be represented as type unsigned long.
  Returns:
    x.

  template <class charT, class traits, class Allocator>
  basic_string<charT, traits, Allocator> to_string() const;

  Effects:
    Constructs a string object of the appropriate type  and  initializes
    it to a string of length N characters.  Each character is determined
    by the value of its corresponding bit position in *this.   Character
    position  N  -  1  corresponds  to  bit  position  zero.  Subsequent
    decreasing character positions correspond to  increasing  bit  posi­
    tions.   Bit  value  zero  becomes  the  character  0, bit value one
    becomes the character 1.
  Returns:
    The created object.

  size_t count() const;

  Returns:
    A count of the number of bits set in *this.

  size_t size() const;

  Returns:
    N.

  bool operator==(const bitset<N>& rhs) const;

  Returns:
    A nonzero value if the value of each bit in *this equals  the  value
    of the corresponding bit in rhs.

  bool operator!=(const bitset<N>& rhs) const;

  Returns:
    A nonzero value if !(*this == rhs).

  bool test(size_t pos) const;

  Requires:
    pos is valid
  Throws:
    out_of_range if pos does not correspond to a valid bit position.
  Returns:
    true if the bit at position pos in *this has the value one.

  bool any() const;

  Returns:
    true if any bit in *this is one.

  bool none() const;

  Returns:
    true if no bit in *this is one.

  bitset<N> operator<<(size_t pos) const;

  Returns:
    bitset<N>(*this) <<= pos.

  bitset<N> operator>>(size_t pos) const;

  Returns:
    bitset<N>(*this) >>= pos.

  23.2.1.3  bitset operators                      [lib.bitset.operators]

  bitset<N> operator&(const bitset<N>& lhs, const bitset<N>& rhs);

  Returns:
    bitset<N>(lhs) &= rhs.

  bitset<N> operator|(const bitset<N>& lhs, const bitset<N>& rhs);

  Returns:
    bitset<N>(lhs) |= rhs.

  bitset<N> operator^(const bitset<N>& lhs, const bitset<N>& rhs);

  Returns:
    bitset<N>(lhs) ^= rhs.

  template <class charT, class traits, size_t N>
    basic_istream<charT, traits>&
    operator>>(basic_istream<charT, traits>& is, bitset<N>& x);

1 A formatted input function (_lib.istream.formatted_).
  Effects:
    Extracts  up  to  N  (single-byte) characters from is.  Stores these
    characters in a temporary object str of type string, then  evaluates
    the  expression  x  =  bitset<N>(str).  Characters are extracted and
    stored until any of the following occurs:

  --N characters have been extracted and stored;

  --end-of-file occurs on the input sequence;

  --the next input character is neither 0 or 1 (in which case the  input
    character is not extracted).

2 If  no  characters  are stored in str, calls is.setstate(ios::failbit)
  (which may throw ios_base::failure (_lib.iostate.flags_).
  Returns:
    is.

  template <class charT, class traits, size_t N>
    basic_ostream<charT, traits>&
    operator<<(basic_ostream<charT, traits>& os, const bitset<N>& x);

  Returns:
    os << x.to_string() (_lib.ostream.formatted_).

  23.2.2  Template class deque                               [lib.deque]

1 A deque is a kind of sequence that, like a vector (_lib.vector_), sup­
  ports random access iterators.  In addition, it supports constant time
  insert and erase operations at the beginning or the  end;  insert  and
  erase  in the middle take linear time.  That is, a deque is especially
  optimized for pushing and popping elements at the beginning  and  end.
  As with vectors, storage management is handled automatically.
  namespace std {
    template <class T, class Allocator = allocator<T> >
    class deque {
    public:
    // _lib.deque.types_ types:
      typedef typename Allocator::reference                 reference;
      typedef typename Allocator::const_reference           const_reference;
      typedef implementation defined                  iterator;
      typedef implementation defined                  const_iterator;
      typedef typename Allocator::size_type                 size_type;
      typedef typename Allocator::difference_type           difference_type;
      typedef T value_type;
      typedef Allocator allocator_type;
      typedef reverse_iterator<iterator, value_type,
                   reference, difference_type>              reverse_iterator;
      typedef reverse_iterator<const_iterator, value_type,
                   const_reference, difference_type>        const_reverse_iterator;
    // _lib.deque.cons_ construct/copy/destroy:
      explicit deque(const Allocator& = Allocator());
      explicit deque(size_type n, const T& value = T(),
          const Allocator& = Allocator());
      template <class InputIterator>
        deque(InputIterator first, InputIterator last,
              const Allocator& = Allocator());
      deque(const deque<T,Allocator>& x);
     ~deque();
      deque<T,Allocator>& operator=(const deque<T,Allocator>& x);
      template <class InputIterator>
        void assign(InputIterator first, InputIterator last);
      template <class Size, class T>
        void assign(Size n, const T& t = T());
      allocator_type get_allocator() const;
    // _lib.deque.iterators_ 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;

    // _lib.deque.capacity_ capacity:
      size_type size() const;
      size_type max_size() const;
      void      resize(size_type sz, T c = T());
      bool      empty() const;
    // _lib.deque.access_ element access:
      reference       operator[](size_type n);
      const_reference operator[](size_type n) const;
      reference       at(size_type n);
      const_reference at(size_type n) const;
      reference       front();
      const_reference front() const;
      reference       back();
      const_reference back() const;
    // _lib.deque.modifiers_ modifiers:
      void push_front(const T& x);
      void push_back(const T& x);
      iterator insert(iterator position, const T& x = T());
      void     insert(iterator position, size_type n, const T& x);
      template <class InputIterator>
        void insert (iterator position, InputIterator first, InputIterator last);
      void pop_front();
      void pop_back();
      iterator erase(iterator position);
      iterator erase(iterator first, iterator last);
      void     swap(deque<T,Allocator>&);
      void     clear();
    };
    template <class T, class Allocator>
      bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
    template <class T, class Allocator>
      bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
    // specialized algorithms:
    template <class T, class Allocator>
      void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);
  }

  23.2.2.1  deque types                                [lib.deque.types]

  23.2.2.2  deque constructors, copy, and               [lib.deque.cons]
       assignment

  template <class InputIterator>
    void assign(InputIterator first, InputIterator last);

  Effects:
        erase(begin(), end());
        insert(begin(), first, last);

  template <class Size, class T> void assign(Size n, const T& t = T());

  Effects:
        erase(begin(), end());
        insert(begin(), n, t);

  23.2.2.3  deque iterator support                 [lib.deque.iterators]

  23.2.2.4  deque capacity                          [lib.deque.capacity]

  void resize(size_type sz, T c = T());

  Effects:
        if (sz > size())
          insert(end(), sz-size(), c);
        else if (sz < size())
          erase(begin()+sz, s.end());
        else
          ; // do nothing

  23.2.2.5  deque element access                      [lib.deque.access]

  23.2.2.6  deque modifiers                        [lib.deque.modifiers]

  iterator insert(iterator position, const T& x = T());
  void     insert(iterator position, size_type n, const T& x);
  template <class InputIterator>
    void insert(iterator position,
                InputIterator first, InputIterator last);

  Effects:
    An insert in the middle of the deque invalidates all  the  iterators
    and references to elements of the deque.  An insert at either end of
    the deque invalidates all the iterators to the  deque,  but  has  no
    effect on the validity of references to elements of the deque.
  Complexity:
    In  the  worst  case,  inserting a single element into a deque takes
    time linear in the minimum of the distance from the insertion  point
    to  the  beginning  of the deque and the distance from the insertion
    point to the end of the deque.  Inserting a single element either at
    the  beginning  or  end  of  a  deque always takes constant time and
    causes a single call to the copy constructor of T.

  iterator erase(iterator position);
  iterator erase(iterator first, iterator last);

  Effects:
    An erase in the middle of the deque invalidates  all  the  iterators
    and references to elements of the deque.   An erase at either end of
    the deque invalidates only the iterators and the references  to  the
    erased elements.

  Complexity:
    The  number  of calls to the destructor is the same as the number of
    elements erased, but the number of the calls to the assignment oper­
    ator  is  equal  to the minimum of the number of elements before the
    erased elements and the number of element after the erased elements.

  23.2.2.7  deque specialized algorithms             [lib.deque.special]

  template <class T, class Allocator>
    void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);

  Effects:
        x.swap(y);

  23.2.3  Template class list                                 [lib.list]

1 A list is a kind of sequence that supports bidirectional iterators and
  allows constant time insert and erase operations anywhere  within  the
  sequence,  with storage management handled automatically.  Unlike vec­
  tors (_lib.vector_) and deques (_lib.deque_), fast  random  access  to
  list  elements is not supported, but many algorithms only need sequen­
  tial access anyway.
  namespace std {
    template <class T, class Allocator = allocator<T> >
    class list {
    public:
    // _lib.list.types_ types:
      typedef typename Allocator::reference                 reference;
      typedef typename Allocator::const_reference           const_reference;
      typedef implementation defined                  iterator;
      typedef implementation defined                  const_iterator;
      typedef typename Allocator::size_type                 size_type;
      typedef typename Allocator::difference_type           difference_type;
      typedef T value_type;
      typedef Allocator allocator_type;
      typedef reverse_bidirectional_iterator<iterator, value_type,
                   reference, difference_type>              reverse_iterator;
      typedef reverse_bidirectional_iterator<const_iterator, value_type,
                   const_reference, difference_type>        const_reverse_iterator;

    // _lib.list.cons_ construct/copy/destroy:
      explicit list(const Allocator& = Allocator());
      explicit list(size_type n, const T& value = T(),
                    const Allocator& = Allocator());
      template <class InputIterator>
        list(InputIterator first, InputIterator last,
             const Allocator& = Allocator());
      list(const list<T,Allocator>& x);
     ~list();
      list<T,Allocator>& operator=(const list<T,Allocator>& x);
      template <class InputIterator>
        void assign(InputIterator first, InputIterator last);
      template <class Size, class T>
        void assign(Size n, const T& t = T());
      allocator_type get_allocator() const;
    // _lib.list.iterators_ 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;
    // _lib.list.capacity_ capacity:
      bool      empty() const;
      size_type size() const;
      size_type max_size() const;
      void      resize(size_type sz, T c = T());
    // element access:
      reference       front();
      const_reference front() const;
      reference       back();
      const_reference back() const;
    // _lib.list.modifiers_ modifiers:
      void push_front(const T& x);
      void pop_front();
      void push_back(const T& x);
      void pop_back();
      iterator insert(iterator position, const T& x = T());
      void     insert(iterator position, size_type n, const T& x);
      template <class InputIterator>
        void insert(iterator position, InputIterator first,
                    InputIterator last);
      iterator erase(iterator position);
      iterator erase(iterator position, iterator last);
      void     swap(list<T,Allocator>&);
      void     clear();
    // _lib.list.ops_ list operations:
      void splice(iterator position, list<T,Allocator>& x);
      void splice(iterator position, list<T,Allocator>& x, iterator i);
      void splice(iterator position, list<T,Allocator>& x, iterator first,
                  iterator last);

      void remove(const T& value);
      template <class Predicate> void remove_if(Predicate pred);
      void unique();
      template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
      void merge(list<T,Allocator>& x);
      template <class Compare> void merge(list<T,Allocator>& x, Compare comp);
      void sort();
      template <class Compare> void sort(Compare comp);
      void reverse();
    };
    template <class T, class Allocator>
      bool operator==(const list<T,Allocator>& x, const list<T,Allocator>& y);
    template <class T, class Allocator>
      bool operator< (const list<T,Allocator>& x, const list<T,Allocator>& y);
    // specialized algorithms:
    template <class T, class Allocator>
      void swap(list<T,Allocator>& x, list<T,Allocator>& y);
  }

  23.2.3.1  list types                                  [lib.list.types]

  23.2.3.2  list constructors, copy, and assignment      [lib.list.cons]

  template <class InputIterator>
    void assign(InputIterator first, InputIterator last);

  Effects:
        erase(begin(), end());
        insert(begin(), first, last);

  template <class Size, class T> void assign(Size n, const T& t = T());

  Effects:
        erase(begin(), end());
        insert(begin(), n, t);

  23.2.3.3  list iterator support                   [lib.list.iterators]

  23.2.3.4  list capacity                            [lib.list.capacity]

  void resize(size_type sz, T c = T());

  Effects:
        if (sz > size())
          insert(end(), sz-size(), c);
        else if (sz < size())
          erase(begin()+sz, s.end());
        else
          ; // do nothing

  23.2.3.5  list element access                        [lib.list.access]

  23.2.3.6  list modifiers                          [lib.list.modifiers]

  iterator insert(iterator position, const T& x = T());
  void     insert(iterator position, size_type n, const T& x);
  template <class InputIterator>
    void insert(iterator position, InputIterator first,
                InputIterator last);

  Notes:
    Does not affect the validity of iterators and references.
  Complexity:
    Insertion  of  a  single element into a list takes constant time and
    exactly one call to the copy constructor of T.  Insertion of  multi­
    ple  elements  into  a  list  is  linear  in  the number of elements
    inserted, and the number of calls to the copy constructor  of  T  is
    exactly equal to the number of elements inserted.

  iterator erase(iterator position);
  iterator erase(iterator first, iterator last);

  Effects:
    Invalidates  only  the  iterators  and references to the erased ele­
    ments.
  Complexity:
    Erasing a single element is a constant time operation with a  single
    call  to  the  destructor of 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 T is exactly equal to the size of the range.

  23.2.3.7  list operations                               [lib.list.ops]

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

2 list provides three splice operations that destructively move elements
  from one list to another.

  void splice(iterator position, list<T,Allocator>& x);

  Requires:
    &x != this.
  Effects:
    Inserts the contents of x before position and x becomes empty.
  Complexity:
    Constant time.

  void splice(iterator position, list<T,Allocator>& x, iterator i);

  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.
  Requires:
    i is a valid dereferenceable iterator of x.
  Complexity:
    Constant time.

  void splice(iterator position, list<T,Allocator>& x, iterator first,
              iterator last);

  Effects:
    Inserts  elements  in  the  range  [first, last) before position and
    removes the elements from x.
  Requires:
    [first, last) is a valid range in x.  The  result  is  undefined  if
    position is an iterator in the range [first, last).
  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)  ==
    true.
  Notes:
    Stable:   the relative order of the elements that are not removed is
    the same as their relative order in the original list.
  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 in the list.
  Complexity:
    Exactly  size()  - 1 applications of the corresponding binary predi­
    cate.

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

  Requires:
    comp defines a strict weak  ordering  (_lib.alg.sorting_),  and  the
    list  and  the  argument  list  are  both  sorted  according to this

    ordering.
  Effects:
    Merges the argument list into the list.
  Notes:
    Stable:  for equivalent elements in the two lists, the elements from
    the  list  always precede the elements from the argument list.  x is
    empty after the merge.
  Complexity:
    At most size() + x.size() - 1 comparisons.

  void reverse();

  Effects:
    Reverses the order of the elements in the list.
  Complexity:
    Linear time.

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

  Requires:
    operator< (for the first version, or comp (for the  second  version)
    defines a strict weak ordering (_lib.alg.sorting_).
  Effects:
    Sorts  the  list  according  to  the operator< or a Compare function
    object.
  Notes:
    Stable:  the relative order of the equivalent elements is preserved.
  Complexity:
    Approximately NlogN comparisons, where N == size().

  23.2.3.8  list specialized algorithms               [lib.list.special]

  template <class T, class Allocator>
    void swap(list<T,Allocator>& x, list<T,Allocator>& y);

  Effects:
        x.swap(y);

  23.2.4  Container adapters                    [lib.container.adapters]

  23.2.4.1  Template class queue                             [lib.queue]

1 Any  sequence  supporting  operations front(), back(), push_back() and
  pop_front() can be used to instantiate  queue.   In  particular,  list
  (_lib.list_) and deque (_lib.deque_) can be used.

  nmespace std {
    template <class T, class Container = deque<T>,
              class Allocator = allocator<T> >
    class queue {
    public:
      typedef typename Container::value_type value_type;
      typedef typename Container::size_type  size_type;
      typedef Allocator allocator_type;
    protected:
      Container c;
    public:
      explicit queue(const Allocator& = Allocator());
      allocator_type get_allocator() const;

      bool      empty() const             { return c.empty(); }
      size_type size()  const             { return c.size(); }
      value_type&       front()           { return c.front(); }
      const value_type& front() const     { return c.front(); }
      value_type&       back()            { return c.back(); }
      const value_type& back() const      { return c.back(); }
      void push(const value_type& x)      { c.push_back(x); }
      void pop()                          { c.pop_front(); }
    };
    template <class T, class Container, class Allocator>
      bool operator==(const queue<T, Container, Allocator>& x,
                      const queue<T, Container, Allocator>& y);
    template <class T, class Container, class Allocator>
      bool operator< (const queue<T, Container, Allocator>& x,
                      const queue<T, Container, Allocator>& y);
  }
  operator==
  Returns:
    x.c == y.c.
    operator<
  Returns:
    x.c < y.c.

  23.2.4.2  Template class priority_queue           [lib.priority.queue]

1 Any  sequence  with  random  access iterator and supporting operations
  front(), push_back() and pop_back() can be used to instantiate  prior­
  ity_queue.    In   particular,   vector   (_lib.vector_)   and   deque
  (_lib.deque_) can be used.  Instantiating priority_queue also involves
  supplying  a  function  or function object for making priority compar­
  isons; the library  assumes  that  the  function  or  function  object
  defines a strict weak ordering (_lib.alg.sorting_).

  namespace std {
    template <class T, class Container = vector<T>,
              class Compare = less<Container::value_type>,
              class Allocator = allocator<T> >
    class priority_queue {
    public:
      typedef typename Container::value_type value_type;
      typedef typename Container::size_type  size_type;
      typedef Allocator allocator_type;
    protected:
      Container c;
      Compare comp;
    public:
      explicit priority_queue(const Compare& x = Compare(),
                              const Allocator& = Allocator());
      template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last,
                       const Compare& x = Compare());
      allocator_type get_allocator() const;
      bool      empty() const       { return c.empty(); }
      size_type size()  const       { return c.size(); }
      const value_type& top() const { return c.front(); }
      void push(const value_type& x);
      void pop();
    };
    // no equality is provided
  }

  23.2.4.2.1  priority_queue constructors            [lib.priqueue.cons]

  priority_queue(const Compare& x = Compare());

  Requires:
    x defines a strict weak ordering (_lib.alg.sorting_).
  Effects:
    Initializes comp with x.

  template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last,
      const Compare& x = Compare());

  Requires:
    x defines a strict weak ordering (_lib.alg.sorting_).
  Effects:
            : c(first, last), comp(x) {
              make_heap(c.begin(), c.end(), comp);
          }

  23.2.4.2.2  priority_queue members              [lib.priqueue.members]

  void push(const value_type& x);

  Effects:
            c.push_back(x);
            push_heap(c.begin(), c.end(), comp);

  void pop();

  Effects:
            pop_heap(c.begin(), c.end(), comp);
            c.pop_back();

  23.2.4.3  Template class stack                             [lib.stack]

1 Any  sequence supporting operations back(), push_back() and pop_back()
  can  be  used   to   instantiate   stack.    In   particular,   vector
  (_lib.vector_), list (_lib.list_) and deque (_lib.deque_) can be used.
  namespace std {
    template <class T, class Container = deque<T>,
              class Allocator = allocator<T> >
    class stack {
    public:
      typedef typename Container::value_type value_type;
      typedef typename Container::size_type  size_type;
      typedef Allocator allocator_type;
    protected:
      Container c;
    public:
      explicit stack(const Allocator& = Allocator());
      allocator_type get_allocator() const;

      bool      empty() const             { return c.empty(); }
      size_type size()  const             { return c.size(); }
      value_type&       top()             { return c.back(); }
      const value_type& top() const       { return c.back(); }
      void push(const value_type& x)      { c.push_back(x); }
      void pop()                          { c.pop_back(); }
    };
    template <class T, class Container, class Allocator>
      bool operator==(const stack<T, Container, Allocator>& x,
                      const stack<T, Container, Allocator>& y);
    template <class T, class Container, class Allocator>
      bool operator< (const stack<T, Container, Allocator>& x,
                      const stack<T, Container, Allocator>& y);
  }
  operator==
  Returns:
    x.c == y.c.  operator<

  Returns:
    x.c < y.c.

  23.2.5  Template class vector                             [lib.vector]

1 A vector is a kind of sequence that supports random access  iterators.
  In  addition,  it  supports (amortized) constant time insert and erase
  operations at the end; insert and erase  in  the  middle  take  linear
  time.   Storage  management is handled automatically, though hints can
  be given to improve efficiency.
  namespace std {
    template <class T, class Allocator = allocator<T> >
    class vector {
    public:
    // _lib.vector.types_ types:
      typedef typename Allocator::reference                 reference;
      typedef typename Allocator::const_reference           const_reference;
      typedef implementation defined                  iterator;
      typedef implementation defined                  const_iterator;
      typedef typename Allocator::size_type       size_type;
      typedef typename Allocator::difference_type difference_type;
      typedef T value_type;
      typedef Allocator allocator_type;
      typedef reverse_iterator<iterator, value_type,
                   reference, difference_type>              reverse_iterator;
      typedef reverse_iterator<const_iterator, value_type,
                   const_reference, difference_type>        const_reverse_iterator;
    // _lib.vector.cons_ construct/copy/destroy:
      explicit vector(const Allocator& = Allocator());
      explicit vector(size_type n, const T& value = T(),
          const Allocator& = Allocator());
      template <class InputIterator>
        vector(InputIterator first, InputIterator last,
          const Allocator& = Allocator());
      vector(const vector<T,Allocator>& x);
     ~vector();
      vector<T,Allocator>& operator=(const vector<T,Allocator>& x);
      template <class InputIterator>
        void assign(InputIterator first, InputIterator last);
      template <class Size, class T> void assign(Size n, const T& t = T());
      allocator_type get_allocator() const;
    // _lib.vector.iterators_ 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;

    // _lib.vector.capacity_ capacity:
      size_type size() const;
      size_type max_size() const;
      void      resize(size_type sz, T c = T());
      size_type capacity() const;
      bool      empty() const;
      void      reserve(size_type n);
    // _lib.vector.access_ element access:
      reference       operator[](size_type n);
      const_reference operator[](size_type n) const;
      const_reference at(size_type n) const;
      reference       at(size_type n);
      reference       front();
      const_reference front() const;
      reference       back();
      const_reference back() const;
    // _lib.vector.modifiers_ modifiers:
      void push_back(const T& x);
      void pop_back();
      iterator insert(iterator position, const T& x = T());
      void     insert(iterator position, size_type n, const T& x);
      template <class InputIterator>
          void insert(iterator position, InputIterator first, InputIterator last);
      iterator erase(iterator position);
      iterator erase(iterator first, iterator last);
      void     swap(vector<T,Allocator>&);
      void     clear();
    };
    template <class T, class Allocator>
      bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
    template <class T, class Allocator>
      bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
    // specialized algorithms:
    template <class T, class Allocator>
      void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
  }

  23.2.5.1  vector types                              [lib.vector.types]

  23.2.5.2  vector constructors, copy, and             [lib.vector.cons]
       assignment

  vector(const Allocator& = Allocator());
  explicit vector(size_type n, const T& value = T(),
                  const Allocator& = Allocator());
  template <class InputIterator>
    vector(InputIterator first, InputIterator last,
           const Allocator& = Allocator());
  vector(const vector<T,Allocator>& x);

  Complexity:
    The  constructor template <class InputIterator> vector(InputIterator

    first, InputIterator last) makes only N calls to the copy  construc­
    tor  of  T  (where  N is the distance between first and last) and no
    reallocations if iterators first and last are of  forward,  bidirec­
    tional,  or  random  access categories.  It does at most 2N calls to
    the copy constructor of T and logN reallocations if  they  are  just
    input  iterators,  since  it is impossible to determine the distance
    between first and last and then do copying.

  template <class InputIterator>
    void assign(InputIterator first, InputIterator last);

  Effects:
        erase(begin(), end());
        insert(begin(), first, last);

  template <class Size, class T> void assign(Size n, const T& t = T());

  Effects:
        erase(begin(), end());
        insert(begin(), n, t);

  23.2.5.3  vector iterator support               [lib.vector.iterators]

  23.2.5.4  vector capacity                        [lib.vector.capacity]

  size_type capacity() const;

  Returns:
    The size of the allocated storage in the vector.

  void reserve(size_type n);

  Effects:
    A directive that informs a vector of a planned change  in  size,  so
    that  it  can  manage  the  storage  allocation  accordingly.  After
    reserve(), capacity() is greater or equal to the argument of reserve
    if  reallocation  happens; and equal to the previous value of capac­
    ity() otherwise.  Reallocation happens at this point if and only  if
    the current capacity is less than the argument of reserve().
  Complexity:
    It does not change the size of the sequence and takes at most linear
    time in the size of the sequence.
  Notes:
    Reallocation invalidates all the references, pointers, and iterators
    referring to the elements in the sequence.  It is guaranteed that no
    reallocation takes place during the  insertions  that  happen  after
    reserve()  takes  place  till  the  time when the size of the vector
    reaches the size specified by reserve().

  void resize(size_type sz, T c = T());

  Effects:
        if (sz > size())
          insert(end(), sz-size(), c);
        else if (sz < size())
          erase(begin()+sz, s.end());
        else
          ; // do nothing

  23.2.5.5  vector element access                    [lib.vector.access]

  23.2.5.6  vector modifiers                      [lib.vector.modifiers]

  iterator insert(iterator position, const T& x = T());
  void     insert(iterator position, size_type n, const T& x);
  template <class InputIterator>
    void insert(iterator position, InputIterator first, InputIterator last);

  Notes:
    Causes reallocation if the new size is greater than the  old  capac­
    ity.   If  no reallocation happens, all the iterators and references
    before the insertion point remain valid.
  Complexity:
    Inserting a single element into a vector is linear in  the  distance
    from the insertion point to the end of the vector.
    The  amortized complexity over the lifetime of a vector of inserting
    a single element at its end is constant.  Insertion of multiple ele­
    ments into a vector with a single call of the insert member function
    is linear in the sum of the number of elements plus the distance  to
    the end of the vector.2)

  iterator erase(iterator position);
  iterator erase(iterator first, iterator last);

  Effects:
    Invalidates  all the iterators and references after the point of the
    erase.
  Complexity:
    The destructor of T is called the number of times equal to the  num­
    ber  of  the  elements  erased,  but the assignment operator of T is
  _________________________
  2)  In other words, it is much faster to insert many elements into the
  middle of a vector at once than to do the insertion  one  at  a  time.
  The  insert  template  member function preallocates enough storage for
  the insertion if the iterators first and last are of forward, bidirec­
  tional  or random access category.  Otherwise, it does insert elements
  one by one and should not be used for inserting  into  the  middle  of
  vectors.

    called the number of times equal to the number of  elements  in  the
    vector after the erased elements.

  23.2.5.7  vector specialized algorithms           [lib.vector.special]

  template <class T, class Allocator>
    void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);

  Effects:
        x.swap(y);

  23.2.6  Class vector<bool>                           [lib.vector.bool]

1 To optimize space allocation, a specialization of vector for bool ele­
  ments is provided:3)
  namespace std {
    template <class Allocator = allocator<T> >
    class vector<bool, Allocator> {
    public:
    // types:
      typedef const reference const_reference;
      typedef implementation defined                     iterator;
      typedef implementation defined                     const_iterator;
      typedef typename Allocator::size_type       size_type;
      typedef typename Allocator::difference_type difference_type;
      typedef bool value_type;
      typedef Allocator allocator_type;
      typedef reverse_iterator<iterator, value_type,
                   reference, difference_type>              reverse_iterator;
      typedef reverse_iterator<const_iterator, value_type,
                   const_reference, difference_type>        const_reverse_iterator;
    // bit reference:
      class reference {
       friend class vector;
       reference();
      public:
       ~reference();
        operator bool() const;
        reference& operator=(const bool x);
        void flip();      // flips the bit
      };

  _________________________
  3) An implementation is expected to provide  specializations  of  vec­
  tor<bool> for all supported memory models.

    // construct/copy/destroy:
      explicit vector(const Allocator& = Allocator());
      explicit vector(size_type n, const bool& value = bool(),
                      const Allocator& = Allocator());
      template <class InputIterator>
        vector(InputIterator first, InputIterator last,
          const Allocator& = Allocator());
      vector(const vector<bool,Allocator>& x);
     ~vector();
      vector<bool,Allocator>& operator=(const vector<bool,Allocator>& x);
      template <class InputIterator>
        void assign(InputIterator first, InputIterator last);
      template <class Size, class T> void assign(Size n, const T& 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;
    // capacity:
      size_type size() const;
      size_type max_size() const;
      void      resize(size_type sz, bool c = false);
      size_type capacity() const;
      bool      empty() const;
      void      reserve(size_type n);
    // element access:
      reference       operator[](size_type n);
      const_reference operator[](size_type n) const;
      const_reference at(size_type n) const;
      reference       at(size_type n);
      reference       front();
      const_reference front() const;
      reference       back();
      const_reference back() const;
    // modifiers:
      void push_back(const bool& x);
      void pop_back();
      iterator insert(iterator position, const bool& x = bool());
      void     insert (iterator position, size_type n, const bool& x);
      template <class InputIterator>
          void insert (iterator position, InputIterator first, InputIterator last);
      iterator erase(iterator position);
      iterator erase(iterator first, iterator last);
      void swap(vector<bool,Allocator>&);
      static void swap(reference x, reference y);
      void flip();        // flips all bits
      void clear();
    };

    template <class Allocator>
      bool operator==(const vector<bool,Allocator>& x,
                      const vector<bool,Allocator>& y);
    template <class Allocator>
      bool operator< (const vector<bool,Allocator>& x,
                      const vector<bool,Allocator>& y);
    // specialized algorithms:
    template <class Allocator>
      void swap(vector<bool,Allocator>& x, vector<bool,Allocator>& y);
  }

2 reference  is  a  class that simulates the behavior of references of a
  single bit in vector<bool>.

  23.3  Associative containers                         [lib.associative]

1 Headers <map> and <set>:

  Header <map> synopsis

  #include <memory>       // for allocator
  #include <utility>      // for pair
  #include <functional>   // for less

  namespace std {
    template <class Key, class T, class Compare = less<Key>,
              class Allocator = allocator<T> >
      class map;
    template <class Key, class T, class Compare, class Allocator>
      bool operator==(const map<Key,T,Compare,Allocator>& x,
                      const map<Key,T,Compare,Allocator>& y);
    template <class Key, class T, class Compare, class Allocator>
      bool operator< (const map<Key,T,Compare,Allocator>& x,
                      const map<Key,T,Compare,Allocator>& y);
    template <class Key, class T, class Compare, class Allocator>
      void swap(map<Key,T,Compare,Allocator>& x,
                map<Key,T,Compare,Allocator>& y);
    template <class Key, class T, class Compare = less<Key>,
              class Allocator = allocator<T> >
      class multimap;
    template <class Key, class T, class Compare, class Allocator>
      bool operator==(const multimap<Key,T,Compare,Allocator>& x,
                      const multimap<Key,T,Compare,Allocator>& y);
    template <class Key, class T, class Compare, class Allocator>
      bool operator< (const multimap<Key,T,Compare,Allocator>& x,
                      const multimap<Key,T,Compare,Allocator>& y);
    template <class Key, class T, class Compare, class Allocator>
      void swap(multimap<Key,T,Compare,Allocator>& x,
                multimap<Key,T,Compare,Allocator>& y);
  }

  Header <set> synopsis

  #include <memory>       // for allocator
  #include <utility>      // for pair
  #include <functional>   // for less

  namespace std {
    template <class Key, class Compare = less<Key>,
              class Allocator = allocator<T> >
      class set;
    template <class 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>
      bool operator< (const set<Key,Compare,Allocator>& x,
                      const set<Key,Compare,Allocator>& y);
    template <class Key, class Compare, class Allocator>
      void swap(set<Key,Compare,Allocator>& x,
                set<Key,Compare,Allocator>& y);
    template <class Key, class Compare = less<Key>,
              class Allocator = allocator<T> >
      class multiset;
    template <class 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>
      bool operator< (const multiset<Key,Compare,Allocator>& x,
                      const multiset<Key,Compare,Allocator>& y);
    template <class Key, class Compare, class Allocator>
      void swap(multiset<Key,Compare,Allocator>& x,
                multiset<Key,Compare,Allocator>& y);
  }

  23.3.1  Template class map                                   [lib.map]

1 A map is a kind of associative container  that  supports  unique  keys
  (contains  at  most  one  of  each  key  value)  and provides for fast
  retrieval of values of another type T based on the keys.  Map supports
  bidirectional iterators.

  +-------                 BEGIN BOX 1                -------+
  Change:  N0845  specified adding a "typedef T referent_type" to map<>.
  However, it already has "typedef T mapped_type".  Hence, referent_type
  has not been added.
  +-------                  END BOX 1                 -------+

  namespace std {
    template <class Key, class T, class Compare = less<Key>,
              class Allocator = allocator<T> >
    class map {
    public:
    // _lib.map.types_ types:
      typedef Key                key_type;
      typedef T                  mapped_type;
      typedef pair<const Key, T> value_type;
      typedef Compare            key_compare;
      typedef Allocator          allocator_type;
      typedef typename Allocator::reference                 reference;
      typedef typename Allocator::const_reference           const_reference;
      typedef implementation defined                  iterator;
      typedef implementation defined                  const_iterator;
      typedef typename Allocator::size_type                 size_type;
      typedef typename Allocator::difference_type           difference_type;
      typedef reverse_iterator<iterator, value_type,
                   reference, difference_type>              reverse_iterator;
      typedef reverse_iterator<const_iterator, value_type,
                   const_reference, difference_type>      const_reverse_iterator;
      class value_compare
        : public binary_function<value_type,value_type,bool> {
      friend class map;
      protected:
        Compare comp;
        value_compare(Compare c) : comp(c) {}
      public:
        bool operator()(const value_type& x, const value_type& y) {
          return comp(x.first, y.first);
        }
      };
    // _lib.map.cons_ construct/copy/destroy:
      explicit map(const Compare& comp = Compare(), const Allocator& = Allocator());
      template <class InputIterator>
        map(InputIterator first, InputIterator last,
            const Compare& comp = Compare(), const Allocator& = Allocator());
      map(const map<Key,T,Compare,Allocator>& x);
     ~map();
      map<Key,T,Compare,Allocator>&
        operator=(const map<Key,T,Compare,Allocator>& x);
    // _lib.map.iterators_ 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;

    // _lib.map.capacity_ capacity:
      bool      empty() const;
      size_type size() const;
      size_type max_size() const;
    // _lib.map.access_ element access:
      mapped_type&       operator[](const key_type& x);
      const mapped_type& operator[](const key_type& x) const;
    // _lib.map.modifiers_ modifiers:
      pair<iterator, bool> insert(const value_type& x);
      iterator             insert(iterator position, const value_type& x);
      template <class InputIterator>
        void insert(InputIterator first, InputIterator last);
      void      erase(iterator position);
      size_type erase(const key_type& x);
      void      erase(iterator first, iterator last);
      void swap(map<Key,T,Compare,Allocator>&);
      void clear();
    // _lib.map.observers_ observers:
      key_compare   key_comp() const;
      value_compare value_comp() const;
    // _lib.map.ops_ map 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 <class Key, class T, class Compare, class Allocator>
      bool operator==(const map<Key,T,Compare,Allocator>& x,
                      const map<Key,T,Compare,Allocator>& y);
    template <class Key, class T, class Compare, class Allocator>
      bool operator< (const map<Key,T,Compare,Allocator>& x,
                      const map<Key,T,Compare,Allocator>& y);
    // specialized algorithms:
    template <class Key, class T, class Compare, class Allocator>
      void swap(map<Key,T,Compare,Allocator>& x,
                map<Key,T,Compare,Allocator>& y);
  }

  23.3.1.1  map types                                    [lib.map.types]

  23.3.1.2  map constructors, copy, and assignment        [lib.map.cons]

  23.3.1.3  map iterator support                     [lib.map.iterators]

  23.3.1.4  map capacity                              [lib.map.capacity]

  23.3.1.5  map element access                          [lib.map.access]

  T& operator[](const key_type& x);

  Returns:
    (*((insert(make_pair(x, T()))).first)).second.

  23.3.1.6  map modifiers                            [lib.map.modifiers]

  23.3.1.7  map observers                            [lib.map.observers]

  23.3.1.8  map operations                                 [lib.map.ops]

  23.3.1.9  map specialized algorithms                 [lib.map.special]

  template <class Key, class T, class Compare, class Allocator>
    void swap(map<Key,T,Compare,Allocator>& x,
              map<Key,T,Compare,Allocator>& y);

  Effects:
        x.swap(y);

  23.3.2  Template class multimap                         [lib.multimap]

1 A multimap is a kind of associative container that supports equivalent
  keys (possibly contains multiple copies of the  same  key  value)  and
  provides  for  fast retrieval of values of another type T based on the
  keys.  Multimap supports bidirectional iterators.

  +-------                 BEGIN BOX 2                -------+
  Change: N0845 specified adding a "typedef  T  referent_type"  to  mul­
  timap<>.   However,  it  already  has "typedef T mapped_type".  Hence,
  referent_type has not been added.
  +-------                  END BOX 2                 -------+

  namespace std {
    template <class Key, class T, class Compare = less<Key>,
              class Allocator = allocator<T> >
    class multimap {
    public:
    // types:
      typedef Key               key_type;
      typedef T                 mapped_type;
      typedef pair<const Key,T> value_type;
      typedef Compare           key_compare;
      typedef Allocator         allocator_type;

      class value_compare
        : public binary_function<value_type,value_type,bool> {
      friend class multimap;
      protected:
        Compare comp;
        value_compare(Compare c) : comp(c) {}
      public:
        bool operator()(const value_type& x, const value_type& y) {
          return comp(x.first, y.first);
        }
      };
      typedef typename Allocator::reference                reference;
      typedef typename Allocator::const_reference          const_reference;
      typedef implementation defined                 iterator;
      typedef implementation defined                 const_iterator;
      typedef typename Allocator::size_type                size_type;
      typedef typename Allocator::difference_type          difference_type;
      typedef reverse_iterator<iterator, value_type,
                   reference, difference_type>             reverse_iterator;
      typedef reverse_iterator<const_iterator, value_type,
                   const_reference, difference_type>     const_reverse_iterator;
    // construct/copy/destroy:
      explicit multimap(const Compare& comp = Compare(),
                        const Allocator& = Allocator());
      template <class InputIterator>
        multimap(InputIterator first, InputIterator last,
                 const Compare& comp = Compare(), const Allocator& = Allocator());
      multimap(const multimap<Key,T,Compare,Allocator>& x);
     ~multimap();
      multimap<Key,T,Compare,Allocator>&
        operator=(const multimap<Key,T,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;
    // capacity:
      bool           empty() const;
      size_type      size() const;
      size_type      max_size() const;
    // modifiers:
      iterator insert(const value_type& x);
      iterator insert(iterator position, const value_type& x);
      template <class InputIterator>
        void insert(InputIterator first, InputIterator last);

      void      erase(iterator position);
      size_type erase(const key_type& x);
      void      erase(iterator first, iterator last);
      void swap(multimap<Key,T,Compare,Allocator>&);
      void clear();
    // observers:
      key_compare    key_comp() const;
      value_compare  value_comp() const;
    // map 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 <class Key, class T, class Compare, class Allocator>
      bool operator==(const multimap<Key,T,Compare,Allocator>& x,
                      const multimap<Key,T,Compare,Allocator>& y);
    template <class Key, class T, class Compare, class Allocator>
      bool operator< (const multimap<Key,T,Compare,Allocator>& x,
                      const multimap<Key,T,Compare,Allocator>& y);
    // specialized algorithms:
    template <class Key, class T, class Compare, class Allocator>
      void swap(multimap<Key,T,Compare,Allocator>& x,
                multimap<Key,T,Compare,Allocator>& y);
  }

  23.3.2.1  multimap specialized algorithms       [lib.multimap.special]

  template <class Key, class T, class Compare, class Allocator>
    void swap(multimap<Key,T,Compare,Allocator>& x,
              multimap<Key,T,Compare,Allocator>& y);

  Effects:
        x.swap(y);

  23.3.3  Template class set                                   [lib.set]

1 A set is a kind of associative container  that  supports  unique  keys
  (contains  at  most  one  of  each  key  value)  and provides for fast
  retrieval of the keys themselves.  Set supports  bidirectional  itera­
  tors.

  namespace std {
    template <class Key, class Compare = less<Key>,
              class Allocator = allocator<T> >
    class set {
    public:
    // _lib.set.types_ 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 implementation defined        iterator;
      typedef implementation defined        const_iterator;
      typedef typename Allocator::size_type       size_type;
      typedef typename Allocator::difference_type difference_type;
      typedef reverse_iterator<iterator, value_type,
        reference, difference_type>               reverse_iterator;
      typedef reverse_iterator<const_iterator, value_type,
        const_reference, difference_type>         const_reverse_iterator;
    // _lib.set.cons_ construct/copy/destroy:
      explicit set(const Compare& comp = Compare(), const Allocator& = Allocator());
      template <class InputIterator>
        set(InputIterator first, InputIterator last,
            const Compare& comp = Compare(), const Allocator& = Allocator());
      set(const set<Key,Compare,Allocator>& x);
     ~set();
      set<Key,Compare,Allocator>& operator=(const set<Key,Compare,Allocator>& x);
      allocator_type get_allocator() const;
    // _lib.set.iterators_ 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;
    // _lib.set.capacity_ capacity:
      bool          empty() const;
      size_type     size() const;
      size_type     max_size() const;
    // _lib.set.modifiers_ modifiers:
      pair<iterator,bool> insert(const value_type& x);
      iterator             insert(iterator position, const value_type& x);
      template <class InputIterator>
          void insert(InputIterator first, InputIterator last);
      void      erase(iterator position);
      size_type erase(const key_type& x);
      void      erase(iterator first, iterator last);
      void swap(set<Key,Compare,Allocator>&);
      void clear();

    // _lib.set.observers_ observers:
      key_compare   key_comp() const;
      value_compare value_comp() const;
    // _lib.set.ops_ set operations:
      iterator  find(const key_type& x) const;
      size_type count(const key_type& x) const;
      iterator  lower_bound(const key_type& x) const;
      iterator  upper_bound(const key_type& x) const;
      pair<iterator,iterator> equal_range(const key_type& x) const;
    };
    template <class 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>
      bool operator< (const set<Key,Compare,Allocator>& x,
                      const set<Key,Compare,Allocator>& y);
    // specialized algorithms:
    template <class Key, class Compare, class Allocator>
      void swap(set<Key,Compare,Allocator>& x,
                set<Key,Compare,Allocator>& y);
  }

  23.3.3.1  set types                                    [lib.set.types]

  23.3.3.2  set constructors, copy, and assignment        [lib.set.cons]

  23.3.3.3  set iterator support                     [lib.set.iterators]

  23.3.3.4  set capacity                              [lib.set.capacity]

  23.3.3.5  set modifiers                            [lib.set.modifiers]

  23.3.3.6  set observers                            [lib.set.observers]

  23.3.3.7  set operations                                 [lib.set.ops]

  23.3.3.8  set specialized algorithms                 [lib.set.special]

  template <class Key, class Compare, class Allocator>
    void swap(set<Key,Compare,Allocator>& x,
              set<Key,Compare,Allocator>& y);

  Effects:
        x.swap(y);

  23.3.4  Template class multiset                         [lib.multiset]

1 A multiset is a kind of associative container that supports equivalent
  keys (possibly contains multiple copies of the  same  key  value)  and
  provides for fast retrieval of the keys themselves.  Multiset supports
  bidirectional iterators.

  namespace std {
    template <class Key, class Compare = less<Key>,
              class Allocator = allocator<T> >
    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 implementation defined        iterator;
      typedef implementation defined        const_iterator;
      typedef typename Allocator::size_type       size_type;
      typedef typename Allocator::difference_type difference_type;
      typedef reverse_iterator<iterator, value_type,
        reference, difference_type>               reverse_iterator;
      typedef reverse_iterator<const_iterator, value_type,
        const_reference, difference_type>         const_reverse_iterator;
    // construct/copy/destroy:
      explicit multiset(const Compare& comp = Compare(),
                        const Allocator& = Allocator());
      template <class InputIterator>
        multiset(InputIterator first, InputIterator last,
                 const Compare& comp = Compare(), const Allocator& = Allocator());
      multiset(const multiset<Key,Compare,Allocator>& x);
     ~multiset();
      multiset<Key,Compare,Allocator>&
          operator=(const 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;
    // capacity:
      bool          empty() const;
      size_type     size() const;
      size_type     max_size() const;
    // modifiers:
      iterator insert(const value_type& x);
      iterator insert(iterator position, const value_type& x);
      template <class InputIterator>
        void insert(InputIterator first, InputIterator last);

      void      erase(iterator position);
      size_type erase(const key_type& x);
      void      erase(iterator first, 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;
      size_type count(const key_type& x) const;
      iterator  lower_bound(const key_type& x) const;
      iterator  upper_bound(const key_type& x) const;
      pair<iterator,iterator> equal_range(const key_type& x) const;
    };
    template <class 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>
      bool operator< (const multiset<Key,Compare,Allocator>& x,
                      const multiset<Key,Compare,Allocator>& y);
    // specialized algorithms:
    template <class Key, class Compare, class Allocator>
      void swap(multiset<Key,Compare,Allocator>& x,
                multiset<Key,Compare,Allocator>& y);
  }

  23.3.4.1  multiset specialized algorithms       [lib.multiset.special]

  template <class Key, class Compare, class Allocator>
    void swap(multiset<Key,Compare,Allocator>& x,
              multiset<Key,Compare,Allocator>& y);

  Effects:
        x.swap(y);