______________________________________________________________________

  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   components   for   sequences
  (_lib.sequences_) and associative containers (_lib.associative_).

  23.1  Sequences                                        [lib.sequences]

1 Headers:

  --<bits>

  --<bitstring>

  --<dynarray>

  --<ptrdynarray>

  --<stl containers (TBD)>

2 Table 1:

                     Table 1--Header <bits> synopsis

       +----------------------------------------------------------+
       |      Type                         Name(s)                |
       +----------------------------------------------------------+
       |Template class:     bits                                  |
       +----------------------------------------------------------+
       |Operator functions:                                       |
       |operator&  (bits)   operator>> (bits)   operator|  (bits) |
       |operator<< (bits)   operator^  (bits)                     |
       +----------------------------------------------------------+

3 Table 2:

                   Table 2--Header <bitstring> synopsis

       +----------------------------------------------------------+
       |         Type                         Name(s)             |
       +----------------------------------------------------------+
       |Class:                    bitstring                       |
       +----------------------------------------------------------+
       |Operator functions:                                       |
       |operator&  (bit_string)   operator>> (bit_string)         |
       |operator+  (bit_string)   operator^  (bit_string)         |
       |operator<< (bit_string)   operator|  (bit_string)         |
       +----------------------------------------------------------+

4 Table 3:

                   Table 3--Header <dynarray> synopsis

            +------------------------------------------------+
            |       Type                   Name(s)           |
            +------------------------------------------------+
            |Template class:      dyn_array                  |
            +------------------------------------------------+
            |Operator function:   operator+  (dyn_array) [3] |
            +------------------------------------------------+

5 Table 4:

                  Table 4--Header <ptrdynarray> synopsis

          +----------------------------------------------------+
          |       Type                     Name(s)             |
          +----------------------------------------------------+
          |Class:               ptr_dyn_array                  |
          +----------------------------------------------------+
          |Operator function:   operator+  (ptr_dyn_array) [3] |
          +----------------------------------------------------+

6 Table 5:

             Table 5--Header <stl containers (TBD)> synopsis

  +------------------------------------------------------------------------------+
  |        Type                                   Name(s)                        |
  +------------------------------------------------------------------------------+
  |Template classes:                                                             |
  |deque                   multimap                 queue                 vector |
  |list                    multiset                 set                          |
  |map                     priority_queue           stack                        |
  +------------------------------------------------------------------------------+
  |Template operators:                                                           |
  |operator<  (deque)      operator<  (vector)      operator== (queue)           |
  |operator<  (list)       operator== (deque)       operator== (set)             |
  |operator<  (map)        operator== (list)        operator== (stack)           |
  |operator<  (multimap)   operator== (map)         operator== (vector)          |
  |operator<  (multiset)   operator== (multimap)                                 |
  |operator<  (set)        operator== (multiset)                                 |
  +------------------------------------------------------------------------------+
  |Class:                  vector<bool,allocator>                                |
  +------------------------------------------------------------------------------+
  |Operator functions:     operator<  (vector<bool,allocator>)                   |
  |                        operator== (vector<bool,allocator>)                   |
  +------------------------------------------------------------------------------+

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

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

5 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.1.1.1  bits constructors                            [lib.cons.bits]
      bits();

1 Constructs  an object of class bits<N>, initializing all bits to zero.
  bits(unsigned long val);

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

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

3 The macro CHAR_BIT is defined in <climits>

4 If M < N, remaining bit positions are initialized to zero.
      bits(const string& str, size_t pos = 0, size_t n = NPOS);

5 Throws  out_of_range if pos > str.len.  Otherwise, the function deter­
  mines the effective length rlen of  the  initializing  string  as  the
  smaller of n and str.len - pos.

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

7 Otherwise, the function constructs an object of  class  bits<N>,  ini­
  tializing the first M bit positions to values determined from the cor­
  responding characters in the string str.  M is the smaller  of  N  and
  rlen.

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

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

  23.1.1.2  bits::operator&=                         [lib.bits::op&=.bt]
      bits<N>& operator&=(const bits<N>& rhs);

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

2 Returns *this.

  23.1.1.3  bits::operator|=                         [lib.bits::op|=.bt]
      bits<N>& operator|=(const bits<N>& rhs);

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

2 Returns *this.

  23.1.1.4  bits::operator^=                         [lib.bits::op^=.bt]
      bits<N>& operator^=(const bits<N>& rhs);

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

2 Returns *this.

  23.1.1.5  bits::operator<<=                        [lib.bits::op.lsh=]
      bits<N>& operator<<=(size_t pos);

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

2 Returns *this.

  23.1.1.6  bits::operator>>=                        [lib.bits::op.rsh=]
      bits<N>& operator>>=(size_t pos);

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

2 Returns *this.

  23.1.1.7  bits::set                                    [lib.bits::set]
      bits<N>& set();

1 Sets all bits in *this.

2 Returns *this.
      bits<N>& set(size_t pos, int val = 1);

3 Throws  out_of_range  if  pos does not correspond to a valid bit posi­
  tion.  Otherwise, the function stores a new value in the bit at  posi­
  tion pos in *this.  If val is nonzero, the stored value is one, other­
  wise it is zero.

4 Returns *this.

  23.1.1.8  bits::reset                                [lib.bits::reset]
      bits<N>& reset();

1 Resets all bits in *this.

2 Returns *this.
      bits<N>& reset(size_t pos);

3 Throws out_of_range if pos does not correspond to a  valid  bit  posi­
  tion.   Otherwise,  the  function  resets  the  bit at position pos in
  *this.

4 Returns *this.

  23.1.1.9  bits::operator~                              [lib.bits::op~]
      bits<N> operator~() const;

1 Constructs an object x of class bits<N> and initializes it with *this.

2 Returns x.toggle().

  23.1.1.10  bits::toggle                             [lib.bits::toggle]
      bits<N>& toggle();

1 Toggles all bits in *this.

2 Returns *this.
      bits<N>& toggle(size_t pos);

3 Throws  out_of_range  if  pos does not correspond to a valid bit posi­
  tion.  Otherwise, the function toggles the  bit  at  position  pos  in
  *this.

4 Returns *this.

  23.1.1.11  bits::to_ushort                       [lib.bits::to.ushort]
      unsigned short to_ushort() const;

1 If  the  integral value x corresponding to the bits in *this cannot be
  represented as type unsigned short, throws overflow_error.

2 Otherwise, returns x.

  23.1.1.12  bits::to_ulong                         [lib.bits::to.ulong]
      unsigned long to_ulong() const;

1 If the integral value x corresponding to the bits in *this  cannot  be
  represented as type unsigned long, throws overflow_error.

2 Otherwise, returns x.

  23.1.1.13  bits::to_string                       [lib.bits::to.string]
      string to_string() const;

1 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 corre­
  sponds to bit position zero.  Subsequent  decreasing  character  posi­
  tions  correspond to increasing bit positions.  Bit value zero becomes
  the character 0, bit value one becomes the character 1.

2 Returns the created object.

  23.1.1.14  bits::count                               [lib.bits::count]
      size_t count() const;

1 Returns a count of the number of bits set in *this.

  23.1.1.15  bits::length                             [lib.bits::length]
      size_t length() const;

1 Returns N.

  23.1.1.16  bits::operator==                        [lib.bits::op==.bt]
      bool operator==(const bits<N>& rhs) const;

1 Returns  a  nonzero value if the value of each bit in *this equals the
  value of the corresponding bit in rhs.

  23.1.1.17  bits::operator!=                        [lib.bits::op!=.bt]
      bool operator!=(const bits<N>& rhs) const;

1 Returns a nonzero value if !(*this == rhs).

  23.1.1.18  bits::test                                 [lib.bits::test]
      bool test(size_t pos) const;

1 Throws out_of_range if pos does not correspond to a  valid  bit  posi­
  tion.

2 Otherwise, returns a nonzero value if the bit at position pos in *this
  has the value one.

  23.1.1.19  bits::any                                   [lib.bits::any]
      bool any() const;

1 Returns a nonzero value if any bit in *this is one.

  23.1.1.20  bits::none                                 [lib.bits::none]
      bool none() const;

