______________________________________________________________________
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 core components (_lib.core_), func
tion objects (_lib.function.objects_), dynamic memory management util
ities (_lib.memory_), and date/time utilities (_lib.date.time_).
20.1 Core components [lib.core]
1 This subclause contains some basic template functions and classes that
are used throughout the rest of the library.
2 Headers:
--<stl core (TBD)>
3 Table 1:
Table 1--Header <stl core (TBD)> synopsis
+-----------------------------------------------------------------------+
| Type Name(s) |
+-----------------------------------------------------------------------+
|Template class: restrictor |
+-----------------------------------------------------------------------+
|Template struct: pair |
+-----------------------------------------------------------------------+
|Template operators: |
|operator!= (T) operator<= (T) operator> (T) |
|operator< (pair) operator== (pair) operator>= (T) |
|operator< (restrictor) operator== (restrictor) |
+-----------------------------------------------------------------------+
|Template function: make_pair |
+-----------------------------------------------------------------------+
|Struct: empty |
+-----------------------------------------------------------------------+
|Operator functions: operator< (empty) operator== (empty) |
+-----------------------------------------------------------------------+
20.1.1 Operators [lib.operators]
1 To avoid redundant definitions of operator!= out of operator== and
operators>, <=, and >= out of operator< the library provides the fol
lowing:
template <class T>
inline bool operator!=(const T& x, const T& y) {
return !(x == y);
}
template <class T>
inline bool operator>(const T& x, const T& y) {
return y < x;
}
template <class T>
inline bool operator<=(const T& x, const T& y) {
return !(y < x);
}
template <class T>
inline bool operator>=(const T& x, const T& y) {
return !(x < y);
}
20.1.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.1.2.1 Empty [lib.empty]
1 The class empty is used as a base class where only == and < are
needed.
struct empty {};
inline bool operator==(const empty&, const empty&) { return true; }
inline bool operator< (const empty&, const empty&) { return false; }
20.1.2.2 Pair [lib.pair]
_________________________
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.
template <class T1, class T2>
struct pair {
T1 first;
T2 second;
pair(const T1& x, const T2& y) : first(x), second(y) {}
};
template <class T1, class T2>
inline bool operator==(const pair<T1, T2>& x, const pair<T1, T2>& y) {
return x.first == y.first && x.second == y.second;
}
template <class T1, class T2>
inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) {
return x.first < y.first || (!(y.first < x.first) && x.second < y.second);
}
template <class T1, class T2>
inline pair<T1, T2> make_pair(const T1& x, const T2& y) {
return pair<T1, T2>(x, y);
}
20.1.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).
template <class T>
class restrictor {
friend bool operator==(const restrictor<T>& x, const restrictor<T>& y);
friend bool operator< (const restrictor<T>& x, const restrictor<T>& y);
protected:
T value;
public:
restrictor(const T& x) : value(x) {}
};
template <class T>
inline bool operator==(const restrictor<T>& x, const restrictor<T>& y) {
return x.value == y.value;
}
template <class T>
inline bool operator<(const restrictor<T>& x, const restrictor<T>& y) {
return x.value < y.value;
}
20.2 Function objects [lib.function.objects]
1 Headers:
--<stl functional (TBD)>
2 Table 2:
Table 2--Header <stl functional (TBD)> synopsis
+------------------------------------------------------------------+
| Type Name(s) |
+------------------------------------------------------------------+
|Template classes: |
|binary_negate pointer_to_binary_function |
|binder1st pointer_to_unary_function |
|binder2nd unary_negate |
+------------------------------------------------------------------+
|Template structs: |
|binary_function less minus times |
|divides less_equal modulus unary_function |
|equal_to logical_and negate |
|greater logical_not not_equal_to |
|greater_equal logical_or plus |
+------------------------------------------------------------------+
|Template functions: |
| bind1st not1 ptr_fun [2] |
| bind2nd not2 |
+------------------------------------------------------------------+
3 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>());
4 If we want to negate every element of a we can do:
transform(a.begin(), a.end(), a.begin(), negate<double>());
5 The corresponding functions will inline the addition and the negation.
6 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.2.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.2.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 { return x + y; }
};
template <class T>
struct minus : binary_function<T, T, T> {
T operator()(const T& x, const T& y) const { return x - y; }
};
template <class T>
struct times : binary_function<T, T, T> {
T operator()(const T& x, const T& y) const { return x * y; }
};
template <class T>
struct divides : binary_function<T, T, T> {
T operator()(const T& x, const T& y) const { return x / y; }
};
template <class T>
struct modulus : binary_function<T, T, T> {
T operator()(const T& x, const T& y) const { return x % y; }
};
template <class T>
struct negate : unary_function<T, T> {
T operator()(const T& x) const { return -x; }
};
20.2.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 { return x == y; }
};
template <class T>
struct not_equal_to : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x != y; }
};
template <class T>
struct greater : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x > y; }
};
template <class T>
struct less : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x < y; }
};
template <class T>
struct greater_equal : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x >= y; }
};
template <class T>
struct less_equal : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x <= y; }
};
20.2.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 { return x && y; }
};
template <class T>
struct logical_or : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x || y; }
};
template <class T>
struct logical_not : unary_function<T, bool> {
bool operator()(const T& x) const { return !x; }
};
20.2.5 Negators [lib.negators]
1 Negators not1 and not2 take a unary and a binary predicate correspond
ingly 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) : restrictor<Predicate>(x) {}
bool operator()(const argument_type& x) const { return !value(x); }
};
template <class Predicate>
unary_negate<Predicate> not1(const Predicate& pred) {
return 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) : restrictor<Predicate>(x) {}
bool operator()(const first_argument_type& x,
const second_argument_type& y) const
{
return !value(x, y);
}
};
template <class Predicate>
binary_negate<Predicate> not2(const Predicate& pred) {
return binary_negate<Predicate>(pred);
}
20.2.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.2.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)
: op(x), value(y) {}
result_type operator()(const argument_type& x) const {
return op(value, x);
}
};
20.2.6.2 bind1st [lib.bind.1st]
template <class Operation, class T>
binder1st<Operation> bind1st(const Operation& op, const T& x) {
return binder1st<Operation>(op, Operation::first_argument_type(x));
}
20.2.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)
: op(x), value(y) {}
result_type operator()(const argument_type& x) const {
return op(x, value);
}
};
20.2.6.4 bind2nd [lib.bind.2nd]
template <class Operation, class T>
binder2nd<Operation> bind2nd(const Operation& op, const T& x) {
return 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.2.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))
: restrictor<Result (*)(Arg)>(x) {}
Result operator()(const Arg& x) const { return value(x); }
};
template <class Arg, class Result>
pointer_to_unary_function<Arg, Result> ptr_fun(Result (*x)(Arg)) {
return 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))
: restrictor<Result (*)(Arg1, Arg2)>(x) {}
Result operator()(const Arg1& x, const Arg2& y) const {
return value(x, y);
}
};
template <class Arg1, class Arg2, class Result>
pointer_to_binary_function<Arg1, Arg2, Result>
ptr_fun(Result (*x)(Arg1, Arg2)) {
return pointer_to_binary_function<Arg1, Arg2, Result>(x);
}
2 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.3 Memory [lib.memory]
1 Headers:
--<stl memory (TBD)>
--<memory>
--<cstdlib>
--<cstring>
2 Table 3:
Table 3--Header <stl memory (TBD)> synopsis
+----------------------------------------------------------------+
| Type Name(s) |
+----------------------------------------------------------------+
|Template classes: allocator raw_storage_iterator |
+----------------------------------------------------------------+
|Template functions: |
|allocate destroy [2] uninitialized_fill_n |
|construct get_temporary_buffer unititialized_fill |
|deallocate uninitialized_copy |
+----------------------------------------------------------------+
3 Table 4:
Table 4--Header <memory> synopsis
+-----------------------------------------------------+
|Type Name(s) |
+-----------------------------------------------------+
|Template functions: objconstruct objdestroy |
| objcopy objmove |
+-----------------------------------------------------+
4 Table 5:
_________________________
2) Compilation systems that have multiple pointer to function types
have to provide additional ptr_fun template functions.
20-10 General utilities DRAFT:y2 October 1994 20.3 Memory
Table 5--Header <cstdlib> synopsis
+------------------------------+
| Type Name(s) |
+------------------------------+
|Functions: calloc malloc |
| free realloc |
+------------------------------+
5 Table 6:
Table 6--Header <cstring> synopsis
+---------------------------------------+
| Type Name(s) |
+---------------------------------------+
|Macro: NULL <cstring> |
+---------------------------------------+
|Type: size_t <cstring> |
+---------------------------------------+
|Functions: memchr memcmp |
|memcpy memmove memset |
+---------------------------------------+
SEE ALSO: ISO C subclause 7.11.2.
20.3.1 The default allocator [lib.default.allocator]
template <class T>
class allocator {
public:
typedef T* pointer;
typedef const T* const_pointer;
typedef T value_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
allocator();
~allocator();
pointer allocate(size_type n);
void deallocate(pointer p);
size_t init_page_size();
size_t max_size();
};
3)
_________________________
3) In addition to allocator the library vendors are expected to pro
vide allocators for all supported memory models.
20.3.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.
template <class OutputIterator, class T>
class raw_storage_iterator : public output_iterator,
restrictor<OutputIterator> {
public:
raw_storage_iterator(OutputIterator x) : restrictor<OutputIterator>(x) {}
raw_storage_iterator<OutputIterator, T>& operator*() { return *this; }
raw_storage_iterator<OutputIterator, T>& operator=(const T& element) {
construct(&*value, element);
return *this;
}
raw_storage_iterator<OutputIterator, T>& operator++() {
++value;
return *this;
}
raw_storage_iterator<OutputIterator, T> operator++(int) {
raw_storage_iterator<OutputIterator, T> tmp = *this;
++value;
return tmp;
}
};
20.3.3 Memory handling primitives [lib.memory.primitives]
20.3.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>
inline T* allocate(ptrdiff_t n, T*); // n >= 0
2 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 pro
vided:
template <class T>
inline T huge* allocate(long long n, T*);
20-12 General utilities DRAFT:y2 October 1994 20.3.3.2 deallocate
20.3.3.2 deallocate [lib.deallocate]
1 Also, the following functions are provided:
template <class T>
inline void deallocate(T* buffer);
20.3.3.3 construct [lib.construct]
template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
new (p) T1(value);
}
20.3.3.4 destroy [lib.destroy]
template <class T>
inline void destroy(T* pointer) {
pointer->T::~T();
}
template <class ForwardIterator>
void destroy(ForwardIterator first, ForwardIterator last) {
while (first != last) destroy(&*first++);
}
5)
20.3.3.5 get_temporary_buffer [lib.get.temporary.buffer]
template <class T>
pair<T*, ptrdiff_t> get_temporary_buffer(ptrdiff_t n, T*);
1 get_temporary_buffer finds the largest buffer not greater than
n*sizeof(T), and returns a pair consisting of the address and the
capacity (in the units of sizeof(T)) of the buffer.6)
20.3.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.
_________________________
5) For every memory model there are corresponding deallocate, con
struct and destroy template functions defined with the first argument
type being the pointer type of the memory model.
6) It is guaranteed that for every memory model that an implementa
tion supports, there is a corresponding get_temporary_buffer template
function defined which is overloaded on the corresponding signed inte
gral type. For example, if a system supports huge pointers and their
difference is of type long long, the following function has to be pro
vided:
template <class T>
pair<T huge *, long long> get_temporary_buffer(long long n, T*);
20.3.4.1 uninitialized_copy [lib.uninitialized.copy]
template <class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_copy(InputIterator first, InputIterator last,
ForwardIterator result)
{
while (first != last) construct(&*result++, *first++);
return result;
}
20.3.4.2 uninitialized_fill [lib.uninitialized.fill]
template <class ForwardIterator, class T>
void uninitialized_fill(ForwardIterator first, ForwardIterator last,
const T& x)
{
while (first != last) construct(&*first++, x);
}
20.3.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)
{
while (n--) construct(&*first++, x);
}
1 The header <memory> defines several template functions that copy, con
struct, and destroy arrays of objects.
20.3.4.4 objcpy [lib.template.objcpy]
template<class T> T* objcpy(T* dest, const T* src, size_t n);
1 Assigns src[I] to dest[I] for all non-negative values of I less than
n. The pointers dest and src shall designate the initial elements of
non-overlapping arrays of n objects of type T. The order in which
assignments take place is unspecified.
2 Returns dest.
template<class T> T* objcpy(void* dest, const T* src, size_t n);
3 Constructs ((T*)dest)[I] by copying src[I] for all non-negative values
of I less than n. The pointer dest shall designate a region of stor
age suitable for representing an array of n objects of type T. The
pointer src shall designate the initial element of an array of n
objects of type T that does not overlap the region designated by dest.
The order in which elements are constructed is unspecified.
4 Returns (T*)dest.
20.3.4.5 objmove [lib.template.objmove]
template<class T> T* objmove(T* dest, T* src, size_t n);
1 Assigns src[I] to dest[I] for all non-negative values of I less than
n. The pointers dest and src shall designate the initial elements of
arrays of n objects of type T. If dest == src, no assignment occurs.
20-14 General utilities DRAFT:y2 October 1994 20.3.4.5 objmove
2 Otherwise, each element of dest is destroyed after it has been
assigned to its corresponding element in src. An element of dest that
is also an element of src is first assigned to its corresponding ele
ment in src, then destroyed, before it is assigned to.
3 The order in which elements are assigned or destroyed is otherwise
unspecified.
4 Returns dest.
template<class T> T* objmove(void* dest, T* src, size_t n);
5 Constructs ((T*)dest)[I] by copying src[I] for all non-negative values
of I less than n. The pointer dest shall designate a region of stor
age suitable for representing an array of n objects of type T. The
pointer src shall designate the initial element of an array of n
objects of type T. If dest == (void*)src, no construction occurs.
6 Otherwise, each element of dest is destroyed after it has been copied
to its corresponding element in src. An element of dest that is also
an element of src is first copied to its corresponding element in src,
then destroyed, before it is constructed.
7 The order in which elements are constructed or destroyed is otherwise
unspecified.
8 Returns (T*)dest.
20.3.4.6 objconstruct [lib.template.objcons]
template<class T> T* objconstruct(void* dest, size_t n);
1 Constructs ((T*)dest)[I] with the constructor T() for all non-negative
values of I less than n. The pointer dest shall designate a region of
storage suitable for representing an array of n objects of type T.
The order in which elements are constructed is unspecified.
2 Returns (T*)dest.
20.3.4.7 objdestroy [lib.template.objdes]
template<class T> void* objdestroy(T* dest, size_t n);
1 Destroys ((T*)dest)[I] for all non-negative values of I less than n.
The pointer dest shall designate an array of n objects of type T. The
order in which elements are destroyed is unspecified.
2 Returns (void*)dest.
20.3.5 C library changes [lib.c.malloc]
1
2 The contents of <cstdlib> are the same as the Standard C library, with
the following changes:
3 The functions calloc, malloc, and realloc do not attempt to allocate
storage by calling operator new.
4 The function free does not attempt to deallocate storage by calling
operator delete.
SEE ALSO: ISO C subclause 7.11.2.
20.4 Date and time [lib.date.time]
1 Headers:
--<ctime>
2 Table 7:
Table 7--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 |
+------------------------------------------------+
3 The contents are the same as the Standard C library.
SEE ALSO: ISO C subclause 7.12, Amendment 1 subclause 4.6.4.