Is there something similar to the copy-and-swap idiom when allocators are involved?

Question

There were a couple of great answers about the copy-and-swap idiom, e.g., explaining the copy and swap idiom and explaining move semantics. The basic idiom working for both copy and move assignment looks like this:

T& T::operator=(T other) {
    this->swap(other);
    return *this;
}

This assignment works for both copy and move assignment because other is copy or move constructed depending on whether the right hand side of the assignment is an lvalue or an rvalue.

Now let's have stateful allocators enter the picture: if T is parameterized on an allocator type like, e.g., std::vector<S, A>, the above idiom doesn't always work! Specifically, std::allocator_traits<A> contains three types indicating whether the allocator should be propagated:

1. std::allocator_traits<A>::propagate_on_container_copy_assignment
2. std::allocator_traits<A>::propagate_on_container_move_assignment
3. std::allocator_traits<A>::propagate_on_container_swap

The default for these three traits is std::false_type (see 20.6.8.1 [allocator.traits.types] paragraph 7, 8, and 9). The normal copy-and-swap idiom doesn't work if any of these traits is std::false_type and the allocators are stateful with the possibility of comparing unequal. For the copy assignment the fix is fairly straight forward:

T& T::operator= (T const& other) {
    T(other, this->get_allocator()).same_allocator_swap(*this);
    return *this;
}

That is, first the object is copied supplying the allocator object of the LHS and then the members are swapped using a function which works if both objects use the same allocator, i.e., when other.get_allocator() == this->get_allocator().

When move assigning it is desirable not to copy the RHS if it can be moved instead. The RHS can be moved if the allocators are identical. Otherwise the object needs to be copied with the appropriate allocator, leading to an assignment operator like this

T& T::operator= (T&& other) {
    T(std::move(other), this->get_allocator()).same_allocator_swap(*this);
    return *this;
}

The approach here is to move construct a temporary while also passing an allocator. Doing so assumes that the type T does have a "move constructor" taking both a T&& for the object state and an allocator to specify the allocator to be used. The burden is put on the move constructor to copy or move according to the allocators being different or identical.

Since the first argument is passed differently the copy and the move assignment can't be folded into just one version of the assignment operator. As a result they need to take their arguments as references and need to explicitly copy or move the arguments inhibiting the potential for copy elision.

Is there a better approach to deal with the assignment operators when allocators are involved?

Gibe

Answer 1

You seem to imply that the classic copy/swap idiom does work for the case that all of the propagate_on_ traits are not false. I don't believe this is the case. For example consider:

std::allocator_traits<A>::propagate_on_container_copy_assignment::value == true
std::allocator_traits<A>::propagate_on_container_swap::value == false

The classic copy/swap idiom assignment operator will not propagate the allocator from the rhs to the lhs, and will instead enter a state of undefined behavior if the two allocator states are not equal.

Your rewrite for the copy assignment operator also does not work this this combination of propagate_on_ traits, because it never propagates the allocator on copy assignment.

I do not believe the copy/swap idiom is advised if one wants to follow the rules for std::containers.

I keep an "allocator behavior" cheat sheet for myself that describes how these members should behave (in English as opposed to standard-eze).

copy assignment operator

If propagate_on_container_copy_assignment::value is true, copy assigns the allocators. In this case, if allocators are not equal prior to the assignment, then first deallocates all memory on the lhs. Then proceeds with copy assigning the values, without transferring any memory ownership. I.e. this->assign(rhs.begin(), rhs.end()).

move assignment operator

1. If propagate_on_container_move_assignment::value is true, deallocate all memory on the lhs, move assign the allocators, then transfer memory ownership from the rhs to the lhs.

2. If propagate_on_container_move_assignment::value is false, and the two allocators are equal, then deallocate all memory on the lhs, then transfer memory ownership from the rhs to the lhs.

3. If propagate_on_container_move_assignment::value is false, and the two allocators are not equal, move assign as if this->assign(make_move_iterator(rhs.begin()), make_move_iterator(rhs.end()).

These descriptions are intended to lead to the highest performance possible, while adhering to the C++11 rules for containers and allocators. Whenever possible, memory resources (such as vector capacity()) are either transferred from the rhs, or reused on the lhs.

The copy/swap idiom always throws away memory resources (such as vector capacity()) on the lhs, instead preemptively allocating such resources in a temporary just prior to deallocating them on the lhs.

For completeness:

swap

If propagate_on_container_swap::value is true, swaps allocators. Regardless, swaps memory ownership. The behavior is undefined if propagate_on_container_swap::value is false and the allocators are not equal.

Tea

OK, my attempt was clearly somewhat incomplete. Your description doesn't yield strong exception safe assignments, even for copy assignment (at least, under some conditions). The answer also implies that there is no reasonably simple recipe known which leverages functionality implemented in other methods. – Festatus

Agreed on the basic exception safety. That is the level specified for the std::containers. The move assignment operator can be marked noexcept if both propagate_on_container_move_assignment::value and is_nothrow_move_assignable<allocator_type>::value are true. And I would only say that I am not aware of a reasonably simple recipe known which leverages functionality implemented in other methods. :-) Somebody else might. My philosophy is to lavish loving care on each special member individually, and aim to implement each with = default as a first choice. – Tea

