______________________________________________________________________

  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             |
         +------------------------------------------------------+
         |                                            <deque>   |
         |                                            <list>    |
         |_lib.sequences_ Sequences                   <queue>   |
         |                                            <stack>   |
         |                                            <vector>  |
         +------------------------------------------------------+
         |_lib.associative_ Associative containers    <map>     |
         |                                            <set>     |
         |_lib.template.bitset_ bitset                <bitset>  |
         +------------------------------------------------------+

  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 All of the complexity requirements in this clause are stated solely in
  terms of the number of operations on the contained objects.  [Example:
  the copy constructor of type vector <vector<int> > has linear complex-
  ity, even though the complexity of copying each contained  vector<int>
  is itself linear.  ]

3 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.

4 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    |
            +------------------------------------------------+
            |t = u        T&            t is equivalent to u |
            +------------------------------------------------+

5 In Tables 3 and 4, X denotes a container class containing  objects  of
  type T, 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.
                                                      convertible to X::const_itera-
                                                      tor.
  ---------------------------------------------------------------------------------------------------
   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 difference   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 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                          note: the destructor is ap-      linear
                                                      plied to every element of a;
                                                      all the memory is deallocated.
  ---------------------------------------------------------------------------------------------------
   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)                        (Note A)     |
  +-------------------------------------------------------------------------------------------------+

                     Table 3--Container requirements

  +---------------------------------------------------------------------------------+
  | expression      return type        operational      assertion/note   complexity |
  |                                     semantics     pre/post-condition            |
  +---------------------------------------------------------------------------------+
  |r = a        X&                                    post: r == a.      linear     |
  +---------------------------------------------------------------------------------+
  |a.size()     size_type           a.end()-a.begin()                    (Note A)   |
  +---------------------------------------------------------------------------------+
  |a.max_size() size_type           size() of the                        (Note A)   |
  |                                 largest possible                                |
  |                                 container.                                      |
  +---------------------------------------------------------------------------------+
  |a.empty()    convertible to bool a.size() == 0                        constant   |
  +---------------------------------------------------------------------------------+
  |a < b        convertible to bool lexicographi-     pre: < is defined  linear     |
  |                                 cal_compare(      for values of T.              |
  |                                 a.begin(),        < is a total or-              |
  |                                 a.end(), b.be-    dering relation.              |
  |                                 gin(), 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_.  Those entries marked ``(Note
  A)'' should have constant complexity.

6 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.

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

8 Copy constructors for all container types defined in this clause  copy
  the  allocator  argument  from their respective first parameters.  All
  other constructors  for  these  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  member  functions,  during the lifetime of each container object.
  In all container types defined in this clause, the member  get_alloca-
  tor()  returns  a  copy  of the Allocator object used to construct the
  container.

9 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   reverse_iterator<iterator>         compile time |
  |iterator                                                                                    |
  +--------------------------------------------------------------------------------------------+
  |X::const_     iterator type pointing to     reverse_iterator<const_iterator>   compile time |
  |reverse_      const T                                                                       |
  |iterator                                                                                    |
  +--------------------------------------------------------------------------------------------+
  |a.rbegin()    reverse_iterator; const_re-   reverse_iterator(end())            constant     |
  |              verse_iterator for constant                                                   |
  |              a                                                                             |
  +--------------------------------------------------------------------------------------------+
  |a.rend()      reverse_iterator; const_re-   reverse_iterator(begin())          constant     |
  |              verse_iterator for constant                                                   |
  |              a                                                                             |
  +--------------------------------------------------------------------------------------------+
  All  container  types  defined  in  this  clause  meet  the additional
  requirements that no swap() function throws an exception  unless  that
  exception  is thrown by the copy constructor or assignment operator of
  the container's Compare object (if any, see _lib.associative.reqmts_).

10Unless  otherwise  stated (either explicitly or by defining a function
  in terms of the application of other  functions),  invoking  a  member
  function  of  a container or passing a container as argument to a con-
  tainer library function will not cause references or iterators to that
  container to become invalid.

  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 a value of X,
  i and j denote iterators satisfying input iterator  requirements,  [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.

4 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          pre: i,j are not iterators into a.                  |
  |                                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(begin(), end())                               |
  |                                post: size() == 0.                                  |
  +------------------------------------------------------------------------------------+

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

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

7 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.

8 The 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.

9 For every sequence defined in this clause:

  --the constructor
      template <class InputIterator>
      X(InputIterator f, InputIterator l, const Allocator& a = Allocator())
    shall have the same effect as:
      X(static_cast<typename X::size_type>(f),
        static_cast<typename X::value_type>(l),
        a)
    if InputIterator is an integral type.

  --the member function:
      template <class InputIterator>
      void insert(iterator p, InputIterator f, InputIterator l)
    shall have the same effect as:
      insert(p,
             static_cast<typename X::size_type>(f),
             static_cast<typename X::value_type>(l)).
    if InputIterator is an integral type.  [Note: This follows  directly
    from  the requirements in the Iterator Requirements Table.  Integral
    types cannot be iterators, so, if n1 and n2 are values of  an  inte-
    gral type N, the expression X(n1, n2) cannot possibly be interpreted
    as construction from a range of iterators.  It must be taken to mean
    the  first  constructor  in the Iterator Requirements Table, not the
    second one.  If there is no conversion from N to X::value_type, then
    this is not a valid expression at all.

10One  way that sequence implementors can satisfy this requirement is to
  specialize the member template for every integral type.  Less  cumber-
  some implementation techniques also exist.   --end note] [Example:
  list<int> x;
  vector<int> y(x.begin(), x.end());      // Construct a vector
                                          // from a range of iterators.
  vector<int> z(100, 1);                  // Construct a vector of 100
                                          // elements, all initialized
                                          // to 1. The arguments are
                                          // not interpreted as iterators.
   --end example]

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()       reference;      *a.begin()              vector, list, deque |
  |                const_refer-                                                |
  |                ence for con-                                               |
  |                stant a                                                     |
  +----------------------------------------------------------------------------+
  |a.back()        reference;      *--a.end()              vector, list, deque |
  |                const_refer-                                                |
  |                ence for con-                                               |
  |                stant 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]            reference;      *(a.begin() + n)        vector, deque       |
  |                const_refer-                                                |
  |                ence for con-                                               |
  |                stant a                                                     |
  +----------------------------------------------------------------------------+
  |a.at(n)         reference;      *(a.begin() + n)        vector, deque       |
  |                const_refer-                                                |
  |                ence for con-                                               |
  |                stant 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  container  is  parameterized on Key and an ordering
  relation Compare that induces a strict weak  ordering  (_lib.alg.sort-
  ing_)  on elements of Key.  In addition, map and multimap associate an
  arbitrary type T with the Key.  The object of type Compare  is  called
  the comparison object of a container.  This comparison object may be a
  pointer to function or an object of a type with an  appropriate  func-
  tion call operator.

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
  equivalent 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:: value_com- a binary pred- is the same as key_compare for set    compile time
   pare           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:: value_com- returns an object of value_compare    constant
                  pare           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.
  -------------------------------------------------------------------------------------

  |                                                                                   |
  |                                                                                   |
  |                                                                                   |
  |                                                                                   |
  |a_eq.insert(t) iterator       inserts t and returns the iterator    logarithmic    |
  |                              pointing to the newly inserted ele-                  |
  |                              ment.                                                |
  +-----------------------------------------------------------------------------------+

               Table 7--Associative container requirements

  -----------------------------------------------------------------------------------------
      expression     return type             assertion/note                complexity
                                           pre/post-condition
  -----------------------------------------------------------------------------------------
   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           pre: i,j are not iterators into a.  Nlog(size()+N) (N
                                   inserts each element from the range is the distance
                                   [i, j) if and only if there is no   from i to j) in
                                   element with key equivalent to the  general;
                                   key of that element in containers   linear if [i, j)
                                   with unique keys; always inserts    is sorted accord-
                                   that element in containers with     ing to val-
                                   equivalent keys.                    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(a.begin(), a.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)                                                    logarithmic

  |                                                                                       |
  |                                                                                       |
  |                                                                                       |
  |                                                                                       |
  |                 iterator; con- returns an iterator pointing to the                    |
  |                 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( a.low-     logarithmic        |
  |                 tor,iterator>; er_bound(k), a.upper_bound(k)).                        |
  |                 pair< con-                                                            |
  |                 st_iterator,                                                          |
  |                 const_itera-                                                          |
  |                 tor> for con-                                                         |
  |                 stant a                                                               |
  +---------------------------------------------------------------------------------------+

8 The insert members shall not affect the validity of iterators and ref-
  erences to the container, and the erase members shall invalidate  only
  iterators and references to the erased elements.

9 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

10For  associative  containers  with  unique keys the stronger condition
  holds,
    value_comp(*i, *j) != false.

11When an associative container is constructed by passing  a  comparison
  object  the  container  shall  not store a pointer or reference to the
  passed object, even if that object is passed by  reference.   When  an
  associative  container is copied, either through a copy constructor or
  an assignment operator, the target container shall then use  the  com-
  parison  object from the container being copied, as if that comparison
  object had been passed to the target container in its constructor.

  23.2  Sequences                                        [lib.sequences]

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

  Header <deque> synopsis

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

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

  namespace std {
    template <class T, class Container = deque<T> > class queue;
    template <class T, class Container>
      bool operator==(const queue<T, Container>& x,
                      const queue<T, Container>& y);
    template <class T, class Container>
      bool operator< (const queue<T, Container>& x,
                      const queue<T, Container>& y);
    template <class T, class Container>
      bool operator!=(const queue<T, Container>& x,
                      const queue<T, Container>& y);
    template <class T, class Container>
      bool operator> (const queue<T, Container>& x,
                      const queue<T, Container>& y);
    template <class T, class Container>
      bool operator>=(const queue<T, Container>& x,
                      const queue<T, Container>& y);
    template <class T, class Container>
      bool operator<=(const queue<T, Container>& x,
                      const queue<T, Container>& y);
    template <class T, class Container = vector<T>,
              class Compare = less<Container::value_type> >
    class priority_queue;
  }

  Header <stack> synopsis

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

  Header <vector> synopsis

  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>
      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>
      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> 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>
      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>
      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 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.

2 A  deque  satisfies  all  of  the requirements of a container and of a
  reversible container (given in tables in _lib.container.requirements_)
  and  of  a  sequence,  including  the  optional  sequence requirements
  (_lib.sequence.reqmts_).  Descriptions  are  provided  here  only  for
  operations  on  deque that are not described in one of these tables or

  for operations where there is additional semantic information.
  namespace std {
    template <class T, class Allocator = allocator<T> >
    class deque {
    public:
      // types:
      typedef typename Allocator::reference             reference;
      typedef typename Allocator::const_reference       const_reference;
      typedef implementation defined                    iterator;        // See _lib.container.requirements_
      typedef implementation defined                    const_iterator;  // See _lib.container.requirements_
      typedef typename Allocator::size_type             size_type;
      typedef typename Allocator::difference_type       difference_type;
      typedef T                                         value_type;
      typedef Allocator                                 allocator_type;
      typedef typename Allocator::pointer               pointer;
      typedef typename Allocator::const_pointer         const_pointer;
      typedef std::reverse_iterator<iterator>           reverse_iterator;
      typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
      // _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);
      void assign(size_type n, const T& t);
      allocator_type get_allocator() const;
      // iterators:
      iterator               begin();
      const_iterator         begin() const;
      iterator               end();
      const_iterator         end() const;
      reverse_iterator       rbegin();
      const_reverse_iterator rbegin() const;
      reverse_iterator       rend();
      const_reverse_iterator rend() const;
      // _lib.deque.capacity_ capacity:
      size_type size() const;
      size_type max_size() const;
      void      resize(size_type sz, T c = T());
      bool      empty() const;

      // 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);
      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);
    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>
      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.1.1  deque constructors, copy, and               [lib.deque.cons]
       assignment

  explicit deque(const Allocator& = Allocator());

  Effects:
    Constructs an empty deque, using the specified allocator.
  Complexity:
    Constant.

  explicit deque(size_t n, const T& value = T(),
                 const Allocator& = Allocator());

  Effects:
    Constructs a deque with n copies of value, using the specified allo-
    cator.
  Complexity:
    Linear in n.

  template <class InputIterator>
    deque(InputIterator first, InputIterator last,
          const Allocator& = Allocator());

  Effects:
    Constructs a deque equal to the the range [first, last),  using  the
    specified allocator.
  Complexity:
    If the iterators first and last are forward iterators, bidirectional
    iterators, or random access iterators the constructor makes  only  N
    calls  to the copy constructor, and performs no reallocations, where
    N is last - first.  It makes at most 2N calls to the copy  construc-
    tor of T and log N reallocations if they are input iterators.1)

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

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

  void assign(size_type n, const T& t);

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

  23.2.1.2  deque capacity                          [lib.deque.capacity]

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

  Effects:

  _________________________
  1)  The  complexity  is greater in the case of input iterators because
  each element must be added individually: it is impossible to determine
  the distance between first abd last before doing the copying.

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

  23.2.1.3  deque modifiers                        [lib.deque.modifiers]

  iterator insert(iterator position, const T& x);
  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 at most equal to the  minimum  of  the  number  of  elements
    before  the  erased  elements  and  the number of elements after the
    erased elements.

  23.2.1.4  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.2  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.

