______________________________________________________________________

  20   General utilities library                         [lib.utilities]

  ______________________________________________________________________

1 This clause describes components used by other elements of  the  Stan-
  dard  C++ library.  These components may also be used by C++ programs.

2 The following clauses describe  utility  and  allocator  requirements,
  utility components, function objects, dynamic memory management utili-
  ties, and date/time utilities, as summarized in Table 1:

                Table 1--General utilities library summary

         +-------------------------------------------------------+
         |                Clause                     Header(s)   |
         +-------------------------------------------------------+
         |_lib.utility.requirements_ Requirements                |
         +-------------------------------------------------------+
         |_lib.utility_ Utility components          <utility>    |
         +-------------------------------------------------------+
         |_lib.function.objects_ Function objects   <functional> |
         +-------------------------------------------------------+
         |_lib.memory_ Memory                       <memory>     |
         +-------------------------------------------------------+
         |_lib.date.time_ Date and time             <ctime>      |
         +-------------------------------------------------------+

  20.1  Requirements                          [lib.utility.requirements]

1 _lib.utility.requirements_ describes requirements  on  template  argu-
  ments.    _lib.equalitycomparable_   through   _lib.copyconstructible_
  describe  requirements  on  types  used  to   instantiate   templates.
  _lib.allocator.requirements_  describes  the  requirements  on storage
  allocators.

  20.1.1  Equality comparison                   [lib.equalitycomparable]

1 In Table 2, T is a type to be supplied by a C++ program  instantiating
  a template, a, b and c are values of type T.

                 Table 2--EqualityComparable requirements

  +------------------------------------------------------------------------+
  |expression       return type                   requirement              |
  +------------------------------------------------------------------------+
  |a == b       convertible to bool   ==  is an equiva-                    |
  |                                   lence   relation,                    |
  |                                   that  is, it sat-                    |
  |                                   isfies  the  fol-                    |
  |                                   lowing    proper-                    |
  |                                   ties:                                |
  |                                                                        |
  |                                   --For all a, a == a.                 |
  |                                                                        |
  |                                   --If a == b, then b == a.            |
  |                                                                        |
  |                                   --If a == b and b == c, then a == c. |
  +------------------------------------------------------------------------+

  20.1.2  Less than comparison                  [lib.lessthancomparable]

1 In the following Table 3, T is a type to be supplied by a C++  program
  instantiating a template, a and b are values of type T.

                 Table 3--LessThanComparable requirements

  +--------------------------------------------------------------------------------------------+
  |expression       return type                             requirement                        |
  +--------------------------------------------------------------------------------------------+
  |a < b        convertible to bool   < is a strict weak ordering relation (_lib.alg.sorting_) |
  +--------------------------------------------------------------------------------------------+

  20.1.3  Copy construction                      [lib.copyconstructible]

1 In  the following Table 4, T is a type to be supplied by a C++ program
  instantiating a template, t is a value of type T, and u is a value  of
  type const T.

                 Table 4--CopyConstructible requirements

          +----------------------------------------------------+
          |expression   return type         requirement        |
          +----------------------------------------------------+
          |T(t)                       t is equivalent to T(t)  |
          +----------------------------------------------------+
          |T(u)                       u is equivalent to T(u)  |
          +----------------------------------------------------+
          |t.~T()                                              |
          +----------------------------------------------------+
          |&t           T*            denotes the address of t |
          +----------------------------------------------------+
          |&u           const T*      denotes the address of u |
          +----------------------------------------------------+

  20.1.4  Default construction                     [lib.default.con.req]

1 The default constructor is not required.  Certain container class mem-
  ber function signatures specify the default constructor as  a  default
  argument.   T()  must be a well-defined expression (_dcl.init_) if one
  of  those  signatures   is   called   using   the   default   argument
  (_dcl.fct.default_).

  20.1.5  Allocator requirements            [lib.allocator.requirements]

1 The  library  describes a standard set of requirements for allocators,
  which are objects that encapsulate the information about an allocation
  model.   This information includes the knowledge of pointer types, the
  type of their difference, the type of the  size  of  objects  in  this
  allocation  model,  as  well as the memory allocation and deallocation
  primitives for it.  All of the  containers  (clause  _lib.containers_)
  are parameterized in terms of allocators.

