______________________________________________________________________

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

  23.1  Container requirements              [lib.container.requirements]

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

2 In  the following Table 2, we assume X is a container class containing
  objects of type T, a and b are values of X, u is an identifier  and  r
  is a value of X&.

                     Table 2--Container requirements

  ---------------------------------------------------------------------------------------------------
       expression               return type                   assertion/note            complexity
                                                            pre/post-condition
  ---------------------------------------------------------------------------------------------------
   X::value_type        T                                                              compile time
  ---------------------------------------------------------------------------------------------------
   X::iterator          iterator type pointing to T   any iterator category except     compile time
                                                      output iterator.
  ---------------------------------------------------------------------------------------------------
   X::const_ iterator   iterator type pointing to     any iterator category except     compile time
                        const T                       output iterator.
  ---------------------------------------------------------------------------------------------------
   X::difference_type   signed integral type          is identical to the distance     compile time
                                                      type of X::iterator and
                                                      X::const_iterator
  ---------------------------------------------------------------------------------------------------
   X:: size_type        unsigned integral type        size_type can represent any      compile time
                                                      non-negative value of differ­
                                                      ence_type
  ---------------------------------------------------------------------------------------------------
   X 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)->               result is not used            post: a.size() == 0.             linear
    ~X()                                              note: the destructor is ap­
                                                      plied to every element of a,
                                                      all the memory is returned.
  ---------------------------------------------------------------------------------------------------
   a.begin()            iterator;                                                      constant
                        const_iterator
                        for constant a
  ---------------------------------------------------------------------------------------------------
   a.end()              iterator;                                                      constant
                        const_iterator
                        for constant a
  ---------------------------------------------------------------------------------------------------
   a == b               convertible to bool           == is an equivalence relation.   linear
                                                      a.size()==b.size()
                                                      && equal(a.begin(),
                                                      a.end(), b.begin())
  ---------------------------------------------------------------------------------------------------

  |                                                                                                 |
  |                                                                                                 |
  |                                                                                                 |
  |                                                                                                 |
  |a != b               convertible to bool           Equivalent to: !(a == b)         linear       |
  +-------------------------------------------------------------------------------------------------+

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

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

4 begin() returns an iterator referring to the first element in the con­
  tainer.  end() returns an iterator which is the past-the-end value.

  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 stack s or queue s, out
  of the basic sequence kinds (or out of other kinds of  sequences  that
  the user might define).

2 In  the  following  Table 3, X is a sequence class, a is value of X, i
  and j satisfy input iterator requirements, [i, j) is a valid range,  n
  is  a value of X::size_type, p is a valid iterator to a, q, q1, q2 are
  valid dereferenceable iterators to a, [q1, q2) is a valid range, t  is
  a value of X::value_type.

3 The complexities of the expressions are sequence dependent.

        Table 3--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)   result is not used   inserts n copies of t before p.                      |
  +----------------------------------------------------------------------------------------------+
  |a.insert(p, i, j)   result is not used   inserts copies of elements in [i, j) before p.       |
  +----------------------------------------------------------------------------------------------+
  |a.erase(q)          result is not used   erases the element pointed to by q.                  |
  +----------------------------------------------------------------------------------------------+
  |a.erase(q1, q2)     result is not used   erases the elements in the range [q1, q2).           |
  +----------------------------------------------------------------------------------------------+

4 vector, 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 fre­
  quent insertions and deletions from the middle of the sequence.  deque
  is  the  data  structure  of choice when most insertions and deletions
  take place at the beginning or at the end of the sequence.

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

6 Table 4:

                  Table 4--Optional sequence operations

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

7 All  the  operations in the above table are provided only for the con­
  tainers for which they take constant time.

  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 All of them are parameterized on Key and an ordering relation  Compare
  that  induces  a  total ordering 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.

3 In this section when we talk about equality of keys we mean the equiv­
  alence relation imposed by the comparison and not  the  operator==  on
  keys.   That  is, two keys k1 and k2 are considered to be equal if for
  the comparison 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  equal  keys.
  set  and map support unique keys.  multiset and multimap support equal
  keys.

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

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