1 Returns a nonzero value if no bit in *this is one.

  23.1.1.21  bits::operator<<                         [lib.bits::op.lsh]
      bits<N> operator<<(size_t pos) const;

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

  23.1.1.22  bits::operator>>                         [lib.bits::op.rsh]
      bits<N> operator>>(size_t pos) const;

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

  23.1.1.23  operator&                                   [lib.op&.bt.bt]
      bits<N> operator&(const bits<N>& lhs, const bits<N>& rhs);

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

  23.1.1.24  operator|                                   [lib.op|.bt.bt]
      bits<N> operator|(const bits<N>& lhs, const bits<N>& rhs);

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

  23.1.1.25  operator^                                   [lib.op^.bt.bt]
      bits<N> operator^(const bits<N>& lhs, const bits<N>& rhs);

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

  23.1.1.26  operator>>                                     [lib.ext.bt]
      istream& operator>>(istream& is, bits<N>& x);

1 A formatted input function, extracts up to N (single-byte)  characters
  from  is.   The function 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,   the  function  calls
  is.setstate(ios::failbit).

3 Returns is.

  23.1.1.27  operator<<                                     [lib.ins.bt]
      ostream& operator<<(ostream& os, const bits<N>& x);

1 Returns os << x.to_string().

  23.1.2  Class bit_string                              [lib.bit.string]

1 The header <bitstring> defines a class and several function signatures
  for representing and manipulating varying-length sequences of bits.
  class bit_string {
  public:
      bit_string();
      bit_string(unsigned long val, size_t n);
      bit_string(const bit_string& str, size_t pos = 0, size_t n = NPOS);
      bit_string(const string& str, size_t pos = 0, size_t n = NPOS);

      bit_string& operator+=(const bit_string& rhs);
      bit_string& operator&=(const bit_string& rhs);
      bit_string& operator|=(const bit_string& rhs);
      bit_string& operator^=(const bit_string& rhs);
      bit_string& operator<<=(size_t pos);
      bit_string& operator>>=(size_t pos);
      bit_string& append(const bit_string& str, pos = 0, n = NPOS);
      bit_string& assign(const bit_string& str, pos = 0, n = NPOS);
      bit_string& insert(size_t pos1, const bit_string& str,
                         size_t pos2 = 0, size_t n = NPOS);
      bit_string& remove(size_t pos = 0, size_t n = NPOS);
      bit_string& replace(size_t pos1, size_t n1, const bit_string& str,
                          size_t pos2 = 0, size_t n2 = NPOS);
      bit_string& set();
      bit_string& set(size_t pos, bool val = 1);
      bit_string& reset();
      bit_string& reset(size_t pos);
      bit_string& toggle();
      bit_string& toggle(size_t pos);
      string to_string() const;
      size_t count() const;
      size_t length() const;
      size_t resize(size_t n, bool val = 0);
      size_t trim();
      size_t find(bool val, size_t pos = 0, size_t n = NPOS) const;
      size_t rfind(bool val, size_t pos = 0, size_t n = NPOS) const;
      bit_string substr(size_t pos, size_t n = NPOS) const;
      bool operator==(const bit_string& rhs) const;
      bool operator!=(const bit_string& rhs) const;
      bool test(size_t pos) const;
      bool any() const;
      bool none() const;
      bit_string operator<<(size_t pos) const;
      bit_string operator>>(size_t pos) const;
      bit_string operator~() const;
  private:
  //  char* ptr;  exposition only
  //  size_t len; exposition only
  };

2 The class bit_string describes an object that  can  store  a  sequence
  consisting  of  a  varying  number  of  bits.  Such a sequence is also
  called a bit string (or simply a string if the type of the elements is
  clear from context).  Storage for the string is allocated and freed as
  necessary by the member functions of class bit_string.

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 bit_string of length len and a value of
  some integral type, bit position pos corresponds to the bit value 1 <<
  (len  -  pos  -  1).2) The integral value corresponding to two or more
  _________________________
  2)  Note that bit position zero is the most-significant bit for an ob­

  bits is the sum of their bit values.

4 For the sake of exposition, the maintained data is presented here as:

  --char*  ptr,  points  to  the  sequence  of  bits, stored one bit per
    element;3)

  --size_t len, the length of the bit sequence.

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

  --a length error is associated with exceptions of type length_error;

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

  23.1.2.1  bit_string constructors                [lib.cons.bit.string]
      bit_string();

1 Constructs an object of class bit_string, initializing:

  --ptr to an unspecified value;

  --len to zero.
          bit_string(unsigned long val, size_t n);

2 Throws length_error if n equals NPOS.  Otherwise,  the  function  con­
  structs  an  object  of  class  bit_string  and determines its initial
  string value from val.  If val is zero, the  corresponding  string  is
  the empty string.  Otherwise, the corresponding string is the shortest
  sequence of bits with the same bit value as val.  If the corresponding
  string  is  shorter than n, the string is extended with elements whose
  values are all zero.  Thus, the function initializes:

  --ptr to point at the first element of the string;

  --len to the length of the string.
          bit_string(const bit_string& str, size_t pos = 0, size_t n = NPOS);

3 Throws out_of_range if pos > str.len.  Otherwise,  the  function  con­
  structs  an  object  of  class bit_string and determines the effective
  length rlen of the initial string  value  as  the  smaller  of  n  and
  str.len - pos.  Thus, the uunction initializes:

  _________________________
  ject of class bit_string, while it is the least-significant bit for an
  object of class bits<N>.
  3) An implementation is, of course, free to  store  the  bit  sequence
  more efficiently.

  --ptr to point at the first element of an allocated copy of rlen  ele­
    ments of the string controlled by str beginning at position pos;

  --len to rlen.
          bit_string(const string& str, size_t pos = 0, size_t n = NPOS);

4 Throws  out_of_range if pos > str.len.  Otherwise, the function deter­
  mines the effective length rlen of  the  initializing  string  as  the
  smaller of n and str.len - pos.

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

6 Otherwise, the function constructs an object of class  bit_string  and
  determines  its initial string value from str.  The length of the con­
  structed string is rlen.  An element of  the  constructed  string  has
  value  zero  if the corresponding character in str, beginning at posi­
  tion pos, is 0.  Otherwise, the element has the value one.

7 Thus, the function initializes:

  --ptr to point at the first element of the string;

  --len to rlen.

  23.1.2.2  bit_string::operator+=             [lib.bit.string::op+=.bs]
      bit_string& operator+=(const bit_string& rhs);

1 Throws length_error if len >= NPOS - rhs.len.

2 Otherwise, the function replaces the string controlled by *this with a
  string  of length len + rhs.len whose first len elements are a copy of
  the original string controlled by *this and whose  remaining  elements
  are a copy of the elements of the string controlled by rhs.

3 Returns *this.

  23.1.2.3  bit_string::operator&=             [lib.bit.string::op&=.bs]
      bit_string& operator&=(const bit_string& rhs);

1 Determines  a length rlen which is the larger of len and rhs.len, then
  behaves as if the shorter of the two strings controlled by  *this  and
  rhs  were  temporarily  extended to length rlen by adding elements all
  with value zero.  The function then replaces the string controlled  by
  *this  with  a string of length rlen whose elements have the value one
  only if both of the corresponding elements of *this and rhs are one.

2 Returns *this.

  23.1.2.4  bit_string::operator|=             [lib.bit.string::op|=.bs]
      bit_string& operator|=(const bit_string& rhs);

1 Determines a length rlen which is the larger of len and rhs.len,  then
  behaves  as  if the shorter of the two strings controlled by *this and

  rhs  were  temporarily  extended to length rlen by adding elements all
  with value zero.  The function then replaces the string controlled  by
  *this  with  a string of length rlen whose elements have the value one
  only if either of the corresponding elements of *this and rhs are one.

2 Returns *this.

  23.1.2.5  bit_string::operator^=             [lib.bit.string::op^=.bs]
      bit_string& operator^=(const bit_string& rhs);

1 Determines  a length rlen which is the larger of len and rhs.len, then
  behaves as if the shorter of the two strings controlled by  *this  and
  rhs  were  temporarily  extended to length rlen by adding elements all
  with value zero.  The function then replaces the string controlled  by
  *this  with  a string of length rlen whose elements have the value one
  only if the corresponding elements of *this  and  rhs  have  different
  values.

2 Returns *this.

  23.1.2.6  bit_string::operator<<=            [lib.bit.string::op.lsh=]
      bit_string& operator<<=(size_t pos);

1 Replaces  each element at position I in the string controlled by *this
  with a value determined as follows:

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

  --If pos < len - I, the new value is the previous value of the element
    at position I + pos.

