Do map and set allocate 1 item at a time always?

Question

I am implementing an allocator for std::map and std::set in C++14. The allocator has to provide a function pointer allocate(size_type n) that allocates space for n items at a time.

After some tests, I have seen std::map and std::set always do allocate(1) on my platform, I have not seen any n > 1. It makes sense to me if I think about the internal tree representation.

Does the standard guarantee this behavior? Or can I safely trust n == 1 always in any specific platform?

Answer 1

Does the standard guarantee this behavior?

No. The standard does not guarantee this.

Or can I safely trust n == 1 always in any specific platform?

The number of allocations when instering is constrained by the complexity of the containers methods. For example, for std::map::insert the standard specifies (from cppreference, only first 3 overloads, inserting a single element):

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

Then the implementers are free to choose an implementation that fulfills this specification. The log(size()) part is because you need to find the place where to insert and allocating space for a fixed number of elements is just a constant contribution to complexity. An implementation could choose to allocate space for two elements every second time it is called. 2 is just as constant as 1. However, it shouldn't be too hard to find cases where allocating 1 is more efficient than allocating 2 in absolute terms. Moreover, std::map and std::set are not required to store their elements in contiguous memory.

Hence, I would assume that it is always 1, but you have no guarantee. If you want to be certain you have to look at the specific implementation, but then you rely on implementation details.

allocate(n) is not the same as allocate(1) n times.

A::allocate(n) must return a single pointer, hence it is not trivial to allocate non-contiguous memory. There is however no requirement that this pointer is a T*. Instead A::allocate(n) returns an A::pointer. This can be any type as long as it satisfies NullablePointer, LegacyRandomAccessIterator, and LegacyContiguousIterator.

cppreference mentions boost::interprocess::offset_ptr as an example of how to allocate segmented memory. You might want to take a look at that. Here is the full quote:

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.