1

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?

BigSandwich
  • 2,768
  • 2
  • 22
  • 26
  • Nothing replaces std::get_temporary_buffer(). Yet. Implementations may still use it (deprecated, not removed) or replace it with its core language equivalent. – DeiDei Oct 12 '17 at 16:38
  • Given what is written [here](https://stackoverflow.com/a/26861151/214671) I'd look for those "magic words" in the standard ("if there is enough extra memory"). – Matteo Italia Oct 12 '17 at 17:00
  • You have something like 4 questions smushed into one. Pick one and stick with it. – Passer By Oct 12 '17 at 17:10
  • They all relate to the question in the title and wouldn't work as stand alone questions – BigSandwich Oct 12 '17 at 19:17

3 Answers3

3

AFAIR none of the standard algorithms allocate memory unless:

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

Correction:

The following algorthms use it:

  • stable_partition
  • inplace_merge
  • stable_sort

It seems that the reality is that libstdc++'s implementation simply tries to allocate a buffer using T::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.

Richard Hodges
  • 68,278
  • 7
  • 90
  • 142
2

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.

T.C.
  • 133,968
  • 17
  • 288
  • 421
0

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

BigSandwich
  • 2,768
  • 2
  • 22
  • 26