2 A  list  satisfies  all  of  the  requirements of a container and of a
  reversible container (given in two tables  in  _lib.container.require-
  ments_) and of a sequence, including most of the the optional sequence
  requirements (_lib.sequence.reqmts_).  The exceptions are  the  opera-
  tor[] and at member functions, which are not provided.2)  Descriptions
  are  provided  here only for operations on list that are not described
  in one of these tables or for operations  where  there  is  additional
  semantic information.
  namespace std {
    template <class T, class Allocator = allocator<T> >
    class list {
    public:
      // types:
      typedef typename Allocator::reference             reference;
      typedef typename Allocator::const_reference       const_reference;
      typedef implementation defined                    iterator;       // See _lib.container.requirements_
      typedef implementation defined                    const_iterator; // See _lib.container.requirements_
      typedef typename Allocator::size_type             size_type;
      typedef typename Allocator::difference_type       difference_type;
      typedef T                                         value_type;
      typedef Allocator                                 allocator_type;
      typedef typename Allocator::pointer               pointer;
      typedef typename Allocator::const_pointer         const_pointer;
      typedef std::reverse_iterator<iterator>           reverse_iterator;
      typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
      // _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);
      void assign(size_type n, const T& t);
      allocator_type get_allocator() const;

  _________________________
  2) These member functions are only provided by containers whose itera-
  tors are random access 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);
      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);
    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>
      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.2.1  list constructors, copy, and assignment      [lib.list.cons]

  explicit list(const Allocator& = Allocator());

  Effects:
    Constructs an empty list, using the specified allocator.
  Complexity:
    Constant.

  explicit list(size_type n, const T& value = T(),
                const Allocator& = Allocator());

  Effects:
    Constructs a list with n copies of value, using the specified  allo-
    cator.
  Complexity:
    Linear in n.

  template <class InputIterator>
  list(InputIterator first, InputIterator last,
       const Allocator& = Allocator());

  Effects:
    Constructs a list equal to the range [first, last).
  Complexity:
    Linear in first - last.

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

  Effects:

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

  void assign(size_type n, const T& t);

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

  23.2.2.2  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, end());
        else
          ;                           // do nothing

  23.2.2.3  list modifiers                          [lib.list.modifiers]

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

  void push_front(const T& x);
  void push_back(const T& x);

  Notes:
    Does  not  affect  the  validity of iterators and references.  If an
    exception is thrown there are no effects.
  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);

  void pop_front();
  void pop_back();
  void clear();.

  Effects:
    Invalidates only the iterators and references  to  the  erased  ele-
    ments.
  Throws:
    Nothing.
  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.2.4  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.
    Invalidates all iterators and references to the list x.
  Throws:
    Nothing
  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.  Invalidates only the iterators and references
    to the spliced element.
  Throws:
    Nothing
  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).   Invalidates
    only the iterators and references to the spliced elements.
  Throws:
    Nothing
  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)  !=
    false.
  Throws:
    Nothing  unless an exception is thrown by *i == value or pred(*i) !=
    false.
  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:
    Eliminates all but the first element from every consecutive group of
    equal elements referred to by the iterator i in the range  [first  +
    1,  last)  for which *i == *(i-1) (for the version of unique with no
    arguments) or pred(*i, *(i - 1)) (for the version of unique  with  a
    predicate argument) holds.
  Throws:
    Nothing  unless  an  exception in thrown by *i == *(i-1) or pred(*i,
    *(i - 1))
  Complexity:
    If the range (last - first) is not empty, exactly (last - first) - 1
    applications  of  the corresponding predicate, otherwise no applica-
    tions of the predicate.

  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 order-
    ing.
  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.   If  an  exception  is
    thrown other than by a comparison there are no effects.

  void reverse();

  Effects:
    Reverses the order of the elements in the list.
  Throws:
    Nothing.
  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.
    If an exception is thrown the order of the elements in the  list  is
    indeterminate.
  Complexity:
    Approximately NlogN comparisons, where N == size().

  23.2.2.5  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.3  Container adaptors                    [lib.container.adaptors]

