Category: allocators
Component type: overview
Allocators encapsulate allocation and deallocation of memory. They provide a low-level interface that permits efficient allocation of many small objects; different allocator types represent different schemes for memory management.
Note that allocators simply allocate and deallocate memory, as opposed to creating and destroying objects. The STL also includes several low-level algorithms for manipulating uninitialized memory.
Note also that allocators do not attempt to encapsulate multiple memory models. The C++ language only defines a single memory model (the difference of two pointers, for example, is always ptrdiff_t), and this memory model is the only one that allocators support. This is a major change from the definition of allocators in the original STL. [1]
The details of the allocator interface are still subject to change, and we do not guarantee that specific member functions will remain in future versions. You should think of an allocator as a "black box". That is, you may select a container's memory allocation strategy by instantiating the container template with a particular allocator [2], but you should not make any assumptions about how the container actually uses the allocator.
The available allocators are as follows. In most cases you shouldn't have to worry about the distinction: the default allocator, alloc, is usually the best choice.
alloc | The default allocator. It is thread-safe, and usually has the best performance characteristics. |
pthread_alloc | A thread-safe allocator that uses a different memory pool for each thread; you can only use pthread_alloc if your operating system provides pthreads. Pthread_alloc is usually faster than alloc, especially on multiprocessor systems. It can, however, cause resource fragmentation: memory deallocated in one thread is not available for use by other threads. |
single_client_alloc | A fast but thread-unsafe allocator. In programs that only have one thread, this allocator might be faster than alloc. |
malloc_alloc | An allocator that simply uses the standard library function malloc. It is thread-safe but slow; the main reason why you might sometimes want to use it is to get more useful information from bounds-checking or leak-detection tools while you are debugging. |
vector<double> V(100, 5.0); // Uses the default allocator.
vector<double, single_client_alloc> local(V.begin(), V.end());
• Allocator
• alloc
• pthread_alloc
• single_client_alloc
• malloc_alloc
• raw_storage_iterator
• construct
• destroy
• uninitialized_copy
• uninitialized_fill
• uninitialized_fill_n
• get_temporary_buffer
• return_temporary_buffer
[1] The reason for this change is that the new interface reduces memory fragmentation, and that it allows an implementation that is both efficient and thread-safe.
[2] Different containers may use different allocators. You might, for example, have some containers that use the default allocator alloc and others that use pthread_alloc. Note, however, that vector<int> and vector<int, pthread_alloc> are distinct types.
Category: allocators
Component type: function
template <class T1, class T2>
void construct(T1* p, const T2& value);
In C++, the operator new allocates memory for an object and then creates an object at that location by calling a constructor. Occasionally, however, it is useful to separate those two operations. [1] If p is a pointer to memory that has been allocated but not initialized, then construct(p, value) creates an object of type T1 at the location pointed to by p. The argument value is passed as an argument to T1's constructor.
Defined in the standard header memory, and in the nonstandard backward-compatibility header algo.h. The construct algorithm is no longer part of the C++ standard; it was present in early drafts, and it is retained in this implementation for backward compatibility.
• T1 must have a constructor that takes a single argument of type T2.
• p is a valid pointer that points to a region of memory whose size is at least sizeof(T1).
• The memory pointed to by p is uninitialized. That is, no object has been constructed at the location p.
double* dp = (double*)malloc(sizeof(double));
construct(dp, 3);
assert(*dp == 3);
[1] In particular, construct, along with other low-level memory allocation primitives, is used to implement container classes.
Allocators, destroy, uninitialized_copy, uninitialized_fill, uninitialized_fill_n, raw_storage_iterator
Category: allocators
Component type: function
Destroy is an overloaded name; there are actually two destroy functions.
template <class T>
void destroy(T* pointer);
template <class ForwardIterator>
void destroy(ForwardIterator first, ForwardIterator last);
In C++, the operator delete destroys an object by calling its destructor, and then deallocates the memory where that object was stored. Occasionally, however, it is useful to separate those two operations. [1] Destroy calls an object's destructor without deallocating the memory where the object was stored.
The first version of destroy destroys the object pointed to by pointer by calling the destructor T::~T(). The memory pointed to by pointer is not deallocated, and can be reused for some other object.
The second version of destroy destroys all of the objects in the range of elements [first, last). It is equivalent to calling destroy(&*i) for each iterator i in the range [first, last).
Defined in the standard header memory, and in the nonstandard backward-compatibility header algo.h. The destroy algorithms are no longer part of the C++ standard; they were present in early drafts, and they are retained in this implementation for backward compatibility.
For the first version of destroy :
• T's destructor, ~T, is accessible.
For the second version of destroy:
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator is mutable.
• ForwardIterator's value type has an accessible destructor.
For the first version of destroy:
• pointer points to a valid object of type T.
For the second version of destroy:
• [first, last) is a valid range.
• Each iterator i in [first, last) points to a valid object.
The run-time complexity of the second version is linear: it calls the destructor exactly last – first times.
class Int {
public:
Int(int x) : val(x) {}
int get() { return val; }
private:
int val;
};
int main() {
Int A[] = { Int(1), Int(2), Int(3), Int(4) };
destroy(A, A + 4);
construct(A, Int(10));
construct(A + 1, Int(11));
construct(A + 2, Int(12));
construct(A + 3, Int(13));
}
[1] In particular, destroy , along with other low-level memory allocation primitives, is used to implement container classes.
Allocators, construct, uninitialized_copy, uninitialized_fill, uninitialized_fill_n, raw_storage_iterator
Categories: allocators, algorithms
Component type: function
template <class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);
In C++, the operator new allocates memory for an object and then creates an object at that location by calling a constructor. Occasionally, however, it is useful to separate those two operations. [1] If each iterator in the range [result, result + (last – first)) points to uninitialized memory, then uninitialized_copy creates a copy of [first, last) in that range. That is, for each iterator i in the input range, uninitialized_copy creates a copy of *i in the location pointed to by the corresponding iterator in the output range by calling construct(&*(result + (i – first)), *i).
Defined in the standard header memory, and in the nonstandard backward-compatibility header algo.h.
• InputIterator is a model of Input Iterator.
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator is mutable.
• ForwardIterator's value type has a constructor that takes a single argument whose type is InputIterator 's value type.
• [first, last) is a valid range.
• [result, result + (last – first)) is a valid range.
• Each iterator in [result, result + (last – first)) points to a region of uninitialized memory that is large enough to store a value of ForwardIterator's value type.
Linear. Exactly last – first constructor calls.
class Int {
public:
Int(int x) : val(x) {}
int get() { return val; }
private:
int val;
};
int main() {
int A1[] = {1, 2, 3, 4, 5, 6, 7};
const int N = sizeof(A1) / sizeof(int);
Int* A2 = (Int*) malloc(N * sizeof(Int));
uninitialized_copy(A1, A1 + N, A2);
}
[1] In particular, this sort of low-level memory management is used in the implementation of some container classes.
Allocators, construct, destroy, uninitialized_fill, uninitialized_fill_n, raw_storage_iterator
Categories: allocators, algorithms
Component type: function
template <class InputIterator, class Size, class ForwardIterator>
ForwardIterator uninitialized_copy_n(InputIterator first, Size count, ForwardIterator result);
In C++, the operator new allocates memory for an object and then creates an object at that location by calling a constructor. Occasionally, however, it is useful to separate those two operations. [1] If each iterator in the range [result, result + n) points to uninitialized memory, then uninitialized_copy_n creates a copy of [first, first + n) in that range. That is, for each iterator i in the input range, uninitialized_copy_n creates a copy of *i in the location pointed to by the corresponding iterator in the output range by calling construct(&*(result + (i – first)), *i).
Defined in the standard header memory, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.
• InputIterator is a model of Input Iterator.
• Size is an integral type.
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator is mutable.
• ForwardIterator's value type has a constructor that takes a single argument whose type is InputIterator's value type.
• n >= 0
• [first, first + n) is a valid range.
• [result, result + n) is a valid range.
• Each iterator in [result, result + n) points to a region of uninitialized memory that is large enough to store a value of ForwardIterator's value type.
Linear. Exactly n constructor calls.
class Int {
public:
Int(int x) : val(x) {}
int get() { return val; }
private:
int val;
};
int main() {
int A1[] = {1, 2, 3, 4, 5, 6, 7};
const int N = sizeof(A1) / sizeof(int);
Int* A2 = (Int*)malloc(N * sizeof(Int));
uninitialized_copy_n(A1, N, A2);
}
[1] In particular, this sort of low-level memory management is used in the implementation of some container classes.
[2] Uninitialized_copy_n is almost, but not quite, redundant. If first is an input iterator, as opposed to a forward iterator, then the uninitialized_copy_n operation can't be expressed in terms of uninitialized_copy.
Allocators, construct, destroy, uninitialized_copy, uninitialized_fill, uninitialized_fill_n, raw_storage_iterator
Categories: allocators, algorithms
Component type: function
template <class ForwardIterator, class T>
void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);
In C++, the operator new allocates memory for an object and then creates an object at that location by calling a constructor. Occasionally, however, it is useful to separate those two operations. [1] If each iterator in the range [first, last) points to uninitialized memory, then uninitialized_fill creates copies of x in that range. That is, for each iterator i in the range [first, last), uninitialized_copy creates a copy of x in the location pointed to i by calling construct(&*i, x).
Defined in the standard header memory, and in the nonstandard backward-compatibility header algo.h.
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator is mutable.
• ForwardIterator's value type has a constructor that takes a single argument of type T.
• [first, last) is a valid range.
• Each iterator in [first, last) points to a region of uninitialized memory that is large enough to store a value of ForwardIterator's value type.
Linear. Exactly last – first constructor calls.
class Int {
public:
Int(int x) : val(x) {}
int get() { return val; }
private:
int val;
};
int main() {
const int N = 137;
Int val(46);
Int* A = (Int*) malloc(N * sizeof(Int));
uninitialized_fill(A, A + N, val);
}
[1] In particular, this sort of low-level memory management is used in the implementation of some container classes.
Allocators, construct, destroy, uninitialized_copy, uninitialized_fill_n, raw_storage_iterator
Categories: allocators, algorithms
Component type: function
template <class ForwardIterator, class Size, class T>
ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& x);
In C++, the operator new allocates memory for an object and then creates an object at that location by calling a constructor. Occasionally, however, it is useful to separate those two operations. [1] If each iterator in the range [first, first + n) points to uninitialized memory, then uninitialized_fill_n creates copies of x in that range. That is, for each iterator i in the range [first, first + n), uninitialized_fill_n creates a copy of x in the location pointed to i by calling construct(&*i, x).
Defined in the standard header memory, and in the nonstandard backward-compatibility header algo.h.
• ForwardIterator is a model of Forward Iterator.
• ForwardIterator is mutable.
• Size is an integral type that is convertible to ForwardIterator's distance type.
• ForwardIterator's value type has a constructor that takes a single argument of type T.
• n is nonnegative.
• [first, first + n) is a valid range.
• Each iterator in [first, first + n) points to a region of uninitialized memory that is large enough to store a value of ForwardIterator's value type.
Linear. Exactly n constructor calls.
class Int {
public:
Int(int x) : val(x) {}
int get() { return val; }
private:
int val;
};
int main() {
const int N = 137;
Int val(46);
Int* A = (Int*) malloc(N * sizeof(Int));
uninitialized_fill_n(A, N, val);
}
[1] In particular, this sort of low-level memory management is used in the implementation of some container classes.
Allocators, construct, destroy, uninitialized_copy, uninitialized_fill, raw_storage_iterator
Category: allocators
Component type: type
Some algorithms, such as stable_sort and inplace_merge, are adaptive: they attempt to use extra temporary memory to store intermediate results, and their run-time complexity is better if that extra memory is available. These algorithms use temporary_buffer to allocate that extra memory.
temporary_buffer's constructor takes two arguments, first and last, of type ForwardIterator; the constructor allocates a buffer that is large enough to contain N objects of type T, where 0 <= N <= last – first [1], and it fills the buffer with objects of type T. The member functions begin() and end() return iterators that point to the beginning and the end of the buffer.
Note that the elements in the buffer are guaranteed to be initialized; that is, begin() points to an object of type T, not to raw memory. However, the initial values of the buffer's elements are unspecified. You should not rely on them to be initialized to any particular value.
temporary_buffer does not have a copy constructor, or an assignment operator. Those operations would have complicated, and not terribly useful, semantics.
(Earlier versions of the STL used get_temporary_buffer and return_temporary_buffer instead of temporary_buffer. temporary_buffer is more convenient, because it does not require using uninitialized_copy , and in some cases it is also more efficient. Additionally, it is much easier to write exception-safe code with temporary_buffer than with get_temporary_buffer and return_temporary_buffer.)
int main() {
vector<int> V(50);
iota(V.begin(), V.end(), 1);
temporary_buffer<vector<int>::iterator, int> buf(V.begin(), V.end());
copy(V.rbegin(), V.rbegin() + buf.size(), buf.begin());
copy(buf.begin(), buf.end(), ostream_iterator<int>(cout, "\n"));
}
Defined in the standard header memory, and in the nonstandard backward-compatibility header algo.h. This class is an SGI extension; it is not part of the C++ standard.
| Parameter | Description | Default |
|---|---|---|
ForwardIterator | The type of the iterators passed as arguments to temporary_buffer's constructor. | |
T | The type of object stored in the temporary buffer. | iterator_traits<ForwardIterator>::value_type [2] |
None. temporary_buffer is vaguely similar to a Container, but it does not provide the entire Container interface. In particular, it is not a model of DefaultConstructible or Assignable.
• ForwardIterator is a model of Forward Iterator
• ForwardIterator is mutable.
• T has a constructor that can take a single argument of ForwardIterator's value type.
None.
| Member | Description |
|---|---|
temporary_buffer(ForwardIterator first, ForwardIterator last) | Allocates a temporary buffer that holds at most last – first elements of type T, and constructs those elements. The initial values of the elements are unspecified. Precondition: [first, last) is a valid range. |
~temporary_buffer() | Destroys the elements in the temporary buffer, and deallocates the buffer itself. |
T* begin() | Returns a pointer to the first element in the buffer. |
T* end() | Returns a pointer that points one past the last element in the buffer. |
ptrdiff_t requested_size() const | Returns the value last – first, where first and last are the arguments that were passed to the constructor. |
ptrdiff_t size() const | Returns the number of elements in the temporary buffer, end() – begin(). The return value satisfies the constraint 0 <= size() <= requested_size(). |
[1] The requested size is last – first. The size of the temporary buffer is never larger than the requested size, but it might well be smaller; the size might even be zero. The intention is that temporary_buffer will allocate as large a buffer as is possible without hurting performance. Note that determining this maximum size is quite difficult: it depends on cache size, physical versus virtual memory, heap fragmentation, and so on. A good implementation of temporary_buffer must be nonportable.
[2] The iterator_traits mechanism relies on partial specialization of templates. If your compiler does not yet implement this features, then you will not be able to use this default parameter; you will have to provide both template arguments.
Category: allocators
Component type: function
template <class T>
pair<T*, ptrdiff_t> get_temporary_buffer(ptrdiff_t len, T*);
Some algorithms, such as stable_sort and inplace_merge, are adaptive: they attempt to use extra temporary memory to store intermediate results, and their run-time complexity is better if that extra memory is available.
The first argument to get_temporary_buffer specifies the requested size of the temporary buffer, and the second specifies the type of object that will be stored in the buffer. That is, get_temporary_buffer(len, (T*) 0) requests a buffer that is aligned for objects of type T and that is large enough to hold len objects of type T. [1]
The return value of get_temporary_buffer is a pairP whose first component is a pointer to the temporary buffer and whose second argument indicates how large the buffer is: the buffer pointed to by P.first is large enough to hold P.second objects of type T. P.second is greater than or equal to 0 [2], and less than or equal to len [1]. Note that P.first is a pointer to uninitialized memory, rather than to actual objects of type T; this memory can be initialized using uninitialized_copy, uninitialized_fill, or uninitialized_fill_n.
As the name suggests, get_temporary_buffer should only be used to obtain temporary memory. If a function allocates memory using get_temporary_buffer, then it must deallocate that memory, using return_temporary_buffer [3], before it returns.
Note: get_temporary_buffer and return_temporary_buffer are only provided for backward compatibility. If you are writing new code, you should instead use the temporary_buffer class.
Defined in the standard header memory, and in the nonstandard backward-compatibility header algo.h.
• len is greater than 0.
int main() {
pair<int*, ptrdiff_t> P = get_temporary_buffer(10000, (int*) 0);
int* buf = P.first;
ptrdiff_t N = P.second;
uninitialized_fill_n(buf, N, 42);
int* result = find_if(buf, buf + N, bind2nd(not_equal_to<int>(), 42));
assert(result == buf + N);
return_temporary_buffer(buf);
}
[1] The argument len is a request, rather than a requirement. The intention is that get_temporary_buffer will return as large a buffer as can be allocated without hurting performance. Note that determining this maximum size is quite difficult: it depends on cache size, physical versus virtual memory, heap fragmentation, and so on. A good implementation of get_temporary_buffer must be nonportable.
[2] If P.second is 0, this means that get_temporary_buffer was unable to allocate a temporary buffer at all. In that case, P.first is a null pointer.
[3] It is unspecified whether get_temporary_buffer is implemented using malloc, or ::operator new, or some other method. The only portable way to return memory that was allocated using get_temporary_buffer is to use return_temporary_buffer.
temporary_buffer, return_temporary_buffer, Allocators
Category: allocators
Component type: function
template <class T>
void return_temporary_buffer(T* p);
Return_temporary_buffer is used to deallocate memory that was allocated using get_temporary_buffer. [1]
Note: get_temporary_buffer and return_temporary_buffer are only provided for backward compatibility. If you are writing new code, you should instead use the temporary_buffer class.
Defined in the standard header memory , and in the nonstandard backward-compatibility header algo.h .
The argument p is a pointer to a block of memory that was allocated using get_temporary_buffer(ptrdiff_t, T*).
int main() {
pair<int*, ptrdiff_t> P = get_temporary_buffer(10000, (int*)0);
int* buf = P.first;
ptrdiff_t N = P.second;
uninitialized_fill_n(buf, N, 42);
int* result = find_if(buf, buf + N, bind2nd(not_equal_to<int>(), 42));
assert(result == buf + N);
return_temporary_buffer(buf);
}
[1] As is always true, memory that was allocated using a particular allocation function must be deallocated using the corresponding deallocation function. Memory obtained using get_temporary_buffer must be deallocated using return_temporary_buffer, rather than using free or ::operator delete.
temporary_buffer, get_temporary_buffer, Allocators