CODEWITHSUNDEEP
c++memorystlc++17stl-algorithm
BigSandwich
BigSandwich

Reputation: 2816

Which Algorithms in the standard algorithm library allocate and is there a way to specify how this allocation occurs?

I'd like to make more use of standard algorithms but have some pretty tight requirements for controlling memory allocation.

Is there a comprehensive list of which algorithms in allocate?
Also, is there anyway to control how this allocation occurs? Is the only option overriding global new? Does that actually work if linking statically? Prior to C++17 it appears that all allocations went through std::get_temporary_buffer() to allocate memory but this seems to deprecated in C++17. What replaces this?

Upvotes: 1

Views: 600

Answers (3)

Richard Hodges
Richard Hodges

Reputation: 69902

Standard algorithms appear to allocate memory due to external factors such as:

  1. your user-defined type allocates memory during copy or move, or
  2. your output iterator allocates memory during assignment of a value - for example std::back_insert_iterator<>

Also, the following algorithms may allocate memory internally as part of their operations:

  • stable_partition
  • inplace_merge
  • stable_sort

It seems that the reality is that libstdc++'s implementation simply tries to allocate a buffer using the non-throwing global operator new, and halves the allocation size if the new call returns null, until the allocation size is zero.

  template<typename _Tp>
     pair<_Tp*, ptrdiff_t>
     __get_temporary_buffer(ptrdiff_t __len, _Tp*)
     {
       const ptrdiff_t __max = numeric_limits<ptrdiff_t>::max() / sizeof(_Tp);
       if (__len > __max)
     __len = __max;
       
       while (__len > 0) 
     {
       _Tp* __tmp = static_cast<_Tp*>(::operator new(__len * sizeof(_Tp), 
                             nothrow));
       if (__tmp != 0)
         return pair<_Tp*, ptrdiff_t>(__tmp, __len);
       __len /= 2;
     }
       return pair<_Tp*, ptrdiff_t>(static_cast<_Tp*>(0), 0);
     }

source: https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.0/memory-source.html

It turns out that this function is controversial since Alexander Stepanov, an original author of the STL, wrote this as a placeholder implementation, leaving documentation that it should never go into production.

Needless to say, it did, and has been in every port of the STL since.

Upvotes: 4

BigSandwich
BigSandwich

Reputation: 2816

Looks like the only way to get control of the allocations is through overriding global new. See here, section "Global replacements"

http://en.cppreference.com/w/cpp/memory/new/operator_new

Since this works at link time, it means that each dll will have to link a translation unit with overridden global new/delete. How exactly this maps to any particular allocation strategy is probably beyond the scope of this question.

The other answers here specify which algorithms attempt to use temporaries.

stable_partition, stable_sort, and inplace_merge

Upvotes: 0

T.C.
T.C.

Reputation: 137425

For the non-parallel algorithms, stable_partition, stable_sort, and inplace_merge are the three that will definitely attempt to get extra memory, falling back to a less efficient algorithm if it can't do so. How exactly they attempt to obtain the memory is not specified.

However, nothing in the standard says that the other algorithms can't attempt to allocate memory just for the heck of it. A high-quality implementation shouldn't, but if you really need for it to not allocate, you should inspect the implementation yourself.

Upvotes: 2

Related Questions