2 Returns *this.

  23.1.2.7  bit_string::operator>>=            [lib.bit.string::op.rsh=]
      bit_string& operator>>=(size_t pos);

1 Replaces  each element at position I in the string controlled by *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  element  at
    position I - pos.

  23.1.2.8  bit_string::append                  [lib.bit.string::append]
      bit_string& append(const bit_string& str, size_t pos = 0,
                         size_t n = NPOS);

1 Throws  out_of_range if pos > str.len.  Otherwise, the function deter­
  mines the effective length rlen of the string to append as the smaller
  of n and str.len - pos.

2 The function then throws length_error if len >= NPOS - rlen.

3 Otherwise, the function replaces the string controlled by *this with a
  string of length len + rlen whose first len elements are a copy of the
  original string controlled by *this and whose remaining elements are a
  copy of the initial elements of the string controlled by str beginning
  at position pos.

4 Returns *this.

  23.1.2.9  bit_string::assign                  [lib.bit.string::assign]
      bit_string& assign(const bit_string& str, size_t pos = 0,
                         size_t n = NPOS);

1 Throws out_of_range if pos > str.len.  Otherwise, the function  deter­
  mines the effective length rlen of the string to assign as the smaller
  of n and str.len - pos.

2 The function then replaces the  string  controlled  by  *this  with  a
  string  of  length  rlen  whose elements are a copy of the string con­
  trolled by str beginning at position pos.

3 Returns *this.

  23.1.2.10  bit_string::insert                 [lib.bit.string::insert]
      bit_string& insert(size_t pos1, const bit_string& str, size_t pos2 = 0,
                         size_t n = NPOS);

1 Throws out_of_range if pos1 > len or pos2 > str.len.   Otherwise,  the
  function  determines the effective length rlen of the string to insert
  as the smaller of n and str.len - pos2.

2 The function then throws length_error if len >= NPOS - rlen.

3 Otherwise, the function replaces the string controlled by *this with a
  string  of  length  len + rlen whose first pos1 elements are a copy of
  the initial elements of the original string controlled by *this, whose
  next rlen elements are a copy of the elements of the string controlled
  by str beginning at position pos2, and whose remaining elements are  a
  copy  of  the  remaining elements of the original string controlled by
  *this.

4 Returns *this.

  23.1.2.11  bit_string::remove                 [lib.bit.string::remove]
      bit_string& remove(size_t pos = 0, size_t n = NPOS);

1 Throws out_of_range if pos > len.  Otherwise, the function  determines
  the  effective  length xlen of the string to be removed as the smaller
  of n and len - pos.

2 The function then replaces the  string  controlled  by  *this  with  a
  string of length len - xlen whose first pos elements are a copy of the
  initial elements of the original string controlled by *this, and whose
  remaining  elements  are a copy of the elements of the original string
  controlled by *this beginning at position pos + xlen.

3 Returns *this.

  23.1.2.12  bit_string::replace               [lib.bit.string::replace]
      bit_string& replace(size_t pos1, size_t n1, const bit_string& str,
                          size_t pos2 = 0, size_t n2 = NPOS);

1 Throws  out_of_range  if pos1 > len or pos2 > str.len.  Otherwise, the
  function determines the effective length xlen  of  the  string  to  be
  removed  as  the smaller of n1 and len - pos1.  It also determines the
  effective length rlen of the string to be inserted as the  smaller  of
  n2 and str.len - pos2.

2 The function then throws length_error if len - xlen >= NPOS - rlen.

3 Otherwise, the function replaces the string controlled by *this with a
  string of length len - xlen + rlen whose first  pos1  elements  are  a
  copy  of  the  initial  elements  of the original string controlled by
  *this, whose next rlen elements are a copy of the initial elements  of
  the  string  controlled  by  str beginning at position pos2, and whose
  remaining elements are a copy of the elements of the  original  string
  controlled by *this beginning at position pos1 + xlen.

4 Returns *this.

  23.1.2.13  bit_string::set                       [lib.bit.string::set]
      bit_string& set();

1 Sets all elements of the string controlled by *this.

2 Returns *this.
      bit_string& set(size_t pos, bool val = 1);

3 Throws out_of_range if pos > len.  Otherwise, if pos == len, the func­
  tion replaces the string controlled by *this with a string  of  length
  len + 1 whose first len elements are a copy of the original string and
  whose remaining element is set according to val.

4 Otherwise, the function sets the element at position pos in the string
  controlled by *this.  If val is nonzero, the stored value is one, oth­
  erwise it is zero.

5 Returns *this.

  23.1.2.14  bit_string::reset                   [lib.bit.string::reset]
      bit_string& reset();

1 Resets all elements of the string controlled by *this.

2 Returns *this.
      bit_string& reset(size_t pos);

3 Throws out_of_range if pos > len.  Otherwise, if pos == len, the func­
  tion  replaces  the string controlled by *this with a string of length
  len + 1 whose first len elements are a copy of the original string and

  whose remaining element is zero.  Otherwise, the function  resets  the
  element at position pos in the string controlled by *this.

  23.1.2.15  bit_string::toggle                 [lib.bit.string::toggle]
      bit_string& toggle();

1 Toggles all elements of the string controlled by *this.

2 Returns *this.
      bit_string& toggle(size_t pos);

3 Throws  out_of_range  if  pos >= len.  Otherwise, the function toggles
  the element at position pos in *this.

  23.1.2.16  bit_string::to_string           [lib.bit.string::to.string]
      string to_string() const;

1 Creates an object of type string and initializes it  to  a  string  of
  length  len  characters.  Each character is determined by the value of
  its corresponding element in the  string  controlled  by  *this.   Bit
  value  zero becomes the character 0, bit value one becomes the charac­
  ter 1.

2 Returns the created object.

  23.1.2.17  bit_string::count                   [lib.bit.string::count]
      size_t count() const;

1 Returns a count of the number of elements set in the string controlled
  by *this.

  23.1.2.18  bit_string::length                 [lib.bit.string::length]
      size_t length() const;

1 Returns len.

  23.1.2.19  bit_string::resize                 [lib.bit.string::resize]
      size_t resize(size_t n, bool val = 0);

1 Throws  length_error if n equals NPOS.  Otherwise, the function alters
  the length of the string controlled by *this as follows:

  --If n <= len, the function replaces the string  controlled  by  *this
    with  a  string of length n whose elements are a copy of the initial
    elements of the original string controlled by *this.

  --If n > len, the function replaces the  string  controlled  by  *this
    with a string of length n whose first len elements are a copy of the
    original string controlled by *this, and  whose  remaining  elements
    all have the value one if val is nonzero, or zero otherwise.

2 Returns the previous value of len.

  23.1.2.20  bit_string::trim                     [lib.bit.string::trim]
      size_t trim();

1 Determines the highest position pos of an element with  value  one  in
  the  string  controlled  by  *this,  if possible.  If no such position
  exists, the function replaces the string with an empty string (len  is
  zero).   Otherwise,  the function replaces the string with a string of
  length pos + 1 whose elements are a copy of the  initial  elements  of
  the original string controlled by *this.

2 Returns the new value of len.

  23.1.2.21  bit_string::find                     [lib.bit.string::find]
      size_t find(bool val, size_t pos = 0, size_t n = NPOS) const;

1 Returns  NPOS  if  pos >= len.  Otherwise, the function determines the
  effective length rlen of the string to be scanned as the smaller of  n
  and len - pos.  The function then determines the lowest position xpos,
  if possible, such that both of the following conditions obtain:

  --pos <= xpos;

  --The element at position xpos in the string controlled  by  *this  is
    one if val is nonzero, or zero otherwise.

2 Returns  xpos  if  the  function  can determine such a value for xpos.
  Otherwise, returns NPOS.

  23.1.2.22  bit_string::rfind                   [lib.bit.string::rfind]
      size_t rfind(bool val, size_t pos = 0, size_t n = NPOS) const;

1 Returns NPOS if pos >= len.  Otherwise, the  function  determines  the
  effective  length rlen of the string to be scanned as the smaller of n
  and len - pos.  The function  then  determines  the  highest  position
  xpos, if possible, such that both of the following conditions obtain:

  --pos <= xpos;

  --The  element  at  position xpos in the string controlled by *this is
    one if val is nonzero, or zero otherwise.