2 Table  5 describes the requirements on types manipulated through allo-
  cators.  All the operations on the allocators are expected to be amor-
  tized  constant time.  Table 6 describes the requirements on allocator
  types.

                Table 5--Descriptive variable definitions

     +---------------------------------------------------------------+
     |Variable                        Definition                     |
     +---------------------------------------------------------------+
     |T, U        any type                                           |
     +---------------------------------------------------------------+
     |X           an Allocator class for type T                      |
     +---------------------------------------------------------------+
     |Y           the corresponding Allocator class for type U       |
     +---------------------------------------------------------------+
     |t           a value of type const T&                           |
     +---------------------------------------------------------------+
     |a, a1, a2   values of type X&                                  |
     +---------------------------------------------------------------+
     |b           a value of type Y                                  |
     +---------------------------------------------------------------+
     |p           a value of type X::pointer, obtained by calling    |
     |            a1.allocate, where a1 == a.                        |
     +---------------------------------------------------------------+
     |q           a value of type X::const_pointer obtained by       |
     |            conversion from a value p.                         |
     +---------------------------------------------------------------+
     |r           a value of type X::reference obtained by           |
     |            the expression *p.                                 |
     +---------------------------------------------------------------+
     |s           a value of type X::const_reference obtained by     |
     |            the expression *q or by conversion from a value r. |
     +---------------------------------------------------------------+
     |u           a value of type Y::const_pointer obtained by       |
     |            calling Y::allocate, or else 0.                    |
     +---------------------------------------------------------------+
     |n           a value of type X::size_type.                      |
     +---------------------------------------------------------------+

                     Table 6--Allocator requirements

  -------------------------------------------------------------------------------------
            expression                 return type               assertion/note
                                                               pre/post-condition
  -------------------------------------------------------------------------------------
   X::pointer                     Pointer to T.
  -------------------------------------------------------------------------------------
   X::const_pointer               Pointer to const T.
  -------------------------------------------------------------------------------------
   X::reference                   T&
  -------------------------------------------------------------------------------------
   X::const_reference             T const&
  -------------------------------------------------------------------------------------
   X::value_type                  Identical to T
  -------------------------------------------------------------------------------------
   X::size_type                   unsigned integral type   a type that can represent
                                                           the size of the largest
                                                           object in the allocation
                                                           model.
  -------------------------------------------------------------------------------------
   X::difference_type             signed integral type     a type that can represent
                                                           the difference between any
                                                           two pointers in the allo-
                                                           cation model.
  -------------------------------------------------------------------------------------
   typename X::rebind<U>::other   Y                        For all U (including T),
                                                           Y::rebind<T>::other is X.
  -------------------------------------------------------------------------------------
   a.address(r)                   X::pointer
  -------------------------------------------------------------------------------------
   a.address(s)                   X::const_pointer
  -------------------------------------------------------------------------------------
   a.allocate(n)                  X::pointer               Memory is allocated for n
   a.allocate(n,u)                                         objects of type T but ob-
                                                           jects are not constructed.
                                                           allocate may raise an ap-
                                                           propriate exception.  The
                                                           result is a random access
                                                           iterator.1)
  -------------------------------------------------------------------------------------
   a.deallocate(p, n)             (not used)               All n T objects in the
                                                           area pointed by p must be
                                                           destroyed prior to this
                                                           call.  n must match the
                                                           value passed to allocate
                                                           to obtain this memory.
                                                           Does not throw exceptions.
                                                           [Note: p must not be null.
                                                            --end note]

  |                                                                                   |
  |                                                                                   |
  |                                                                                   |
  |                                                                                   |
  +-----------------------------------------------------------------------------------+
  |a.max_size()                   X::size_type             the largest value that can |
  |                                                        meaningfully be passed to  |
  |                                                        X::allocate().             |
  +-----------------------------------------------------------------------------------+
  |a1 == a2                       bool                     returns true iff storage   |
  |                                                        allocated from each can be |
  |                                                        deallocated via the other. |
  +-----------------------------------------------------------------------------------+
  |a1 != a2                       bool                     same as !(a1 == a2)        |
  +-----------------------------------------------------------------------------------+
  |X()                                                     creates a default in-      |
  |                                                        stance. Note: a destructor |
  |                                                        is assumed.                |
  +-----------------------------------------------------------------------------------+
  |X a(b);                                                 post: Y(a) == b            |
  +-----------------------------------------------------------------------------------+
  |a.construct(p,t)               (not used)               Effect: new((void*)p) T(t) |
  +-----------------------------------------------------------------------------------+
  |a.destroy(p)                   (not used)               Effect: ((T*)p)->~T()      |
  +-----------------------------------------------------------------------------------+

3 The  template  class member rebind in the table above is effectively a
  template typedef: if the name Allocator is bound to  SomeAllocator<T>,
  then Allocator::rebind<U>::other is the same type as SomeAllocator<U>.

4 Implementations of containers described in this International Standard
  are  permitted to assume that their Allocator template parameter meets
  the following two additional requirements beyond those in Table 6.

  --All instances of a given allocator type are required  to  be  inter-
    changeable and always compare equal to each other.

  --The  typedef  members pointer, const_pointer, size_type, and differ-
    ence_type are required to be T*, T const*,  size_t,  and  ptrdiff_t,
    respectively.

5 Implementors  are encouraged to supply libraries that can accept allo-
  cators that encapsulate more general memory models  and  that  support
  non-equal   instances.   In  such  implementations,  any  requirements
  imposed on allocators by containers  beyond  those  requirements  that
  appear in Table 6, and the semantics of containers and algorithms when
  allocator instances compare non-equal, are implementation-defined.

  20.2  Utility components                                 [lib.utility]

1 This subclause contains some basic template functions and classes that
  are used throughout the rest of the library.

  _________________________
  1)  It is intended that a.allocate be an efficient means of allocating
  a single object of type T, even when sizeof(T)  is  small.   That  is,
  there is no need for a container to maintain its own ``free list''.

  Header <utility> synopsis

  namespace std {
    // _lib.operators_, operators:
    namespace rel_ops {
      template<class T> bool operator!=(const T&, const T&);
      template<class T> bool operator> (const T&, const T&);
      template<class T> bool operator<=(const T&, const T&);
      template<class T> bool operator>=(const T&, const T&);
    }
    // _lib.pairs_, pairs:
    template <class T1, class T2> struct pair;
    template <class T1, class T2>
      bool operator==(const pair<T1,T2>&, const pair<T1,T2>&);
    template <class T1, class T2>
      bool operator< (const pair<T1,T2>&, const pair<T1,T2>&);
    template <class T1, class T2>
      bool operator!=(const pair<T1,T2>&, const pair<T1,T2>&);
    template <class T1, class T2>
      bool operator> (const pair<T1,T2>&, const pair<T1,T2>&);
    template <class T1, class T2>
      bool operator>=(const pair<T1,T2>&, const pair<T1,T2>&);
    template <class T1, class T2>
      bool operator<=(const pair<T1,T2>&, const pair<T1,T2>&);
    template <class T1, class T2> pair<T1,T2> make_pair(const T1&, const T2&);
  }

  20.2.1  Operators                                      [lib.operators]