1 The  container  adaptors each take a Container template parameter, and
  each constructor takes a Container reference argument.  This container
  is copied into the Container member of each adaptor.

  23.2.3.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.
  namespace std {
    template <class T, class Container = deque<T> >
    class queue {
    public:
      typedef typename Container::value_type            value_type;
      typedef typename Container::size_type             size_type;
      typedef typename Container                        container_type;
    protected:
      Container c;
    public:
      explicit queue(const Container& = Container());

      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>
      bool operator==(const queue<T, Container>& x,
                      const queue<T, Container>& y);
    template <class T, class Container>
      bool operator< (const queue<T, Container>& x,
                      const queue<T, Container>& y);
    template <class T, class Container>
      bool operator!=(const queue<T, Container>& x,
                      const queue<T, Container>& y);
    template <class T, class Container>
      bool operator> (const queue<T, Container>& x,
                      const queue<T, Container>& y);
    template <class T, class Container>
      bool operator>=(const queue<T, Container>& x,
                      const queue<T, Container>& y);
    template <class T, class Container>
      bool operator<=(const queue<T, Container>& x,
                      const queue<T, Container>& y);
  }
  operator==
  Returns:
    x.c == y.c.

    operator<
  Returns:
    x.c < y.c.

  23.2.3.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 priority_queue {
    public:
      typedef typename Container::value_type            value_type;
      typedef typename Container::size_type             size_type;
      typedef typename Container                        container_type;
    protected:
      Container c;
      Compare comp;
    public:
      explicit priority_queue(const Compare& x = Compare(),
                              const Container& = Container());
      template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last,
                       const Compare& x = Compare(),
                       const Container& = Container());
      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.3.2.1  priority_queue constructors            [lib.priqueue.cons]

  priority_queue(const Compare& x = Compare(),
                 const Container& y = Container());

  Requires:
    x defines a strict weak ordering (_lib.alg.sorting_).
  Effects:
    Initializes  comp  with  x  and c with y; calls make_heap(c.begin(),
    c.end(), comp).

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

  Requires:
    x defines a strict weak ordering (_lib.alg.sorting_).
  Effects:
    Initializes c with y and comp with x; calls c.insert(c.end(), first,
    last); and finally calls make_heap(c.begin(), c.end(), comp).

  23.2.3.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.3.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.vec-
  tor_), list (_lib.list_) and deque (_lib.deque_) can be used.
  namespace std {
    template <class T, class Container = deque<T> >
    class stack {
    public:
      typedef typename Container::value_type            value_type;
      typedef typename Container::size_type             size_type;
      typedef typename Container                        container_type;
    protected:
      Container c;
    public:
      explicit stack(const Container& = Container());

      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>
      bool operator==(const stack<T, Container>& x,
                      const stack<T, Container>& y);
    template <class T, class Container>
      bool operator< (const stack<T, Container>& x,
                      const stack<T, Container>& y);
    template <class T, class Container>
      bool operator!=(const stack<T, Container>& x,
                      const stack<T, Container>& y);
    template <class T, class Container>
      bool operator> (const stack<T, Container>& x,
                      const stack<T, Container>& y);
    template <class T, class Container>
      bool operator>=(const stack<T, Container>& x,
                      const stack<T, Container>& y);
    template <class T, class Container>
      bool operator<=(const stack<T, Container>& x,
                      const stack<T, Container>& y);
  }

  23.2.4  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.

2 A  vector  satisfies  all  of the requirements of a container and of a
  reversible container (given in two tables  in  _lib.container.require-
  ments_)  and  of  a  sequence, including most of the optional sequence
  requirements  (_lib.sequence.reqmts_).    The   exceptions   are   the
  push_front  and  pop_front  member  functions, which are not provided.
  Descriptions are provided here only for operations on vector that  are
  not  described in one of these tables or for operations where there is
  additional semantic information.
  namespace std {
    template <class T, class Allocator = allocator<T> >
    class vector {
    public:
      // types:
      typedef typename Allocator::reference             reference;
      typedef typename Allocator::const_reference       const_reference;
      typedef implementation defined                    iterator;       // See _lib.container.requirements_
      typedef implementation defined                    const_iterator; // See _lib.container.requirements_
      typedef typename Allocator::size_type             size_type;
      typedef typename Allocator::difference_type       difference_type;
      typedef T                                         value_type;
      typedef Allocator                                 allocator_type;
      typedef typename Allocator::pointer               pointer;
      typedef typename Allocator::const_pointer         const_pointer
      typedef std::reverse_iterator<iterator>           reverse_iterator;
      typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;

      // _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);
      void assign(size_type n, const T& u);
      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;
      // _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);
      // 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);
      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);
    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>
      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.4.1  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);

  void assign(size_type n, const T& t);

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

  23.2.4.2  vector capacity                        [lib.vector.capacity]

  size_type capacity() const;

  Returns:
    The total number of  elements  that  the  vector  can  hold  without
    requiring reallocation.

  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 insertions that happen after a call
    to reserve() until the time when an insertion would make the size of
    the  vector  greater than the size specified in the most recent call
    to 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, end());
        else
          ;                           // do nothing

  23.2.4.3  vector modifiers                      [lib.vector.modifiers]

  iterator insert(iterator position, const T& x);
  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:
    If first and last are forward iterators, bidirectional iterators, or
    random  access  iterators, the complexity is linear in the number of
    elements in the range [first, last) plus the distance to the end  of
    the  vector.  If they are input iterators, the complexity is propor-
    tional to the number of elements in the range  [first,  last)  times
    the distance to the end of the vector.

  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
    called the number of times equal to the number of  elements  in  the
    vector after the erased elements.

  23.2.4.4  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.5  Class vector<bool>                           [lib.vector.bool]

