Making use of allocators in a custom container class

Question

I'm developing a container-like class and I would like to make use of the standard allocator infrastructure much like the standard containers. On the net I find a lot of material about how to use the std::allocator class alone, or how to define a custom allocator for standard containers, but the material about how to make generically use of an standard conforming allocator is very rare, in particular in the context of C++11, where things seem to be much easier from the point of view of who writes a custom allocator, but more complex from the container's point of view.

So my question is about how to correctly make use of a standard conforming allocator in the most generic way, specifically:

• First of all, when should I design a custom container in this way? Is there a sensible performance overhead (including missing optimization opportunities) in using the default allocator instead of plain new/delete?
• Do I have to explicitly call contained objects' destructors?
• How do I discriminate between stateful and stateless allocators?
• How to handle stateful allocators?
  • When (if ever) are two instances interchangeable (when can I destroy with one instance the memory allocated with another one)?
  • They have to be copied when the container is copied?
  • They can/have to be moved when the container is moved?
  • In the container's move constructor and move assignment operator, when can I move the pointer to allocated memory, and when do I have to allocate different memory and move the elements instead?
• Are there issues about exception safety in this context?

I'm specifically interested in an answer about the C++11 world (does it change anything in C++14?)

Answer 1

In all answers below, I'm assuming you want to follow the rules for C++11 std-defined containers. The standard does not require you to write your custom containers this way.

• First of all, when should I design a custom container in this way? Is there a sensible performance overhead (including missing optimization opportunities) in using the default allocator instead of plain new/delete?

One of the most common and effective uses for custom allocators is to have it allocate off of the stack, for performance reasons. If your custom container can not accept such an allocator, then your clients will not be able to perform such an optimization.

• Do I have to explicitly call contained objects' destructors?

You have to explicitly call allocator_traits<allocator_type>::destroy(alloc, ptr), which in turn will either directly call the value_type's destructor, or will call the destroy member of the allocator_type.

• How do I discriminate between stateful and stateless allocators?

I would not bother. Just assume the allocator is stateful.

• How to handle stateful allocators?

Follow the rules laid out in C++11 very carefully. Especially those for allocator-aware containers specified in [container.requirements.general]. The rules are too numerous to list here. However I'm happy to answer specific questions on any of those rules. But step one is get a copy of the standard, and read it, at least the container requirements sections. I recommend the latest C++14 working draft for this purpose.

• When (if ever) are two instances interchangeable (when can I destroy with one instance the memory allocated with another one)?

If two allocators compare equal, then either can deallocate pointers allocated from the other. Copies (either by copy construction or copy assignment) are required to compare equal.

• They have to be copied when the container is copied?

Search the standard for propagate_on and select_on_container_copy_construction for the nitty gritty details. The nutshell answer is "it depends."

• They can/have to be moved when the container is moved?

Have to be for move construction. Move assignment depends on propagate_on_container_move_assignment.

• In the container's move constructor and move assignment operator, when can I move the pointer to allocated memory, and when do I have to allocate different memory and move the elements instead?

The newly move constructed container should have gotten its allocator by move constructing the rhs's allocator. These two allocators are required to compare equal. So you can transfer memory ownership for all allocated memory for which your container has a valid state for that pointer being nullptr in the rhs.

The move assignment operator is arguably the most complicated: The behavior depends on propagate_on_container_move_assignment and whether or not the two allocators compare equal. A more complete description is below in my "allocator cheat sheet."

• Are there issues about exception safety in this context?

Yes, tons. [allocator.requirements] lists the allocator requirements, which the container can depend on. This includes which operations can and can not throw.

You will also need to deal with the possibility that the allocator's pointer is not actually a value_type*. [allocator.requirements] is also the place to look for these details.

Good luck. This is not a beginner project. If you have more specific questions, post them to SO. To get started, go straight to the standard. I am not aware of any other authoritative source on the subject.

Here is a cheat-sheet I made for myself which describes allocator behavior, and the container's special members. It is written in English, not standard-eze. If you find any discrepancies between my cheat sheet, and the C++14 working draft, trust the working draft. One known discrepancy is that I've added noexcept specs in ways the standard has not.

---

Allocator behavior:

C() noexcept(is_nothrow_default_constructible<allocator_type>::value);

C(const C& c);

Gets allocator from alloc_traits::select_on_container_copy_construction(c).

C(const C& c, const allocator_type& a);

Gets allocator from a.

C(C&& c)
  noexcept(is_nothrow_move_constructible<allocator_type>::value && ...);

Gets allocator from move(c.get_allocator()), transfers resources.

C(C&& c, const allocator_type& a);

Gets allocator from a. Transfers resources if a == c.get_allocator(). Move constructs from each c[i] if a != c.get_allocator().

C& operator=(const C& c);

If alloc_traits::propagate_on_container_copy_assignment::value is true, copy assigns allocators. In this case, if allocators are not equal prior to assignment, dumps all resources from *this.

C& operator=(C&& c)
  noexcept(
    allocator_type::propagate_on_container_move_assignment::value &&
    is_nothrow_move_assignable<allocator_type>::value);

If alloc_traits::propagate_on_container_move_assignment::value is true, dumps resources, move assigns allocators, and transfers resources from c.

If alloc_traits::propagate_on_container_move_assignment::value is false and get_allocator() == c.get_allocator(), dumps resources, and transfers resources from c.

If alloc_traits::propagate_on_container_move_assignment::value is false and get_allocator() != c.get_allocator(), move assigns each c[i].

void swap(C& c)
  noexcept(!allocator_type::propagate_on_container_swap::value ||
           __is_nothrow_swappable<allocator_type>::value);

If alloc_traits::propagate_on_container_swap::value is true, swaps allocators. Regardless, swaps resources. Undefined behavior if the allocators are unequal and propagate_on_container_swap::value is false.