1 To  avoid  redundant  definitions  of operator!= out of operator== and
  operators >, <=, and >= out of operator<,  the  library  provides  the
  following:

  template <class T> bool operator!=(const T& x, const T& y);

  Requires:
    Type T is EqualityComparable (_lib.equalitycomparable_).
  Returns:
    !(x == y).

  template <class T> bool operator>(const T& x, const T& y);

  Requires:
    Type T is LessThanComparable (_lib.lessthancomparable_).
  Returns:
    y < x.

  template <class T> bool operator<=(const T& x, const T& y);

  Requires:
    Type T is LessThanComparable (_lib.lessthancomparable_).
  Returns:
    !(y < x).

  template <class T> bool operator>=(const T& x, const T& y);

  Requires:
    Type T is LessThanComparable (_lib.lessthancomparable_).
  Returns:
    !(x < y).

2 In this library, whenever a declaration is provided for an operator!=,
  operator>, operator>=, or operator<=, and requirements  and  semantics
  are  not  explicitly  provided,  the requirements and semantics are as
  specified in this clause.

  20.2.2  Pairs                                              [lib.pairs]

1 The library provides a template for  heterogeneous  pairs  of  values.
  The  library  also  provides  a matching template function to simplify
  their construction.

  template <class T1, class T2>
  struct pair {
    typedef T1 first_type;
    typedef T2 second_type;

    T1 first;
    T2 second;
    pair();
    pair(const T1& x, const T2& y);
    template<class U, class V> pair(const pair<U, V> &p);
  };

  pair();

  Effects:
    Initializes its members as if  implemented:  pair()  :  first(T1()),
    second(T2()) {}

  pair(const T1& x, const T2& y);

  Effects:
    The constructor initializes first with x and second with y.

  template<class U, class V> pair(const pair<U, V> &p);

  Effects:
    Initializes  members from the corresponding members of the argument,
    performing implicit conversions as needed.

  template <class T1, class T2>
    bool operator==(const pair<T1, T2>& x, const pair<T1, T2>& y);

  Returns:
    x.first == y.first && x.second == y.second.

  template <class T1, class T2>
    bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y);

  Returns:
    x.first < y.first || (!(y.first < x.first) && x.second <  y.second).

  template <class T1, class T2>
    pair<T1, T2> make_pair(const T1& x, const T2& y);

  Returns:
    pair<T1, T2>(x, y).

2 [Example: In place of:
    return pair<int, double>(5, 3.1415926);   // explicit types
  a C++ program may contain:
    return make_pair(5, 3.1415926);           // types are deduced
   --end example]

  20.3  Function objects                          [lib.function.objects]

1 Function  objects  are  objects  with an operator() defined.  They are
  important for the effective use of the library.  In the  places  where
  one  would  expect  to  pass a pointer to a function to an algorithmic
  template (clause _lib.algorithms_),  the  interface  is  specified  to
  accept  an  object  with  an  operator() defined.  This not only makes
  algorithmic templates  work  with  pointers  to  functions,  but  also
  enables them to work with arbitrary function objects.

  Header <functional> synopsis

  namespace std {
    // _lib.base_, base:
    template <class Arg, class Result> struct unary_function;
    template <class Arg1, class Arg2, class Result> struct binary_function;
    // _lib.arithmetic.operations_, arithmetic operations:
    template <class T> struct plus;
    template <class T> struct minus;
    template <class T> struct multiplies;
    template <class T> struct divides;
    template <class T> struct modulus;
    template <class T> struct negate;

    // _lib.comparisons_, comparisons:
    template <class T> struct equal_to;
    template <class T> struct not_equal_to;
    template <class T> struct greater;
    template <class T> struct less;
    template <class T> struct greater_equal;
    template <class T> struct less_equal;
    // _lib.logical.operations_, logical operations:
    template <class T> struct logical_and;
    template <class T> struct logical_or;
    template <class T> struct logical_not;
    // _lib.negators_, negators:
    template <class Predicate> struct unary_negate;
    template <class Predicate>
      unary_negate<Predicate>  not1(const Predicate&);
    template <class Predicate> struct binary_negate;
    template <class Predicate>
      binary_negate<Predicate> not2(const Predicate&);
    // _lib.binders_, binders:
    template <class Operation>  class binder1st;
    template <class Operation, class T>
      binder1st<Operation> bind1st(const Operation&, const T&);
    template <class Operation> class binder2nd;
    template <class Operation, class T>
      binder2nd<Operation> bind2nd(const Operation&, const T&);
    // _lib.function.pointer.adaptors_, adaptors:
    template <class Arg, class Result> class pointer_to_unary_function;
    template <class Arg, class Result>
      pointer_to_unary_function<Arg,Result> ptr_fun(Result (*)(Arg));
    template <class Arg1, class Arg2, class Result>
      class pointer_to_binary_function;
    template <class Arg1, class Arg2, class Result>
      pointer_to_binary_function<Arg1,Arg2,Result> ptr_fun(Result (*)(Arg1,Arg2));
    // _lib.member.pointer.adaptors_, adaptors:
    template<class S, class T> class mem_fun_t;
    template<class S, class T, class A> class mem_fun1_t;
    template<class S, class T>
        mem_fun_t<S,T> mem_fun(S (T::*f)());
    template<class S, class T, class A>
        mem_fun1_t<S,T,A> mem_fun1(S (T::*f)(A));
    template<class S, class T> class mem_fun_ref_t;
    template<class S, class T, class A> class mem_fun1_ref_t;
    template<class S, class T>
        mem_fun_ref_t<S,T> mem_fun_ref(S (T::*f)());
    template<class S, class T, class A>
        mem_fun1_ref_t<S,T,A> mem_fun1_ref(S (T::*f)(A));
  }

