Idiom for obeying propagate_on_copy_assignment in Container without allocator

Question

Suppose you have a Container which internally uses other standard containers to form more complex data structures. Thankfully, the standard containers are already designed to do all the necessary work to ensure allocators are copied/assigned etc.

So, normally if we have some Container c, and internally it has an std::vector<int>, we can write a copy-assignment operator that just says:

Container& operator = (const Container& c) { m_vec = c.m_vec; return *this; }

In fact we don't even have to write that (since it's just what the default copy assignment operator does), but let's just say that in this case there's some extra required logic that the default operator wouldn't do:

Container& operator = (const Container& c) 
{
   /* some other stuff... */
   m_vec = c.m_vec;
   return *this; 
}

So, in this case there's no problem because the vector assignment operator does all the work for us to make sure that allocators are properly copied-on-assignment or not copied.

But... what if we have a vector which we can't simply copy-assign. Suppose it is a vector of pointers to some other internal structure.

Say we have an internal vector which holds pointers: std::vector<node*, Alloc>

So, normally in our copy-assignment operator, we'd have to say:

Container& operator = (const Container& other) 
{
   vector<node*, Alloc>::allocator_type alloc = m_vec.get_allocator();
   for (auto it = m_vec.begin(); it != m_vec.end(); ++it) alloc.deallocate(*it);
   m_vec.clear();

   for (auto it = other.m_vec.begin(); it != other.m_vec.end(); ++it)
   {
     node* n = alloc.allocate(1); // this is wrong, we might need to use other.get_allocator() here!
     alloc.construct(n, *(*it));
     m_vec.push_back(n);
   }

   return *this; 
}