Question: I figured make_move_iterator unconditionally moves elements, however what if those elements are not noexcept movable and you flagged your container move noexcept as by propagate_on_container_move_assignment::value and is_nothrow_move_assignable<allocator_type>::value? Shouldn't you use std::move_if_noexcept for such cases? (I guess an iterator equivalent doesn't exist you would have to constexpr branch) – Kurtzig

lib++ makes vector move assignment noexcept conditional on propagate_on_container_move_assignment or Alloc:: is_always_equal. If condition #3 is the case, even noexcept movable of the value_type isn't sufficient as capacity of the lhs may need to be increased. For other containers similar issues also arise. – Tea

Answer 2

Special case: PMR aware containers

I've been dealing with pmr containers over the last few months and I really came to like them. So in the manner of @Howard Hinnant I made my own little boilerplate cheatsheed for a most efficient pmr-aware container in the hopes that somebody might find this helpful, as there are many things which need to be considered (and I don't even know if that's all of it...).

As we know we will only be dealing with a hardcoded std::byte allocator, we can make certain assumptions, most notably we never propagate allocators (except for DLS move see below)! This saves us from the checks. Here's my current implementation:

Demo

#include <memory_resource>

struct pmr_container
{
    using allocator_type = std::pmr::polymorphic_allocator<std::byte>;

    allocator_type get_allocator() const {
        return subcontainer_.get_allocator(); // 1) retrieve
    }

    explicit pmr_container(allocator_type allocator = {}) // 2) global allocator default
        :   subcontainer_( allocator )  // 3 parenthesis init
    { }

    pmr_container(const pmr_container& other, allocator_type allocator = {}) // 4 const ref
        :   subcontainer_( allocator )
    {
        operator=(other);
    }

    pmr_container(const pmr_container&& other) noexcept // 5) noexcept propagating move (DLS)
        :   subcontainer_( other.get_allocator() )
    {
        operator=(std::move(other));
    }

    pmr_container(const pmr_container&& other, allocator_type allocator) // 6) pmr aware move
        :   subcontainer_( allocator ) // 7 may be the same
    {
        operator=(std::move(other));
    }

    pmr_container& operator=(const pmr_container& other) {
        scalar_ = other.scalar_;
        subcontainer_ = other.subcontainer_;
        return *this;
    }

    pmr_container& operator=(pmr_container&& other) {
        // 8 relay check to data member
        scalar_ = std::move(other.scalar_); // Just for the looks
        subcontainer_ = std::move(other.subcontainer_);
        return *this;
    }

    // void* self_managed_ = nullptr;
    int scalar_ = 10;
    std::pmr::vector<std::pmr::string> subcontainer_;
};

int main()
{
    pmr_container a;
    pmr_container b = a;
    pmr_container c = std::move(b);
}

1. As we pushed allocator info into datamembers we don't waste storage storing them ourselves
2. Default initialization will result in global allocator (allocator = {})
3. Propagate allocator to member constructor. WARNING: DO NOT use curly braces + use explicit to prevent accidental construction of the container from allocators to suit e.g. vectors initializer_list constructor
4. Make sure to use const references for copy ctor to be able to bind to rvalue-refs (just a general hint
5. Use "dirty little secret" (DLS) (David Sankel) move constructor to allow for nothrow move assignements (otherwise copy ctor might be selected). This ctor always uses others memory resource.
6. Regular move ctor for use with pmr containers (containers will propagate their allocator e.g. in emplace_back()-calls)
7. While allocators probably are different this is not guaranteed. In case the allocators are the same we can actually do a "move". Otherwise we have to copy everything anyway.
8. In this simple case we don't even need to check if allocators are the same. This will be done for us in the managed resource (e.g. vector) if we invoke the right assignement operator.

Additional notes:

1. Self-managed resources. In case we actually do resource management ourselves (because std::pmr::unique_ptr doesn't exist yet :/) we actually would have to check for allocator equallity on assignement. I have not done any thinking into that but it shouldn't be to complicated (maybe I update this if someone needs it).

2. Other talks: @Pablo Halpers Talk Allocators: The Good Parts mentions certain concepts picked up here. However there are certain inefficies and possible misunderstandings that could lead to errors (from experience). 1) Most notably he implements the assignement operator in terms of swap(). If you use std::swap this will lead to circular dependency because swap will invoke the move ctor itself which in this and his example is implemented on the basis of the assignement operators. 2) He uses if &other == this check which is redundant in terms of the operations performed and just adds an additional branch overhead.

3. copy & swap: You can't use the copy and swap idiom because default containers won't allow you to. Citing cppreference:

polymorphic_allocator does not propagate on container copy assignment, move assignment, or swap. As a result, move assignment of a polymorphic_allocator-using container can throw, and swapping two polymorphic_allocator-using containers whose allocators do not compare equal results in undefined behavior.

Which basically says even if you would implement your own friend swap function overload for your container, you couldn't use std::swap and its overloads to swap the pmr-aware data members around without going to UB-land. Besides that, the swap idiom can make code up to 70% slower depending on container size ref.

Kurtzig