2 Using  function objects together with function templates increases the
  expressive power of the library as well as making the  resulting  code
  much more efficient.

3 [Example:  If a C++ program wants to have a by-element addition of two
  vectors a and b containing double and put the result into  a,  it  can

  do:
    transform(a.begin(), a.end(), b.begin(), a.begin(), plus<double>());
   --end example]

4 [Example: To negate every element of a:
    transform(a.begin(), a.end(), a.begin(), negate<double>());
  The corresponding functions will inline the addition and the negation.
   --end example]

5 To enable adaptors and other components to manipulate function objects
  that  take  one  or two arguments it is required that they correspond-
  ingly provide typedefs  argument_type  and  result_type  for  function
  objects  that  take one argument and first_argument_type, second_argu-
  ment_type, and result_type for function objects that  take  two  argu-
  ments.

  20.3.1  Base                                                [lib.base]

1 The  following  classes  are  provided to simplify the typedefs of the
  argument and result types:
    template <class Arg, class Result>
    struct unary_function {
      typedef Arg    argument_type;
      typedef Result result_type;
    };
    template <class Arg1, class Arg2, class Result>
    struct binary_function {
      typedef Arg1   first_argument_type;
      typedef Arg2   second_argument_type;
      typedef Result result_type;
    };

  20.3.2  Arithmetic operations              [lib.arithmetic.operations]

1 The library provides basic function object  classes  for  all  of  the
  arithmetic operators in the language (_expr.mul_, _expr.add_).

  template <class T> struct plus : binary_function<T,T,T> {
    T operator()(const T& x, const T& y) const;
  };

2 operator() returns x + y.

  template <class T> struct minus : binary_function<T,T,T> {
    T operator()(const T& x, const T& y) const;
  };

3 operator() returns x - y.

  template <class T> struct multiplies : binary_function<T,T,T> {
    T operator()(const T& x, const T& y) const;
  };

4 operator() returns x * y.

  template <class T> struct divides : binary_function<T,T,T> {
    T operator()(const T& x, const T& y) const;
  };

5 operator() returns x / y.

  template <class T> struct modulus : binary_function<T,T,T> {
    T operator()(const T& x, const T& y) const;
  };

6 operator() returns x % y.

  template <class T> struct negate : unary_function<T,T> {
    T operator()(const T& x) const;
  };

7 operator() returns -x.

  20.3.3  Comparisons                                  [lib.comparisons]

1 The library provides basic function object classes for all of the com-
  parison operators in the language (_expr.rel_, _expr.eq_).

  template <class T> struct equal_to : binary_function<T,T,bool> {
    bool operator()(const T& x, const T& y) const;
  };

2 operator() returns x == y.

  template <class T> struct not_equal_to : binary_function<T,T,bool> {
    bool operator()(const T& x, const T& y) const;
  };

3 operator() returns x != y.

  template <class T> struct greater : binary_function<T,T,bool> {
    bool operator()(const T& x, const T& y) const;
  };

4 operator() returns x > y.

  template <class T> struct less : binary_function<T,T,bool> {
    bool operator()(const T& x, const T& y) const;
  };

5 operator() returns x < y.

  template <class T> struct greater_equal : binary_function<T,T,bool> {
    bool operator()(const T& x, const T& y) const;
  };

6 operator() returns x >= y.

  template <class T> struct less_equal : binary_function<T,T,bool> {
    bool operator()(const T& x, const T& y) const;
  };

7 operator() returns x <= y.

8 For templates greater, less, greater_equal, and less_equal,  the  spe-
  cializations  for  any  pointer  type yield a total order, even if the
  built-in operators <, >, <=, >= do not.

  20.3.4  Logical operations                    [lib.logical.operations]

1 The library provides basic function object classes for all of the log-
  ical   operators   in  the  language  (_expr.log.and_,  _expr.log.or_,
  _expr.unary.op_).

  template <class T> struct logical_and : binary_function<T,T,bool> {
    bool operator()(const T& x, const T& y) const;
  };

2 operator() returns x && y.

  template <class T> struct logical_or : binary_function<T,T,bool> {
    bool operator()(const T& x, const T& y) const;
  };

3 operator() returns x || y.

  template <class T> struct logical_not : unary_function<T,bool> {
    bool operator()(const T& x) const;
  };

