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

Question

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?

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

metal · Accepted Answer · 2023-11-08 14:21:23Z

4

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

your user-defined type allocates memory during copy or move, or
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.

edited Nov 8, 2023 at 14:21

metal

6,3321 gold badge38 silver badges49 bronze badges

answered Oct 12, 2017 at 16:43

Richard Hodges

70.3k8 gold badges103 silver badges157 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

BigSandwich Over a year ago

Not true, std::get_temporary_buffer() was an explicit way for them to allocate.

metal Over a year ago

Additional detail from the get_temporary_buffer() docs: "This API was originally designed with the intent of providing a more efficient implementation than the general-purpose operator new, but no such implementation was created and the API was deprecated and removed [in C++20]."

T.C. · Accepted Answer · 2017-10-12 18:36:00Z

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.

answered Oct 12, 2017 at 18:36

T.C.

139k18 gold badges306 silver badges440 bronze badges

Comments

BigSandwich · Accepted Answer · 2017-10-13 16:00:36Z

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

answered Oct 13, 2017 at 16:00

BigSandwich

2,8162 gold badges25 silver badges28 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related