1 To optimize space allocation, a specialization of vector for bool ele-
  ments is provided:
  namespace std {
    template <class Allocator> class vector<bool, Allocator> {
    public:
      // types:
      typedef bool                                      const_reference;
      typedef implementation defined                    iterator;       // See _lib.container.requirements_
      typedef implementation defined                    const_iterator; // See _lib.container.requirements_
      typedef typename Allocator::size_type             size_type;
      typedef typename Allocator::difference_type       difference_type;
      typedef bool                                      value_type;
      typedef Allocator                                 allocator_type;
      typedef typename Allocator::pointer               pointer;
      typedef typename Allocator::const_pointer         const_pointer
      typedef std::reverse_iterator<iterator>           reverse_iterator;
      typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;

      // bit reference:
      class reference {
       friend class vector;
       reference();
      public:
       ~reference();
        operator bool() const;
        reference& operator=(const bool x);
        reference& operator=(const reference& x);
        void flip();              // flips the bit
      };
      // 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);
      void assign(size_type n, const T& t);
      allocator_type get_allocator() const;
      // iterators:
      iterator               begin();
      const_iterator         begin() const;
      iterator               end();
      const_iterator         end() const;
      reverse_iterator       rbegin();
      const_reverse_iterator rbegin() const;
      reverse_iterator       rend();
      const_reverse_iterator rend() const;
      // 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);
      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);
    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>
      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

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

  namespace std {
    template <class Key, class Compare = less<Key>,
              class Allocator = allocator<Key> >
      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>
      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>
      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<Key> >
      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>
      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>
      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.

2 A map satisfies all of the  requirements  of  a  container  and  of  a
  reversible container (_lib.container.requirements_) and of an associa-
  tive container (_lib.associative.reqmts_).  A map also  provides  most
  operations  described  in  (_lib.associative.reqmts_) for unique keys.
  This means that a map supports the a_uniq operations in (_lib.associa-
  tive.reqmts_)  but  not  the  a_eq  operations.   For a map<Key,T> the
  key_type is Key and the value_type is pair<const Key,T>.  Descriptions
  are provided here only for operations on map that are not described in
  one of those tables or for operations where there is additional seman-
  tic information.
  namespace std {
    template <class Key, class T, class Compare = less<Key>,
              class Allocator = allocator<T> >
    class map {
    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;
      typedef typename Allocator::reference             reference;
      typedef typename Allocator::const_reference       const_reference;
      typedef implementation defined                    iterator;       // See _lib.container.requirements_
      typedef implementation defined                    const_iterator; // See _lib.container.requirements_
      typedef typename Allocator::size_type             size_type;
      typedef typename Allocator::difference_type       difference_type;
      typedef typename Allocator::pointer               pointer;
      typedef typename Allocator::const_pointer         const_pointer;
      typedef std::reverse_iterator<iterator>           reverse_iterator;
      typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
      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) const {
          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);
      // 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;
      // _lib.map.access_ element access:
      reference operator[](const key_type& x);
      // 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();
      // 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);
    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>
      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 constructors, copy, and assignment        [lib.map.cons]

  explicit map(const Compare& comp = Compare(),
               const Allocator& = Allocator());

  Effects:
    Constructs  an  empty  map using the specified comparison object and
    allocator.
  Complexity:
    Constant.

  template <class InputIterator>
    map(InputIterator first, InputIterator last,
        const Compare& comp = Compare(), const Allocator& = Allocator());

  Effects:
    Constructs an empty map using the specified  comparison  object  and
    allocator, and inserts elements from the range [first, last).
  Complexity:
    Linear  in N if the range [first, last) is already sorted using comp
    and otherwise N log N, where N is last - first.

  23.3.1.2  map element access                          [lib.map.access]

  reference operator[](const key_type& x);

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

  23.3.1.3  map operations                                 [lib.map.ops]

  iterator       find(const key_type& x);
  const_iterator find(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;

1 The find, lower_bound, upper_bound and  equal_range  member  functions
  each  have  two  versions, one const and the other non-const.  In each
  case the behavior of the two functions is identical  except  that  the
  const  version  returns  a const_iterator and the non-const version an
  iterator(_lib.associative.reqmts_).

  23.3.1.4  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  containing 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.

2 A  multimap  satisfies all of the requirements of a container and of a
  reversible container (_lib.container.requirements_) and of an associa-
  tive  container  (_lib.associative.reqmts_).  A multimap also provides

  most operations  described  in  (_lib.associative.reqmts_)  for  equal
  keys.   This  means  that  a  multimap supports the a_eq operations in
  (_lib.associative.reqmts_) but not the a_uniq operations.  For a  mul-
  timap<Key,T>  the  key_type  is  Key  and the value_type is pair<const
  Key,T>.  Descriptions are provided here only for  operations  on  mul-
  timap  that are not described in one of those tables or for operations
  where there is additional semantic information.
  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;
      typedef typename Allocator::reference             reference;
      typedef typename Allocator::const_reference       const_reference;
      typedef implementation defined                    iterator;       // See _lib.container.requirements_
      typedef implementation defined                    const_iterator; // See _lib.container.requirements_
      typedef typename Allocator::size_type             size_type;
      typedef typename Allocator::difference_type       difference_type;
      typedef typename Allocator::pointer               pointer;
      typedef typename Allocator::const_pointer         const_pointer;
      typedef std::reverse_iterator<iterator>           reverse_iterator;
      typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
      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) const {
          return comp(x.first, y.first);
        }
      };
      // 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);
    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>
      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 constructors                    [lib.multimap.cons]

  explicit multimap(const Compare& comp = Compare(),
                    const Allocator& = Allocator());

  Effects:
    Constructs an empty multimap using the specified  comparison  object
    and allocator.
  Complexity:
    Constant.

  template <class InputIterator>
    multimap(InputIterator first, InputIterator last,
             const Compare& comp = Compare(),
             const Allocator& = Allocator()0;

  Effects:
    Constructs  an  empty multimap using the specified comparison object
    and allocator, and inserts elements from the range [first, last).
  Complexity:
    Linear in N if the range [first, last).   is  already  sorted  using
    comp and otherwise N log N, where N is last - first.

  23.3.2.2  multimap operations                       [lib.multimap.ops]

  iterator       find(const key_type &x);
  const_iterator find(const key_type& x) const;

  iterator       lower_bound(const key_type& x);
  const_iterator lower_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;

1 The  find,  lower_bound, upper_bound, and equal_range member functions
  each have two versions, one const and one non-const.  In each case the
  behavior  of  the two versions is identical except that the const ver-
  sion returns a const_iterator and  the  non-const  version  an  itera-
  tor(_lib.associative.reqmts).

  23.3.2.3  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.

2 A set satisfies all of the  requirements  of  a  container  and  of  a
  reversible  container  (_lib.container.requirements_), and of an asso-
  ciative container (_lib.associative.reqmts_).   A  set  also  provides
  most  operations  described  in  (_lib.associative.reqmts_) for unique
  keys.  This means  that  a  set  supports  the  a_uniq  operations  in
  (_lib.associative.reqmts_)   but  not  the  a_eq  operations.   For  a
  set<Key> both the key_type and value_type are Key.   Descriptions  are
  provided here only for operations on set that are not described in one
  of these tables and for operations where there is additional  semantic
  information.

  namespace std {
    template <class Key, class Compare = less<Key>,
              class Allocator = allocator<Key> >
    class set {
    public:
      // types:
      typedef Key                                       key_type;
      typedef Key                                       value_type;
      typedef Compare                                   key_compare;
      typedef Compare                                   value_compare;
      typedef Allocator                                 allocator_type;
      typedef typename Allocator::reference             reference;
      typedef typename Allocator::const_reference       const_reference;
      typedef implementation defined                    iterator;       // See _lib.container.requirements_
      typedef implementation defined                    const_iterator; // See _lib.container.requirements_
      typedef typename Allocator::size_type             size_type;
      typedef typename Allocator::difference_type       difference_type;
      typedef typename Allocator::pointer               pointer;
      typedef typename Allocator::const_pointer         const_pointer;
      typedef std::reverse_iterator<iterator>           reverse_iterator;
      typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
      // _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;
      // 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:
      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();

      // 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 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>
      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>
      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 constructors, copy, and assignment        [lib.set.cons]

  explicit set(const Compare& comp = Compare(),
               const Allocator& = Allocator());

  Effects:
    Constructs  an  empty set using the specified comparison objects and
    allocator.
  Complexity:
    Constant.

  template <class InputIterator>
    set(InputIterator first, last,
        const Compare& comp = Compare(), const Allocator& = Allocator());

  Effects:
    Constructs an empty set using the specified  comparison  object  and

    allocator, and inserts elements from the range [first, last).
  Complexity:
    Linear  in N if the range [first, last) is already sorted using comp
    and otherwise N log N, where N is last - first.

  23.3.3.2  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.

2 A  multiset  satisfies all of the requirements of a container and of a
  reversible container (_lib.container.requirements_), and of  an  asso-
  ciative  container (_lib.associative.reqmts_).  multiset also provides
  most operations described in (_lib.associative.reqmts_) for  duplicate
  keys.   This  means  that  a  multiset supports the a_eq operations in
  (_lib.associative.reqmts_) but not the a_uniq operations.  For a  mul-
  tiset<Key> both the key_type and value_type are Key.  Descriptions are
  provided here only for operations on multiset that are  not  described
  in  one  of  these tables and for operations where there is additional
  semantic information.
  namespace std {
    template <class Key, class Compare = less<Key>,
              class Allocator = allocator<Key> >
    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;       // See _lib.container.requirements_
      typedef implementation defined                    const_iterator; // See _lib.container.requirements_
      typedef typename Allocator::size_type             size_type;
      typedef typename Allocator::difference_type       difference_type;
      typedef typename Allocator::pointer               pointer;
      typedef typename Allocator::const_pointer         const_pointer;
      typedef std::reverse_iterator<iterator>           reverse_iterator;
      typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;

      // 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);
    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>
      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 constructors                    [lib.multiset.cons]

  explicit multiset(const Compare& comp = Compare(),
                    const Allocator& = Allocator());

  Effects:
    Constructs an empty set using the specified  comparison  object  and
    allocator.
  Complexity:
    Constant.

  template <class InputIterator>
    multiset(InputIterator first, last,
             const Compare& comp = Compare(), const Allocator& = Allocator());

  Effects:
    Constructs  an  empty multiset using the specified comparison object
    and allocator, and inserts elements from the range [first, last).
  Complexity:
    Linear in N if the range [first, last) is already sorted using  comp
    and otherwise N log N, where N is last - first.

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

  23.3.5  Template class bitset                    [lib.template.bitset]

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

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);
      template<class charT, class traits, class Allocator>
        explicit bitset(
          const basic_string<charT,traits,Allocator>& str,
          typename basic_string<charT,traits,Allocator>::size_type pos = 0,
          typename basic_string<charT,traits,Allocator>::size_type n =
            basic_string<charT,traits,Allocator>::npos);
      // _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.3.5.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).3)
    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
  _________________________
  3)  The macro CHAR_BIT is defined in <climits> (_lib.support.limits_).

  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.

  23.3.5.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.3.5.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.template   to_string<charT,traits,allocator<charT>   >()
    (_lib.ostream.formatted_).