2 Returns xpos if the function can determine  such  a  value  for  xpos.
  Otherwise, returns NPOS.

  23.1.2.23  bit_string::substr                 [lib.bit.string::substr]
      bit_string substr(size_t pos, size_t n = NPOS) const;

1 Returns bit_string(*this, pos, n).

  23.1.2.24  bit_string::operator==            [lib.bit.string::op==.bs]
      bool operator==(const bit_string& rhs) const;

1 Returns  zero  if len != rhs.len or if the value of any element of the
  string controlled by *this differs from the value of the corresponding

  element of the string controlled by rhs.

  23.1.2.25  bit_string::operator!=            [lib.bit.string::op!=.bs]
      bool operator!=(const bit_string& rhs) const;

1 Returns a nonzero value if !(*this == rhs).

  23.1.2.26  bit_string::test                     [lib.bit.string::test]
      bool test(size_t pos) const;

1 Throws out_of_range if pos >= len.  Otherwise, the function returns  a
  nonzero  value if the element at position pos in the string controlled
  by *this is one.

  23.1.2.27  bit_string::any                       [lib.bit.string::any]
      bool any() const;

1 Returns a nonzero value if any bit is set in the string controlled  by
  *this.

  23.1.2.28  bit_string::none                     [lib.bit.string::none]
      bool none() const;

1 Returns  a  nonzero value if no bit is set in the string controlled by
  *this.

  23.1.2.29  bit_string::operator<<             [lib.bit.string::op.lsh]
      bit_string operator<<(size_t pos) const;

1 Constructs an object x of class bit_string  and  initializes  it  with
  *this.

2 Returns x <<= pos.

  23.1.2.30  bit_string::operator>>             [lib.bit.string::op.rsh]
      bit_string operator>>(size_t pos) const;

1 Constructs  an  object  x  of class bit_string and initializes it with
  *this.

2 Returns x >>= pos.

  23.1.2.31  bit_string::operator~                 [lib.bit.string::op~]
      bit_string operator~() const;

1 Constructs an object x of class bit_string  and  initializes  it  with
  *this.

2 Returns x.toggle().

  23.1.2.32  operator+                                   [lib.op+.bs.bs]
      bit_string operator+(const bit_string& lhs, const bit_string& rhs);

1 Constructs  an  object  x  of class bit_string and initializes it with
  lhs.

2 Returns x += rhs.

  23.1.2.33  operator&                                   [lib.op&.bs.bs]
      bit_string operator&(const bit_string& lhs, const bit_string& rhs);

1 Constructs an object x of class bit_string  and  initializes  it  with
  lhs.

2 Returns x &= rhs.

  23.1.2.34  operator|                                   [lib.op|.bs.bs]
      bit_string operator|(const bit_string& lhs, const bit_string& rhs);

1 Constructs  an  object  x  of class bit_string and initializes it with
  lhs.

2 Returns x |= rhs.

  23.1.2.35  operator^                                   [lib.op^.bs.bs]
      bit_string operator^(const bit_string& lhs, const bit_string& rhs);

1 Constructs an object x of class bit_string  and  initializes  it  with
  lhs.

2 Returns x ^= rhs.

  23.1.2.36  operator>>                                     [lib.ext.bs]
      istream& operator>>(istream& is, bit_string& x);

1 A  formatted  input  function,  extracts  up to NPOS - 1 (single-byte)
  characters from is.  The function behaves as if it stores these  char­
  acters  in  a  temporary object str of type string, then evaluates the
  expression x = bit_string(str).  Characters are extracted  and  stored
  until any of the following occurs:

  --NPOS - 1 characters have been extracted and stored;

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

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

2 If  no  characters   are   stored   in   str,   the   function   calls
  is.setstate(ios::failbit).

3 Returns is.

  23.1.2.37  operator<<                                     [lib.ins.bs]
      ostream& operator<<(ostream& os, const bit_string& x);

1 Returns os << x.to_string().

  23.1.3  Template class dyn_array              [lib.template.dyn.array]

1 The  header  <dynarray>  defines  a template class and several related
  functions for representing and manipulating varying-size sequences  of
  some object type T.
  template<class T> class dyn_array {
  public:
      dyn_array();
      dyn_array(size_t size, capacity cap);
      dyn_array(const dyn_array<T>& arr);
      dyn_array(const T& obj, size_t rep = 1);
      dyn_array(const T* parr, size_t n);
      dyn_array<T>& operator+=(const dyn_array<T>& rhs);
      dyn_array<T>& operator+=(const T& obj);
      dyn_array<T>& append(const T& obj, size_t rep = 1);
      dyn_array<T>& append(const T* parr, size_t n = 1);
      dyn_array<T>& assign(const T& obj, size_t rep = 1);
      dyn_array<T>& assign(const T* parr, size_t n = 1);
      dyn_array<T>& insert(size_t pos, const dyn_array<T>& arr);
      dyn_array<T>& insert(size_t pos, const T& obj, size_t rep = 1);
      dyn_array<T>& insert(size_t pos, const T* parr, size_t n = 1);
      dyn_array<T>& remove(size_t pos = 0, size_t n = NPOS);
      dyn_array<T>& sub_array(dyn_array<T>& arr, size_t pos,
                              size_t n = NPOS);
      void swap(dyn_array<T>& arr);
      const T& get_at(size_t pos) const;
      void     put_at(size_t pos, const T& obj);
      T&       operator[](size_t pos);
      const T& operator[](size_t pos) const;
      T*       data();
      const T* data() const;
      size_t length() const;
      void resize(size_t n);
      void resize(size_t n, const T& obj);
      size_t reserve() const;
      void reserve(size_t res_arg);
  private:
  //  T* ptr;             exposition only
  //  size_t len, res;    exposition only
  };

2 The  template  class dyn_array<T> describes an object that can store a
  sequence consisting of a varying number of objects  of  type  T.   The
  first element of the sequence is at position zero.  Such a sequence is
  also called a dynamic array. An object of type T shall have:

  --a default constructor T();

  --a copy constructor T(const T&);

  --an assignment operator T& operator=(const T&);

  --a destructor ~T().

3 For the function signatures described in this subclause:

  --it  is  unspecified whether an operation described in this subclause
    as initializing an object of type T with a copy calls its copy  con­
    structor,  calls  its default constructor followed by its assignment
    operator, or does nothing to an object that is already properly ini­
    tialized;

  --it  is  unspecified  how many times objects of type T are copied, or
    constructed and destroyed.4)

4 For the sake of exposition, the maintained data is presented here as:

  --T *ptr, points to the sequence of objects;

  --size_t len, counts the number of objects currently in the sequence;

  --size_t res, for an unallocated sequence, holds the recommended allo­
    cation  size  of  the  sequence,  while  for  an allocated sequence,
    becomes the currently allocated size.

5 In all cases, len <= res.

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

  --a length error is associated with exceptions of type length_error.

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

  23.1.3.1  dyn_array constructors                  [lib.cons.dyn.array]
      dyn_array();

1 Constructs an object of class dyn_array<T>, initializing:

  --ptr to an unspecified value;

  --len to zero;

  --res to an unspecified value.
          dyn_array(size_t size, capacity cap);
  _________________________
  4) Objects that cannot tolerate this uncertainty, or that fail to meet
  the  stated  requirements, can sometimes be organized into dynamic ar­
  rays through the intermediary of an object of class ptrdyn_array<T>.

2 Throws length_error if size equals NPOS and cap is default_size.  Oth­
  erwise,  the  function constructs an object of class dyn_array<T>.  If
  cap is default_size, the function initializes:

  --ptr to point at the first element of an allocated array of size ele­
    ments  of  type T, each initialized with the default constructor for
    type T;

  --len to size;

  --res to a value at least as large as len.

3 Otherwise, cap shall be reserve and the function initializes:

  --ptr to an unspecified value;

  --len to zero;

  --res to size.
          dyn_array(const dyn_array<T>& arr);

4 Constructs an object of class dyn_array<T> and determines its  initial
  dynamic  array  value  by  copying the elements from the dynamic array
  designated by arr.  Thus, the function initializes:

  --ptr to point at the first element of an allocated array  of  arr.len
    elements  of type T, each initialized with a copy of the correspond­
    ing element from the dynamic array designated by arr;

  --len to arr.len;

  --res to a value at least as large as len.
          dyn_array(const T& obj, size_t rep = 1);

