______________________________________________________________________

  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 alocator 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 One of the common problems in portability is to be able to 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 memory model, as well as the memory allo­
  cation and deallocation primitives for it.

2 The library addresses this problem by  providing  a  standard  set  of
  requirements  for  allocators, which are objects that encapsulate this
  information.  All of the containers  are  parameterized  in  terms  of
  allocators.   That  dramatically  simplifies  the task of dealing with
  multiple memory models.

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

4 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
                                                  value_type.
  --------------------------------------------------------------------------------
   X::const_pointer     pointer to const T type   the result of operator* of
                                                  values of X::const_pointer is
                                                  of const value_type; 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.init_page_size()   X::size_type              the returned value is the op­
                                                  timal value for an initial
                                                  buffer size of the given type.
                                                  It is assumed that if k is re­
                                                  turned by init_page_size, t is
                                                  the construction time for T,
                                                  and u is the time that it
                                                  takes to do allocate(k), then
                                                  k * t is much greater than u.

  |                                                                              |
  |                                                                              |
  |                                                                              |
  |                                                                              |
  +------------------------------------------------------------------------------+
  |a.max_size()         X::size_type              the size of the largest buffer |
  |                                               that can be allocated          |
  +------------------------------------------------------------------------------+

  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.tuples_, tuples:
    struct empty;
    bool operator==(const empty&, const empty&);
    bool operator< (const empty&, const empty&);
    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&);
  // subclause _lib.restrictor_, restrictor:
    template <class T> class restrictor;
    template <class T>
      bool operator==(const restrictor<T>&, const restrictor<T>&);
    template <class T>
      bool operator< (const restrictor<T>&, const restrictor<T>&);
  }

  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  Tuples                                            [lib.tuples]

1 The library includes templates for heterogeneous n-tuples for n  equal
  to  0 and 2.  For non-empty tuples the  library provides matching tem­
  plate functions to simplify their construction.1)

2 For example, instead of saying,
    return pair<int, double>(5, 3.1415926); // explicit types

3 one may say
    return make_pair(5, 3.1415926); // types are deduced

  20.2.2.1  Empty                                            [lib.empty]

1 The class empty is used as a base  class  where  only  ==  and  <  are
  needed.

  struct empty {};

  bool operator==(const empty&, const empty&);

  Returns:
    true.

    bool operator< (const empty&, const empty&);

  Returns:
    false.

  20.2.2.2  Pair                                              [lib.pair]

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

  _________________________
  1) Users and library venders can provide  additional  n-tuples  for  n
  equal to 1 (singleton) and n greater than 2.  For example, triples and
  quadruples may be defined.

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

  20.2.3  Restrictor                                    [lib.restrictor]

1 Restrictor is a template class that hides a  value  of  any  type  and
  restricts  the available operations to equality and less than (if they
  are provided for the type).
  namespace std {
    template <class T>
    class restrictor {
    protected:
      T value;
    public:
      restrictor(const T& x) : value(x) {}
    };

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

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

  Returns:
    x.value == y.value.

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

  Returns:
    x.value < y.value.

  20.3  Function objects                          [lib.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));
  }

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, the interface is specified to accept an object with an oper­
  ator() defined.  This not only makes algorithmic templates  work  with
  pointers  to  functions,  but also enables them to work with arbitrary
  function objects.  Using function objects together with function  tem­
  plates increases the expressive power of the library as well as making
  the resulting code much more efficient.  For example, if  we  want  to
  have  a  by-element  addition of two vectors a and b containing double
  and put the result into a we can do:
    transform(a.begin(), a.end(), b.begin(), b.end(), a.begin(), plus<double>());

2 If we want to negate every element of a we can do:
    transform(a.begin(), a.end(), a.begin(), negate<double>());

3 The corresponding functions will inline the addition and the negation.

4 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 : empty {
      typedef Arg    argument_type;
      typedef Result result_type;
    };
    template <class Arg1, class Arg2, class Result>
    struct binary_function : empty {
      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.

  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.

  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]

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

1 operator() returns x && y.

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

