Allocator propagation policies in your new modern

问题:

What is the reason for having these traits in a container (https://en.cppreference.com/w/cpp/memory/allocator_traits)

propagate_on_container_copy_assignment  Alloc::propagate_on_container_copy_assignment if present, otherwise std::false_type
propagate_on_container_move_assignment  Alloc::propagate_on_container_move_assignment if present, otherwise std::false_type
propagate_on_container_swap             Alloc::propagate_on_container_swap if present, otherwise std::false_type

is_always_equal(since C++17)            Alloc::is_always_equal if present, otherwise std::is_empty<Alloc>::type

I understand that the container implementation will behave in one way or another in their implementation of assignment and swap. (and that handling of these case is horrible code.) I also understand that sometimes one might need to leave the move-from container in a state that is resizeble or that at least some very last deallocation can be called, so the allocator can't be left invalid. (I personally think that is a weak argument.)

But the question is, Why can't that information be already part of the normal implementation an semantics of the custom allocator type itself?

I mean, container copy-assignment can try copy-assign the source allocator, and if that syntactic copy assign doesn't really copy, then, well, it is like saying that your container doesn't propagate_on_container_copy_assignment.

In the same way instead of using is_always_equal one can actually make the allocator assignment do nothing.

(Besides, if is_always_equal is true one can make operator== for allocators return std::true_type to signal that.)

It looks to me that these traits seem to try override the semantics that one can give to the custom allocator by normal C++ means. This seems to play against generic programming and the current C++ philosophy.

The only reason, I can think of this can be useful to fulfill some kind of backward compatibility with "old" containers.

If I were to write a new container and/or an new non-trivial allocator today, can I rely on the sematics of the allocator and forget about these traits?

In my view, as long as the moved-from allocator can "deallocate" a null pointer state (which means mostly to do nothing in this case), then it should be fine, and if resize throws that is fine (valid) too, it simply means that the allocator doesn't have access to its heap anymore.

---

EDIT: In practical terms, Can I write the containers simply this way? and delegate the complexity to the semantics of the custom allocators?:

templata<class Allocator>
struct my_container{
  Allocator alloc_;
  ...
  my_container& operator=(my_container const& other){
    alloc_ = other.alloc_; // if allocator is_always_equal equal this is ok, if allocator shouldn't propagate on copy, Alloc::operator=(Alloc const&) simply shouldn't do anything in the first place
    ... handle copy...
    return *this;
  }
  my_container& operator=(my_container&& other){
    alloc_ = std::move(other.alloc_); // if allocator shouldn't propagate on move then Alloc::operator=(Alloc&&) simply shouldn't do anything.
    ... handle move...
    return *this;
  }
  void swap(my_container& other){
     using std::swap;
     swap(alloc, other.alloc); //again, we assume that this does the correct thing (including not actually swapping anything if that is the desired criteria. (that would be the case equivalent to `propagate_on_container_swap==std::false_type`)
     ... handle swap...
  }
}

I think the only true requirement to an allocator is that, a moved-from allocator should be able to do this.

my_allocator a2(std::move(a1));
a1.deallocate(nullptr, 0); // should ok, so moved-from container is destructed (without exception)
a1.allocate(n); // well defined behavior, (including possibly throwing bad_alloc).

回答1:

Nicol Bolas's answer is very accurate. I would say it like this:

• An allocator is a handle to a heap. It's a value-semantic type, just like a pointer or an int or a string. When you copy an allocator, you get a copy of its value. Copies compare equal. This works for allocators just like it works for pointers or ints or strings.

• One thing you can do with an allocator is pass it around to different algorithms and data structures using pure value semantics. The STL doesn't have much in this department, but it does have e.g. allocate_shared.

• Another thing you can do with an allocator is give it to an STL container. You give the allocator to the container during construction of the container. At certain points during its lifetime, the container will encounter other allocators, and it will have to make a choice.

---

A<int> originalAlloc = ...;
std::vector<int, A<int>> johnny(originalAlloc);

A<int> strangeAlloc = ...;
std::vector<int, A<int>> pusher(strangeAlloc);

// pssst kid wanna try my allocator? it'll make you feel good
johnny = std::move(pusher);

---

At this point, johnny has to make a tough decision: "I'm adopting pusher's elements' values as far as my value is concerned; should I also adopt his allocator?"

The way johnny makes his decision, in C++11-and-later, is to consult allocator_traits<A<int>>::propagate_on_container_move_assignment and do what it says: if it says true then we'll adopt strangeAlloc, and if it says false we'll stick to our principles and stick with our original allocator. Sticking with our original allocator does mean we might have to do a bunch of extra work to make copies of all pusher's elements (we can't just pilfer his data pointer, because it points into the heap associated with strangeAlloc, not the heap associated with originalAlloc).