7 In the following Table 5, 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  iterator  requirements and refer to elements of value_type, [i,
  j) is a valid range, p is a valid iterator to a, q, q1, q2  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 5--Associative container requirements (in addition to container)

  +--------------------------------------------------------------------------------------+
  |   expression     return type               assertion/note               complexity   |
  |                                          pre/post-condition                          |
  +--------------------------------------------------------------------------------------+
  |X::key_type      Key                                                   compile time   |
  |                                                                                      |
  |X:: key_compare  Compare        defaults to less<key_type>.            compile time   |
  |                                                                                      |
  |X:: val­         a binary pred­ is the same as key_compare for set and compile time   |
  |ue_compare       icate type     multiset; is an ordering relation on                  |
  |                                pairs induced by the first component                  |
  |                                (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); lin­  |
  |                                                                       ear if [i, j)  |
  |                                                                       is sorted with |
  |                                                                       value_comp()   |
  +--------------------------------------------------------------------------------------+
  |X(i, j)                         same as above, but uses Compare() as a same as        |
  |X a(i, j);                      comparison object.                     above          |
  +--------------------------------------------------------------------------------------+
  |a.key_comp()     X::            returns the comparison object out of   constant       |
  |                 key_compare    which a was constructed.                              |
  +--------------------------------------------------------------------------------------+
  |a.value_comp()   X:: val­       returns an object of value_compare     constant       |
  |                 ue_compare     constructed out of the comparison ob­                 |
  |                                ject.                                                 |
  +--------------------------------------------------------------------------------------+
  |a_uniq.insert(t) pair<iterator, inserts t if and only if there is no   logarithmic    |
  |                 bool>          element in the container with key                     |
  |                                equal to the key of t.  The bool com­                 |
  |                                ponent of the returned pair indicates                 |
  |                                whether the insertion takes place and                 |
  |                                the iterator component of the pair                    |
  |                                points to the element with key equal                  |
  |                                to the key of t.                                      |
  +--------------------------------------------------------------------------------------+

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

  |                                                                                           |
  |                                                                                           |
  |                                                                                           |
  |                                                                                           |
  +-------------------------------------------------------------------------------------------+
  |a.equal_range(k) pair< itera­       equivalent to make_pair(            logarithmic        |
  |                 tor,iterator>;         a.lower_bound(k),                                  |
  |                 pair< con­             a.upper_bound(k)).                                 |
  |                 st_iterator, con­                                                         |
  |                 st_iterator> for                                                          |
  |                 constant a                                                                |
  +-------------------------------------------------------------------------------------------+

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

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

  23.2  Sequences                                        [lib.sequences]

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

  Header <bits> 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 bits;
    template <size_t N>
      istream& operator>>(istream& is, bits<N>& x);
    template <size_t N>
      ostream& operator<<(ostream& os, const bits<N>& x);
  }

  Header <deque> synopsis

  #include <memory>       // for allocator
  namespace std {
    template <class T, class Allocator = allocator> 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);
  }

  Header <list> synopsis

  #include <memory>       // for allocator
  namespace std {
    template <class T, class Allocator = allocator> 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);
  }

  Header <queue> synopsis

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

  Header <stack> synopsis

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

  Header <vector> synopsis

  #include <memory>       // for allocator
  namespace std {
    template <class T, class Allocator = allocator> 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);

    class vector<bool,allocator>;
    bool operator==(const vector<bool,allocator>& x,
                    const vector<bool,allocator>& y);
    bool operator< (const vector<bool,allocator>& x,
                    const vector<bool,allocator>& y);
  }

  23.2.1  Template class bits                        [lib.template.bits]

1 The  header  <bits> 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 bits {
    public:
      bits();
      bits(unsigned long val);
      bits(const string& str, size_t pos = 0, size_t n = NPOS);
      bits<N>& operator&=(const bits<N>& rhs);
      bits<N>& operator|=(const bits<N>& rhs);
      bits<N>& operator^=(const bits<N>& rhs);
      bits<N>& operator<<=(size_t pos);
      bits<N>& operator>>=(size_t pos);
      bits<N>& set();
      bits<N>& set(size_t pos, int val = 1);
      bits<N>& reset();
      bits<N>& reset(size_t pos);
      bits<N>  operator~() const;
      bits<N>& toggle();
      bits<N>& toggle(size_t pos);
      unsigned short to_ushort() const;
      unsigned long  to_ulong() const;
      string to_string() const;
      size_t count() const;
      size_t length() const;
      bool operator==(const bits<N>& rhs) const;
      bool operator!=(const bits<N>& rhs) const;
      bool test(size_t pos) const;
      bool any() const;
      bool none() const;
      bits<N> operator<<(size_t pos) const;
      bits<N> operator>>(size_t pos) const;
    private:
  //  char array[N];      exposition only
    };
  }

