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

Question

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

是否有分配算法的完整列表？
另外，是否有办法控制这种分配的发生方式？唯一的选择是压倒全球新的吗？如果静态链接，这实际上有效吗？ 在 C++17 之前，似乎所有分配都通过 std::get_temporary_buffer() 来分配内存，但这在 C++17 中似乎已弃用。什么可以替代这个？

Answer 1

标准算法似乎会由于外部因素而分配内存，例如：

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

   std::back_insert_iterator<>

此外，以下算法可能会在内部分配内存作为其操作的一部分：

• 稳定_分区
• 就地合并
• 稳定排序

事实似乎是 libstdc++ 的实现只是尝试使用非抛出全局

operator new

来分配缓冲区，并且如果

new

调用返回 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

看起来控制分配的唯一方法是通过覆盖全局 new。请参阅此处的“全局替换”部分

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

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

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

stable_partition、stable_sort 和 inplace_merge