The point is, deciding to stick with your current allocator or adopt a new one is a decision that makes sense only in the context of a container. That's why the traits propagate_on_container_move_assignment (POCMA) and POCCA and POCS all have "container" in the name. It's about what happens during container assignment, not allocator assignment. Allocator assignment follows value semantics, because allocators are value-semantic types. Period.

So, should propagate_on_container_move_assignment (POCMA) and POCCA and POCS all have been attributes of the container type? Should we have had std::vector<int> which promiscuously adopts allocators, and std::stickyvector<int> that always sticks with the allocator it was constructed with? Well, probably.

C++17 kind of pretends that we did do it that way, by giving typedefs like std::pmr::vector<int> that look very similar to std::stickyvector<int>; but under the hood std::pmr::vector<int> is just a typedef for std::vector<int, std::pmr::polymorphic_allocator<int>> and still figures out what to do by consulting std::allocator_traits<std::pmr::polymorphic_allocator<int>>.

回答2:

I mean, container copy-assignment can try copy-assign the source allocator, and if that syntactic copy assign doesn't really copy, then, well, it is like saying that your container doesn't propagate_on_container_copy_assignment.

The concept/named requirement "CopyAssignable" means something more than just the ability to assign an lvalue into an object of the same type as that lvalue. It has a semantic meaning as well: the destination object is expected to be equivalent in value to that of the original object. If your type provides a copy assignment operator, the expectation is that this operator copies the object. And pretty much everything in the standard library that allows copy assignment requires this.

If you give the standard library a type that it requires to be CopyAssignable, and it has a copy assignment operator which doesn't abide by the semantic meaning of that concept/named requirement, undefined behavior results.

The allocator has a "value" of some sort. And copying an allocator copies that "value". The question that propagating on copy/move/swap is basically asking this question: is the value of the allocator part of the value of the container? That question only gets raised in the confines of dealing with containers; when dealing with allocators in general, the question is moot. The allocator has a value, and copying it copies that value. But what that means relative to previously allocated storage is an entirely separate question.

Hence the trait.

If I were to write a new container and/or an new non-trivial allocator today, can I rely on the sematics of the allocator and forget about these traits?

...

Can I write the containers simply this way? and delegate the complexity to the semantics of the custom allocators?:

A container that violates the rules of an AllocatorAwareContainer is not an allocator aware container, and you cannot reasonably pass allocators to it that follow the standard library allocator model. Similarly, an allocator that violates the rules of an Allocator cannot reasonably be given to an AllocatorAwareContainer, since that model requires that the allocator actually be an Allocator. This includes the syntactic and semantic rules.

If you do not provide values for the propagate_on_* properties, then the default value of false will be used. This means that it won't try to propagate your allocator, so you won't run afoul of the need for the allocator to be copy/move-assignable or swappable. However, this also means that your allocator's copy/move/swap behavior will never be used, so it doesn't matter what semantics you give these operations. Also, without propagation, if two allocators were unequal, it means a linear time move/swap.

However, an AllocatorAwareContainer is still not allowed to ignore these properties, since by definition, it must implement them in order to assume that role. If an allocator defines a copy assignment operator, but makes its propagate-on-copy false (which is perfectly valid code), you cannot invoke the allocator's copy assignment operator when copy-assigning the container.

Basically, the only way to make this work is to live in your own universe where you only use your "containers" with your "allocators" and never try to use any standard library equivalents with your "containers/allocators".

---

A historical review can also be helpful.

For historical purposes, the propagate_on_* features had a winding history to C++11, but it never appeared as you suggest.

The earliest paper I can find on this subject is N2525 (PDF): Allocator-specific Swap and Move Behavior. The principle intent of this mechanism is to allow certain classes of stateful iterators to be able to have constant-time move and swap operations.

This was subsumed for a time by a concept-based version, but once that was removed from C++0x, it went back to the traits class with a new name and a more simplified interface (PDF) (yes, the interface you're using now is the simple version. You're welcome ;) ).

So in all cases, there was an explicit recognition that there needed to be a distinction between the existence of copy/move/swap and the meaning of these operation with respect to a container.

---

and that handling of these case is horrible code.

But it's not. In C++17, you just use if constexpr. In older version, you have to rely on SFINAE, but that just means writing functions like this:

template<typename Alloc>
std::enable_if_t<std::allocator_traits<Alloc>::propagate_on_container_copy_assignment::value> copy_assign_allocator(Alloc &dst, const Alloc &src)
{
  dst = src;
}

template<typename Alloc>
std::enable_if_t<!std::allocator_traits<Alloc>::propagate_on_container_copy_assignment::value> copy_assign_allocator(Alloc &dst, const Alloc &src) {}

Along with versions for move and swap. Then just call that function to do the copy/move/swap or to not do the copy/move/swap, in accord with propagation behavior.