2 The  template  class  bits<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 bits<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 val­
  ues.

  +-------                 BEGIN BOX 1                -------+
  For the sake of exposition, the maintained data is presented here as:

  --char array[N], the sequence of bits, stored one bit per element.1)
  +-------                  END BOX 1                 -------+

  _________________________
  1) An implementation is free to store the bit sequence more efficient­

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;

  --an   out-of-range  error  is  associated  with  exceptions  of  type
    out_of_range;

  --an overflow error  is  associated  with  exceptions  of  type  over­
    flow_error.

  23.2.1.1  bits constructors                            [lib.cons.bits]

  bits();

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

    bits(unsigned long val);

  Effects:
    Constructs an object of class bits<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).2)
    If M < N, remaining bit positions are initialized to zero.

    bits(const string& str, size_t pos = 0, size_t n = NPOS);

  Requires:
    pos<=
  Throws:
    out_of_range if pos > str.len.
  Effects:
    Determines the effective length rlen of the initializing  string  as
    the smaller of n and str.len - 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 bits<N>,  ini­
    tializing  the  first  M bit positions to values determined from the
    corresponding characters in the string str.  M is the smaller  of  N
    and rlen.

1 An element of the constructed string has value zero if the correspond­
  ing character in str, beginning at position pos, is 0.  Otherwise, the
  element has the value one.  Character position pos + M - 1 corresponds
  to bit position zero.  Subsequent decreasing character positions  cor­
  respond to increasing bit positions.
  _________________________
  ly.
  2) The macro CHAR_BIT is defined in <climits>(_lib.support.limits_).

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

  23.2.1.2  bits::operator&=                         [lib.bits::op&=.bt]

  bits<N>& operator&=(const bits<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.

  23.2.1.3  bits::operator|=                         [lib.bits::op|=.bt]

  bits<N>& operator|=(const bits<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.

  23.2.1.4  bits::operator^=                         [lib.bits::op^=.bt]

  bits<N>& operator^=(const bits<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.

  23.2.1.5  bits::operator<<=                        [lib.bits::op.lsh=]

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

  23.2.1.6  bits::operator>>=                        [lib.bits::op.rsh=]

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

  23.2.1.7  bits::set                                    [lib.bits::set]

  bits<N>& set();

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

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

  23.2.1.8  bits::reset                                [lib.bits::reset]

  bits<N>& reset();

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

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

  23.2.1.9  bits::operator~                              [lib.bits::op~]

  bits<N> operator~() const;

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

  23.2.1.10  bits::toggle                             [lib.bits::toggle]

  bits<N>& toggle();

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

    bits<N>& toggle(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.

  23.2.1.11  bits::to_ushort                       [lib.bits::to.ushort]

  unsigned short to_ushort() const;

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

  23.2.1.12  bits::to_ulong                         [lib.bits::to.ulong]

  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.

  23.2.1.13  bits::to_string                       [lib.bits::to.string]

  string to_string() const;

  Effects:
    Constructs an object of type string 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 positions.   Bit  value  zero
    becomes the character 0, bit value one becomes the character 1.
  Returns:
    The created object.

  23.2.1.14  bits::count                               [lib.bits::count]

  size_t count() const;

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

  23.2.1.15  bits::length                             [lib.bits::length]

  size_t length() const;

  Returns:
    N.

  23.2.1.16  bits::operator==                        [lib.bits::op==.bt]

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

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

  23.2.1.17  bits::operator!=                        [lib.bits::op!=.bt]

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

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

  23.2.1.18  bits::test                                 [lib.bits::test]

  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.

  23.2.1.19  bits::any                                   [lib.bits::any]

  bool any() const;

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

  23.2.1.20  bits::none                                 [lib.bits::none]

  bool none() const;

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

  23.2.1.21  bits::operator<<                         [lib.bits::op.lsh]

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

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

  23.2.1.22  bits::operator>>                         [lib.bits::op.rsh]

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

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

  23.2.1.23  operator&                                   [lib.bits::op&]

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

  Returns:
    bits<N>(lhs) &= pos.

  23.2.1.24  operator|                                   [lib.bits::op|]

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

  Returns:
    bits<N>(lhs) |= pos.

  23.2.1.25  operator^                                   [lib.bits::op^]

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

  Returns:
    bits<N>(lhs) ^= pos.

  23.2.1.26  operator>>                                  [lib.bits::ext]

  template <size_t N>
    istream& operator>>(istream& is, bits<N>& x);

1 A formatted input function.
  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  =  bits<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).
  Returns:
    is.

  23.2.1.27  operator<<                                  [lib.bits::ins]

  template <size_t N>
    ostream& operator<<(ostream& os, const bits<N>& x);

  Returns:
    os << x.to_string().

  23.2.2  Template class deque                               [lib.deque]

1 A deque is a kind of sequence that, like a vector (_lib.vector_), sup­
  ports random access iterators.  In addition, it supports constant time
  insert and erase operations at the beginning or the  end;  insert  and
  erase  in the middle take linear time.  That is, a deque is especially
  optimized for pushing and popping elements at the beginning  and  end.
  As with vectors, storage management is handled automatically.
  namespace std {
    template <class T, class Allocator = allocator>
    class deque {
    public:
    // types:
      typedef Allocator::types<T>::pointer       iterator;
      typedef Allocator::types<T>::const_pointer const_iterator;
      typedef Allocator::size_type       size_type;
      typedef Allocator::difference_type difference_type;
      typedef T value_type;

    // construct/copy/destroy:
      deque();
      deque(size_type n, const T& value = T());
      deque(const deque<T,Allocator>& x);
      template <class InputIterator>
        deque(InputIterator first, InputIterator last);
     ~deque();
      deque<T,Allocator>& operator=(const deque<T,Allocator>& x);
      template <class InputIterator>
        void assign(InputIterator first, InputIterator last);
      template <class Size, class T>
        void assign(Size n, const T& t = T());
    // observers:
      iterator       begin();
      const_iterator begin() const;
      iterator       end();
      const_iterator end() const;
      size_type size() const;
      size_type max_size() const;
      void      resize(size_type sz, T c = T());
      bool      empty() const;
      T&       operator[](size_type n);
      const T& operator[](size_type n) const;
      const T& at(size_type n) const;
      T&       at(size_type n);
      T&       front();
      const T& front() const;
      T&       back();
      const T& back() const;
    // modifiers:
      void push_front(const T& x);
      void push_back(const T& x);
      iterator insert(iterator position, const T& x = T());
      void     insert(iterator position, size_type n, const T& x = T());
      template <class InputIterator>
        void insert (iterator position, InputIterator first, InputIterator last);
      void pop_front();
      void pop_back();
      void erase(iterator position);
      void erase(iterator first, iterator last);
    };
    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);
  }

  23.2.2.1  deque members                            [lib.deque.members]

  23.2.2.1.1  assign                                  [lib.deque.assign]

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

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

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

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

  23.2.2.1.2  insert                                  [lib.deque.insert]

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

  Effects:
    Invalidates  all  the  iterators  and references to the deque if the
    insertion pointer is not at either end.   Insertion  at  either  end
    does not affect iterators and references.
  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.

  23.2.2.1.3  erase                                    [lib.deque.erase]

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

  Effects:
    Invalidates all the iterators and references to  the  deque  if  the
    erasing  point is not at either end.  Erasing at either end does not
    affect iterators  and  references.   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 operator is equal to the mini­
    mum  of  the  number  of elements before the erased elements and the
    number of element after the erased elements.

  23.2.2.1.4  resize                                  [lib.deque.resize]

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

  Effects:
        if (sz > size())
          s.insert(s.end(), s.size()-sz, v);
        else if (sz < size())
          s.erase(s.begin()+sz, s.end());
        else
          ???

  23.2.3  Template class list                                 [lib.list]

1 A list is a kind of sequence that supports bidirectional iterators and
  allows  constant  time insert and erase operations anywhere within the
  sequence, with storage management handled automatically.  Unlike  vec­
  tors  (_lib.vector_)  and  deques (_lib.deque_), fast random access to
  list elements is not supported, but many algorithms only need  sequen­
  tial access anyway.
  namespace std {
    template <class T, class Allocator = allocator>
    class list {
    public:
    // types:
      typedef Allocator::types<T>::pointer       iterator;
      typedef Allocator::types<T>::const_pointer const_iterator;
      typedef Allocator::size_type       size_type;
      typedef Allocator::difference_type difference_type;
      typedef T value_type;
    // construct/copy/destroy:
      list();
      list(size_type n, const T& value = T());
      template <class InputIterator>
        list(InputIterator first, InputIterator last);
      list(const list<T,Allocator>& x);
     ~list();
      list<T,Allocator>& operator=(const list<T,Allocator>& x);
      template <class InputIterator>
        void assign(InputIterator first, InputIterator last);
      template <class Size, class T>
        void assign(Size n, const T& t = T());

    // observers:
      iterator       begin();
      const_iterator begin() const;
      iterator       end();
      const_iterator end() const;
      bool      empty() const;
      size_type size() const;
      size_type max_size() const;
      void      resize(size_type sz, T c = T());
      T&       front();
      const T& front() const;
      T&       back();
      const T& back() const;
    // modifiers:
      void push_front(const T& x);
      void pop_front();
      void push_back(const T& x);
      void pop_back();
      iterator insert(iterator position, const T& x = T());
      void     insert(iterator position, size_type n, const T& x = T());
      template <class InputIterator>
        void insert(iterator position, InputIterator first,
                    InputIterator last);
      void erase(iterator position);
      void erase(iterator position, iterator last);
    // special mutative operations on list:
      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);
  }

  23.2.3.1  list members                              [lib.list.members]

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.

  23.2.3.1.1  assign                                   [lib.list.assign]

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

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

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

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

  23.2.3.1.2  insert                                   [lib.list.insert]

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

  Notes:

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

  23.2.3.1.3  erase                                     [lib.list.erase]

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

  Effects:
    Invalidates  only  the  iterators  and references to the erased ele­
    ments.
  Complexity:
    Erasing a single element is a constant time operation with a  single
    call  to  the  destructor of T.  Erasing a range in a list is linear
    time in the size of the  range  and  the  number  of  calls  to  the
    destructor of type T is exactly equal to the size of the range.

  23.2.3.1.4  resize                                   [lib.list.resize]

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

  Effects:

        if (sz > size())
          s.insert(s.end(), s.size()-sz, v);
        else if (sz < size())
          s.erase(s.begin()+sz, s.end());
        else
          ???

  23.2.3.1.5  splice                                   [lib.list.splice]

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

  Effects:
    Inserts the contents of x before position and x becomes empty.
  Complexity:
    Constant time.

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

  Effects:
    Inserts  an  element pointed to by i from list x before position and
    removes the element from x.
  Requires:
    i is a valid 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.
  Complexity:
    Linear time.

  23.2.3.1.6  remove                                   [lib.list.remove]

  void remove(const T& value);
  template <class Predicate> void remove_if(Predicate pred);

  Effects:
    Erases  all the elements in the list referred by the list iterator i
    for which the following conditions hold:  *i == value,  pred(*i)  ==
    true.
  Notes:
    Stable:   the relative order of the elements that are not removed is
    the same as their relative order in the original list.
  Complexity:
    Exactly size() applications of the corresponding predicate.

  23.2.3.1.7  unique                                   [lib.list.unique]

  void   unique();
  template <class BinaryPredicate>
    void unique(BinaryPredicate binary_pred);

  Effects:
    Erases all but the first element from  every  consecutive  group  of
    equal elements in the list.
  Complexity:
    Exactly  size()  - 1 applications of the corresponding binary predi­
    cate.

  23.2.3.1.8  merge                                     [lib.list.merge]

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

  Effects:
    Merges the argument list into the  list  (both  are  assumed  to  be
    sorted).
  Notes:
    Stable:   for equal 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.

  23.2.3.1.9  reverse                                 [lib.list.reverse]

  void   reverse();

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

  23.2.3.1.10  sort                                      [lib.list.sort]

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

  Effects:
    Sorts  the  list  according  to  the operator< or a compare function
    object.
  Notes:
    Stable:  the relative order of the equal elements is preserved.
  Complexity:
    Approximately NlogN comparisons, where N == size().

  23.2.4  Template class queue                               [lib.queue]

1 Any sequence supporting operations front(),  back(),  push_back()  and
  pop_front()   can  be  used  to  instantiate  queue.   In  particular,
  list(_lib.list_) and deque(_lib.deque_) can be used.
  nmespace std {
    template <class Container>
    class queue {
    public:
      typedef Container::value_type value_type;
      typedef Container::size_type  size_type;
    protected:
      Container c;
    public:
      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 Container>
      bool operator==(const queue<Container>& x, const queue<Container>& y);
  }
  operator==
  Returns:
    x.c == y.c.

  23.2.5  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.
  namespace std {
    template <class Container, class Compare = less<Container::value_type> >
    class priority_queue {
    public:
      typedef Container::value_type value_type;
      typedef Container::size_type  size_type;
    protected:
      Container c;
      Compare comp;
    public:
      priority_queue(const Compare& x = Compare());
      template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last,
          const Compare& x = Compare());

      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.6  priority_queue members            [lib.priority.queue.members]

  23.2.6.1  priority_queue constructors              [lib.priqueue.cons]

  priority_queue(const Compare& x = Compare());
  Effects:
      : c(), comp(x) {}

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

  Effects:
            : c(first, last), comp(x) {
              make_heap(c.begin(), c.end(), comp);
          }

  23.2.6.2  push                                     [lib.priqueue.push]

  void push(const value_type& x);

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

  23.2.6.3  pop                                       [lib.priqueue.pop]

  void pop();

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

  23.2.7  Template class stack                               [lib.stack]

1 Any  sequence supporting operations back(), push_back() and pop_back()
  can   be   used   to   instantiate   stack.    In   particular,   vec­
  tor(_lib.vector_),  list(_lib.list_)  and  deque(_lib.deque_)  can  be
  used.

2 For example, stack<vector<int> > is an integer stack made out of  vec­
  tor, and stack<deque<char> > is a character stack made out of deque.

  namespace std {
    template <class Container>
    class stack {
    public:
      typedef Container::value_type value_type;
      typedef Container::size_type  size_type;
    protected:
      Container c;
    public:
      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 Container>
      bool operator==(const stack<Container>& x, const stack<Container>& y);
  }
  operator==
  Returns:
    x.c == y.c.

  23.2.8  Template class vector                             [lib.vector]

1 A  vector  is a kind of sequence supports random access iterators.  In
  addition, it supports (amortized) constant time insert and erase oper­
  ations  at  the  end; insert and erase in the middle take linear time.
  Storage management is handled automatically, though hints can be given
  to improve efficiency.
  namespace std {
    template <class T, class Allocator = allocator>
    class vector {
    public:
    // types:
      typedef Allocator::types<T>::pointer       iterator;
      typedef Allocator::types<T>::const_pointer const_iterator;
      typedef Allocator::size_type       size_type;
      typedef Allocator::difference_type difference_type;
      typedef T value_type;
    // construct/copy/destroy:
      vector();
      vector(size_type n, const T& value = T());
      vector(const vector<T,Allocator>& x);
      template <class InputIterator>
        vector(InputIterator first, InputIterator last);
     ~vector();
      vector<T,Allocator>& operator=(const vector<T,Allocator>& x);
      template <class InputIterator>
        void assign(InputIterator first, InputIterator last);
      template <class Size, class T> void assign(Size n, const T& t = T());
      void reserve(size_type n);

    // observers:
      iterator       begin();
      const_iterator begin() const;
      iterator       end();
      const_iterator end() const;
      size_type size() const;
      size_type max_size() const;
      void      resize(size_type sz, T c = T());
      size_type capacity() const;
      bool      empty() const;
      T&       operator[](size_type n);
      const T& operator[](size_type n) const;
      const T& at(size_type n) const;
      T&       at(size_type n);
      T&       front();
      const T& front() const;
      T&       back();
      const T& back() const;
    // modifiers:
      void push_back(const T& x);
      void pop_back();
      iterator insert(iterator position, const T& x = T());
      void     insert(iterator position, size_type n, const T& x = T());
      template <class InputIterator>
          void insert(iterator position, InputIterator first, InputIterator last);
      void erase(iterator position);
      void erase(iterator first, iterator last);
    };
    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);
  }

  23.2.8.1  vector members                          [lib.vector.members]

  23.2.8.1.1  vector constructor                       [lib.vector.cons]

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

  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.

  23.2.8.1.2  assign                                 [lib.vector.assign]

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

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

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

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

  23.2.8.1.3  capacity                             [lib.vector.capacity]

  size_type capacity() const;

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

  23.2.8.1.4  reserve                               [lib.vector.reserve]

  void reserve(size_type n);

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

  23.2.8.1.5  resize                                 [lib.vector.resize]

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

  Effects:
        if (sz > size())
          s.insert(s.end(), s.size()-sz, v);
        else if (sz < size())
          s.erase(s.begin()+sz, s.end());
        else
          ???

  23.2.8.1.6  insert                                 [lib.vector.insert]

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

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

  23.2.8.1.7  erase                                   [lib.vector.erase]

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

  Effects:
    Invalidates  all the iterators and references after the point of the
    erase.  The destructor of T is called the number of times  equal  to
    the  number 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.9  Class vector<bool>                           [lib.vector.bool]

1 To optimize space allocation, a specialization for bool is provided:4)

  _________________________
  3)  In other words, it is much faster to insert many elements into the
  middle of a vector at once than to do the insertion  one  at  a  time.
  The  insert  template  member function preallocates enough storage for
  the insertion if the iterators first and last are of forward, bidirec­
  tional  or random access category.  Otherwise, it does insert elements
  one by one and should not be used for inserting  into  the  middle  of
  vectors.
  4) Every implementation is expected to provide specializations of vec­
  tor<bool> for all supported memory models.

  namespace std {
    class vector<bool,allocator> {
    public:
    // bit reference:
      class reference {
      public:
         ~reference();
          operator bool() const;
          reference& operator=(const bool x);
          void flip();      // flips the bit
      };
    // types:
      typedef Allocator::types<T>::pointer       iterator;
      typedef Allocator::types<T>::const_pointer const_iterator;
      typedef Allocator::size_type       size_type;
      typedef Allocator::difference_type difference_type;
      typedef bool      value_type;
    // construct/copy/destroy:
      vector();
      vector(size_type n, const bool& value = bool());
      vector(const vector<bool,allocator>& x);
      template <class InputIterator>
        vector(InputIterator first, InputIterator last);
     ~vector();
      vector<bool,allocator>& operator=(const vector<bool,allocator>& x);
      void reserve(size_type n);
    // observers:
      iterator       begin();
      const_iterator begin() const;
      iterator       end();
      const_iterator end() const;
      size_type size() const;
      size_type max_size() const;
      size_type capacity() const;
      bool empty() const;
      reference       operator[](size_type n);
      const reference operator[](size_type n) const;
      const reference at(size_type n) const;
      reference       at(size_type n);
      reference       front();
      const reference front() const;
      reference       back();
      const reference back() const;
    // modifiers:
      void push_back(const bool& x);
      void pop_back();
      iterator insert(iterator position, const bool& x = bool());
      void     insert (iterator position, size_type n, const bool& x = bool());
      template <class InputIterator>
          void insert (iterator position, InputIterator first, InputIterator last);
      void erase(iterator position);
      void erase(iterator first, iterator last);
    };

    bool operator==(const vector<bool,allocator>& x,
                    const vector<bool,allocator>& y);
    bool operator< (const vector<bool,allocator>& x,
                    const vector<bool,allocator>& y);
  }

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

  23.3  Associative containers                         [lib.associative]

1 Headers <map> and <set>:

  Header <map> synopsis

  #include <memory>       // for allocator
  #include <utility>      // for pair
  #include <functional>   // for less
  namespace std {
    template <class Key, class T, class Compare = less<Key>,
              class Allocator = allocator>
      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 = less<Key>,
              class Allocator = allocator>
      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);
  }

  Header <set> synopsis

  #include <memory>       // for allocator
  #include <utility>      // for pair
  #include <functional>   // for less
  namespace std {
    template <class Key, class Compare = less<Key>, class Allocator = allocator>
      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 = less<Key>, class Allocator = allocator>
      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);
  }

  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.
  namespace std {
    template <class Key, class T, class Compare = less<Key>,
              class Allocator = allocator>
    class map {
    public:
    // types:
      typedef Key                key_type;
      typedef pair<const Key, T> value_type;
      typedef Compare            key_compare;
      class value_compare
        : public binary_function<value_type,value_type,bool> {
      friend class map;
      protected:
        Compare comp;
        value_compare(Compare c) : comp(c) {}
      public:
        bool operator()(const value_type& x, const value_type& y) {
          return comp(x.first, y.first);
        }
      };
  ISSUE Are these typedefs correct?
      typedef Allocator::types<T>::pointer       iterator;
      typedef Allocator::types<T>::const_pointer const_iterator;
      typedef Allocator::size_type       size_type;
      typedef Allocator::difference_type difference_type;
    // construct/copy/destroy:
      map(const Compare& comp = Compare());
      template <class InputIterator>
        map(InputIterator first, InputIterator last,
            const Compare& comp = Compare());
      map(const map<Key,T,Compare,Allocator>& x);
     ~map();
      map<Key,T,Compare,Allocator>&
        operator=(const map<Key,T,Compare,Allocator>& x);

    // observers:
      key_compare   key_comp() const;
      value_compare value_comp() const;
      iterator       begin();
      const_iterator begin() const;
      iterator       end();
      const_iterator end() const;
      bool      empty() const;
      size_type size() const;
      size_type max_size() const;
      T& 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);
    // 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);
  }

  23.3.1.1  map members                                [lib.map.members]

  +-------                 BEGIN BOX 2                -------+
  To Be Specified
  +-------                  END BOX 2                 -------+

  23.3.1.1.1  operator[] lib.map::subscript

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

  Effects:
    (*((m.insert(make_pair(k, T()))).first)).second.

  23.3.2  Template class multimap                         [lib.multimap]

