标准算法库中的哪些算法进行分配，有没有办法指定这种分配是如何发生的？

Question

我想更多地使用标准算法，但对控制内存分配有一些非常严格的要求。

是否有分配算法的完整列表？
另外，有没有办法控制这种分配是如何发生的？是覆盖全局新的唯一选择吗？如果静态链接，那真的有效吗？在 C++17 之前，似乎所有分配都通过 std::get_temporary_buffer() 来分配内存，但这在 C++17 中似乎已被弃用。用什么代替它？

Answer 1

AFAIR none 标准算法分配内存，除非：

您的用户定义类型在复制或移动期间分配内存，或者
您的输出迭代器在赋值期间分配内存 - 例如 std::back_insert_iterator<>

更正：

以下算法使用它：

stable_partition
inplace_merge
stable_sort

似乎事实是 libstdc++ 的实现只是尝试使用 T::operator new 分配缓冲区，如果 new 调用 returns null，则分配大小减半，直到分配大小为零。

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

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

事实证明，这个函数是有争议的，因为 STL 的原作者 Alexander Stepanov 将其写成一个占位符实现，留下了它永远不应该投入生产的文档。

不用说，它做到了，并且从那以后一直在 STL 的每个端口。

Answer 2

对于非并行算法，stable_partition、stable_sort 和 inplace_merge 是三个肯定会尝试获取额外内存的算法，如果出现以下情况，则回退到效率较低的算法它不能这样做。未指定他们究竟如何尝试获取内存。

但是，标准中没有任何内容表明其他算法不能尝试分配内存只是为了它的存在。一个高质量的实现不应该，但如果你真的需要它不分配，你应该自己检查实现。

Answer 3

看起来控制分配的唯一方法是覆盖全局新的。请参阅此处，第 "Global replacements"

部分

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

由于这在 link 时有效，这意味着每个 dll 都必须 link 一个具有覆盖全局 new/delete 的翻译单元。这究竟如何映射到任何特定的分配策略可能超出了这个问题的范围。

此处的其他答案指定了哪些算法尝试使用临时变量。

stable_partition、stable_sort 和 inplace_merge

标准算法库中的哪些算法进行分配，有没有办法指定这种分配是如何发生的？

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

c++

memory

stl

c++17

stl-algorithm