总是映射和设置分配1项吗？

Question

我采取一个allocator的std::map和std::set在C++ 14.分配器必须提供一次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)容器大小的对数,O(log(size())).

然后,实施者可以自由选择满足此规范的实现.这log(size())部分是因为您需要找到插入的位置,并为固定数量的元素分配空间只是对复杂性的不断贡献.实现可以选择每次调用它时为两个元素分配空间.2与1一样常数.但是,找到分配1比绝对值分配2更有效的情况应该不难.此外,std::map和std::set 不要求存储其在连续的存储元件.

因此,我认为它总是1,但你无法保证.如果你想确定你必须查看具体的实现,但是你依赖于实现细节.

allocate(n)和allocate(1)n次不一样.

A::allocate(n)必须返回单个指针,因此分配非连续内存并非易事.但是,没有要求该指针是a T*.而是A::allocate(n)返回一个A::pointer.这可以是任何类型,只要它满足NullablePointer,LegacyRandomAccessIterator和LegacyContiguousIterator.

cppreference提到boost :: interprocess :: offset_ptr作为如何分配分段内存的示例.你可能想看一下.这是完整的引用:

花哨的指针

当成员类型指针不是原始指针类型时,它通常被称为"花式指针".这样的指针被引入以支持分段存储器体系结构和用于今天访问该从由原始指针访问的均匀的虚拟地址空间的不同地址空间中分配的对象.花式指针的一个示例是与映射地址无关的指针boost :: interprocess :: offset_ptr,这使得可以在共享内存中分配基于节点的数据结构,例如std :: set,以及映射在不同地址中的内存映射文件.每个过程.通过类模板std :: pointer_traits,可以独立于提供它们的分配器使用花式指针.