1 A multimap is a kind of associative container that supports equal keys
  (possibly contains multiple copies of the same key value) and provides
  for fast retrieval of values of another type T based on the keys.
  namespace std {
    template <class Key, class T, class Compare = less<Key>,
              class Allocator = allocator>
    class multimap {
    public:
    // types:
      typedef Key               key_type;
      typedef pair<const Key,T> value_type;
      typedef Compare           key_compare;
      class value_compare
        : public binary_function<value_type,value_type,bool> {
      friend class multimap;
      protected:
        Compare comp;
        value_compare(Compare c) : comp(c) {}
      public:
        bool operator()(const value_type& x, const value_type& y) {
          return comp(x.first, y.first);
        }
      };
  ISSUE Are these typedefs correct?
      typedef Allocator::types<T>::pointer       iterator;
      typedef Allocator::types<T>::const_pointer const_iterator;
      typedef Allocator::size_type       size_type;
      typedef Allocator::difference_type difference_type;
    // construct/copy/destroy:
      multimap(const Compare& comp = Compare());
      template <class InputIterator>
        multimap(InputIterator first, InputIterator last,
                 const Compare& comp = Compare());
      multimap(const multimap<Key,T,Compare,Allocator>& x);
     ~multimap();
      multimap<Key,T,Compare,Allocator>&
        operator=(const multimap<Key,T,Compare,Allocator>& x);
    // observers:
      key_compare    key_comp() const;
      value_compare  value_comp() const;
      iterator       begin();
      const_iterator begin() const;
      iterator       end();
      const_iterator end() const;
      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);
    // multimap 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);
  }

  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.
  namespace std {
    template <class Key, class Compare = less<Key>, class Allocator = allocator>
    class set {
    public:
    // types:
      typedef Key     key_type;
      typedef Key     value_type;
      typedef Compare key_compare;
      typedef Compare value_compare;
      typedef Allocator::types<T>::pointer       iterator;
      typedef Allocator::types<T>::const_pointer const_iterator;
      typedef Allocator::size_type       size_type;
      typedef Allocator::difference_type difference_type;
    // construct/copy/destroy:
      set(const Compare& comp = Compare());
      template <class InputIterator>
        set(InputIterator first, InputIterator last,
            const Compare& comp = Compare());
      set(const set<Key,Compare,Allocator>& x);
     ~set();
      set<Key,Compare,Allocator>& operator=(const set<Key,Compare,Allocator>& x);

    // observers:
      key_compare   key_comp() const;
      value_compare value_comp() const;
      iterator      begin() const;
      iterator      end() const;
      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);
    // 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);
  }

  23.3.4  Template class multiset                         [lib.multiset]

1 A multiset is a kind of associative container that supports equal keys
  (possibly contains multiple copies of the same key value) and provides
  for fast retrieval of the keys themselves.
  namespace std {
    template <class Key, class Compare = less<Key>, class Allocator = allocator>
    class multiset {
    public:
    // types:
      typedef Key     key_type;
      typedef Key     value_type;
      typedef Compare key_compare;
      typedef Compare value_compare;
      typedef Allocator::types<T>::pointer       iterator;
      typedef Allocator::types<T>::const_pointer const_iterator;
      typedef Allocator::size_type       size_type;
      typedef Allocator::difference_type difference_type;

    // construct/copy/destroy:
      multiset(const Compare& comp = Compare());
      template <class InputIterator>
        multiset(InputIterator first, InputIterator last,
                 const Compare& comp = Compare());
      multiset(const multiset<Key,Compare,Allocator>& x);
     ~multiset();
      multiset<Key,Compare,Allocator>&
          operator=(const multiset<Key,Compare,Allocator>& x);
    // observers:
      key_compare   key_comp() const;
      value_compare value_comp() const;
      iterator      begin() const;
      iterator      end() const;
      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);
    // multiset 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);
  }