4 operator() returns !x.

  20.3.5  Negators                                        [lib.negators]

1 Negators not1 and not2 take a unary and a  binary  predicate,  respec-
  tively, and return their complements (_expr.unary.op_).

  template <class Predicate>
    class unary_negate
      : public unary_function<typename Predicate::argument_type,bool> {
  public:
    explicit unary_negate(const Predicate& pred);
    bool operator()(const argument_type& x) const;
  };

2 operator() returns !pred(x).

  template <class Predicate>
    unary_negate<Predicate> not1(const Predicate& pred);

  Returns:
    unary_negate<Predicate>(pred).

  template <class Predicate>
    class binary_negate
      : public binary_function<typename Predicate::first_argument_type,
                               typename Predicate::second_argument_type, bool> {
    public:
      explicit binary_negate(const Predicate& pred);
      bool operator()(const first_argument_type&  x,
                      const second_argument_type& y) const;
    };

3 operator() returns !pred(x,y).

  template <class Predicate>
    binary_negate<Predicate> not2(const Predicate& pred);

  Returns:
    binary_negate<Predicate>(pred).

  20.3.6  Binders                                          [lib.binders]

1 Binders  bind1st and bind2nd take a function object f of two arguments
  and a value x and return a function object of one argument constructed
  out of f with the first or second argument correspondingly bound to x.

  20.3.6.1  Template class binder1st                    [lib.binder.1st]
    template <class Operation>
    class binder1st
      : public unary_function<typename Operation::second_argument_type,
                              typename Operation::result_type> {
    protected:
      Operation                      op;
      typename Operation::first_argument_type value;
    public:
      binder1st(const Operation& x, const typename Operation::first_argument_type& y);
      result_type operator()(const argument_type& x) const;
    };

1 The constructor initializes op with x and value with y.

2 operator() returns op(value,x).

  20.3.6.2  bind1st                                       [lib.bind.1st]

  template <class Operation, class T>
    binder1st<Operation> bind1st(const Operation& op, const T& x);

  Returns:
    binder1st<Operation>(op,       typename       Operation::first_argu-
    ment_type(x)).

  20.3.6.3  Template class binder2nd                    [lib.binder.2nd]
    template <class Operation>
    class binder2nd
      : public unary_function<typename Operation::first_argument_type,
                              typename Operation::result_type> {
    protected:
      Operation                       op;
      typename Operation::second_argument_type value;
    public:
      binder2nd(const Operation& x, const typename Operation::second_argument_type& y);
      result_type operator()(const argument_type& x) const;
    };

1 The constructor initializes op with x and value with y.

2 operator() returns op(x,value).

  20.3.6.4  bind2nd                                       [lib.bind.2nd]

  template <class Operation, class T>
    binder2nd<Operation> bind2nd(const Operation& op, const T& x);

  Returns:
    binder2nd<Operation>(op,       typename      Operation::second_argu-
    ment_type(x)).

1 [Example:
    find_if(v.begin(), v.end(), bind2nd(greater<int>(), 5));
  finds the first integer in vector v greater than 5;
    find_if(v.begin(), v.end(), bind1st(greater<int>(), 5));
  finds the first integer in v less than 5.   --end example]

  20.3.7  Adaptors for pointers to       [lib.function.pointer.adaptors]
       functions

1 To  allow  pointers to (unary and binary) functions to work with func-
  tion adaptors the library provides:
    template <class Arg, class Result>
    class pointer_to_unary_function : public unary_function<Arg, Result> {
    public:
      explicit pointer_to_unary_function(Result (*f)(Arg));
      Result operator()(Arg x) const;
    };

2 operator() returns f(x).

  template <class Arg, class Result>
    pointer_to_unary_function<Arg, Result> ptr_fun(Result (*f)(Arg));

  Returns:
    pointer_to_unary_function<Arg, Result>(f).
        template <class Arg1, class Arg2, class Result>
        class pointer_to_binary_function : public binary_function<Arg1,Arg2,Result> {
        public:
          explicit pointer_to_binary_function(Result (*f)(Arg1, Arg2));
          Result operator()(Arg1 x, Arg2 y) const;
        };

3 operator() returns f(x,y).

  template <class Arg1, class Arg2, class Result>
    pointer_to_binary_function<Arg1,Arg2,Result>
      ptr_fun(Result (*f)(Arg1, Arg2));

  Returns:
    pointer_to_binary_function<Arg1,Arg2,Result>(f).

4 [Example:
      replace_if(v.begin(), v.end(), not1(bind2nd(ptr_fun(strcmp), "C")), "C++");
  replaces each C with C++ in sequence v.2)  --end example]

  20.3.8  Adaptors for pointers to         [lib.member.pointer.adaptors]
       members

1 The purpose of the following is to provide  the  same  facilities  for
  pointer  to  members  as  those  provided for pointers to functions in
  _lib.function.pointer.adaptors_.
    template <class S, class T> class mem_fun_t
          : public unary_function<T*, S> {
    public:
      explicit mem_fun_t(S (T::*p)());
      S operator()(T* p) const;
  };

2 mem_fun_t calls the member function it is  initialized  with  given  a
  pointer argument.
    template <class S, class T, class A> class mem_fun1_t
          : public binary_function<T*, A, S> {
    public:
      explicit mem_fun1_t(S (T::*p)(A));
      S operator()(T* p, A x) const;
  };

