______________________________________________________________________

  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 subclauses describe allocator requirements, utility com­
  ponents,  function  objects,  dynamic memory management utilities, and
  date/time utilities, as summarized in Table 1:

                Table 1--General utilities library summary

   +-------------------------------------------------------------------+
   |                     Subclause                         Header(s)   |
   +-------------------------------------------------------------------+
   |_lib.allocator.requirements_ Allocator 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  Allocator requirements              [lib.allocator.requirements]

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

2 In the following Table 2, X denotes an allocator class for objects  of
  type  T,  a  denotes  a  value  of  X,  n  denotes an instance of type
  X::size_type, p denotes an  instance  of  type  X::pointer  which  was
  obtained from X.

3 All the operations on the allocators are expected to be amortized con­
  stant time.

                     Table 2--Allocator requirements

  +------------------------------------------------------------------------------+
  |    expression             return type                 assertion/note         |
  |                                                     pre/post-condition       |
  +------------------------------------------------------------------------------+
  |X::value_type        T                                                        |
  +------------------------------------------------------------------------------+
  |X::pointer           pointer to T              the result of operator* of     |
  |                                               values of X::pointer is of     |
  |                                               reference.                     |
  +------------------------------------------------------------------------------+
  |X::const_pointer     pointer to const T type   the result of operator* of     |
  |                                               values of X::const_pointer is  |
  |                                               of const reference; it is the  |
  |                                               same type of pointer as        |
  |                                               X::pointer, in particular,     |
  |                                               sizeof(X::const_pointer) ==    |
  |                                               sizeof(X::pointer).            |
  +------------------------------------------------------------------------------+
  |X::size_type         unsigned integral type    the type that can represent    |
  |                                               the size of the largest object |
  |                                               in the memory model.           |
  +------------------------------------------------------------------------------+
  |X::difference_type   signed integral type      the type that can represent    |
  |                                               the difference between any two |
  |                                               pointers in the memory model.  |
  +------------------------------------------------------------------------------+
  |X a;                                           note: a destructor is assumed. |
  +------------------------------------------------------------------------------+
  |a.allocate(n)        X::pointer                memory is allocated for n ob­  |
  |                                               jects of type T but objects    |
  |                                               are not constructed. allocate  |
  |                                               may raise an appropriate ex­   |
  |                                               ception.                       |
  +------------------------------------------------------------------------------+
  |a.deallocate(p)      result is not used        all the objects in the area    |
  |                                               pointed by p should be de­     |
  |                                               stroyed prior to the call of   |
  |                                               the deallocate.                |
  +------------------------------------------------------------------------------+
  |a.max_size()         X::size_type              the largest positive value of  |
  |                                               X::difference_type.            |
  +------------------------------------------------------------------------------+

  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.

  Header <utility> synopsis

  namespace std {
  // subclause _lib.operators_, operators:
    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&);
  // subclause _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> 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);

  Returns:
    !(x == y).

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

  Returns:
    y < x.

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

  Returns:
    !(y < x).

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

  Returns:
    !(x < y).

  20.2.2  Pairs                                              [lib.pairs]

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

  template <class T1, class T2>
  struct pair {
    T1 first;
    T2 second;
    pair(const T1& x, const T2& y);
  };

2 The constructor initializes first with x and second with y.

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

3 [Example: Instead of writing,
    return pair<int, double>(5, 3.1415926); // explicit types
  a C++ program may write:
    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 (_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 {
  // subclause _lib.base_, base:
    template <class Arg, class Result> struct unary_function;
    template <class Arg1, class Arg2, class Result> struct binary_function;

  // subclause _lib.arithmetic.operations_, arithmetic operations:
    template <class T> struct plus;
    template <class T> struct minus;
    template <class T> struct times;
    template <class T> struct divides;
    template <class T> struct modulus;
    template <class T> struct negate;
  // subclause _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;
  // subclause _lib.logical.operations_, logical operations:
    template <class T> struct logical_and;
    template <class T> struct logical_or;
    template <class T> struct logical_not;
  // subclause _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&);
  // subclause _lib.binders_, binders:
    template <class Operation>  struct 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&);
  // subclause _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));
  }

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,  sec­
  ond_argument_type, and result_type for function objects that take  two
  arguments.

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

  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<Predicate::argument_type,bool> {
  public:
    explicit unary_negate(const Predicate& pred);
    bool operator()(const argument_type& x) const;
  };

  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<Predicate::first_argument_type,
                               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;
    };