5 Throws length_error if rep equals NPOS.  Otherwise, the function  con­
  structs  an  object  of  class dyn_array<T> and determines its initial
  dynamic array value by copying obj into all  rep  values.   Thus,  the
  function initializes:

  --ptr  to point at the first element of an allocated array of rep ele­
    ments of type T, each initialized by copying obj;

  --len to rep;

  --res to a value at least as large as len.
          dyn_array(const T* parr, size_t n);

6 Throws   length_error   if   n   equals   NPOS.    Otherwise,   throws
  invalid_argument  if  parr  is  a null pointer.  Otherwise, parr shall
  designate the first element of an array of at least n elements of type
  T.

7 The  function  then  constructs  an  object  of class dyn_array<T> and
  determines its initial dynamic array value  by  copying  the  elements

  from the array designated by parr.  Thus, the function initializes:

  --ptr to point at the first element of an allocated array  of  n  ele­
    ments  of  type T, each initialized with a copy of the corresponding
    element from the array designated by parr;

  --len to n;

  --res to a value at least as large as len.

  23.1.3.2  dyn_array::operator+=                  [lib.dyn.array::op+=]
      dyn_array<T>& operator+=(const dyn_array<T>& rhs);

1 Throws length_error if len >= NPOS - rhs.len.  Otherwise, the function
  replaces the dynamic array designated by *this with a dynamic array of
  length len + rhs.len whose first len elements are a copy of the origi­
  nal dynamic array designated by *this and whose remaining elements are
  a copy of the elements of the dynamic array designated by rhs.

2 Returns *this.
      dyn_array<T>& operator+=(const T& obj);

3 Returns append(obj).

  23.1.3.3  dyn_array::append                    [lib.dyn.array::append]
      dyn_array<T>& append(const T& obj, size_t rep = 1);

1 Throws length_error if len >= NPOS -  rep.   Otherwise,  the  function
  replaces the dynamic array designated by *this with a dynamic array of
  length len + rep whose first len elements are a copy of  the  original
  dynamic  array  designated  by  *this and whose remaining elements are
  each a copy of obj.

2 Returns *this.
      dyn_array<T>& append(const T* parr, size_t n = 1);

3 Throws length_error if len >=  NPOS  -  n.   Otherwise,  the  function
  throws  invalid_argument  if n > 0 and parr is a null pointer.  Other­
  wise, parr shall designate the first element of an array of at least n
  elements of type T.

4 The  function then replaces the dynamic array designated by *this with
  a dynamic array of length len + n whose first len elements are a  copy
  of  the original dynamic array designated by *this and whose remaining
  elements are a copy of the initial elements of the array designated by
  parr.

5 Returns *this.

  23.1.3.4  dyn_array::assign                    [lib.dyn.array::assign]
      dyn_array<T>& assign(const T& obj, size_t rep = 1);

1 Throws  length_error if rep == NPOS.  Otherwise, the function replaces
  the dynamic array designated by *this with a dynamic array  of  length

  rep each of whose elements is a copy of obj.

2 Returns *this.
      dyn_array<T>& assign(const T* parr, size_t n = 1);

3 Throws length_error if n ==  NPOS.   Otherwise,  the  function  throws
  invalid_argument if n > 0 and parr is a null pointer.

4 Otherwise,  parr  shall  designate the first element of an array of at
  least n elements of type T.

5 The function then replaces the dynamic array designated by *this  with
  a  dynamic  array of length n whose elements are a copy of the initial
  elements of the array designated by parr.

6 Returns *this.

  23.1.3.5  dyn_array::insert                    [lib.dyn.array::insert]
      dyn_array<T>& insert(size_t pos, const dyn_array<T>& arr);

1 Throws out_of_range if pos >  len.   Otherwise,  the  function  throws
  length_error if len >= NPOS - arr.len.

2 Otherwise, the function replaces the dynamic array designated by *this
  with a dynamic array of length len + arr.len whose first pos  elements
  are  a copy of the initial elements of the original dynamic array des­
  ignated by *this, whose next arr.len elements are a copy of  the  ini­
  tial  elements  of  the  dynamic  array  designated  by arr, and whose
  remaining elements are a copy of the remaining elements of the  origi­
  nal dynamic array designated by *this.

3 Returns *this.
      dyn_array<T>& insert(size_t pos, const T& obj, size_t rep = 1);

4 Throws  out_of_range  if  pos  >  len.  Otherwise, the function throws
  length_error if len >= NPOS - rep.

5 Otherwise, the function replaces the dynamic array designated by *this
  with  a dynamic array of length len + rep whose first pos elements are
  a copy of the initial elements of the original  dynamic  array  desig­
  nated  by  *this,  whose next rep elements are each a copy of obj, and
  whose remaining elements are a copy of the remaining elements  of  the
  original dynamic array designated by *this.

6 Returns *this.
      dyn_array<T>& insert(size_t pos, const T* parr, size_t n = 1);

7 Throws  out_of_range  if  pos  >  len.  Otherwise, the function throws
  length_error if len >= NPOS  -  n.   Otherwise,  the  function  throws
  invalid_argument if n > 0 and parr is a null pointer.  Otherwise, parr
  shall designate the first element of an array of at least  n  elements
  of type T.

8 The function then replaces the dynamic array designated by *this  with
  a  dynamic array of length len + n whose first pos elements are a copy
  of the initial elements of the original dynamic  array  designated  by
  *this, whose next n elements are a copy of the initial elements of the
  array designated by parr, and whose remaining elements are a  copy  of
  the  remaining  elements  of  the original dynamic array designated by
  *this.

9 Returns *this.

  23.1.3.6  dyn_array::remove                    [lib.dyn.array::remove]
      dyn_array<T>& remove(size_t pos = 0, size_t n = NPOS);

1 Throws out_of_range if pos > len.  Otherwise, the function  determines
  the effective length xlen of the sequence to be removed as the smaller
  of n and len - pos.

2 The function then replaces the dynamic array designated by *this  with
  a  dynamic  array  of length len - xlen whose first pos elements are a
  copy of the initial elements of the original dynamic array  designated
  by  *this,  and whose remaining elements are a copy of the elements of
  the original dynamic array designated by *this beginning  at  position
  pos  + xlen.  The original xlen elements beginning at position pos are
  destroyed.

3 Returns *this.

  23.1.3.7  dyn_array::sub_array              [lib.dyn.array::sub.array]
      dyn_array<T>& sub_array(dyn_array<T>& arr, size_t pos, size_t n = NPOS);

1 Throws out_of_range if pos > len.  Otherwise, the function  determines
  the  effective length rlen of the dynamic array designated by *this as
  the smaller of n and arr.len - pos.

2 The function then replaces the dynamic array designated by arr with  a
  dynamic array of length rlen whose elements are a copy of the elements
  of the dynamic array designated by *this beginning at position pos.

3 Returns arr.

  23.1.3.8  dyn_array::swap                        [lib.dyn.array::swap]
      void swap(dyn_array<T>& arr);

1 Replaces the dynamic array designated by *this with the dynamic  array
  designated  by  arr,  and replaces the dynamic array designated by arr
  with the dynamic array originally designated by *this.5)

  _________________________
  5) Presumably, this operation occurs with no actual copying  of  array
  elements.

  23.1.3.9  dyn_array::get_at                    [lib.dyn.array::get.at]
      const T& get_at(size_t pos) const;

1 Throws out_of_range if pos >= len.  Otherwise, returns ptr[pos].

2 The reference returned is invalid after a subsequent call to any  mem­
  ber function for the object.

  23.1.3.10  dyn_array::put_at                   [lib.dyn.array::put.at]
      void put_at(size_t pos, const T& obj);

1 Throws  out_of_range  if  pos >= len.  Otherwise, the function assigns
  obj to the element at position pos in the dynamic array designated  by
  *this.

  23.1.3.11  dyn_array::operator[]             [lib.dyn.array::op.array]
      T&       operator[](size_t pos);
      const T& operator[](size_t pos) const;

1 If pos < len, returns the element at position pos in the dynamic array
  designated by *this.  Otherwise, the behavior is undefined.

2 The reference returned is invalid after a subsequent call to any  mem­
  ber function for the object.

  23.1.3.12  dyn_array::data                       [lib.dyn.array::data]
      T*       data();
      const T* data() const;

1 Returns  ptr if len is nonzero, otherwise a null pointer.  The program
  shall not alter any of the values stored in the  dynamic  array.   Nor
  shall  the  program  treat the returned value as a valid pointer value
  after any subsequent call to a non-const member function of the  class
  dyn_array<T> that designates the same object as this.

  23.1.3.13  dyn_array::length                   [lib.dyn.array::length]
      size_t length() const;