So in the above example, we need to manually deallocate all the node objects in m_vec, and then construct new node objects from the RHS container. (Note that I'm using the same allocator object the vector uses internally in order to allocate node objects.)

But if we want to be standards compliant here and AllocatorAware, we need to check if allocator_traits<std::vector<node*, Alloc>::allocator_type> sets propagate_on_container_copy_assign to true. If it does, we need to use the other container's allocator to construct the copied nodes.

But... our container type Container doesn't use it's own allocator. It just uses an internal std::vector... so how can we tell our internal std::vector instance to use a copied allocator if necessary? The vector doesn't have something like a "use_allocator" or "set_allocator" member function.

So, the only thing I came up with is something like:

if (std::allocator_traits<Alloc>::propagate_on_container_copy_assignment::value)
{
   m_vec = std::vector<node*, Alloc>(other.get_allocator());
}

...and then we could construct our nodes with the return value of m_vec.get_allocator();

Is this a valid idiom for creating an allocator aware container that doesn't keep it's own allocator, but rather defers to an internal standard container?

Answer 1

One problem with using swap to implement copy assignment in this example is that if propagate_on_assignment == true_type and propagate_on_container_swap == false_type, then the allocator is not propagated from other to *this, because the swap refuses to do so.

A second problem with this approach is that if both propagate_on_assignment and propagate_on_container_swap == true_type but other.m_vec.get_allocator() != m_vec.get_allocator(), then you do propagate the allocator but you get undefined behavior at the point of swap.

To do this right, you really need to design your operator= from first principals. For this exercise I'm assuming that Container looks something like this:

template <class T, class Alloc>
struct Container
{
    using value_type = T;
    static_assert(std::is_same<typename Alloc::value_type, value_type>{}, "");
    using allocator_type = Alloc;

    struct node {};
    using NodePtr = typename std::pointer_traits<
              typename std::allocator_traits<allocator_type>::pointer>::template
                                                                   rebind<node>;
    using NodePtrAlloc = typename std::allocator_traits<allocator_type>::template
                                                          rebind_alloc<NodePtr>;
    std::vector<NodePtr, NodePtrAlloc> m_vec;
    // ...

I.e. Container is templated on T and Alloc, and that the implementation allows for the possibility that Alloc is using "fancy pointers" (i.e. node* is actually a class type).

In this event, here is what the Container copy assignment operator might look like:

Container&
operator = (const Container& other) 
{
    if (this != &other)
    {
        using NodeAlloc = typename std::allocator_traits<NodePtrAlloc>::template
                                                                 rebind_alloc<node>;
        using NodeTraits = std::allocator_traits<NodeAlloc>;

        NodeAlloc alloc = m_vec.get_allocator();
        for (auto node_ptr : m_vec)
        {
            NodeTraits::destroy(alloc, std::addressof(*node_ptr));
            NodeTraits::deallocate(alloc, node_ptr, 1);
        }
        if (typename NodeTraits::propagate_on_container_copy_assignment{})
            m_vec = other.m_vec;
        m_vec.clear();
        m_vec.reserve(other.m_vec.size());
        NodeAlloc alloc2 = m_vec.get_allocator();
        for (auto node_ptr : other.m_vec)
        {
            using deleter = allocator_deleter<NodeAlloc>;
            deleter hold{alloc2, 1};
            std::unique_ptr<node, deleter&> n{NodeTraits::allocate(alloc2, 1),
                                              hold};
            NodeTraits::construct(alloc2, std::addressof(*n), *node_ptr);
            hold.constructed = true;
            m_vec.push_back(n.get());
            n.release();
        }
    }
    return *this; 
}

Explanation:

In order to allocate and deallocate memory with a compatible allocator, we need to use std::allocator_traits to create an "allocator<node>". This is named NodeAlloc in the above example. It is also convenient to form traits for this allocator, termed NodeTraits above.

The first job is to a converted copy of the lhs allocator (converted from allocator<node*> to allocator<node>), and use that allocator to both destroy and deallocate the lhs nodes. std::addressof is needed to convert the possibly "fancy pointer" to an actual node* in the call to destroy.

Next, and this is a bit subtle, we need to propagate m_vec.get_allocator() to m_vec, but only if propagate_on_container_copy_assignment is true. The copy assignment operator of the vector is the best way to do this. This unnecessarily copy some NodePtrs, however I still believe this is the best way to get that allocator propagated. We could also do the vector assignment if propagate_on_container_copy_assignment is false, thus avoiding the if-statement. The assignment would not propagate the allocator if propagate_on_container_copy_assignment is false, but then we still might assign some NodePtrs, when all we really need is a no-op.

If propagate_on_container_copy_assignment is true, and the two allocators are unequal, the vector copy assignment operator will correctly handle dumping the lhs resources for us prior to assigning the allocators. This is a complication that is easy to overlook, and thus best left up to the vector copy assignment operator.

If propagate_on_container_copy_assignment is false, that means we don't need to worry about the case where we have unequal allocators. We aren't going to swap any resources.

In any event, after doing this, we should clear() the lhs. This operation does not dump capacity() and so is not wasteful. At this point we have a zero-sized lhs with the correct allocator, and perhaps even some non-zero capacity() to play with.

As an optimization we can reserve with other.size(), in case the lhs capacity is not sufficient. This line is not necessary for correctness. It is a pure optimization.

Just in case m_vec.get_allocator() might now return a new allocator, we go ahead and get a fresh copy of it, named alloc2 above.

We can now use alloc2 to allocate, construct, and store new nodes which are copy constructed from the rhs.

To be exception safe, we should use an RAII device to hold the allocated pointer while we construct into it, and push_back it into the vector. Either the construction can throw, as can the push_back(). The RAII device must be aware of whether it needs to just deallocate, or both destruct and deallocate in an exception circumstance. The RAII device also needs to be "fancy pointer"-aware. It turns out that it is very easy to build all of this using std::unique_ptr combined with a custom deleter:

template <class Alloc>
class allocator_deleter
{
    using traits = std::allocator_traits<Alloc>;
public:
    using pointer   = typename traits::pointer;
    using size_type = typename traits::size_type;
private:
    Alloc& alloc_;
    size_type s_;
public:
    bool constructed = false;

    allocator_deleter(Alloc& a, size_type s) noexcept
        : alloc_(a)
        , s_(s)
    {}

    void
    operator()(pointer p) noexcept
    {
        if (constructed)
            traits::destroy(alloc_, std::addressof(*p));
        traits::deallocate(alloc_, p, s_);
    }
};

Note the consistent use of std::allocator_traits for all accesses to the allocator. This allows std::allocator_traits to provide defaults so that the author of Alloc need not provide them. For example std::allocator_traits can provide default implementations for construct, destroy, and propagate_on_container_copy_assignment.

Also note the consistent avoidance of the assumption that NodePtr is a node*.

Answer 2

It seems reasonable to leverage existing functionality. Personally, I would go a step further and actually leverage an existing implementation to do the copy. Generally, it seems a suitable copy-and-swap idiom is the easiest approach to implement copy assign:

Container& Container::operator= (Container const& other) {
    Container(other,
              std::allocator_traits<Alloc>::propagate_on_assignment
              ? other.get_allocator()
              : this->get_allocator()).swap(*this);
    return *this;
}

This approach makes a few assumptions, though:

1. The copy constructor is implemented in a form which [optionally] gets an allocator passed:

   Container::Container(Container const& other, Alloc allcoator = Alloc()));
   

2. It assumes that the swap() appropriately swaps the allocator.

It is worth pointing out that this approach has the advantage of being reasonably simple and providing a strong exception guarantee but it uses newly allocated memory. If the memory of the LHS object is reused it may result in better performance, e.g., because the used memory is already resonably close to the processor. That is, for an initial implementation I would use the copy and swap implementation (using an extended copy constructor as mentioned above) and replace it by a more involved implementation if profiling indicates that's needed.