______________________________________________________________________ 20 General utilities library [lib.utilities] ______________________________________________________________________ 1 This clause describes components used by other elements of the Stan- dard C++ library. These components may also be used by C++ programs. 2 The following clauses describe utility and allocator requirements, utility components, function objects, dynamic memory management utili- ties, and date/time utilities, as summarized in Table 1: Table 1--General utilities library summary +-------------------------------------------------------+ | Clause Header(s) | +-------------------------------------------------------+ |_lib.utility.requirements_ Requirements | +-------------------------------------------------------+ |_lib.utility_ Utility components <utility> | +-------------------------------------------------------+ |_lib.function.objects_ Function objects <functional> | +-------------------------------------------------------+ |_lib.memory_ Memory <memory> | +-------------------------------------------------------+ |_lib.date.time_ Date and time <ctime> | +-------------------------------------------------------+ 20.1 Requirements [lib.utility.requirements] 1 _lib.utility.requirements_ describes requirements on template argu- ments. _lib.equalitycomparable_ through _lib.copyconstructible_ describe requirements on types used to instantiate templates. _lib.allocator.requirements_ describes the requirements on storage allocators. 20.1.1 Equality comparison [lib.equalitycomparable] 1 In Table 2, T is a type to be supplied by a C++ program instantiating a template, a, b and c are values of type T. Table 2--EqualityComparable requirements +------------------------------------------------------------------------+ |expression return type requirement | +------------------------------------------------------------------------+ |a == b convertible to bool == is an equiva- | | lence relation, | | that is, it sat- | | isfies the fol- | | lowing proper- | | ties: | | | | --For all a, a == a. | | | | --If a == b, then b == a. | | | | --If a == b and b == c, then a == c. | +------------------------------------------------------------------------+ 20.1.2 Less than comparison [lib.lessthancomparable] 1 In the following Table 3, T is a type to be supplied by a C++ program instantiating a template, a and b are values of type T. Table 3--LessThanComparable requirements +--------------------------------------------------------------------------------------------+ |expression return type requirement | +--------------------------------------------------------------------------------------------+ |a < b convertible to bool < is a strict weak ordering relation (_lib.alg.sorting_) | +--------------------------------------------------------------------------------------------+ 20.1.3 Copy construction [lib.copyconstructible] 1 In the following Table 4, T is a type to be supplied by a C++ program instantiating a template, t is a value of type T, and u is a value of type const T. Table 4--CopyConstructible requirements +----------------------------------------------------+ |expression return type requirement | +----------------------------------------------------+ |T(t) t is equivalent to T(t) | +----------------------------------------------------+ |T(u) u is equivalent to T(u) | +----------------------------------------------------+ |t.~T() | +----------------------------------------------------+ |&t T* denotes the address of t | +----------------------------------------------------+ |&u const T* denotes the address of u | +----------------------------------------------------+ 20.1.4 Default construction [lib.default.con.req] 1 The default constructor is not required. Certain container class mem- ber function signatures specify the default constructor as a default argument. T() must be a well-defined expression (_dcl.init_) if one of those signatures is called using the default argument (_dcl.fct.default_). 20.1.5 Allocator requirements [lib.allocator.requirements] 1 The library describes a standard set of requirements for allocators, which are objects that encapsulate the information about an allocation model. This information includes the knowledge of pointer types, the type of their difference, the type of the size of objects in this allocation model, as well as the memory allocation and deallocation primitives for it. All of the containers (clause _lib.containers_) are parameterized in terms of allocators. 2 Table 5 describes the requirements on types manipulated through allo- cators. All the operations on the allocators are expected to be amor- tized constant time. Table 6 describes the requirements on allocator types. Table 5--Descriptive variable definitions +---------------------------------------------------------------+ |Variable Definition | +---------------------------------------------------------------+ |T, U any type | +---------------------------------------------------------------+ |X an Allocator class for type T | +---------------------------------------------------------------+ |Y the corresponding Allocator class for type U | +---------------------------------------------------------------+ |t a value of type const T& | +---------------------------------------------------------------+ |a, a1, a2 values of type X& | +---------------------------------------------------------------+ |b a value of type Y | +---------------------------------------------------------------+ |p a value of type X::pointer, obtained by calling | | a1.allocate, where a1 == a. | +---------------------------------------------------------------+ |q a value of type X::const_pointer obtained by | | conversion from a value p. | +---------------------------------------------------------------+ |r a value of type X::reference obtained by | | the expression *p. | +---------------------------------------------------------------+ |s a value of type X::const_reference obtained by | | the expression *q or by conversion from a value r. | +---------------------------------------------------------------+ |u a value of type Y::const_pointer obtained by | | calling Y::allocate, or else 0. | +---------------------------------------------------------------+ |n a value of type X::size_type. | +---------------------------------------------------------------+ Table 6--Allocator requirements ------------------------------------------------------------------------------------- expression return type assertion/note pre/post-condition ------------------------------------------------------------------------------------- X::pointer Pointer to T. ------------------------------------------------------------------------------------- X::const_pointer Pointer to const T. ------------------------------------------------------------------------------------- X::reference T& ------------------------------------------------------------------------------------- X::const_reference T const& ------------------------------------------------------------------------------------- X::value_type Identical to T ------------------------------------------------------------------------------------- X::size_type unsigned integral type a type that can represent the size of the largest object in the allocation model. ------------------------------------------------------------------------------------- X::difference_type signed integral type a type that can represent the difference between any two pointers in the allo- cation model. ------------------------------------------------------------------------------------- typename X::rebind<U>::other Y For all U (including T), Y::rebind<T>::other is X. ------------------------------------------------------------------------------------- a.address(r) X::pointer ------------------------------------------------------------------------------------- a.address(s) X::const_pointer ------------------------------------------------------------------------------------- a.allocate(n) X::pointer Memory is allocated for n a.allocate(n,u) objects of type T but ob- jects are not constructed. allocate may raise an ap- propriate exception. The result is a random access iterator.1) ------------------------------------------------------------------------------------- a.deallocate(p, n) (not used) All n T objects in the area pointed by p must be destroyed prior to this call. n must match the value passed to allocate to obtain this memory. Does not throw exceptions. [Note: p must not be null. --end note] | | | | | | | | +-----------------------------------------------------------------------------------+ |a.max_size() X::size_type the largest value that can | | meaningfully be passed to | | X::allocate(). | +-----------------------------------------------------------------------------------+ |a1 == a2 bool returns true iff storage | | allocated from each can be | | deallocated via the other. | +-----------------------------------------------------------------------------------+ |a1 != a2 bool same as !(a1 == a2) | +-----------------------------------------------------------------------------------+ |X() creates a default in- | | stance. Note: a destructor | | is assumed. | +-----------------------------------------------------------------------------------+ |X a(b); post: Y(a) == b | +-----------------------------------------------------------------------------------+ |a.construct(p,t) (not used) Effect: new((void*)p) T(t) | +-----------------------------------------------------------------------------------+ |a.destroy(p) (not used) Effect: ((T*)p)->~T() | +-----------------------------------------------------------------------------------+ 3 The template class member rebind in the table above is effectively a template typedef: if the name Allocator is bound to SomeAllocator<T>, then Allocator::rebind<U>::other is the same type as SomeAllocator<U>. 4 Implementations of containers described in this International Standard are permitted to assume that their Allocator template parameter meets the following two additional requirements beyond those in Table 6. --All instances of a given allocator type are required to be inter- changeable and always compare equal to each other. --The typedef members pointer, const_pointer, size_type, and differ- ence_type are required to be T*, T const*, size_t, and ptrdiff_t, respectively. 5 Implementors are encouraged to supply libraries that can accept allo- cators that encapsulate more general memory models and that support non-equal instances. In such implementations, any requirements imposed on allocators by containers beyond those requirements that appear in Table 6, and the semantics of containers and algorithms when allocator instances compare non-equal, are implementation-defined. 20.2 Utility components [lib.utility] 1 This subclause contains some basic template functions and classes that are used throughout the rest of the library. _________________________ 1) It is intended that a.allocate be an efficient means of allocating a single object of type T, even when sizeof(T) is small. That is, there is no need for a container to maintain its own ``free list''. Header <utility> synopsis namespace std { // _lib.operators_, operators: namespace rel_ops { template<class T> bool operator!=(const T&, const T&); template<class T> bool operator> (const T&, const T&); template<class T> bool operator<=(const T&, const T&); template<class T> bool operator>=(const T&, const T&); } // _lib.pairs_, pairs: template <class T1, class T2> struct pair; template <class T1, class T2> bool operator==(const pair<T1,T2>&, const pair<T1,T2>&); template <class T1, class T2> bool operator< (const pair<T1,T2>&, const pair<T1,T2>&); template <class T1, class T2> bool operator!=(const pair<T1,T2>&, const pair<T1,T2>&); template <class T1, class T2> bool operator> (const pair<T1,T2>&, const pair<T1,T2>&); template <class T1, class T2> bool operator>=(const pair<T1,T2>&, const pair<T1,T2>&); template <class T1, class T2> bool operator<=(const pair<T1,T2>&, const pair<T1,T2>&); template <class T1, class T2> pair<T1,T2> make_pair(const T1&, const T2&); } 20.2.1 Operators [lib.operators] 1 To avoid redundant definitions of operator!= out of operator== and operators >, <=, and >= out of operator<, the library provides the following: template <class T> bool operator!=(const T& x, const T& y); Requires: Type T is EqualityComparable (_lib.equalitycomparable_). Returns: !(x == y). template <class T> bool operator>(const T& x, const T& y); Requires: Type T is LessThanComparable (_lib.lessthancomparable_). Returns: y < x. template <class T> bool operator<=(const T& x, const T& y); Requires: Type T is LessThanComparable (_lib.lessthancomparable_). Returns: !(y < x). template <class T> bool operator>=(const T& x, const T& y); Requires: Type T is LessThanComparable (_lib.lessthancomparable_). Returns: !(x < y). 2 In this library, whenever a declaration is provided for an operator!=, operator>, operator>=, or operator<=, and requirements and semantics are not explicitly provided, the requirements and semantics are as specified in this clause. 20.2.2 Pairs [lib.pairs] 1 The library provides a template for heterogeneous pairs of values. The library also provides a matching template function to simplify their construction. template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair(); pair(const T1& x, const T2& y); template<class U, class V> pair(const pair<U, V> &p); }; pair(); Effects: Initializes its members as if implemented: pair() : first(T1()), second(T2()) {} pair(const T1& x, const T2& y); Effects: The constructor initializes first with x and second with y. template<class U, class V> pair(const pair<U, V> &p); Effects: Initializes members from the corresponding members of the argument, performing implicit conversions as needed. template <class T1, class T2> bool operator==(const pair<T1, T2>& x, const pair<T1, T2>& y); Returns: x.first == y.first && x.second == y.second. template <class T1, class T2> bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y); Returns: x.first < y.first || (!(y.first < x.first) && x.second < y.second). template <class T1, class T2> pair<T1, T2> make_pair(const T1& x, const T2& y); Returns: pair<T1, T2>(x, y). 2 [Example: In place of: return pair<int, double>(5, 3.1415926); // explicit types a C++ program may contain: return make_pair(5, 3.1415926); // types are deduced --end example] 20.3 Function objects [lib.function.objects] 1 Function objects are objects with an operator() defined. They are important for the effective use of the library. In the places where one would expect to pass a pointer to a function to an algorithmic template (clause _lib.algorithms_), the interface is specified to accept an object with an operator() defined. This not only makes algorithmic templates work with pointers to functions, but also enables them to work with arbitrary function objects. Header <functional> synopsis namespace std { // _lib.base_, base: template <class Arg, class Result> struct unary_function; template <class Arg1, class Arg2, class Result> struct binary_function; // _lib.arithmetic.operations_, arithmetic operations: template <class T> struct plus; template <class T> struct minus; template <class T> struct multiplies; template <class T> struct divides; template <class T> struct modulus; template <class T> struct negate; // _lib.comparisons_, comparisons: template <class T> struct equal_to; template <class T> struct not_equal_to; template <class T> struct greater; template <class T> struct less; template <class T> struct greater_equal; template <class T> struct less_equal; // _lib.logical.operations_, logical operations: template <class T> struct logical_and; template <class T> struct logical_or; template <class T> struct logical_not; // _lib.negators_, negators: template <class Predicate> struct unary_negate; template <class Predicate> unary_negate<Predicate> not1(const Predicate&); template <class Predicate> struct binary_negate; template <class Predicate> binary_negate<Predicate> not2(const Predicate&); // _lib.binders_, binders: template <class Operation> class binder1st; template <class Operation, class T> binder1st<Operation> bind1st(const Operation&, const T&); template <class Operation> class binder2nd; template <class Operation, class T> binder2nd<Operation> bind2nd(const Operation&, const T&); // _lib.function.pointer.adaptors_, adaptors: template <class Arg, class Result> class pointer_to_unary_function; template <class Arg, class Result> pointer_to_unary_function<Arg,Result> ptr_fun(Result (*)(Arg)); template <class Arg1, class Arg2, class Result> class pointer_to_binary_function; template <class Arg1, class Arg2, class Result> pointer_to_binary_function<Arg1,Arg2,Result> ptr_fun(Result (*)(Arg1,Arg2)); // _lib.member.pointer.adaptors_, adaptors: template<class S, class T> class mem_fun_t; template<class S, class T, class A> class mem_fun1_t; template<class S, class T> mem_fun_t<S,T> mem_fun(S (T::*f)()); template<class S, class T, class A> mem_fun1_t<S,T,A> mem_fun1(S (T::*f)(A)); template<class S, class T> class mem_fun_ref_t; template<class S, class T, class A> class mem_fun1_ref_t; template<class S, class T> mem_fun_ref_t<S,T> mem_fun_ref(S (T::*f)()); template<class S, class T, class A> mem_fun1_ref_t<S,T,A> mem_fun1_ref(S (T::*f)(A)); } 2 Using function objects together with function templates increases the expressive power of the library as well as making the resulting code much more efficient. 3 [Example: If a C++ program wants to have a by-element addition of two vectors a and b containing double and put the result into a, it can do: transform(a.begin(), a.end(), b.begin(), a.begin(), plus<double>()); --end example] 4 [Example: To negate every element of a: transform(a.begin(), a.end(), a.begin(), negate<double>()); The corresponding functions will inline the addition and the negation. --end example] 5 To enable adaptors and other components to manipulate function objects that take one or two arguments it is required that they correspond- ingly provide typedefs argument_type and result_type for function objects that take one argument and first_argument_type, second_argu- ment_type, and result_type for function objects that take two argu- ments. 20.3.1 Base [lib.base] 1 The following classes are provided to simplify the typedefs of the argument and result types: template <class Arg, class Result> struct unary_function { typedef Arg argument_type; typedef Result result_type; }; template <class Arg1, class Arg2, class Result> struct binary_function { typedef Arg1 first_argument_type; typedef Arg2 second_argument_type; typedef Result result_type; }; 20.3.2 Arithmetic operations [lib.arithmetic.operations] 1 The library provides basic function object classes for all of the arithmetic operators in the language (_expr.mul_, _expr.add_). template <class T> struct plus : binary_function<T,T,T> { T operator()(const T& x, const T& y) const; }; 2 operator() returns x + y. template <class T> struct minus : binary_function<T,T,T> { T operator()(const T& x, const T& y) const; }; 3 operator() returns x - y. template <class T> struct multiplies : binary_function<T,T,T> { T operator()(const T& x, const T& y) const; }; 4 operator() returns x * y. template <class T> struct divides : binary_function<T,T,T> { T operator()(const T& x, const T& y) const; }; 5 operator() returns x / y. template <class T> struct modulus : binary_function<T,T,T> { T operator()(const T& x, const T& y) const; }; 6 operator() returns x % y. template <class T> struct negate : unary_function<T,T> { T operator()(const T& x) const; }; 7 operator() returns -x. 20.3.3 Comparisons [lib.comparisons] 1 The library provides basic function object classes for all of the com- parison operators in the language (_expr.rel_, _expr.eq_). template <class T> struct equal_to : binary_function<T,T,bool> { bool operator()(const T& x, const T& y) const; }; 2 operator() returns x == y. template <class T> struct not_equal_to : binary_function<T,T,bool> { bool operator()(const T& x, const T& y) const; }; 3 operator() returns x != y. template <class T> struct greater : binary_function<T,T,bool> { bool operator()(const T& x, const T& y) const; }; 4 operator() returns x > y. template <class T> struct less : binary_function<T,T,bool> { bool operator()(const T& x, const T& y) const; }; 5 operator() returns x < y. template <class T> struct greater_equal : binary_function<T,T,bool> { bool operator()(const T& x, const T& y) const; }; 6 operator() returns x >= y. template <class T> struct less_equal : binary_function<T,T,bool> { bool operator()(const T& x, const T& y) const; }; 7 operator() returns x <= y. 8 For templates greater, less, greater_equal, and less_equal, the spe- cializations for any pointer type yield a total order, even if the built-in operators <, >, <=, >= do not. 20.3.4 Logical operations [lib.logical.operations] 1 The library provides basic function object classes for all of the log- ical operators in the language (_expr.log.and_, _expr.log.or_, _expr.unary.op_). template <class T> struct logical_and : binary_function<T,T,bool> { bool operator()(const T& x, const T& y) const; }; 2 operator() returns x && y. template <class T> struct logical_or : binary_function<T,T,bool> { bool operator()(const T& x, const T& y) const; }; 3 operator() returns x || y. template <class T> struct logical_not : unary_function<T,bool> { bool operator()(const T& x) const; }; 4 operator() returns !x. 20.3.5 Negators [lib.negators] 1 Negators not1 and not2 take a unary and a binary predicate, respec- tively, and return their complements (_expr.unary.op_). template <class Predicate> class unary_negate : public unary_function<typename Predicate::argument_type,bool> { public: explicit unary_negate(const Predicate& pred); bool operator()(const argument_type& x) const; }; 2 operator() returns !pred(x). template <class Predicate> unary_negate<Predicate> not1(const Predicate& pred); Returns: unary_negate<Predicate>(pred). template <class Predicate> class binary_negate : public binary_function<typename Predicate::first_argument_type, typename Predicate::second_argument_type, bool> { public: explicit binary_negate(const Predicate& pred); bool operator()(const first_argument_type& x, const second_argument_type& y) const; }; 3 operator() returns !pred(x,y). template <class Predicate> binary_negate<Predicate> not2(const Predicate& pred); Returns: binary_negate<Predicate>(pred). 20.3.6 Binders [lib.binders] 1 Binders bind1st and bind2nd take a function object f of two arguments and a value x and return a function object of one argument constructed out of f with the first or second argument correspondingly bound to x. 20.3.6.1 Template class binder1st [lib.binder.1st] template <class Operation> class binder1st : public unary_function<typename Operation::second_argument_type, typename Operation::result_type> { protected: Operation op; typename Operation::first_argument_type value; public: binder1st(const Operation& x, const typename Operation::first_argument_type& y); result_type operator()(const argument_type& x) const; }; 1 The constructor initializes op with x and value with y. 2 operator() returns op(value,x). 20.3.6.2 bind1st [lib.bind.1st] template <class Operation, class T> binder1st<Operation> bind1st(const Operation& op, const T& x); Returns: binder1st<Operation>(op, typename Operation::first_argu- ment_type(x)). 20.3.6.3 Template class binder2nd [lib.binder.2nd] template <class Operation> class binder2nd : public unary_function<typename Operation::first_argument_type, typename Operation::result_type> { protected: Operation op; typename Operation::second_argument_type value; public: binder2nd(const Operation& x, const typename Operation::second_argument_type& y); result_type operator()(const argument_type& x) const; }; 1 The constructor initializes op with x and value with y. 2 operator() returns op(x,value). 20.3.6.4 bind2nd [lib.bind.2nd] template <class Operation, class T> binder2nd<Operation> bind2nd(const Operation& op, const T& x); Returns: binder2nd<Operation>(op, typename Operation::second_argu- ment_type(x)). 1 [Example: find_if(v.begin(), v.end(), bind2nd(greater<int>(), 5)); finds the first integer in vector v greater than 5; find_if(v.begin(), v.end(), bind1st(greater<int>(), 5)); finds the first integer in v less than 5. --end example] 20.3.7 Adaptors for pointers to [lib.function.pointer.adaptors] functions 1 To allow pointers to (unary and binary) functions to work with func- tion adaptors the library provides: template <class Arg, class Result> class pointer_to_unary_function : public unary_function<Arg, Result> { public: explicit pointer_to_unary_function(Result (*f)(Arg)); Result operator()(Arg x) const; }; 2 operator() returns f(x). template <class Arg, class Result> pointer_to_unary_function<Arg, Result> ptr_fun(Result (*f)(Arg)); Returns: pointer_to_unary_function<Arg, Result>(f). template <class Arg1, class Arg2, class Result> class pointer_to_binary_function : public binary_function<Arg1,Arg2,Result> { public: explicit pointer_to_binary_function(Result (*f)(Arg1, Arg2)); Result operator()(Arg1 x, Arg2 y) const; }; 3 operator() returns f(x,y). template <class Arg1, class Arg2, class Result> pointer_to_binary_function<Arg1,Arg2,Result> ptr_fun(Result (*f)(Arg1, Arg2)); Returns: pointer_to_binary_function<Arg1,Arg2,Result>(f). 4 [Example: replace_if(v.begin(), v.end(), not1(bind2nd(ptr_fun(strcmp), "C")), "C++"); replaces each C with C++ in sequence v.2) --end example] 20.3.8 Adaptors for pointers to [lib.member.pointer.adaptors] members 1 The purpose of the following is to provide the same facilities for pointer to members as those provided for pointers to functions in _lib.function.pointer.adaptors_. template <class S, class T> class mem_fun_t : public unary_function<T*, S> { public: explicit mem_fun_t(S (T::*p)()); S operator()(T* p) const; }; 2 mem_fun_t calls the member function it is initialized with given a pointer argument. template <class S, class T, class A> class mem_fun1_t : public binary_function<T*, A, S> { public: explicit mem_fun1_t(S (T::*p)(A)); S operator()(T* p, A x) const; }; 3 mem_fun1_t calls the member function it is initialized with given a pointer argument and an additional argument of the appropriate type. template<class S, class T> mem_fun_t<S,T> mem_fun(S (T::*f)()); template<class S, class T, class A> mem_fun1_t<S,T,A> mem_fun1(S (T::*f)(A)); 4 mem_fun(&X::f) returns an object through which X::f can be called given a pointer to an X followed by the argument required for f (if any). template <class S, class T> class mem_fun_ref_t : public unary_function<T, S> { public: explicit mem_fun_ref_t(S (T::*p)()); S operator()(T& p) const; }; 5 mem_fun_ref_t calls the member function it is initialized with given a reference argument. _________________________ 2) Implementations that have multiple pointer to function types pro- vide additional ptr_fun template functions. template <class S, class T, class A> class mem_fun1_ref_t : public binary_function<T, A, S> { public: explicit mem_fun1_ref_t(S (T::*p)(A)); S operator()(T& p, A x) const; }; 6 mem_fun1_ref_t calls the member function it is initialized with given a reference argument and an additional argument of the appropriate type. template<class S, class T> mem_fun_ref_t<S,T> mem_fun_ref(S (T::*f)()); template<class S, class T, class A> mem_fun1_ref_t<S,T,A> mem_fun1_ref(S (T::*f)(A)); 7 mem_fun_ref(&X::f) returns an object through which X::f can be called given a reference to an X followed by the argument required for f (if any). 20.4 Memory [lib.memory] Header <memory> synopsis namespace std { // _lib.default.allocator_, the default allocator: template <class T> class allocator; template <> class allocator<void>; template <class T, class U> bool operator==(const allocator<T>&, const allocator<U>&) throw(); template <class T, class U> bool operator!=(const allocator<T>&, const allocator<U>&) throw(); // _lib.storage.iterator_, raw storage iterator: template <class OutputIterator, class T> class raw_storage_iterator; // _lib.temporary.buffer_, temporary buffers: template <class T> pair<T*,ptrdiff_t> get_temporary_buffer(ptrdiff_t n); template <class T> void return_temporary_buffer(T* p); // _lib.specialized.algorithms_, specialized algorithms: template <class InputIterator, class ForwardIterator> ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result); template <class ForwardIterator, class T> void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x); template <class ForwardIterator, class Size, class T> void uninitialized_fill_n(ForwardIterator first, Size n, const T& x); // _lib.auto.ptr_, pointers: template<class X> class auto_ptr; } 20.4.1 The default allocator [lib.default.allocator] namespace std { template <class T> class allocator; // specialize for void: template <> class allocator<void> { public: typedef void* pointer; typedef const void* const_pointer; // reference-to-void members are impossible. typedef void value_type; template <class U> struct rebind { typedef allocator<U> other; }; }; template <class T> class allocator { public: typedef size_t size_type; typedef ptrdiff_t difference_type; typedef T* pointer; typedef const T* const_pointer; typedef T& reference; typedef const T& const_reference; typedef T value_type; template <class U> struct rebind { typedef allocator<U> other; }; allocator() throw(); allocator(const allocator&) throw(); template <class U> allocator(const allocator<U>&) throw(); ~allocator() throw(); pointer address(reference x) const; const_pointer address(const_reference x) const; pointer allocate( size_type, typename allocator<void>::const_pointer hint = 0); void deallocate(pointer p, size_type n); size_type max_size() const throw(); void construct(pointer p, const T& val); void destroy(pointer p); }; } 20.4.1.1 allocator members [lib.allocator.members] pointer address(reference x) const; Returns: &x. const_pointer address(const_reference x) const; Returns: &x. pointer allocate(size_type n, allocator<void>::const_pointer hint=0); Notes: Uses ::operator new(size_t) (_lib.new.delete_). Requires: hint either 0 or previously obtained from member allocate and not yet passed to member deallocate. The value hint may be used by an implementation to help improve performance3). Returns: a pointer to the initial element of an array of storage of size n * sizeof(T), aligned appropriately for objects of type T. Note: the storage is obtained by calling ::operator new(size_t), but it is unspecified when or how often this function is called. The use of hint is unspecified, but intended as an aid to locality if an imple- mentation so desires. Throws: bad_alloc if the storage cannot be obtained. void deallocate(pointer p, size_type n); Requires: p shall be a pointer value obtained from allocate(). n shall equal the value passed as the first argument to the invocation of allocate which returned p. Effects: Deallocates the storage referenced by p. Notes: Uses ::operator delete(void*) (_lib.new.delete_), but it is unspeci- fied when this function is called. size_type max_size() const throw(); Returns: the largest value N for which the call allocate(N,0) might succeed. void construct(pointer p, const_reference val); Returns: new((void *)p) T(val) void destroy(pointer p); Returns: ((T*)p)->~T() _________________________ 3) In a container member function, the address of an adjacent element is often a good choice to pass for this argument. 20.4.1.2 allocator globals [lib.allocator.globals] template <class T1, class T2> bool operator==(const allocator<T1>&, const allocator<T2>&) throw(); Returns: true. template <class T1, class T2> bool operator!=(const allocator<T1>&, const allocator<T2>&) throw(); Returns: false. 20.4.2 Raw storage iterator [lib.storage.iterator] 1 raw_storage_iterator is provided to enable algorithms to store the results into uninitialized memory. The formal template parameter Out- putIterator is required to have its operator* return an object for which operator& is defined and returns a pointer to T, and is also required to satisfy the requirements of an output iterator (_lib.out- put.iterators_). namespace std { template <class OutputIterator, class T> class raw_storage_iterator : public iterator<output_iterator_tag,void,void,void,void> { public: explicit raw_storage_iterator(OutputIterator x); raw_storage_iterator<OutputIterator,T>& operator*(); raw_storage_iterator<OutputIterator,T>& operator=(const T& element); raw_storage_iterator<OutputIterator,T>& operator++(); raw_storage_iterator<OutputIterator,T> operator++(int); }; } raw_storage_iterator(OutputIterator x); Effects: Initializes the iterator to point to the same value to which x points. raw_storage_iterator<OutputIterator,T>& operator*(); Returns: *this raw_storage_iterator<OutputIterator,T>& operator=(const T& element); Effects: Constructs a value from element at the location to which the itera- tor points. Returns: A reference to the iterator. raw_storage_iterator<OutputIterator,T>& operator++(); Effects: Pre-increment: advances the iterator and returns a reference to the updated iterator. raw_storage_iterator<OutputIterator,T> operator++(int); Effects: Post-increment: advances the iterator and returns the old value of the iterator. 20.4.3 Temporary buffers [lib.temporary.buffer] template <class T> pair<T*, ptrdiff_t> get_temporary_buffer(ptrdiff_t n); Effects: Obtains a pointer to storage sufficient to store up to n adjacent T objects. Returns: A pair containing the buffer's address and capacity (in the units of sizeof(T)), or a pair of 0 values if no storage can be obtained. template <class T> void return_temporary_buffer(T* p); Effects: Deallocates the buffer to which p points. Requires: The buffer shall have been previously allocated by get_tempo- rary_buffer. 20.4.4 Specialized algorithms [lib.specialized.algorithms] 1 All the iterators that are used as formal template parameters in the following algorithms are required to have their operator* return an object for which operator& is defined and returns a pointer to T. In the algorithm uninitialized_copy, the formal template parameter InputIterator is required to satisfy the requirements of an input iterator (_lib.input.iterators_). In all of the following algorithms, the formal template parameter ForwardIterator is required to satisfy the requirements of a forward iterator (_lib.forward.iterators_) and also to satisfy the requirements of a mutable iterator (_lib.iterator.requirements_), and is required to have the property that no exceptions are thrown from increment, assignment, comparison, or dereference of valid iterators. In the following algorithms, if an exception is thrown there are no effects. 20.4.4.1 uninitialized_copy [lib.uninitialized.copy] template <class InputIterator, class ForwardIterator> ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result); Effects: for (; first != last; ++result, ++first) new (static_cast<void*>(&*result)) typename iterator_traits<ForwardIterator::value_type(*first); Returns: result 20.4.4.2 uninitialized_fill [lib.uninitialized.fill] template <class ForwardIterator, class T> void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x); Effects: for (; first != last; ++first) new (static_cast<void*>(&*first)) typename iterator_traits<ForwardIterator::value_type(x); 20.4.4.3 uninitialized_fill_n [lib.uninitialized.fill.n] template <class ForwardIterator, class Size, class T> void uninitialized_fill_n(ForwardIterator first, Size n, const T& x); Effects: for (; n--; ++first) new (static_cast<void*>(&*first)) typename iterator_traits<ForwardIterator::value_type(x); 20.4.5 Template class auto_ptr [lib.auto.ptr] 1 Template auto_ptr stores a pointer to an object obtained via new and deletes that object when it itself is destroyed (such as when leaving block scope _stmt.dcl_). namespace std { template<class X> class auto_ptr { public: typedef X element_type; // _lib.auto.ptr.cons_ construct/copy/destroy: explicit auto_ptr(X* p =0) throw(); auto_ptr(const auto_ptr&) throw(); template<class Y> auto_ptr(const auto_ptr<Y>&) throw(); auto_ptr& operator=(const auto_ptr&) throw(); template<class Y> auto_ptr& operator=(const auto_ptr<Y>&) throw(); ~auto_ptr(); // _lib.auto.ptr.members_ members: X& operator*() const throw(); X* operator->() const throw(); X* get() const throw(); X* release() const throw(); }; } 2 The auto_ptr provides a semantics of strict ownership. After initial construction an auto_ptr owns the object it holds a pointer to. Copy- ing an auto_ptr copies the pointer and transfers ownership to the des- tination. If more than one auto_ptr owns the same object at the same time the behavior of the program is undefined. 20.4.5.1 auto_ptr constructors [lib.auto.ptr.cons] explicit auto_ptr(X* p =0) throw(); Postconditions: *this holds the pointer to p. *this owns *get() if and only if p is not a null pointer. auto_ptr(const auto_ptr& a) throw(); Effects: Calls a.release(). Postconditions: *this holds the pointer returned from a.release(). *this owns *get() if and only if a owned *a on entry. template<class Y> auto_ptr(const auto_ptr<Y>& a) throw(); Requires: Y* can be implicitly converted to X*. Effects: Calls a.release(). Postconditions: *this holds the pointer returned from a.release(). *this owns *get() if and only if a owned *a on entry. auto_ptr& operator=(const auto_ptr& a) throw(); Requires: The expression delete get() is well formed. Effects: If *this is the same object as a there are no effects. Otherwise, call a.release(), and if *this owns *get() then delete get(). Returns: *this. Postconditions: If *this is not the same object as a then *this holds the pointer returned from a.release(). *this owns *get() if and only if a owned *a on entry. template<class Y> auto_ptr& operator=(const auto_ptr<Y>& a) throw(); Requires: Y* can be implicitly converted to X*. The expression delete get() is well formed. Effects: If *this is the same object as a there are no effects. Otherwise, call a.release(), and if *this owns *get() then delete get(). Returns: *this. Postconditions: If *this is not the same object as a then *this holds the pointer returned from a.release(). *this owns *get() if and only if a owned *a on entry. ~auto_ptr(); Requires: The expression delete get() is well formed. Effects: If *this owns *get() then delete get(). 20.4.5.2 auto_ptr members [lib.auto.ptr.members] X& operator*() const throw(); Requires: get() != 0 Returns: *get() X* operator->() const throw(); Returns: get() X* get() const throw(); Returns: The pointer *this holds. X* release() const throw(); Returns: get() Postcondition: *this is not the owner of *get(). 20.4.6 C Library [lib.c.malloc] 1 Header <cstdlib> (Table 7): Table 7--Header <cstdlib> synopsis +------------------------------+ | Type Name(s) | +------------------------------+ |Functions: calloc malloc | | free realloc | +------------------------------+ 2 The contents are the same as the Standard C library header <stdlib.h>, with the following changes: 3 The functions calloc(), malloc(), and realloc() do not attempt to allocate storage by calling ::operator new() (_lib.support.dynamic_). 4 The function free() does not attempt to deallocate storage by calling ::operator delete(). SEE ALSO: ISO C clause 7.11.2. 5 Header <cstring> (Table 8): Table 8--Header <cstring> synopsis +------------------------------+ | Type Name(s) | +------------------------------+ |Macro: NULL | +------------------------------+ |Type: size_t | +------------------------------+ |Functions: memchr memcmp | |memcpy memmove memset | +------------------------------+ 6 The contents are the same as the Standard C library header <string.h>, with the change to memchr() specified in _lib.c.strings_. SEE ALSO: ISO C clause 7.11.2. 20.5 Date and time [lib.date.time] 1 Header <ctime> (Table 9): Table 9--Header <ctime> synopsis +---------------------------------------------------+ | Type Name(s) | +---------------------------------------------------+ |Macros: NULL | +---------------------------------------------------+ |Types: size_t clock_t time_t | +---------------------------------------------------+ |Struct: tm | +---------------------------------------------------+ |Functions: | |asctime clock difftime localtime strftime | |ctime gmtime mktime time | +---------------------------------------------------+ 2 The contents are the same as the Standard C library header <time.h>. SEE ALSO: ISO C clause 7.12, Amendment 1 clause 4.6.4.