2 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<Operation::second_argument_type,
                              Operation::result_type> {
    protected:
      Operation     op;
      argument_type value;
    public:
      binder1st(const Operation& x, const 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, Operation::first_argument_type(x)).

  20.3.6.3  Template class binder2nd                    [lib.binder.2nd]
    template <class Operation>
    class binder2nd
      : public unary_function<Operation::first_argument_type,
                              Operation::result_type> {
    protected:
      Operation     op;
      argument_type value;
    public:
      binder2nd(const Operation& x, const 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, Operation::second_argument_type(x)).

1 [Example:
    find(v.begin(), v.end(), bind2nd(greater<int>(), 5));
  finds the first integer in vector v greater than 5;
    find(v.begin(), v.end(), bind1st(greater<int>(), 5));
  finds the first integer in v not greater 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()(const 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()(const Arg1& x, const 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.1)  --end example]

  _________________________
  1) Implementations that have multiple pointer to function types  shall
  provide additional ptr_fun template functions.

  20.4  Memory                                              [lib.memory]

  Header <memory> synopsis

  #include <cstddef>      // for size_t, ptrdiff_t
  #include <iterator>     // for output_iterator
  #include <utility>      // for pair

  namespace std {
  // subclause _lib.default.allocator_, the default allocator:
    class allocator;
    class allocator::types<void>;
    void* operator new(size_t N, allocator& a);
  // subclause _lib.storage.iterator_, raw storage iterator:
    template <class OutputIterator, class T> class raw_storage_iterator;
  // subclause _lib.memory.primitives_, memory handling primitives:
    template <class T> T*   allocate(ptrdiff_t n, T*);
    template <class T> void deallocate(T* buffer);
    template <class T1, class T2> void construct(T1* p, const T2& value);
    template <class T>            void destroy(T* pointer);
    template <class ForwardIterator>
      void destroy(ForwardIterator first, ForwardIterator last);
    template <class T>
      pair<T*,ptrdiff_t> get_temporary_buffer(ptrdiff_t n, T*);
    template <class T> void return_temporary_buffer(T* p, T*);
  // subclause _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);
  // subclause _lib.auto.ptr_, pointers:
    template<class X> class auto_ptr;
  }

  20.4.1  The default allocator                  [lib.default.allocator]
  namespace std {
    class allocator {
    public:
      typedef size_t    size_type;
      typedef ptrdiff_t difference_type;
      template <class T> class types {
        typedef T*        pointer;
        typedef const T*  const_pointer;
        typedef T&        reference;
        typedef const T&  const_reference;
        typedef T         value_type;
      };
      allocator();
     ~allocator();

      template<class T> typename types<T>::pointer
        address(types<T>::reference x) const;
      template<class T> typename types<T>::const_pointer
        address(types<T>::const_reference x) const;
      template<class T, class U> typename types<T>::pointer
        allocate(size_type, types<U>::const_pointer hint);
      template<class T> void deallocate(types<T>::pointer p);
      size_type max_size() const;
    };
    class allocator::types<void> {  // specialization
    public:
      typedef void* pointer;
      typedef void  value_type;
    };
    void* operator new(size_t N, allocator& a);
  }

1 The  members  allocate()  and  deallocate() are parameterized to allow
  them to be specialized for particular types in user allocators.2)

2 It  is  assumed that any pointer types have a (possibly lossy) conver­
  sion to void*, yielding a pointer sufficient for use as the this value
  in    a    constructor    or    destructor,    and    conversions   to
  A::types<void>::pointer (for  appropriate  A)  as  well,  for  use  by
  A::deallocate().

  20.4.1.1  allocator members                    [lib.allocator.members]

  template<class T> typename types<T>::pointer
    address(typename types<T>::reference x) const;

  Returns:
    &x.

  template<class T> typename types<T>::const_pointer
    address(typename types<T>::const_reference x) const;

  Returns:
    &x.

  template<class T, class U>
    typename types<T>::pointer
      allocate(size_type n, typename types<U>::const_pointer hint);

  Notes:
    Uses ::operator new(size_t) (_lib.new.delete_).
  _________________________
  2) In implementation is expected to provide allocators  for  all  sup­
  ported memory models.

  +-------                 BEGIN BOX 1                -------+
  TBS:   using hint should be documented as unspecified, but intended as
  an aid to locality if an implementation can use it so.
  +-------                  END BOX 1                 -------+

  Returns:
    new T, if n  == 1.  Returns new T[n], if n  > 1.

  +-------                 BEGIN BOX 2                -------+
  ISSUE: Is this right?  How does deallocate() know which form of delete
  to use?
  +-------                  END BOX 2                 -------+

  template<class T> void deallocate(typename types<T>::pointer p);

  Requires:
    p shall be a pointer value obtained from allocate().
  Effects:
    Deallocates the storage referenced by p.
  Notes:
    Uses ::operator delete(void*) (_lib.new.delete_).

  size_type max_size() const;

  Returns:

  +-------                 BEGIN BOX 3                -------+
  TBS
  +-------                  END BOX 3                 -------+

  20.4.1.2  allocator placement new            [lib.allocator.placement]

  void* operator new(size_t N, allocator& a);

  Returns:
    a.allocate<char,void>(N,0).

  20.4.1.3  Example allocator                    [lib.allocator.example]

