______________________________________________________________________
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 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
+-------------------------------------------------------+
| Subclause 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 This subclause describes requirements on template arguments. Sub
clauses _lib.equalitycomparable_ through _lib.copyconstructible_
describe requirements on types used to instantiate templates. Sub
clause _lib.allocator.requirements_ describes the requirements on
storage allocators.
20.1.1 Equality comparison [lib.equalitycomparable]
1 In the following Table 2, T is a type to be supplied by a C++ program
instantiating a template, a and b are values of type T.
Table 2--EqualityComparable requirements
+----------------------------------------------------------------------------------+
|expression return type post-condition complexity |
+----------------------------------------------------------------------------------+
|a == b convertible to bool == is an equivalence relationship constant |
+----------------------------------------------------------------------------------+
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 post-condition complexity |
+---------------------------------------------------------------------------------------------------------+
|a < b convertible to bool < is a strict weak ordering relation (_lib.alg.sorting_) constant |
+---------------------------------------------------------------------------------------------------------+
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 valuse of
type const T.
Table 4--CopyConstructible requirements
+-----------------------------------------------------------------+
|expression return type post-condition complexity |
+-----------------------------------------------------------------+
|T(t) t is equivalent to T(t) constant |
+-----------------------------------------------------------------+
|T(u) u is equivalent to T(u) constant |
+-----------------------------------------------------------------+
|t.~T() constant |
+-----------------------------------------------------------------+
|&t T* denotes the address of t constant |
+-----------------------------------------------------------------+
|&u const T* denotes the address of u constant |
+-----------------------------------------------------------------+
2 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.4 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 (_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 5--Descriptive variable definitions
+-----------------------------------------------------------------+
|Variable Definition |
+-----------------------------------------------------------------+
|X An Allocator class |
+-----------------------------------------------------------------+
|T any type |
+-----------------------------------------------------------------+
|t a value of type const T& |
+-----------------------------------------------------------------+
|a, a1, a2 Values of type X& |
+-----------------------------------------------------------------+
|p a value of type X::pointer obtained by calling |
| allocate on some a1 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 applying |
| unary operator* to a value p. |
+-----------------------------------------------------------------+
|s a value of type X::const_reference obtained by |
| applying unary operator* to a value q or by |
| conversion from a value r. |
+-----------------------------------------------------------------+
|u a value of type X::rebind<U>::const_pointer for some |
| type U, obtained by calling member a1.allocate |
| on some a1 where a1 == a. |
+-----------------------------------------------------------------+
|n a value of type X::size_type. |
+-----------------------------------------------------------------+
3 Table 6 describes the requirements on allocator types.
Table 6--Allocator requirements
--------------------------------------------------------------------------------
expression return type assertion/note
pre/post-condition
--------------------------------------------------------------------------------
X::pointer convertible to T* and
void*
--------------------------------------------------------------------------------
X::const_pointer convertible to const T*
and const void*
--------------------------------------------------------------------------------
X::reference convertible to T&
--------------------------------------------------------------------------------
X::const_reference convertible to const T&
--------------------------------------------------------------------------------
X::value_type Identical to T
--------------------------------------------------------------------------------
X::size_type unsigned integral type the type that can represent
the size of the largest object
in the allocation model.
--------------------------------------------------------------------------------
X::difference_type signed integral type the type that can represent
the difference between any two
pointers in the allocation
model.
--------------------------------------------------------------------------------
typename X::
rebind<U>::other for X an instantiation
of XT<T>, the type
XT<U>.
--------------------------------------------------------------------------------
X a; note: a destructor is assumed.
a.address(r) X::pointer
--------------------------------------------------------------------------------
a.address(s) X::const_pointer
--------------------------------------------------------------------------------
a.allocate(n) X::pointer memory is allocated for n ob
a.allocate(n,u) jects of type T but objects
are not constructed. allocate
may raise an appropriate ex
ception. The result is a ran
dom access iterator.
--------------------------------------------------------------------------------
a.deallocate(p) (not used) all the objects in the area
pointed by p should be de
stroyed prior to the call of
deallocate
--------------------------------------------------------------------------------
new(x) T X::pointer new((void*)x.allocate(1)) T
| |
| |
| |
| |
+------------------------------------------------------------------------------+
|new(x) T[n] X::pointer new((void*)x.allocate(n)) T[n] |
+------------------------------------------------------------------------------+
|a.max_size() X::size_type the largest value that can |
| meaningfully be passed to |
| X::allocate(). |
+------------------------------------------------------------------------------+
|a1 == a2 bool Returns true iff the two allo |
| cators are interchangeable, |
| such that storage allocated |
| from each can be deallocated |
| via the other. |
+------------------------------------------------------------------------------+
|a1 != a2 bool same as !(a1 == a2) |
+------------------------------------------------------------------------------+
|a1 = a2 X& post: a1 == a2 |
+------------------------------------------------------------------------------+
|X a1(a2); post: a1 == a2 |
+------------------------------------------------------------------------------+
|x.construct(p,u) (not used) Effect: new((void*)p) T(u) |
+------------------------------------------------------------------------------+
|x.destroy(p) (not used) Effect: ((T*)p)->~T() |
+------------------------------------------------------------------------------+
4 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 a conversion to
XT<void>::const_pointer (for appropriate XT) as well, for use by
X::allocate.
+------- BEGIN BOX 1 -------+
Change: Modified the requirements for conversions from X::pointer to
X::const_pointer and XT<void>::const_pointer. An issue will be opened
on whether this is the correct and complete set of necessary conver
sions. (E.g. what about the reference types?)
+------- END BOX 1 -------+
5 The second parameter to the call a.allocate in the table above is an
implementation-defined hint from the container implementor to the
allocator, typically as an aid for locality of reference1).
+------- BEGIN BOX 2 -------+
Change: The expression allocate<U>(n,u) in N0790R1 was changed to
allocate(n,u), replacing the member template with reliance on the
required pointer-to-void conversion. This resolves implementability
problems.
+------- END BOX 2 -------+
_________________________
1) In a container member function, the address of an adjacent element
is often a good choice to pass for this argument.
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:
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&);
}
// 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);
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).
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 {
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 (_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> 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&);
// 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));
// subclause _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_fun(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_fun_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, 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_). In all
cases, type T is convertible to type bool.
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;
};
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<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;
};
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<Operation::second_argument_type,
Operation::result_type> {
protected:
Operation op;
Operation::first_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;
Operation::second_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_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()(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.2) --end example]
_________________________
2) Implementations that have multiple pointer to function types pro
vide additional ptr_fun template functions.
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 the
preceeding section.
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);
};
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);
};
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));
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);
};
mem_fun_ref_t calls the member function it is initialized with given a
reference argument.
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);
};
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));
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
#include <cstddef> // for size_t, ptrdiff_t
#include <iterator> // for iterator traits
#include <utility> // for pair
namespace std {
// subclause _lib.default.allocator_, the default allocator:
template <class T> class allocator;
template <> class allocator<void>;
template <class T> void* operator new(size_t N, allocator<T>& a);
bool operator==(const allocator&, const allocator&) throw();
bool operator!=(const allocator&, const allocator&) throw();
// 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 ForwardIterator>
void destroy(ForwardIterator first, ForwardIterator last);
template <class T>
pair<T*,ptrdiff_t> get_temporary_buffer(ptrdiff_t n);
template <class T> void return_temporary_buffer(T* p);
// 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 {
template <class T> class allocator;
// specialize for void:
template <> class allocator<void> {
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
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; };
allocator() throw();
template <class U> allocator(const allocator<U>&) throw();
template <class U> allocator operator=(const allocator<U>&) throw();
~allocator() throw();
pointer allocate(size_type, const void* hint);
void deallocate(pointer p);
size_type max_size() const throw();
};
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();
template <class U> allocator(const allocator<U>&) throw();
template <class U> allocator& operator= (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 max_size() const throw();
void construct(pointer p, const T& val);
void destroy(pointer p);
};
template <class T>
void* operator new(size_t N, allocator<T>& a);
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();
}
+------- BEGIN BOX 3 -------+
Change: N0790R1 specified a template member allocate using a default
template argument, which is forbidden. It has been replaced by a non-
template member relying on the required conversion to const void*.
+------- END BOX 3 -------+
+------- BEGIN BOX 4 -------+
Change: The following was specified in N0790R1, but this isn't the
right place for it, and a similar statement already appears in the
right place. "It is assumed that any pointer types have a (possibly
lossy) conversion to void*, yielding a pointer sufficient for use as
the this value in a constructor or destructor."
+------- END BOX 4 -------+
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);
Notes:
Uses ::operator new(size_t) (_lib.new.delete_).
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(), 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);
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_), but it is
unspecified 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) T1(val)
void destroy(pointer p);
Returns:
((T*)p)->~T()
20.4.1.2 allocator globals [lib.allocator.globals]
void* operator new(size_t N, allocator& a);
Returns:
a.allocate<char,void>(N,0).
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.1.3 Example allocator [lib.allocator.example]
1 [Example: Here is a sample container parameterized on the allocator
type:
template <class T, class Allocator = allocator<T> >
class AContainer {
template <class T> class Treenode;
typedef typename Allocator::rebind< Treenode<T> >::other
Treenode_allocator;
Treenode_allocator::pointer Treenode_ptr;
template <class T>
struct Treenode { Treenode_ptr left_, right_; T t; };
public:
explicit AContainer(const Allocator& alloc = Allocator())
: alloc_(alloc), root_(0) {}
void aMember();
private:
Treenode_allocator alloc_;
Treenode_ptr root_;
};
template <class T, class Allocator>
void AContainer::aMember()
{
Treenode_ptr p = new(alloc_.allocate(1, this)) Treenode<T>;
...
alloc_.destroy(p);
alloc_.deallocate(p);
}
Here is an allocator for shared memory:
template <class T>
class shared_allocator: public std::allocator<T> {
class impl {
explicit impl(void* region);
~impl();
void* allocate(size_t);
void* deallocate(void*);
template <class T> friend class shared_allocator<T>;
}
impl* impl_;
public:
template <class U> struct rebind { typedef shared_allocator<U> other; };
explicit shared_allocator(void* region) : impl_(new impl(region)) {}
template <class U>
shared_allocator(const shared_allocator<U>&) throw();
template <class U>
shared_allocator& operator=(const shared_allocator<U>&) throw();
~shared_allocator();
pointer allocate(size_t N, const void* hint);
{ return impl_->allocate(N*sizeof T); }
void deallocate(pointer p)
{ impl_->deallocate(p); }
};
--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 iterator<output_iterator_tag,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]
+------- BEGIN BOX 5 -------+
ISSUE: Is there something here that cannot be done with operator new
and operator delete?
+------- END BOX 5 -------+
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.3)
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_temporary_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.
20.4.4.1 uninitialized_copy [lib.uninitialized.copy]
template <class InputIterator, class ForwardIterator>
ForwardIterator
uninitialized_copy(InputIterator first, InputIterator last,
ForwardIterator result);
_________________________
3) For every allocation 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*);
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_n [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 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 T element_type;
// _lib.auto.ptr.cons_ construct/copy/destroy:
explicit auto_ptr(X* p =0);
template<class Y> auto_ptr(const auto_ptr<Y>&);
template<class Y> auto_ptr& operator=(const auto_ptr<Y>&);
~auto_ptr();
// _lib.auto.ptr.members_ members:
X& operator*() const;
X* operator->() const;
X* get() const;
X* release();
};
}
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 behaviour of the program is undefined.
20.4.5.1 auto_ptr constructors [lib.auto.ptr.cons]
explicit auto_ptr(X* p =0);
Requires:
p points to an object of type X or a class derived from X for which
delete p is defined and accessible, or else p is a null pointer.
Postconditions:
*this holds the pointer to p. *this owns *get() if and only if p is
not a null pointer.
template<class Y> auto_ptr(const auto_ptr<Y>& a);
Requires:
Y is type X or a class derived from X for which delete (Y*) is
defined and accessible.
Effects:
Calls a.release().
Postconditions:
*this holds the pointer returned from a.release(). *this owns
*get() if and only if a owns *a.
template<class Y> auto_ptr& operator=(const auto_ptr<Y>& a);
Requires:
Y is type X or a class derived from X for which delete (Y*) is
defined and accessible.
Effects:
If *this owns *get() and *this != &a then delete get(). Calls
a.release().
Returns:
*this.
Postconditions:
*this holds the pointer returned from a.release(). *this owns
*get() if and only if a owns *a.
~auto_ptr();
Effects:
If *this owns *get() then delete get().
20.4.5.2 auto_ptr members [lib.auto.ptr.members]
X& operator*() const;
Requires:
get() != 0
Returns:
*get()
X* operator->() const;
Returns:
get()
X* get() const;
Returns:
The pointer *this holds.
X* release() const;
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, 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 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, 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 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.
+------- BEGIN BOX 6 -------+
Note: in Monterey we accepted the resolution for issue 20-007 in
95-0099R1, the body of which was "to be specified"! So this sub-
clause still needs work:-)
Steve Rumsby
+------- END BOX 6 -------+
SEE ALSO: ISO C subclause 7.12, Amendment 1 subclause 4.6.4.