get_temporary_buffer


Category: allocators	Component type: function

Prototype

template <class T>
pair<T*, ptrdiff_t> get_temporary_buffer(ptrdiff_t len, T*);

Description

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 pair P 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.

Definition

Defined in algo.h. The implementation is in tempbuf.h.

Requirements on types

Preconditions

len is greater than 0.

Complexity

Example

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

Notes

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