1 Returns len.

  23.1.3.14  dyn_array::resize                   [lib.dyn.array::resize]
      void resize(size_t n);

1 Throws  length_error  if  n  equals  NPOS.  Otherwise, if n != len the
  function alters the length of the dynamic array designated by *this as
  follows:

  --If  n  <  len, the function replaces the dynamic array designated by
    *this with a dynamic array of length n whose elements are a copy  of
    the  initial  elements  of  the original dynamic array designated by
    *this.  Any remaining elements are destroyed.

  --If n > len, the function replaces the dynamic  array  designated  by
    *this  with a dynamic array of length n whose first len elements are

    a  copy of the original dynamic array designated by *this, and whose
    remaining elements are all initialized with the default  constructor
    for class T.
          void resize(size_t n, const T& obj);

2 Throws  length_error  if  n  equals  NPOS.  Otherwise, if n != len the
  function alters the length of the dynamic array designated by *this as
  follows:

  --If  n  <  len, the function replaces the dynamic array designated by
    *this with a dynamic array of length n whose elements are a copy  of
    the  initial  elements  of  the original dynamic array designated by
    *this.  Any remaining elements are destroyed.

  --If n > len, the function replaces the dynamic  array  designated  by
    *this  with a dynamic array of length n whose first len elements are
    a copy of the original dynamic array designated by *this, and  whose
    remaining elements are all initialized by copying obj.

  23.1.3.15  dyn_array::reserve                 [lib.dyn.array::reserve]
      size_t reserve() const;

1 Returns res.
      void reserve(size_t res_arg);

2 If  no dynamic array is allocated, assigns res_arg to res.  Otherwise,
  whether or how the function alters res is unspecified.

  23.1.3.16  operator+                                   [lib.op+.da.da]
      dyn_array<T> operator+(const dyn_array<T>& lhs,
                                             const dyn_array<T>& rhs);

1 Returns dyn_array<T>(lhs) += rhs.
      dyn_array<T> operator+(const dyn_array<T>& lhs, const T& obj);

2 Returns dyn_array<T>(lhs) += rhs.
      dyn_array<T> operator+(const T& obj, const dyn_array<T>& rhs);

3 Returns dyn_array<T>(lhs) += rhs.

  23.1.4  Template class ptr_dyn_array      [lib.template.ptr.dyn.array]

1 The  header <ptrdynarray> defines a template and several related func­
  tions for representing  and  manipulating  varying-size  sequences  of
  pointers to some object type T.
  template<class T> class ptr_dyn_array : public dyn_array<void*> {
  public:
      ptr_dyn_array();
      ptr_dyn_array(size_t size, capacity cap);
      ptr_dyn_array(const ptr_dyn_array<T>& arr);
      ptr_dyn_array(T* obj, size_t rep = 1);
      ptr_dyn_array(T** parr, size_t n = 1);

      ptr_dyn_array<T>& operator+=(const ptr_dyn_array<T>& rhs);
      ptr_dyn_array<T>& operator+=(T* obj);
      ptr_dyn_array<T>& append(T* obj, size_t rep = 1);
      ptr_dyn_array<T>& append(T** parr, size_t n = 1);
      ptr_dyn_array<T>& assign(T* obj, size_t rep = 1);
      ptr_dyn_array<T>& assign(T** parr, size_t n = 1);
      ptr_dyn_array<T>& insert(size_t pos, const ptr_dyn_array<T>& arr);
      ptr_dyn_array<T>& insert(size_t pos, T* obj, size_t rep = 1);
      ptr_dyn_array<T>& insert(size_t pos, T** parr, size_t n = 1);
      ptr_dyn_array<T>& remove(size_t pos = 0, size_t n = NPOS);
      ptr_dyn_array<T>& sub_array(ptr_dyn_array<T>& arr, size_t pos,
                                                  size_t n = NPOS);
      void swap(ptr_dyn_array<T>& arr);
      T*   get_at(size_t pos) const;
      void put_at(size_t pos, T* obj);
      T*&       operator[](size_t pos);
      T* const& operator[](size_t pos) const;
      T**       data();
      const T** data() const;
      size_t length() const;
      void resize(size_t n);
      void resize(size_t n, T* obj);
      size_t reserve() const;
      void   reserve(size_t res_arg);
  };

2 The template class ptr_dyn_array<T> describes an object that can store
  a  sequence  consisting of a varying number of objects of type pointer
  to T.  Such a sequence is also called a dynamic pointer array. Objects
  of type T are never created, destroyed, copied, assigned, or otherwise
  accessed by the function signatures described in this subclause.

  23.1.4.1  ptr_dyn_array constructors          [lib.cons.ptr.dyn.array]
      ptr_dyn_array();

1 Constructs an object of class ptr_dyn_array<T>, initializing the  base
  class with dyn_array<void*>().
      ptr_dyn_array(size_t size, capacity cap);

2 Constructs  an object of class ptr_dyn_array<T>, initializing the base
  class with dyn_array<void*>(size, cap).
      ptr_dyn_array(const ptr_dyn_array<T>& arr);

3 Constructs an object of class ptr_dyn_array<T>, initializing the  base
  class with dyn_array<void*>(arr).
      ptr_dyn_array(T* obj, size_t rep = 1);

4 Constructs  an object of class ptr_dyn_array<T>, initializing the base
  class with dyn_array<void*>((void*)obj, rep).
      ptr_dyn_array(const T** parr, size_t n);

5 Constructs an object of class ptr_dyn_array<T>, initializing the  base
  class with dyn_array<void*>((void**)parr, n).

  23.1.4.2  ptr_dyn_array::operator+=          [lib.ptr.dyn.array::op+=]
      ptr_dyn_array<T>& operator+=(const ptr_dyn_array<T>& rhs);

1 Returns         (ptr_dyn_array<T>&)dyn_array<void*>::operator+=((const
  dyn_array<void*>&)rhs).
      ptr_dyn_array<T>& operator+=(T* obj);

2 Returns  (ptr_dyn_array<T>&)dyn_array<void*>:: operator+=((void*)obj).

  23.1.4.3  ptr_dyn_array::append            [lib.ptr.dyn.array::append]
      ptr_dyn_array<T>& append(T* obj, size_t rep = 1);

1 Returns (ptr_dyn_array<T>&)dyn_array<void*>::append((void*)obj,  rep).
      ptr_dyn_array<T>& append(T** parr, size_t n = 1);

2 Returns  (ptr_dyn_array<T>&)dyn_array<void*>::append((void**)parr, n).

  23.1.4.4  ptr_dyn_array::assign            [lib.ptr.dyn.array::assign]
      ptr_dyn_array<T>& assign(T* obj, size_t rep = 1);

1 Returns (ptr_dyn_array<T>&)dyn_array<void*>::assign((void*)obj,  rep).
      ptr_dyn_array<T>& assign(T** parr, size_t n = 1);

2 Returns  (ptr_dyn_array<T>&)dyn_array<void*>::assign((void**)parr, n).

  23.1.4.5  ptr_dyn_array::insert            [lib.ptr.dyn.array::insert]
      ptr_dyn_array<T>& insert(size_t pos, const ptr_dyn_array<T>& arr);

1 Returns    (ptr_dyn_array<T>&)dyn_array<void*>::insert(pos,     (const
  dyn_array<void*>&)arr).
      ptr_dyn_array<T>& insert(size_t pos, T*obj, size_t rep = 1);

2 Returns  (ptr_dyn_array<T>&)dyn_array<void*>::insert(pos,  (void*)obj,
  rep).
      ptr_dyn_array<T>& insert(size_t pos, T**parr, size_t n = 1);

3 Returns (ptr_dyn_array<T>&)dyn_array<void*>::insert(pos, (void**)parr,
  n).

  23.1.4.6  ptr_dyn_array::remove            [lib.ptr.dyn.array::remove]
      ptr_dyn_array<T>& remove(size_t pos = 0, size_t n = NPOS);

1 Returns (ptr_dyn_array<T>&)dyn_array<void*>::remove(pos, n).

  23.1.4.7  ptr_dyn_array::sub_array      [lib.ptr.dyn.array::sub.array]
      ptr_dyn_array<T>& sub_array(ptr_dyn_array<T>& arr, size_t pos,
                                                  size_t n = NPOS);

