c++ - unordered_set 可以为节点和桶列表使用不同的分配器吗？

Question

我想使用 std::pmr::unordered_map与 std::pmr::monotonic_buffer_resource .两者配合得很好，因为集合的节点是稳定的，所以我不会通过重新分配在缓冲区资源中创建很多洞:

 std::pmr::monotonic_buffer_resource res;
 std::pmr::unordered_set<T> set(&res);

也就是说，除了桶列表，当集合重新散列时需要重新分配它，因为它超过了 max_load_factor()。 .假设我不能 reserve()我的出路，而且我实际上关心自增长以来旧桶列表留下的缓冲区资源中的漏洞，我有什么选择？
如果我知道 unordered_set实现为 std::vector<std::forward_list> ，如在(某些版本的)MSVC 中，那么我应该能够使用 scoped_allocator为 vector 提供不同的分配器和 forward_list .但是 a) 我不能依赖 unordered_set成为 vector<forward_list>可移植代码和 b) scoped_allocator是 Allocator而 monotonic_buffer_resource是 memory_resource , 阻抗不匹配将导致非常复杂的初始化。
或者我可以写一个 switch_memory_resource委托(delegate)给其他 memory_resource s 基于请求的大小。然后我可以使用 monotonic_buffer_resource对于与节点大小相匹配的请求(但是，我也不能便携地知道)和 default_memory_resource()对于其他一切。我可能会做出有根据的猜测，节点最多为 sizeof(struct {void* next; size_t hash; T value;})。 ，通过将其乘以 2 来添加一些误差范围，并将其用作两个 memory_resource 之间的截止值s，但我想知道是否有更清洁的方法？

Answer 1

几年前我提出并被 C++17 采用的少量具体资源类型是一组极简的有用分配器。正如您的问题所证明的那样，它们并没有为每种情况提供最佳行为。调音盘不多，我对缺少功能感到有些遗憾，但它们在大多数情况下仍然有用。
对于您的具体情况，您说“假设我无法 reserve() 摆脱这种情况，并且我实际上关心自增长以来旧桶列表留下的缓冲区资源中的漏洞。”我不确定任何通用分配器可以帮助你。桶列表的几何增长将在任何分配策略中留下漏洞。问题是这些孔是否可以重复使用和/或最小化。正如您所指出的，只有针对特定情况精心定制的分配器才能最大限度地减少这些漏洞。但也许你的假设太强了。
考虑 std::pmr::vector<int> .这是 monotonic_buffer_resource 的最坏情况。因为每次重新分配都会导致内存泄漏。然而，即使是这种情况，最坏情况下的内存浪费也只有 50%；也就是说，它使用的内存永远不会超过使用完美重用内存块的资源的两倍。诚然，50% 可能非常糟糕，但在你的场景中，我们说的要少得多。对于相当大的集合，与桶和数据本身相比，桶列表很小，您可以使用 reserve尽量减少重新分配。所以我的第一条建议是继续使用 monotonic_buffer_resource无需更改，并测量您是否有 Not Acceptable 内存使用。第二个实验是使用 unsynchronized_pool_resource由(上游)monotonic_buffer_resource 支持.
如果您决定为此目的创建一个自定义资源，这可能是富有成效的，甚至可能很有趣，那么您选择一些较低阈值来传递给单调分配器的方法可能会奏效，而且实际上不会付出很多努力。您还可以考虑使其具有自适应性:保留最后一个分配大小的列表，例如 4 个。如果任何大小的命中数超过两次，则假设它是您的节点大小并从单调资源分配这些节点，而其他请求则直接传递给上游资源。但是请注意，只有在您知道发生了什么时才使用这样的自定义分配器。如果您有 std::pmr::unordered_set<std::pmr::string> ，那么这两种方法都可能导致许多字符串从上游资源中分配，从而失去单调缓冲区的好处。如您所见，在您的遗愿 list 中过于吝啬内存可能会适得其反。您可能会发现未修改的 monotonic_buffer_resource是一个更好的选择。
祝你好运，请在此处报告您的发现。此外，如果您对可以解决您的问题(或任何其他常见分配问题)的通用资源有想法，我很想听听。标准中肯定有一些更有用的资源类型的空间。