c++ - map 和 set 总是一次分配 1 个项目吗？

Question

我正在为 C++14 中的 std::map 和 std::set 实现一个分配器。分配器必须提供函数 pointer allocate(size_type n) 一次为 n 项分配空间。

经过一些测试，我发现 std::map 和 std::set 在我的平台上总是执行 allocate(1)，我还没有看到任何 n > 1。如果我考虑内部树表示，这对我来说很有意义。

标准是否保证这种行为？或者我可以安全地信任 n == 1 始终在任何特定平台上吗？

Answer 1

标准是否保证这种行为？

没有。该标准不保证这一点。

或者我可以在任何特定平台上始终安全地信任 n == 1 吗？

插入时分配的数量受容器方法复杂性的限制。例如，对于 std::map::insert，标准指定(来自 cppreference，仅前 3 个重载，插入单个元素):

1-3) Logarithmic in the size of the container, O(log(size())).

然后实现者可以自由选择满足此规范的实现。 log(size()) 部分是因为您需要找到插入的位置，并且为固定数量的元素分配空间只会增加复杂性。实现可以选择在每次调用时为两个元素分配空间。 2 与 1 一样不变。但是，不难发现分配 1 比分配 2 绝对值更有效的情况。此外，std::map 和 std::set 不需要将它们的元素存储在连续内存中。

因此，我假设它始终为 1，但您无法保证。如果你想确定你必须查看具体的实现，但是你依赖于实现细节。

allocate(n) 与 allocate(1) n 次不同。

A::allocate(n) 必须返回单个指针，因此分配非连续内存并非易事。然而，不要求此指针是 T*。相反，A::allocate(n) 返回一个 A::pointer。这可以是任何类型，只要它满足 NullablePointer、LegacyRandomAccessIterator 和 LegacyContiguousIterator。

cppreference提及 boost::interprocess::offset_ptr作为如何分配分段内存的示例。你可能想看看那个。这是完整的引述:

Fancy pointers

When the member type pointer is not a raw pointer type, it is commonly referred to as a "fancy pointer". Such pointers were introduced to support segmented memory architectures and are used today to access objects allocated in address spaces that differ from the homogeneous virtual address space that is accessed by raw pointers. An example of a fancy pointer is the mapping address-independent pointer boost::interprocess::offset_ptr, which makes it possible to allocate node-based data structures such as std::set in shared memory and memory mapped files mapped in different addresses in every process. Fancy pointers can be used independently of the allocator that provided them, through the class template std::pointer_traits.