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

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)?

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