1 [Example:  For  example,  here  is an allocator that allows objects in
  main memory, shared memory, or  private  heaps.   Notably,  with  this
  allocator  such  objects  stored  under different disciplines have the
  same type; this is not necessarily the case for other allocators.

    #include <memory>     // for allocator
    class runtime_allocator : public std::allocator {
      class impl {
        impl();
        virtual ~impl();

        virtual void* allocate(size_t)  =0;
        virtual void  deallocate(void*) =0;
        friend class runtime_allocator
        // ... etc. (including a reference count)
      };

      impl* impl_;  // the actual storage manager

    protected:
      runtime_allocator(runtime_allocator::impl* i);
     ~runtime_allocator();

    public:
      void* allocate(size_t n) { return impl_->allocate(n); }
      template<class T> void deallocate(T* p) { impl_->deallocate(p); }
    };

    inline void* operator new(size_t N, runtime_allocator& a)
      { return a.allocate(N); }
    class shared_allocator : public runtime_allocator {

      class shared_impl : runtime_allocator::impl {
        shared_impl(void* region);
        virtual ~shared_impl();
        virtual void* allocate(size_t);
        virtual void  deallocate(void*);
      };

      shared_allocator(void* region) : runtime_allocator(new shared_impl(region)) {}
     ~shared_allocator() {}
    };
    class heap : public runtime_allocator {

      class heap_impl : runtime_allocator::impl {
        heap_impl();
        virtual ~heap_impl();
        virtual void* allocate(size_t);
        virtual void  deallocate(void*);
      };

      heap_allocator() : runtime_allocator(new heap_impl) {}
     ~heap_allocator() {}
    };
   --end example]

  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.
  namespace std {
    template <class OutputIterator, class T>
    class raw_storage_iterator : public output_iterator {
    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:
    A reference to the value to which the iterator points.

  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  Memory handling primitives             [lib.memory.primitives]

  +-------                 BEGIN BOX 4                -------+
  ISSUE:  Is  there  anything going on here with allocate and deallocate
  that can't be handled by operator new and operator delete  and/or  the
  default allocator?
  +-------                  END BOX 4                 -------+

  20.4.3.1  allocate                                      [lib.allocate]

1 To obtain a typed pointer to an uninitialized memory buffer of a given
  size the following function is defined:

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

  Requires:
    n shall be >= 0.
  Effects:
    The size (in  bytes)  of  the  allocated  buffer  is  no  less  than
    n*sizeof(T).3)

  20.4.3.2  deallocate                                  [lib.deallocate]

1 Also, the following functions are provided:

  template <class T> void deallocate(T* buffer);

  +-------                 BEGIN BOX 5                -------+
  TBS
  +-------                  END BOX 5                 -------+

  20.4.3.3  construct                                    [lib.construct]

  template <class T1, class T2> void construct(T1* p, const T2& value);

  _________________________
  3)  For  every memory model there is a corresponding allocate template
  function defined with the first  argument type being the distance type
  of  the  pointers  in the memory model.  For example, if a compilation
  system supports huge pointers with the distance type being long  long,
  the following template function is provided:
    template <class T> T huge* allocate(long long n, T*);
  For  every  memory model there are corresponding deallocate, construct
  and destroy template functions defined with the  first  argument  type
  being the pointer type of the memory model.

  Effects:
    Initializes the location to which p points with value.

  20.4.3.4  destroy                                        [lib.destroy]

  template <class T> void destroy(T* pointer);

  Effects:
    Invokes the destructor for the value to which pointer points.

  template <class ForwardIterator>
    void destroy(ForwardIterator first, ForwardIterator last);

  Effects:
    Destroys all the values in the range [first,last).

  20.4.3.5  Temporary buffers                     [lib.temporary.buffer]

  +-------                 BEGIN BOX 6                -------+
  ISSUE:  Is  there something here that cannot be done with operator new
  and operator delete?
  +-------                  END BOX 6                 -------+

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

  Effects:
    Finds the largest buffer not greater than n*sizeof(T)
  Returns:
    A pair containing the buffer's address and capacity (in the units of
    sizeof(T)).4)

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

  Effects:
    Returns the buffer to which p points.
  Requires:
    The    buffer    shall    have    been   previously   allocated   by
    get_temporary_buffer.

  _________________________
  4) For every  memory model that an implementation supports, there is a
  corresponding get_temporary_buffer template function defined which  is
  overloaded on the corresponding signed integral type.  For example, if
  a system  supports huge pointers and their difference is of type  long
  long, the following function has to be provided:
    template <class T>
      pair<T huge *, long long> get_temporary_buffer(long long n, T*);

  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.

  20.4.4.1  uninitialized_copy                  [lib.uninitialized.copy]

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

  Effects:
    while (first != last) construct(&*result++, *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:
    while (first != last) construct(&*first++, x);

  20.4.4.3  uninitialized_fill                [lib.uninitialized.fill.n]

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

  Effects:
    while (n--) construct(&*first++, x);

  20.4.5  Template class auto_ptr                         [lib.auto.ptr]

1 Template auto_ptr holds onto a pointer 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:
    // _lib.auto.ptr.cons_ construct/copy/destroy:
      explicit auto_ptr(X* p =0);
      auto_ptr(auto_ptr&);
      void operator=(auto_ptr&);
     ~auto_ptr();

    // _lib.auto.ptr.members_ members:
      X& operator*() const;
      X* operator->() const;
      X* get() const;
      X* release();
      X* reset(X* p =0);
    };
  }