1 Returns (ptr_dyn_array<T>&)dyn_array<void*>::sub_array(arr, pos, n).

  23.1.4.8  ptr_dyn_array::swap                [lib.ptr.dyn.array::swap]
      void swap(ptr_dyn_array<T>& arr);

1 Calls dyn_array<void*>::swap(arr).

  23.1.4.9  ptr_dyn_array::get_at            [lib.ptr.dyn.array::get.at]
      T* get_at(size_t pos) const;

1 Returns (T*)dyn_array<void*>::get_at(pos).

  23.1.4.10  ptr_dyn_array::put_at           [lib.ptr.dyn.array::put.at]
      void put_at(size_t pos, T* obj);

1 Calls dyn_array<void*>::put_at(pos, (void*)obj).

  23.1.4.11                                [lib.ptr.dyn.array::op.array]
       ptr_dyn_array::operator[]
      T*&       operator[](size_t pos);
      T* const& operator[](size_t pos) const;

1 Returns (T*&)dyn_array<void*>::operator[](pos).

  23.1.4.12  ptr_dyn_array::data               [lib.ptr.dyn.array::data]
      T** data();
      const T** data() const;

1 Returns (T*)dyn_array<void*>::data().

  23.1.4.13  ptr_dyn_array::length           [lib.ptr.dyn.array::length]
      size_t length() const;

1 Returns dyn_array<void*>::length().

  23.1.4.14  ptr_dyn_array::resize           [lib.ptr.dyn.array::resize]
      void resize(size_t n);

1 Calls dyn_array<void*>::resize(n).
      void resize(size_t n, T* obj);

2 Calls dyn_array<void*>::resize(n, (void*)obj).

  23.1.4.15  ptr_dyn_array::reserve         [lib.ptr.dyn.array::reserve]
      size_t reserve() const;

1 Returns dyn_array<void*>::reserve().
      void reserve(size_t res_arg);

2 Returns dyn_array<void*>::reserve(res_arg).

  23.1.4.16  operator+                                 [lib.op+.pda.pda]
      ptr_dyn_array<T> operator+(const ptr_dyn_array<T>& lhs,
      const ptr_dyn_array<T>& rhs);

1 Returns ptr_dyn_array<T><T>(lhs) += rhs).
      ptr_dyn_array<T> operator+(const ptr_dyn_array<T>& lhs, T* obj);

2 Returns ptr_dyn_array<T><T>(lhs) += rhs).
      ptr_dyn_array<T> operator+(T* obj, const ptr_dyn_array<T>& rhs);

3 Returns ptr_dyn_array<T><T>(lhs) += rhs).

  23.1.5  Template class vector                             [lib.vector]

1 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.
  template <class T, template <class U> class Allocator = allocator>
  class vector {
  public:
    // typedefs:
      typedef ? iterator;
      typedef ? const_iterator;
      typedef ? size_type;
      typedef ? difference_type;
      typedef T value_type;
    // allocation/deallocation:
      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);
      void reserve(size_type n);
    // accessors:
      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;
      T&       operator[](size_type n);
      const T& operator[](size_type n) const;
      T&       front();
      const T& front() const;
      T&       back();
      const T& back() const;

    // insert/erase:
      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.1.5.1  Typedefs                               [lib.vector.typedefs]

1 iterator  is  a random access iterator referring to T.  The exact type
  is implementation dependent and determined by Allocator.

2 const_iterator is a constant random access iterator referring to const
  T.  The exact type is implementation dependent and determined by Allo­
  cator.   It  is  guaranteed  that   there   is   a   constructor   for
  const_iterator out of iterator.

3 size_type is an unsigned integral type.  The exact type is implementa­
  tion dependent and determined by Allocator.

4 difference_type is a signed integral type.  The exact type  is  imple­
  mentation dependent and determined by Allocator.

  23.1.5.2  Constructors                               [lib.vector.cons]

1 The  constructor  template  <class InputIterator> vector(InputIterator
  first, InputIterator last) makes only N calls to the copy  constructor
  of T (where N is the distance between first and last) and no realloca­
  tions if iterators first and last are of  forward,  bidirectional,  or
  random  access  categories.  It does at most 2N calls to the copy con­
  structor 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.1.5.3  Member functions                        [lib.vector.members]

1 The member function capacity returns the size of the allocated storage
  in  the  vector.   The  member  function  reserve  is 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 insertions  that  happen  after  reserve  takes
  place till the time when the size of the vector reaches the size spec­
  ified by reserve.

2 insert causes reallocation if the new size is  greater  than  the  old
  capacity.   If  no  reallocation happens, all the iterators and refer­
  ences before the insertion point remain  valid.   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 con­
  stant.  Insertion of multiple elements 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.   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, bidirectional or  ran­
  dom  access  category.   Otherwise, it does insert elements one by one
  and should not be used for inserting into the middle of vectors.

3 erase 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 vec­
  tor after the erased elements.

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

1 To optimize space allocation, a specialization for bool is provided:
  class vector<bool, allocator> {
  public:
    // bit reference:
      class reference {
      public:
         ~reference();
          operator bool() const;
          reference& operator=(const bool x);
          void flip();      // flips the bit
      };
    // typedefs:
      typedef ? iterator;
      typedef ? const_iterator;
      typedef size_t    size_type;
      typedef ptrdiff_t difference_type ;
      typedef bool      value_type;

    // allocation/deallocation:
      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);
    // accessors:
      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;
      reference       front();
      const reference front() const;
      reference       back();
      const reference back() const;
    // insert/erase:
      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>.

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

  +-------                 BEGIN BOX 1                -------+
  At  present,  it is not possible to templatize a specialization.  That
  is, we cannot write:
    template <template <class U> class Allocator = allocator>
    class vector<bool, Allocator> { /* ... */ };
  Therefore, only vector<bool, allocator> is provided.
  +-------                  END BOX 1                 -------+

  23.1.7  Template class list                                 [lib.list]

1 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 and deques, fast random access to list elements is not supported,
  but many algorithms only need sequential access anyway.
  template <class T, template <class U> class Allocator = allocator>
  class list {
  public:
    // typedefs:
      typedef ? iterator;
      typedef ? const_iterator;
      typedef ? size_type;
      typedef ? difference_type;
      typedef T value_type;
    // allocation/deallocation:
      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);
    // accessors:
      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&       front();
      const T& front() const;
      T&       back();
      const T& back() const;
    // insert/erase:
      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 first, 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.1.7.1  Typedefs                                 [lib.list.typedefs]

1 iterator is a bidirectional iterator referring to T.  The  exact  type
  is implementation dependent and determined by Allocator.

2 const_iterator is a constant bidirectional iterator referring to const
  T.  The exact type is implementation dependent and determined by Allo­
  cator.    It   is   guaranteed   that   there  is  a  constructor  for
  const_iterator out of iterator.

3 size_type is an unsigned integral type.  The exact type is implementa­
  tion dependent and determined by Allocator.

4 difference_type  is  a signed integral type.  The exact type is imple­
  mentation dependent and determined by Allocator.

  23.1.7.2  Member functions                          [lib.list.members]

1 insert does not affect  the  validity  of  iterators  and  references.
  Insertion  of  a  single  element  into a list takes constant time and
  exactly one call to the copy constructor of T.  Insertion of  multiple
  elements into a list is linear in the number of elements inserted, and
  the number of calls to the copy constructor of T is exactly  equal  to
  the number of elements inserted.

2 erase invalidates only the iterators and references to the erased ele­
  ments.  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 lin­
  ear 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.

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

4 list provides three splice operations that destructively move elements
  from one list to another:

5 void splice(iterator position, list<T, Allocator>& x) inserts the con­
  tents  of  x  before  position and x becomes empty.  It takes constant
  time.

6 void splice(iterator position,  list<T,  Allocator>&  x,  iterator  i)
  inserts  an  element  pointed  to by i from list x before position and
  removes the element from x.  It takes constant time.   i  is  a  valid
  iterator of x.

7 void  splice(iterator position, list<T, Allocator>& x, iterator first,
  iterator last) inserts elements in  the  range  [first,  last)  before
  position  and  removes  the  elements  from  x.  It takes linear time.
  [first, last) is a valid range in x.

