Authoring a container to work with both c++11 and pmr allocators

Question

How do I correctly create a container that works with both, C++11 and C++17 polymorphic allocators? Here's what I have so far (as a generic boilerplate template):

Explanation: I've included two fields, res_ which shows how dynamic memory is managed directly from the container, whereas field vec_ is used to demonstrate how the allocator propagates downwards. I've taken a lot from Pablo Halpern's talk Allocators: The Good Parts but he mainly talks about pmr allocators, not the c++11 ones.

Demo

#include <cstdio>
#include <vector>
#include <memory>
#include <memory_resource>


template <typename T, typename Allocator = std::allocator<T>>
struct MyContainer {

    auto get_allocator() const -> Allocator {
        return vec_.get_allocator();
    }

    MyContainer(Allocator allocator = {})
        : vec_{ allocator }
    {}

    MyContainer(T val, Allocator allocator = {})
        : MyContainer(allocator)
    {
        res_ = std::allocator_traits<Allocator>::allocate(allocator, sizeof(T));
        std::allocator_traits<Allocator>::construct(allocator, res_, std::move(val));
    }

    ~MyContainer() {
        Allocator allocator = get_allocator();
        std::allocator_traits<Allocator>::destroy(allocator, std::addressof(res_));
        std::allocator_traits<Allocator>::deallocate(allocator, res_, sizeof(T));
        res_ = nullptr;
    }

    MyContainer(const MyContainer& other, Allocator allocator = {})
        : MyContainer(allocator)
    {
        operator=(other);
    }

    MyContainer(MyContainer&& other) noexcept
        : MyContainer(other.get_allocator())
    {
        operator=(std::move(other));
    }

    MyContainer(MyContainer&& other, Allocator allocator = {})
        : MyContainer(allocator)
    {
        operator=(std::move(other));
    }

    auto operator=(MyContainer&& other) -> MyContainer& {
        if (other.get_allocator() == get_allocator()) {
            std::swap(*this, other);
        } else {
            operator=(other); // Copy assign
        }
    }

    auto operator=(const MyContainer& other) -> MyContainer& {
        if (other != this) {
            std::allocator_traits<Allocator>::construct(get_allocator(), std::addressof(vec_), vec_);
            std::allocator_traits<Allocator>::construct(get_allocator(), std::addressof(res_), other);
        }
        return *this;
    }
    
private:
    std::vector<T, Allocator> vec_; // Propagation
    T* res_ = nullptr;
};

int main() {
    MyContainer<std::string, std::pmr::polymorphic_allocator<std::byte>> ctr1 = std::string{"Hello World!"};

    MyContainer<double> ctr2 = 2.5;
}

However even this doesn't work as planned, as vector expects its value type to match that of the allocator:

<source>:67:31:   required from 'struct MyContainer<std::__cxx11::basic_string<char>, std::pmr::polymorphic_allocator<std::byte> >'
<source>:72:74:   required from here
/opt/compiler-explorer/gcc-13.1.0/include/c++/13.1.0/bits/stl_vector.h:438:64: error: static assertion failed: std::vector must have the same value_type as its allocator
  438 |       static_assert(is_same<typename _Alloc::value_type, _Tp>::value,
      | 

What else am I missing? Should I maybe propagate differently based on allocator's propagation traits (is this required for generic containers)?

Answer 1

tl;dr

• All standard library containers must be given an allocator with a value_type that is the same as the value_type of the container; otherwise it would be ill-formed.
  So in this case one would need to either use a std::pmr::polymorphic_allocator<std::string> for MyContainer, or rebind the allocator type before passing it to std::vector, e.g.:

  // option 1
  MyContainer<std::string, std::pmr::polymorphic_allocator<std::string>> ctr1 = /* ... */;
  
  // option 2
  template <class T, class Allocator = std::allocator<T>>
  struct MyContainer {
      // ...
  private:
      std::vector<T, typename std::allocator_traits<Allocator>::template rebind_alloc<T>> vec_;
  };
  
  MyContainer<std::string, std::pmr::polymorphic_allocator<std::byte>> ctr1 = /* ... */;
  

• This is not a problem in the video you linked, because it defines a user-defined container, so it does not matter that it is not an allocator-aware container.
• Implementing a container class that can handle both std::polymorphic_allocator and std::allocator is comparatively easy - both satisfy the named requirement Allocator, so the special sauce needed in this case is just to do nothing special - implement them as a bog-standard allocator (basically use std::allocator_traits<Alloc> for all interactions with the allocator)
  • This does include manually checking the propagation preferences of the allocator (implement them exactly as described in the table "Influence on container operations" on the Allocator requirements page)

---

1. Why the given code example is ill-formed

All containers that are allocator-aware containers must have an allocator with a value_type that is the same as the value_type of the container.

This is mandated in the standard by: (emphasis mine)

24.2.2.5 Allocator-aware containers (4)
⁽³⁾ In this subclause,
^(3.1) - X denotes an allocator-aware container class with a value_type of T using an allocator of type A,
[...] A type X meets the allocator-aware container requirements if X meets the container requirements and the following types, statements, and expressions are well-formed and have the specified semantics.

typename X::allocator_type

• ⁽⁴⁾ Result: A
• ⁽⁵⁾ Mandates: allocator_type​::​value_type is the same as X​::​value_type.

So the following statement must always be true for an allocator-aware container:

static_assert(
    std::same_as<
        Container::value_type,
        Container::allocator_type::value_type
    >
);

---

Note that all containers defined in the standard library (except std::array) are mandated to be allocator-aware. (see 24.2.2.5 (1) Allocator-aware containers)

---

Note that in your example that statement will not be satisfied:

// Hypothetical, won't compile
using Container = std::vector<std::string, std::pmr::polymorphic_allocator<std::byte>>;

// will be std::string
using ContainerValueType = Container::value_type;
// will be std::byte (std::pmr::polymorphic_allocator<std::byte>::value_type)
using AllocatorValueType = Container::allocator_type::value_type;

// would fail
static_assert(std::same_as<ContainerValueType, AllocatorValueType>);

• So this version of std::vector would not be an allocator-aware container (because it doesn't fulfill this requirement)
• But the standard mandates that std::vector must be an allocator-aware container

=> This is ill-formed due to contradiction in the standard.

Note that this also matches the error message you got from gcc:

error: static assertion failed: std::vector must have the same value_type as its allocator

---

2. Why it's not a problem in the linked video

The Youtube Video you linked in the comments (CppCon 2017: Pablo Halpern “Allocators: The Good Parts”) is about a user-defined container class that does not utilize any standard library containers.

There are no rules that the standard imposes for user-defined container types, so one can basically do whatever one wants there.

Here's a small transcript of the class the talk is about:

template<class Tp>
class slist {
public:
  using value_type = Tp;
  using reference = value_type&;
  // ...
  // non-template use of polymorphic_allocator
  using allocator_type = std::pmr::polymorphic_allocator<std::byte>;

  // Constructors
  // Every constructor has an variant taking an allocator
  slist(allocator_type a = {});
  slist(const slist& other, allocator_type a = {});
  slist(slist&& other);
  slist(slist&& other, allocator_type a = {});

  // ...
};

Note that the allocator_type is hardcoded to std::pmr::polymorphic_allocator<std::byte>, so allocator_type::value_type will generally not match slist::value_type (except the case where both are std::byte);

So this container does not satisfy the requirements of an allocator-aware container most of the time.
But there's also no requirement for it to do so.
=> well-formed

^{Note: It would be ill-formed if one would pass e.g. an slist<> to a function that mandates that its parameter must be an allocator-aware container. - But as long as one avoids that there's no issue with defining almost-conforming containers.}

---

3. How to write a container that works with any allocator

Note that std::pmr::polymorphic_allocator satisfies the named requirement Allocator, exactly like std::allocator does.
(All allocators that are intended to be used with standard containers must satisfy that requirement)

So the trick to support both is just to do nothing special - treat the std::pmr::polymorphic_allocator like any other allocator, since it's just that. (use std::allocator_traits<Alloc> for basically everything)

Note that this also means that you should respect the std::allocator_traits<Allocator>::propagate_on_ container_copy / container_move_assignment / container_swap values.
Which for polymorphic_allocator means that the allocator should not propagate when copying / moving / swapping the container.
Because doing so can lead to surprising lifetime issues - see for example this answer.

(Of course those should always be respected, not only just for polymorphic_allocators)

Answer 2

I've spent the last day assembling any resource I've found about allocators and came up with a generic design. I will post it here, someone might find it helpful.

Generic stl-like allocator aware container implementation

Demo

#include <cstdio>
#include <vector>
#include <memory>
#include <memory_resource>
#include <type_traits> /* is_nothrow_swappable */


template <typename T, typename Allocator = std::allocator<T>>
struct MyContainer {
    using allocator_type = Allocator;
    using alloc_traits = typename std::allocator_traits<Allocator>;

    auto get_allocator() const -> Allocator& {
        return allocator_;
    }

    MyContainer(Allocator allocator = {})
        : vec_{ allocator }
    {}

    MyContainer(T val, Allocator allocator = {})
        : MyContainer(allocator)
    {
        res_ = alloc_traits::allocate(allocator_, sizeof(T));
        alloc_traits::construct(allocator_, res_, std::move(val));
    }

    ~MyContainer() {
        if (res_) {
            alloc_traits::destroy(allocator_, res_);
            alloc_traits::deallocate(allocator_, res_, sizeof(T));
        }
    }

    MyContainer(const MyContainer& other, Allocator allocator = {})
        : MyContainer(allocator)
    {
        // Copy resource
        res_ = alloc_traits::allocate(allocator_, sizeof(T));
        alloc_traits::construct(allocator_, res_, *other.res_);
        // Copy types with value semantics
        vec_ = other.vec_;
    }

    MyContainer(MyContainer&& other) noexcept
        : MyContainer(std::move(other), other.get_allocator())
    {}

    MyContainer(MyContainer&& other, Allocator allocator = {})
        : MyContainer(allocator)
    {
        // Move resource
        res_ = std::move(other.res_);
        other.res_ = nullptr;
        // Move types with value semantics
        vec_ = std::move(other.vec_);
    }

    auto operator=(MyContainer&& other) noexcept(
            std::conjunction_v<alloc_traits::propagate_on_container_move_assignment,
            std::is_nothrow_move_assignable<Allocator>>) -> MyContainer&
    {
        if constexpr(std::disjunction_v<
            typename alloc_traits::propagate_on_container_move_assignment,
            typename alloc_traits::is_always_equal>)
        {
            MyContainer tmp{ std::move(other), allocator_ };
            swap_data_(tmp);
            allocator_ = std::move(other.allocator_);
        } else {
            if (allocator_ != other.allocator_) {
                // Must copy
                MyContainer tmp{ other, allocator_ };
                swap_data_(tmp);
            } else {
                MyContainer tmp{ std::move(other), allocator_ };
                swap_data_(tmp);
            }
        }
        return *this;
    }

    auto operator=(const MyContainer& other) -> MyContainer& {
        // copy construct from other with our allocator
        MyContainer tmp(other, allocator_);
        swap_data_(tmp);
        if constexpr (alloc_traits::propagate_on_container_copy_assignment::value) {
            allocator_ = other.allocator_;
        }
        return *this;
    }

    auto swap(MyContainer& other) noexcept -> void {
        // UB in case propagate_on_container_swap is true and allocators are not the same
        // However no assert triggered as this could be weirdly intended by a knowing user
        swap_data_(other);
        if constexpr (alloc_traits::propagate_on_container_swap) {
            swap(allocator_, other.allocator_); // Swap always noexcept
        }
    }

    friend auto swap(MyContainer& lhs, MyContainer& rhs) -> void {
        lhs.swap(rhs);
    }
    
private:

    auto swap_data_(MyContainer& other) noexcept {
        // TBAA information for compiler optimization will not be lost unless
        // unqualified swap uses XOR swap semantics.
        swap(other.res_, res_);
        swap(other.vec_, vec_);
    }

    std::vector<T, Allocator> vec_; // To model propagation
    T* res_ = nullptr;
#ifdef _MSC_VER
    [[msvc::no_unique_address]]
#else
    [[no_unique_address]]
#endif
    Allocator allocator_;
};

int main() {
    // MyContainer<int, std::pmr::polymorphic_allocator<int>> ctr1 = 5;
    MyContainer<std::string, std::pmr::polymorphic_allocator<std::string>> ctr1 = std::string{"Hello World!"};
    MyContainer<double> ctr2 = 2.5;
}

Notes:

General shape:

• The container takes an allocator type template argument, which necessarily means that containers using a different allocator type will be a different type entirely (meaning they will not be move/copy/swap-able to each other at all).
• All resource management (allocating / freeing of memory + constructing / destroying of objects) must be done through the allocator interface std::allocator_traits<Allocator>. You can never use allocator->allocate() directly as std::allocator_traits provides defaults even for std::allocator<T> (the default allocator) which are not necessarily available in the type!
• private inheritance from the allocator allows for empty base optimization so stateless allocators don't take up space (note stl-containers sometimes store allocator in a sentinel node / unoccupied data section). This requires a non-const allocator& to be retrievable through static_cast in get_alloc_();

Allocator propagation:

Unfortunately, allocators have a customization point in which they are allowed to propagate to other containers on the three operations move, copy and swap, which in hindsight caused only harm but if we want to conform to the stl we need to account for these cases:

• move: b.allocator will be move assigned to a.allocator in case propagate_on_container_move_assignment::value is true
• copy: b.allocator will be copied to a.allocator in case propagate_on_container_copy_assignment::value is true
• swap: a.allocator will be swaped with b.allocator in case propagate_on_container_swap::value is true

Constructors

• Constructors can generally be easily implemented in terms of assignement operators and a delegating constructor, which gobbles up the optional allocator argument.
• The move ctor needs to be twofold as in some cases move cannot be noexcept (in case allocators differ the move assignement operator needs to copy data over to new memory arena which might throw). Noexcept move is only possible if the allocator is the same (runtime check) OR the allocator is knowingly duplicated (in which case we know it's the same).

move assignement

Check out Howard Hinnant's brilliant answer here.

• Problem: Container elements are allocated by one container and deallocated by the other container after move. In case different allocators perform the allocation / deallocation on one element this is officially UB!
• If allocators are the same from the start or we know that other.allocator propagates to us (can be checked at compile-time, alloc_traits::propagate_on_container_move_assignment::value is true) this is no problem, we can move.
• But if allocators mismatch and other.allocator doesn't propagate we must copy construct all elements to the new memory arena using our allocator.

copy assignement

• Copy allocator first if alloc_traits::propagate_on_container_copy_assignment::value evaluates to true.
• Then copy assign all elements from the other container.

swap

• Swap must never throw (is always noexcept according to standard), hence we cannot do fancy copy stuff (as this would allocate / construct which could throw). This means it's only actually possible to really swap if allocators are the same or propagated on swap (alloc_traits::propagate_on_container_swap).
• We could choose to assert here (as is done by libstdc++) but that would potentially hinder an experienced user who made sure his two allocators work with each other, so my take is to leave it to the user to make his containers well defined.
• Include friend swap that is found by ADL so that we correspond to idiomatic unqualified swap principle.
• needs an internal function swap_data() that only swaps the guts of our container without allocator, as allocators are conditionally swapped.

noexcept

• Swap is always noexcept as defined by the standard (§23.2.1[container.requirements.general] sections 8 and 10). Swap will presumably use noexcept move through unqualified swap-calls to the member fields to exchange internal member fields.
• The move assignment operator can be marked noexcept only if both propagate_on_container_move_assignment::value and is_nothrow_move_assignable<allocator_type>::value evaluate to true (as the allocator is also moved to the new object in case).
• Copy assignement / construction can never guarantee noexcept as it allocates and constructs new elements, i.e. asks for system memory and calls constructors. Could in theory be noexcept only if the container is still empty, but runtime checks are not supported by C++.
• The move constructor can only be noexcept if we know allocators are the same and we can noexcept move the elements, hence we include an extended move ctor that can't guarantee that as it takes an allocator argument to leave the default move ctor noexcept. The extended move ctor could be noexcept if alloctors compare equal but runtime checks are not supported by C++.

Exception safety, copy & swap:

• The copy & swap - idiom cannot be used in stl-conforming allocater aware containers as the idiom foresees implementing the assignement operators based on copy/move constructor. However, the allocator propagation traits might differ between copy/move assignement, so those need to be seperated. Copy & swap can however still be implemented for fields excluding allocator in the move_assign_()-method.
• Only basic exception safety can be given (as is the standard for stl-containers).

Unresolved questions:

• Would it be theoretically possible that an object is copy/move constructed with a certain allocator which is then switched for a propagating allocator from the other object right away? (potential optimization point).
• Is it necessary to include an additional branch to check for self assignement (note: the branch would be repeated by copy ctor as it delegates to operator=(&))?
• Possible inefficiency as we runtime dispatch on allocator equality in case of noexcept move because we delegate to operator=(&&). Maybe call move_assign_ directly?
• noexcept move with extended move constructor looks like conditionally possible if allocators propagate anyway OR compare always equal.
• In case other core data also stores an allocator (e.g. is an stl-container), we can push our allocator to the leaf and retrieve it from there to save cache. For this to work, the allocators within a container hierarchy must always match up (I must look into this more to make sure this is the case for above implementation!)

Maybe someone can help me with the last questions!

rev1

I added changed things that came to mind:

• cppreference says that noexcept functions may call functions that throw an exception. I used this to delegate to the extended move ctor without losing optimization (for conciseness):

Note that a noexcept specification on a function is not a compile-time check; it is merely a method for a programmer to inform the compiler whether or not a function should throw exceptions.

• I fixed resource allocation. Previously I had just an empty assign() function, but ofc this needed implementation.
• Fixed a few overheads: -- nulling the res pointer in case of destruction -- check for allocator equality when move constructing when allocator is propagated anyway.
• Fixed bug: I noticed that I cannot delegate from constructors to assignement as this would check for propagation traits (which allows the weird behaviour of constructing with one allocator then propagating the allocator from the other object right away)
• I used copy & swap idiom now also for copy assignement which gets rid of an extra free_res_() function and adds exception safety. I will have to check again but I think assignement has now strong exception safety.
• used C++20 feature no_unique_address as a more elegant way to address allocator storage for empty allocator types.

Sources:

• AllocatorAwareContainer: Introduction and pitfalls of propagate_on_container_XXX defaults
• Is there something similar to the copy-and-swap idiom when allocators are involved?
• libstdc++ vector
• libc++ vector