2 operator() returns x || y.

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

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

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

  Returns:
    !value(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>,
          restrictor<Predicate> {
      public:
          binary_negate(const Predicate& x);
          bool operator()(const first_argument_type&  x,
                          const second_argument_type& y) const;
      };

2 operator() returns !value(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 For 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.

  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>, restrictor<Result (*)(Arg)> {
    public:
      pointer_to_unary_function(Result (*x)(Arg));
      Result operator()(const Arg& x) const;
    };

2 operator() returns value(x).

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

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

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

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

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

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

  20.4  Memory                                              [lib.memory]

  Header <memory> synopsis

  _________________________
  2)  Compilation  systems  that have multiple pointer to function types
  have to provide additional ptr_fun template functions.

  #include <cstddef>      // for size_t, ptrdiff_t
  #include <iterator>     // for output_iterator
  #include <utility>      // for restrictor
  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*);
  // 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.pointers_, pointers:
    template<class X> class auto_ptr;
  }

1 Header <cstdlib> (Table 3):

                    Table 3--Header <cstdlib> synopsis

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

2 Header <cstdlib> (Table 4):

                    Table 4--Header <cstring> synopsis

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

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

  SEE ALSO: ISO C subclause 7.11.2.

  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> types<T>::pointer
                          address(types<T>::reference x) const;
      template<class T> types<T>::const_pointer
                          address(types<T>::const_reference x) const;
      template<class T, class U>
        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> {   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.3)
  _________________________
  3) In addition to allocator the library vendors are expected  to  pro­

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> types<T>::pointer
  ddress(types<T>::reference x) const;

  Returns:
    &x.

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

  Returns:
    &x.

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

  Effects:
    Allocates storage, optionally using hint to

  +-------                 BEGIN BOX 1                -------+
  TBS:  To Be Specified
  +-------                  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(types<T>::pointer p);

  Requires:
    p shall be a pointer value obtained from allocate().
  Effects:
    Deallocates the storage referenced by p.

    size_type max_size() const;

  _________________________
  vide allocators for all supported memory models.

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

  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, restrictor<OutputIterator> {
    public:
      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);
    };
  }

  20.4.2.1  raw_storage_iterator members           [lib.storage.members]

  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]

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

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

  20.4.3.2  deallocate                                  [lib.deallocate]

1 Also, the following functions are provided:

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

  +-------                 BEGIN BOX 4                -------+
  TBS
  +-------                  END BOX 4                 -------+

  20.4.3.3  construct                                    [lib.construct]

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

  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  get_temporary_buffer              [lib.get.temporary.buffer]

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

  _________________________
  5) 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  Pointers                                        [lib.pointers]

  20.4.5.1  Template class auto_ptr                       [lib.auto.ptr]

1 Template auto_ptr holds onto a pointer obtained via new and deletes it
  when it goes out of scope.

  namespace std {
    template<class X> class auto_ptr {
      auto_ptr(auto_ptr&,void);
      void operator=(auto_ptr&);
    public:
      auto_ptr(X* p =0);
     ~auto_ptr();
      X& operator*() const;
      X* operator->() const;
      X* get() const;
      X* release();
      X* reset(X* =0);
    };
  }

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

  20.4.5.2.1  auto_ptr constructor                  [lib.auto.ptr::ctor]

  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:
    a.get() == p

  20.4.5.2.2  auto_ptr destructor                   [lib.auto.ptr::dtor]

  ~auto_ptr();

  Effects:
    delete get()

  20.4.5.2.3  operator*                              [lib.auto.ptr::op*]

  X& operator*() const;

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

  20.4.5.2.4  operator->                            [lib.auto.ptr::op->]

  X* operator->() const;

  Returns:
    get()->m

  20.4.5.2.5  release                            [lib.auto.ptr::release]

  X* release();

  Postcondition:
    get() == 0

  20.4.5.2.6  reset                                [lib.auto.ptr::reset]

  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 changes                               [lib.c.malloc]

1 The contents of <cstdlib> are the same as the Standard C library, with
  the following changes:

2 The  functions  calloc, malloc, and realloc do not attempt to allocate
  storage by calling operator new.

3 The function free does not attempt to deallocate  storage  by  calling
  operator delete.  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.