3 mem_fun1_t  calls  the  member function it is initialized with given a
  pointer argument and an additional argument of the appropriate type.
    template<class S, class T> mem_fun_t<S,T>
       mem_fun(S (T::*f)());
    template<class S, class T, class A> mem_fun1_t<S,T,A>
       mem_fun1(S (T::*f)(A));

4 mem_fun(&X::f) returns an object through  which  X::f  can  be  called
  given  a  pointer  to an X followed by the argument required for f (if
  any).
    template <class S, class T> class mem_fun_ref_t
          : public unary_function<T, S> {
    public:
      explicit mem_fun_ref_t(S (T::*p)());
      S operator()(T& p) const;
  };

5 mem_fun_ref_t calls the member function it is initialized with given a
  reference argument.

  _________________________
  2) Implementations that have multiple pointer to function  types  pro-
  vide additional ptr_fun template functions.

    template <class S, class T, class A> class mem_fun1_ref_t
          : public binary_function<T, A, S> {
    public:
      explicit mem_fun1_ref_t(S (T::*p)(A));
      S operator()(T& p, A x) const;
  };

6 mem_fun1_ref_t  calls the member function it is initialized with given
  a reference argument and an additional  argument  of  the  appropriate
  type.
    template<class S, class T> mem_fun_ref_t<S,T>
       mem_fun_ref(S (T::*f)());
    template<class S, class T, class A> mem_fun1_ref_t<S,T,A>
       mem_fun1_ref(S (T::*f)(A));

7 mem_fun_ref(&X::f)  returns an object through which X::f can be called
  given a reference to an X followed by the argument required for f  (if
  any).

  20.4  Memory                                              [lib.memory]

  Header <memory> synopsis

  namespace std {
    // _lib.default.allocator_, the default allocator:
    template <class T> class allocator;
    template <> class allocator<void>;
    template <class T, class U>
      bool operator==(const allocator<T>&, const allocator<U>&) throw();
    template <class T, class U>
      bool operator!=(const allocator<T>&, const allocator<U>&) throw();
    // _lib.storage.iterator_, raw storage iterator:
    template <class OutputIterator, class T> class raw_storage_iterator;
    // _lib.temporary.buffer_, temporary buffers:
    template <class T>
      pair<T*,ptrdiff_t> get_temporary_buffer(ptrdiff_t n);
    template <class T>
      void return_temporary_buffer(T* p);
    // _lib.specialized.algorithms_, specialized algorithms:
    template <class InputIterator, class ForwardIterator>
      ForwardIterator
        uninitialized_copy(InputIterator first, InputIterator last,
                           ForwardIterator result);
    template <class ForwardIterator, class T>
      void uninitialized_fill(ForwardIterator first, ForwardIterator last,
                              const T& x);
    template <class ForwardIterator, class Size, class T>
      void uninitialized_fill_n(ForwardIterator first, Size n, const T& x);
    // _lib.auto.ptr_, pointers:
    template<class X> class auto_ptr;
  }

  20.4.1  The default allocator                  [lib.default.allocator]
  namespace std {
    template <class T> class allocator;
    // specialize for void:
    template <> class allocator<void> {
    public:
      typedef void*       pointer;
      typedef const void* const_pointer;
      // reference-to-void members are impossible.
      typedef void  value_type;
      template <class U> struct rebind { typedef allocator<U> other; };
    };
    template <class T> class allocator {
     public:
      typedef size_t    size_type;
      typedef ptrdiff_t difference_type;
      typedef T*        pointer;
      typedef const T*  const_pointer;
      typedef T&        reference;
      typedef const T&  const_reference;
      typedef T         value_type;
      template <class U> struct rebind { typedef allocator<U> other; };
      allocator() throw();
      allocator(const allocator&) throw();
      template <class U> allocator(const allocator<U>&) throw();
     ~allocator() throw();
      pointer address(reference x) const;
      const_pointer address(const_reference x) const;
      pointer allocate(
        size_type, typename allocator<void>::const_pointer hint = 0);
      void deallocate(pointer p, size_type n);
      size_type max_size() const throw();
      void construct(pointer p, const T& val);
      void destroy(pointer p);
    };
  }

  20.4.1.1  allocator members                    [lib.allocator.members]

  pointer address(reference x) const;

  Returns:
    &x.

  const_pointer address(const_reference x) const;

  Returns:
    &x.

  pointer allocate(size_type n, allocator<void>::const_pointer hint=0);

  Notes:
    Uses ::operator new(size_t) (_lib.new.delete_).
  Requires:
    hint  either  0  or previously obtained from member allocate and not
    yet passed to member deallocate.  The value hint may be used  by  an
    implementation to help improve performance3).
  Returns:
    a pointer to the initial element of an array of storage of size n  *
    sizeof(T), aligned appropriately for objects of type T.
  Note:
    the storage is obtained by calling ::operator new(size_t), but it is
    unspecified when or how often this function is called.  The  use  of
    hint is unspecified, but intended as an aid to locality if an imple-
    mentation so desires.
  Throws:
    bad_alloc if the storage cannot be obtained.

  void deallocate(pointer p, size_type n);

  Requires:
    p shall be a pointer value obtained from allocate().  n shall  equal
    the value passed as the first argument to the invocation of allocate
    which returned p.
  Effects:
    Deallocates the storage referenced by p.
  Notes:
    Uses ::operator delete(void*) (_lib.new.delete_), but it is unspeci-
    fied when this function is called.

  size_type max_size() const throw();

  Returns:
    the  largest value N for which the call allocate(N,0) might succeed.

  void construct(pointer p, const_reference val);

  Returns:
    new((void *)p) T(val)

  void destroy(pointer p);

  Returns:
    ((T*)p)->~T()

  _________________________
  3)  In a container member function, the address of an adjacent element
  is often a good choice to pass for this argument.

  20.4.1.2  allocator globals                    [lib.allocator.globals]

  template <class T1, class T2>
    bool operator==(const allocator<T1>&, const allocator<T2>&) throw();

  Returns:
    true.

  template <class T1, class T2>
    bool operator!=(const allocator<T1>&, const allocator<T2>&) throw();

  Returns:
    false.

  20.4.2  Raw storage iterator                    [lib.storage.iterator]