2 The auto_ptr provides a semantics of strict ownership.  An object  may
  be  safely  pointed  to  by  only one auto_ptr, so copying an auto_ptr
  copies the pointer and transfers ownership to the destination.

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

  explicit auto_ptr(X* p =0);

  Requires:
    p points to an object of class X or a class derived from X for which
    delete p is defined and accessible, or else p is a null pointer.
  Postcondition:
    get() == p

  auto_ptr(auto_ptr& a);

  Effects:
    copies the argument a to *this.
    Calls a.release().
  Postcondition:
    get() == the value returned from a.release().5)

  void operator=(auto_ptr& a);

  Effects:
    copies the argument a to *this.
    Calls reset(a.release()).
  Postcondition:
    get() == the value returned from a.release().

  ~auto_ptr();

  Effects:
    delete get()

  _________________________
  5)  That  is,  the  value  returned by a.get() before clearing it with
  a.release().

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

  X& operator*() const;

  Requires:
    get() != 0
  Returns:
    *get()

  X* get() const;

  Returns:
    The  pointer  p  specified  as  the  argument  to  the   constructor
    auto_ptr(X*  p)  or  as  the  argument  to  the  most recent call to
    reset(X* p).

  X* operator->() const;

  Returns:
    get()->m

  X* release();

  Postcondition:
    get() == 0

  X* reset(X* p =0);

  Requires:
    p points to an object of class X or a class derived from X for which
    delete p is defined and accessible, or else p is a null pointer
  Postcondition:
    get() == p

  20.4.6  C Library                                       [lib.c.malloc]

1 Header <cstdlib> (Table 3):

                    Table 3--Header <cstdlib> synopsis

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

2 The  contents are the same as the Standard C library, with the follow­
  ing 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 subclause 7.11.2.

5 Header <cstring> (Table 4):

                    Table 4--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, with the change
  to memchr() specified in subclause _lib.c.strings_.

  SEE ALSO: ISO C subclause 7.11.2.

  20.5  Date and time                                    [lib.date.time]

1 Header <ctime> (Table 5):

                     Table 5--Header <ctime> synopsis

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

2 The contents are the same as the Standard C library.

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