8 remove erases all the elements in the list referred by the list itera­
  tor i for which the following conditions hold:   *i == value, pred(*i)
  == true.  remove is stable, that is, the relative order  of  the  ele­
  ments  that are not removed is the same as their relative order in the
  original list.  Exactly size() applications of the corresponding pred­
  icate are done.

9 unique  erases  all but the first element from every consecutive group
  of equal elements in the list.  Exactly size() - 1 applications of the
  corresponding binary predicate are done.

10merge  merges  the argument list into the list (both are assumed to be
  sorted).  The merge is stable, that is, 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.  At most size() + x.size()
  - 1 comparisons are done.

11reverse  reverses the order of the elements in the list.  It is linear
  time.

12sort sorts the list according to the operator< or a  compare  function
  object.   It  is stable, that is, the relative order of the equal ele­
  ments is preserved.  Approximately NlogN comparisons are done where  N
  is equal to size().

  23.1.8  Template class deque                               [lib.deque]

1 deque  is  a  kind  of  sequence  that, like a vector, supports 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.  As with vectors, storage management is  han­
  dled automatically.

  template <class T, template <class U> class Allocator = allocator>
  class deque {
  public:
    // typedefs:
      typedef ? iterator;
      typedef ? const_iterator;
      typedef ? size_type;
      typedef ? difference_type;
      typedef T value_type;
    // allocation/deallocation:
      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);
    // accessors:
      iterator       begin();
      const_iterator begin() const;
      iterator       end();
      const_iterator end() const;
      size_type size() const;
      size_type max_size() const;
      bool empty() const;
      T&       operator[](size_type n);
      const T& operator[](size_type n) const;
      T&       front();
      const T& front() const;
      T&       back();
      const T& back() const;
  // insert/erase:
    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.1.8.1  Typedefs                                [lib.deque.typedefs]

1 iterator is a random access iterator referring to T.  The  exact  type
  is implementation dependent and determined by Allocator.

2 const_iterator is a constant random access iterator referring to const
  T.  The exact type is implementation dependent and determined by Allo­
  cator.    It   is   guaranteed   that   there  is  a  constructor  for
  const_iterator out of iterator.

3 size_type is an unsigned integral type.  The exact type is implementa­
  tion dependent and determined by Allocator.

4 difference_type  is  a signed integral type.  The exact type is imple­
  mentation dependent and determined by Allocator.

  23.1.8.2  Member functions                         [lib.deque.members]

1 insert 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.  In the worst case,  insert­
  ing  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 con­
  structor of T.  That is, a deque is especially optimized  for  pushing
  and popping elements at the beginning and end.

2 erase 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 destruc­
  tor is the same as the number of elements erased, but  the  number  of
  the  calls  to  the assignment operator is equal to the minimum of the
  number of elements before the erased elements and the number  of  ele­
  ment after the erased elements.

  23.1.9  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, list and deque  can
  be used.
  template <class Container>
  class stack {
  friend bool operator==(const stack<Container>& x, const stack<Container>& y);
  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) {
    return x.c == y.c;
  }

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.

  23.1.10  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  and
  deque can be used.
  template <class Container>
  class queue {
  friend bool operator==(const queue<Container>& x, const queue<Container>& y);
  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) {
    return x.c == y.c;
  }

  23.1.11  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 and deque can be used.
  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()) : c(), comp(x) {}
    template <class InputIterator>
      priority_queue(InputIterator first, InputIterator last,
        const Compare& x = Compare())
      : c(first, last), comp(x) {
        make_heap(c.begin(), c.end(), comp);
    }
    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) {
      c.push_back(x);
      push_heap(c.begin(), c.end(), comp);
    }
    void pop() {
      pop_heap(c.begin(), c.end(), comp);
      c.pop_back();
    }
  };

  // no equality is provided

  23.2  Associative containers                         [lib.associative]

  23.2.1  Template class set                                   [lib.set]

1 set is a kind of associative container that supports unique keys (con­
  tains  at  most one of each key value) and provides for fast retrieval
  of the keys themselves.
  template <class Key, class Compare = less<Key>,
    template <class U> class Allocator = allocator>
  class set {
  public:
  // typedefs:
    typedef Key     key_type;
    typedef Key     value_type;
    typedef Compare key_compare;
    typedef Compare value_compare;
    typedef ? iterator;
    typedef iterator const_iterator;
    typedef ? size_type;
    typedef ? difference_type;
  // allocation/deallocation:
    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);

  // accessors:
    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;
  // insert/erase:
    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.2.1.1  Typedefs                                  [lib.set.typedefs]

1 iterator  is  a  constant  bidirectional  iterator  referring to const
  value_type.  The exact type is implementation dependent and determined
  by Allocator.

2 const_iterator is the same type as iterator.

3 size_type is an unsigned integral type.  The exact type is implementa­
  tion dependent and determined by Allocator.

4 difference_type is a signed integral type.  The exact type  is  imple­
  mentation dependent and determined by Allocator.

  23.2.2  Template class multiset                         [lib.multiset]

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

  template <class Key, class Compare = less<Key>,
    template <class U> class Allocator = allocator>
  class multiset {
  public:
  // typedefs:
    typedef Key     key_type;
    typedef Key     value_type;
    typedef Compare key_compare;
    typedef Compare value_compare;
    typedef ? iterator;
    typedef iterator const_iterator;
    typedef ? size_type;
    typedef ? difference_type;
  // allocation/deallocation:
    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);
  // accessors:
    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;
  // insert/erase:
    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);

  23.2.2.1  Typedefs                             [lib.multiset.typedefs]

1 iterator is a  constant  bidirectional  iterator  referring  to  const
  value_type.  The exact type is implementation dependent and determined
  by Allocator.

2 const_iterator is the same type as iterator.

3 size_type is an unsigned integral type.  The exact type is implementa­
  tion dependent and determined by Allocator.

4 difference_type  is  a signed integral type.  The exact type is imple­
  mentation dependent and determined by Allocator.

  23.2.3  Template class map                                   [lib.map]

1 map is a kind of associative container that supports unique keys (con­
  tains  at  most one of each key value) and provides for fast retrieval
  of values of another type T based on the keys.
  template <class Key, class T, class Compare = less<Key>,
    template <class U> class Allocator = allocator>
  class map {
  public:
  // typedefs:
    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);
      }
    };
    typedef ? iterator;
    typedef ? const_iterator;
    typedef ? size_type;
    typedef ? difference_type;
  // allocation/deallocation:
    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);

  // accessors:
    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);
  // insert/erase:
    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.2.3.1  Typedefs                                  [lib.map.typedefs]

1 iterator  is  a  bidirectional  iterator referring to value_type.  The
  exact type is implementation dependent and determined by Allocator.

2 const_iterator is the a constant bidirectional iterator  referring  to
  const  value_type.   The  exact  type  is implementation dependent and
  determined by Allocator.  It is guaranteed that there is a constructor
  for const_iterator out of iterator.

3 size_type is an unsigned integral type.  The exact type is implementa­
  tion dependent and determined by Allocator.

4 difference_type is a signed integral type.  The exact type  is  imple­
  mentation dependent and determined by Allocator.

  23.2.3.2  Member functions                           [lib.map.members]

1 In addition to the standard set of  member  functions  of  associative
  containers,  map provides T& operator[](const key_type&).  For a map m
  and    key    k,    m[k]     is     semantically     equivalent     to
  (*((m.insert(make_pair(k, T()))).first)).second.

  23.2.4  Template class multimap                         [lib.multimap]

1 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.
  template <class Key, class T, class Compare = less<Key>,
             template <class U> class Allocator = allocator>
  class multimap {
  public:
  // typedefs:
    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);
      }
    };
    typedef ? iterator;
    typedef ? const_iterator;
    typedef ? size_type;
    typedef ? difference_type;
  // allocation/deallocation:
    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);
  // accessors:
    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;

  // insert/erase:
    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.2.4.1  Typedefs                             [lib.multimap.typedefs]

1 iterator is a bidirectional iterator  referring  to  value_type.   The
  exact type is implementation dependent and determined by Allocator.

2 const_iterator  is  the a constant bidirectional iterator referring to
  const value_type.  The exact  type  is  implementation  dependent  and
  determined by Allocator.  It is guaranteed that there is a constructor
  for const_iterator out of iterator.

3 size_type is an unsigned integral type.  The exact type is implementa­
  tion dependent and determined by Allocator.

4 difference_type  is  a signed integral type.  The exact type is imple­
  mentation dependent and determined by Allocator.