1 raw_storage_iterator is provided to enable  algorithms  to  store  the
  results into uninitialized memory.  The formal template parameter Out-
  putIterator is required to have its operator*  return  an  object  for
  which  operator&  is  defined  and returns a pointer to T, and is also
  required to satisfy the requirements of an output iterator  (_lib.out-
  put.iterators_).
  namespace std {
    template <class OutputIterator, class T>
    class raw_storage_iterator
      : public iterator<output_iterator_tag,void,void,void,void> {
    public:
      explicit raw_storage_iterator(OutputIterator x);
      raw_storage_iterator<OutputIterator,T>& operator*();
      raw_storage_iterator<OutputIterator,T>& operator=(const T& element);
      raw_storage_iterator<OutputIterator,T>& operator++();
      raw_storage_iterator<OutputIterator,T>  operator++(int);
    };
  }

  raw_storage_iterator(OutputIterator x);

  Effects:
    Initializes  the  iterator  to  point  to  the same value to which x
    points.

  raw_storage_iterator<OutputIterator,T>& operator*();

  Returns:
    *this

  raw_storage_iterator<OutputIterator,T>& operator=(const T& element);

  Effects:
    Constructs a value from element at the location to which the  itera-
    tor points.
  Returns:
    A reference to the iterator.

  raw_storage_iterator<OutputIterator,T>& operator++();

  Effects:
    Pre-increment:  advances the iterator and returns a reference to the
    updated iterator.

  raw_storage_iterator<OutputIterator,T> operator++(int);

  Effects:
    Post-increment:  advances the iterator and returns the old value  of
    the iterator.

  20.4.3  Temporary buffers                       [lib.temporary.buffer]

  template <class T>
    pair<T*, ptrdiff_t> get_temporary_buffer(ptrdiff_t n);

  Effects:
    Obtains  a pointer to storage sufficient to store up to n adjacent T
    objects.
  Returns:
    A pair containing the buffer's address and capacity (in the units of
    sizeof(T)), or a pair of 0 values if no storage can be obtained.

  template <class T> void return_temporary_buffer(T* p);

  Effects:
    Deallocates the buffer to which p points.
  Requires:
    The  buffer  shall  have  been  previously  allocated  by get_tempo-
    rary_buffer.

  20.4.4  Specialized algorithms            [lib.specialized.algorithms]

1 All the iterators that are used as formal template parameters  in  the
  following  algorithms  are required to  have their operator* return an
  object for which operator& is defined and returns a pointer to T.   In
  the   algorithm  uninitialized_copy,  the  formal  template  parameter
  InputIterator is required to satisfy  the  requirements  of  an  input
  iterator (_lib.input.iterators_).  In all of the following algorithms,
  the formal template parameter ForwardIterator is required  to  satisfy
  the  requirements  of a forward iterator (_lib.forward.iterators_) and
  also   to   satisfy   the   requirements   of   a   mutable   iterator

  (_lib.iterator.requirements_),  and  is  required to have the property
  that no exceptions are thrown from increment, assignment,  comparison,
  or dereference of valid iterators.  In the following algorithms, if an
  exception is thrown there are no effects.

  20.4.4.1  uninitialized_copy                  [lib.uninitialized.copy]

  template <class InputIterator, class ForwardIterator>
    ForwardIterator
      uninitialized_copy(InputIterator first, InputIterator last,
                         ForwardIterator result);

  Effects:

  for (; first != last; ++result, ++first)
      new (static_cast<void*>(&*result))
              typename iterator_traits<ForwardIterator::value_type(*first);

  Returns:
    result

  20.4.4.2  uninitialized_fill                  [lib.uninitialized.fill]

  template <class ForwardIterator, class T>
    void uninitialized_fill(ForwardIterator first, ForwardIterator last,
                            const T& x);

  Effects:

  for (; first != last; ++first)
      new (static_cast<void*>(&*first))
              typename iterator_traits<ForwardIterator::value_type(x);

  20.4.4.3  uninitialized_fill_n              [lib.uninitialized.fill.n]

  template <class ForwardIterator, class Size, class T>
    void uninitialized_fill_n(ForwardIterator first, Size n, const T& x);

  Effects:

  for (; n--; ++first)
      new (static_cast<void*>(&*first))
              typename iterator_traits<ForwardIterator::value_type(x);

  20.4.5  Template class auto_ptr                         [lib.auto.ptr]

