map 和 set 总是一次分配 1 个项目吗？
Do map and set allocate 1 item at a time always?
我在 C++14 中为 std::map 和 std::set 实现分配器。分配器必须提供一个函数 pointer allocate(size_type n)，一次为 n 项分配 space。
经过一些测试，我看到 std::map 和 std::set 在我的平台上总是做 allocate(1)，我没有看到任何 n > 1。如果我考虑内部树表示，这对我来说很有意义。
标准是否保证这种行为？或者我可以安全地信任 n == 1 始终在任何特定平台上吗？
标准是否保证这种行为？
没有。该标准不保证这一点。
或者我可以在任何特定平台上始终安全地信任 n == 1 吗？
安装时分配的数量受容器方法复杂性的限制。例如，对于 std::map::insert，标准指定（来自 cppreference，仅前 3 个重载，插入单个元素）：
1-3) Logarithmic in the size of the container, O(log(size())).
然后实现者可以自由选择满足此规范的实现。 log(size()) 部分是因为您需要找到插入的位置，并且为固定数量的元素分配 space 只会增加复杂性。
一个实现可以选择在每次调用时为两个元素分配 space 。 2 与 1 一样不变。但是，不难发现分配 1 比分配 2 绝对值更有效的情况。此外，std::map 和 std::set 不需要将它们的元素存储在连续的内存中。
因此，我假设它始终为 1，但您不能保证。如果你想确定你必须查看具体的实现，但是你依赖于实现细节。
allocate(n)不等于allocate(1)n次
A::allocate(n) 必须 return 单个指针，因此分配非连续内存并非易事。然而，并不要求该指针是 T*。相反 A::allocate(n) return 是 A::pointer。这可以是任何类型，只要它满足 NullablePointer、LegacyRandomAccessIterator 和 LegacyContiguousIterator.
以cppreference mentions 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.
我在 C++14 中为 std::map 和 std::set 实现分配器。分配器必须提供一个函数 pointer allocate(size_type n)，一次为 n 项分配 space。
经过一些测试，我看到 std::map 和 std::set 在我的平台上总是做 allocate(1)，我没有看到任何 n > 1。如果我考虑内部树表示，这对我来说很有意义。
标准是否保证这种行为？或者我可以安全地信任 n == 1 始终在任何特定平台上吗？
标准是否保证这种行为？
没有。该标准不保证这一点。
或者我可以在任何特定平台上始终安全地信任 n == 1 吗？
安装时分配的数量受容器方法复杂性的限制。例如，对于 std::map::insert，标准指定（来自 cppreference，仅前 3 个重载，插入单个元素）：
1-3) Logarithmic in the size of the container, O(log(size())).
然后实现者可以自由选择满足此规范的实现。 log(size()) 部分是因为您需要找到插入的位置，并且为固定数量的元素分配 space 只会增加复杂性。
一个实现可以选择在每次调用时为两个元素分配 space 。 2 与 1 一样不变。但是，不难发现分配 1 比分配 2 绝对值更有效的情况。此外，std::map 和 std::set 不需要将它们的元素存储在连续的内存中。
因此，我假设它始终为 1，但您不能保证。如果你想确定你必须查看具体的实现，但是你依赖于实现细节。
allocate(n)不等于allocate(1)n次
A::allocate(n) 必须 return 单个指针，因此分配非连续内存并非易事。然而，并不要求该指针是 T*。相反 A::allocate(n) return 是 A::pointer。这可以是任何类型，只要它满足 NullablePointer、LegacyRandomAccessIterator 和 LegacyContiguousIterator.
cppreference mentions 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.