1 Template auto_ptr stores a pointer to an object obtained via  new  and
  deletes  that object when it itself is destroyed (such as when leaving
  block scope _stmt.dcl_).
  namespace std {
    template<class X> class auto_ptr {
    public:
      typedef X element_type;
      // _lib.auto.ptr.cons_ construct/copy/destroy:
      explicit auto_ptr(X* p =0) throw();
      auto_ptr(const auto_ptr&) throw();
      template<class Y> auto_ptr(const auto_ptr<Y>&) throw();
      auto_ptr& operator=(const auto_ptr&) throw();
      template<class Y> auto_ptr& operator=(const auto_ptr<Y>&) throw();
     ~auto_ptr();
      // _lib.auto.ptr.members_ members:
      X& operator*() const throw();
      X* operator->() const throw();
      X* get() const throw();
      X* release() const throw();
    };
  }

2 The auto_ptr provides a semantics of strict ownership.  After  initial
  construction an auto_ptr owns the object it holds a pointer to.  Copy-
  ing an auto_ptr copies the pointer and transfers ownership to the des-
  tination.   If more than one auto_ptr owns the same object at the same
  time the behavior of the program is undefined.

  20.4.5.1  auto_ptr constructors                    [lib.auto.ptr.cons]

  explicit auto_ptr(X* p =0) throw();

  Postconditions:
    *this holds the pointer to p.  *this owns *get() if and only if p is
    not a null pointer.

  auto_ptr(const auto_ptr& a) throw();

  Effects:
    Calls a.release().
  Postconditions:
    *this  holds  the  pointer  returned  from  a.release().  *this owns
    *get() if and only if a owned *a on entry.

  template<class Y> auto_ptr(const auto_ptr<Y>& a) throw();

  Requires:
    Y* can be implicitly converted to X*.

  Effects:
    Calls a.release().
  Postconditions:
    *this holds the  pointer  returned  from  a.release().   *this  owns
    *get() if and only if a owned *a on entry.

  auto_ptr& operator=(const auto_ptr& a) throw();

  Requires:
    The expression delete get() is well formed.
  Effects:
    If  *this  is the same object as a there are no effects.  Otherwise,
    call a.release(), and if *this owns *get() then delete get().
  Returns:
    *this.
  Postconditions:
    If *this is not the same object as a then *this  holds  the  pointer
    returned from a.release().  *this owns *get() if and only if a owned
    *a on entry.

  template<class Y> auto_ptr& operator=(const auto_ptr<Y>& a) throw();

  Requires:
    Y* can be implicitly converted to X*.  The expression  delete  get()
    is well formed.
  Effects:
    If  *this  is the same object as a there are no effects.  Otherwise,
    call a.release(), and if *this owns *get() then delete get().
  Returns:
    *this.
  Postconditions:
    If *this is not the same object as a then *this  holds  the  pointer
    returned from a.release().  *this owns *get() if and only if a owned
    *a on entry.

  ~auto_ptr();

  Requires:
    The expression delete get() is well formed.
  Effects:
    If *this owns *get() then delete get().

  20.4.5.2  auto_ptr members                      [lib.auto.ptr.members]

  X& operator*() const throw();

  Requires:
    get() != 0

  Returns:
    *get()

  X* operator->() const throw();

  Returns:
    get()

  X* get() const throw();

  Returns:
    The pointer *this holds.

  X* release() const throw();

  Returns:
    get()
  Postcondition:
    *this is not the owner of *get().

  20.4.6  C Library                                       [lib.c.malloc]

1 Header <cstdlib> (Table 7):

                    Table 7--Header <cstdlib> synopsis

                     +------------------------------+
                     |   Type          Name(s)      |
                     +------------------------------+
                     |Functions:   calloc   malloc  |
                     |             free     realloc |
                     +------------------------------+

2 The contents are the same as the Standard C library header <stdlib.h>,
  with the following changes:

3 The  functions  calloc(),  malloc(),  and  realloc() do not attempt to
  allocate storage by calling ::operator new()  (_lib.support.dynamic_).

4 The  function free() does not attempt to deallocate storage by calling
  ::operator delete().

  SEE ALSO: ISO C clause 7.11.2.

5 Header <cstring> (Table 8):

                    Table 8--Header <cstring> synopsis

                     +------------------------------+
                     |   Type          Name(s)      |
                     +------------------------------+
                     |Macro:       NULL             |
                     +------------------------------+
                     |Type:        size_t           |
                     +------------------------------+
                     |Functions:   memchr    memcmp |
                     |memcpy       memmove   memset |
                     +------------------------------+

6 The contents are the same as the Standard C library header <string.h>,
  with the change to memchr() specified in _lib.c.strings_.

  SEE ALSO: ISO C clause 7.11.2.

  20.5  Date and time                                    [lib.date.time]

1 Header <ctime> (Table 9):

                     Table 9--Header <ctime> synopsis

           +---------------------------------------------------+
           | Type                     Name(s)                  |
           +---------------------------------------------------+
           |Macros:   NULL                                     |
           +---------------------------------------------------+
           |Types:    size_t   clock_t    time_t               |
           +---------------------------------------------------+
           |Struct:   tm                                       |
           +---------------------------------------------------+
           |Functions:                                         |
           |asctime   clock    difftime   localtime   strftime |
           |ctime     gmtime   mktime     time                 |
           +---------------------------------------------------+

2 The contents are the same as the Standard C library header <time.h>.

  SEE ALSO: ISO C clause 7.12, Amendment 1 clause 4.6.4.