AllocatorAwareContainer: Introduction and pitfalls of propagate_on_container_XXX defaults

05 Oct 2015 by Jonathan

While I was writing the std_allocator adapter of foonathan/memory I’ve learned some not so well-known facts about the STL Allocator and AllocatorAwareContainer concepts I’d like to share. Let’s take a deep breath and dive in into an aspect of the STL containers that isn’t that well covered: Allocator storage.

I will explain the comparison properties of Allocators, show the C++11 propagate_on_container_XXX traits and how the combination of the two can lead to an unnecessary pessimization and a probably not widely known case of undefined behavior.

Introduction to the Problem

I am going to start with the following allocator:

#include <memory>

std::size_t alloc_count = 0u;

template <typename T>
class my_allocator
{
public:
	using value_type = T;

	my_allocator()
	: id_(++alloc_count) {}

	template <typename U>
	my_allocator(const my_allocator<U> &other)
	: id_(other.id_)
	{}

	T* allocate(std::size_t n)
	{
		return std::allocator<T>().allocate(n);
	}

	void deallocate(T *ptr, std::size_t n)
	{
		std::allocator<T>().deallocate(ptr, n);
	}

	std::size_t id() const
	{
		return id_;
	}

private:
	std::size_t id_;

	template <typename T1, typename T2>
	friend bool operator==(const my_allocator<T1> a, const my_allocator<T2>&b);
};

template <typename T, typename U>
bool operator==(const my_allocator<T> a, const my_allocator<U>&b)
{
	return a.id_ == b.id_;
}

template <typename T, typename U>
bool operator!=(const my_allocator<T>&a, const my_allocator<U>&b)
{
	return !(a == b);
}

The above class my_allocator is a naïve and (for the sake of this post) very simplified implementation of an allocator with a name. Each allocator created gets an unique identifier which is useful for debugging purposes. Two allocators are considered equal if they have the same identifier.

It uses the C++11 std::allocator_traits to provide only this minimal interface. All access through an Allocator is done through the traits. They provide default implementations for all the other functions.

A real implementation wouldn’t use the value of a global integer variable as identifier and wouldn’t just forward to std::allocator in the actual allocation functions, but this implementation is enough to keep us busy for now.

If you are wondering about the second constructor taking a different instantiation of my_allocator, it is required by the Allocator concept. Some containers like std::list get an allocator of the value_type, e.g. int, but need to allocate a different type, e.g. the list node. They rebind the allocator to the type they need and use this constructor to create the new instance.

In this implementation it simply copies the identifier.

int main()
{
	std::vector<int, my_allocator<int>> a, b, c;

	a.push_back(0);

	b.push_back(2);
	b.push_back(4);

	c.push_back(1);
	c.push_back(3);

	a = std::move(c);
	std::swap(a, b);

	std::cout << a[0] << ' ' << b[0] << '\n';
}

The above snippet uses the allocator class in three std::vector objects. The containers are populated, then a is move assigned to c, a and b are swapped and the first value of a and b is printed.

The code compiles, runs and prints as expected 2 1 under GCC and Clang. Everything’s alright - except that it is undefined behavior and crashes under MSVC.

And apart from the undefined behavior, there is also one operation which is probably more expensive and dangerous than expected.

To understand why, we need to take a step back and look at allocator comparison and AllocatorAwareContainer classes.

All allocators are created (un-)equal

Every Allocator must provide comparison operators for (in-)equality.

Equality of an allocator is determined through the ability of allocating memory with one allocator and deallocating it with another. In other words: Two allocators a and b shall compare equal, if memory allocated by a can be deallocated by b and vice-versa.

The comparison can e.g. be used in AllocatorAwareContainer classes to avoid unnecessary operations if the allocators are already equal.

Starting with C++17, own allocator classes can specify a typedef is_always_equal.

is_always_equal is one of those C++11 booelan typedefs. Instead of specyfing a boolean constant, the standard library is using more and more typedefs to an integral constant. is_always_equal and the propogate_on_container_XXX typedefs are those and need to be either std::true_type or std::false_type (or derived).

If this is std::true_type, two allocator objects are always considered equal. If this typedef is not provided, the std::allocator_traits will forward to std::is_emtpy: Empty, that is, stateless types have no state to be not equal and are thus always equal. This can be used as an additional optimization and especially for noexcept specifications, which will become clear later on.

For the remainder of this blog post, the usage of different or equal allocators is the equality described here, not actual object identity.

AllocatorAwareContainer

AllocatorAwareContainer is a new concept in C++11 and describes how Allocator objects should be handled inside of containers. All STL containers except std::array are modelling this concept.

It requires some less interesting stuff like a get_allocator() function or that every allocation is done through the Allocator, but also specifies how and when an allocator object is copied or moved. This behavior has some interesting consequences.

AllocatorAwareContainer: Copy/Move constructors

Copy and move constructors of an AllocatorAwareContainer copy or move the allocator object respectively. Move is done directly by invoking its move constructor, copying can be controlled via a special function, select_on_container_copy_construction().

Yes, that’s the name. I am not kidding. Look it up.

If an Allocator provides this member function it will be called in the copy constructor of an allocator. If the member function does not exist, the default will simply return a copy of the passed allocator.

The actual signature of it inside the traits is static Alloc select_on_container_copy_construction(const Alloc& a); Since the return value is by value, it is not possible to prevent a copy by returning a reference to *this inside the member function. The traits function will copy it anyway.

select_on_container_copy_construction() allows an Allocator writer to keep track of container copies and/or modifies state in the copied allocator. I don’t find this function that (or at all) useful and although searching on Github does give almost 30,000 results most of them are either tests of standard library implementations, adapter classes which need to forward, or workarounds for MSVC.

A corresponding select_on_container_move_construnction() is missing. That’s the kind of consistency you want.

AllocatorAwareContainer: Copy/Move assignment operators

Move constructor was pretty straightforward, copy constructor a little bit over-generic, but so far it was pretty intuitive behavior. Well, that is going to change now with the assignment operators.

The problem with assignment is that the container has already objects in it (usually). Assigning a new container requires getting rid of those and acquiring new ones. If the allocator objects are equal, this is pretty straightforward. If not, it gets interesting.

Ignoring exception safety, the container first needs to destroy the old objects and deallocates their memory with the old allocator. Then it allocates the new memory. For that, it uses the new allocator. Or the old allocator… Is the allocator assigned if the container is assigned?

In general, there are three options:

Don’t assign the allocator. A container simply uses the same allocator as before.
Assign the allocator using a copy/move of the other allocator object.
Assign the allocator to a completely different object.

Option 3 is (luckily) out of question. So the choice is only between option 1 and 2. This choice can be done by the user, the default is option 1.

So assigning the container objects does not assign the allocator objects by default. This choice has various pitfalls in addition to being unintuitive. It also has the additional (non-)benefit of not being able to ever change the allocator object inside a container.

The option can be chosen via propagate_on_container_copy_assignment and propagate_on_container_move_assignment.

I am still serious, that is their name.

If your Allocator class provides one of these - wonderfully named - boolean typedefs, it controls whether or not the allocator will propgate on assignment, that is, be assigned. If the class doesn’t provide them, the allocator_traits will provide the - bad - default of std::false_type preventing allocator assignment.

The assignment will be done by calling the allocator’s copy or move assignment operator respectively.

Again there is no select_on_container_copy_assignment() function or similar for controlling this behavior. This function only exists for one out of four operations. I bet there is a valid reason for this. I just don’t know it.

AllocatorAwareContainer: Swap

Swapping behaves similar to assignment. Unequal allocators are only swapped if propagate_on_container_swap has the appropriate value (or type, that is). The default is again std::false_type.

AllocatorAwareContainer: Summary

So, to sum it up, for two containers with different allocator:

The copy constructor will copy construct the Allocator through the select_on_container_copy_construction() function.
The move constructor will move construct the Allocator. Directly, without a select_on_container_move_construnction() or similar.
The move assignment operator will move assign the Allocator if propagate_on_container is std::true_type (not the default).
The copy assignment operator will copy assign the Allocator if propagate_on_container_move_assignment is std::false_type (not the default). There is no select_on_container_copy_assignment() like in the copy constructor.
Swap will swap the Allocator if propagate_on_container_swap is std::true_type (not the default).

A sample and pretty dumb AllocatorAwareContainer class can be found as part of a tutorial for my memory library here. Note that it cannot use the usual copy-and-swap idioms in the assignment operators and has a lot of boilerplate.

This behavior can lead to two cases of unexpected behavior.

Pitfall #1: Move assignment

Move assignment of a container is a pretty straightforward operation: Just copy the pointer, set the old one to nullptr and you are good to go. Right? Wrong.

Consider the move operation from the beginning again:

a = std::move(c);

Moving transfers ownership over the memory. The assignment of a to c transfers ownership, a will own the memory from c after the operation. a is responsible for c’s memory, i.e. it will deallocate it when required.

Combining this with different allocators leads to an interesting behavior: When a is destroyed or needs to grow, it will deallocate the memory using its allocator. But the memory was allocated by c’s allocator! Allocating memory from one allocator and deallocating from a different allocator is probably not a good idea.[citation needed]

So the containers cannot simply transfer the ownership in a move assignment with different allocators. They have to do similar work as in a copy assignment: allocate new, std::move_if_noexcept individual elements, deallocate old, adjust pointer, do something to mark other object as moved-from.

This operation is probably more expensive than expected and - more importantly - a potential throwing operation! Container move assignment can only be noexcept if propagate_on_container_move_assignment is std::true_type, in which case the allocator is moved along with the pointers and the fast version is used. Otherwise the allocators are compared and depending on the result the slow move is required.

The aforementioned is_always_equal can be used in C++17 to avoid the comparison similar to propagate_on_container_move_assignment.

Pitfall #2: Swap

Swapping is similar to move: Just swap the pointers and you’re good - unless you are dealing with unequal allocators which are not propagate_on_container_swap. Let’s take the swap operation from the beginning again as example:

std::swap(a, b);

Since a’s and b’s allocators are unequal, the pointers cannot be simply swapped. This would again lead to a deallocation through the wrong allocator.

So the operation has to be a little bit more complicated: It has to allocate new memory for both containers and then swap the elements from - from where exactly? All elements are in old memory, the new memory does not contain any object to swap with!

Okay, so it has to create elements in the new memory using the default constructor. That does not work on types without default constructor.

Fine, it has to std::move_if_noexcept-construct the elements in the new memory from the old memory of the other container in the new memory of the first container. Then it can deallocate the old memory and is good to go.

Except it can’t do that.

§23.2.1[container.requirements.general] sections 8 and 10:

8 - The expression a.swap(b), for containers a and b of a standard container type other than array, shall exchange the values of a and b without invoking any move, copy, or swap operations on the individual container elements. […]

10 - Unless otherwise specified [..] all container types defined in this Clause meet the following additional requirements: […]

— no swap() function throws an exception.

— no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped.

The described way would call the elements move constructor and can throw an exception in the memory allocation step and invalidate all references, pointers or iterators referrering to all elements. So it would violate all requirements of a containers swap function except the one saying that it shall exchange the contents.

Fun fact: Fulfilling 1 of 4 requirements is enough to model the entire concept, 6.25% is the passing grade as Scott Meyers describes it in his great talk “The last thing D needs” at around 36:25.

So it has to allocate new memory without throwing any exceptions and swap the objects into new memory without invoking any operations on the stored type and adjusts all external pointers to the elements so they point to the object in the new location instead of the old.

Trivial, right?

The standard resolves this situation as usual in the rest of section 8:

If allocator_traits<allocator_type>::propagate_on_container_swap::value is true, then the allocators of a and b shall also be exchanged using an unqualified call to non-member swap. Otherwise, they shall not be swapped, and the behavior is undefined unless a.get_allocator() == b.get_allocator().

Swapping two container with unequal allocators who are not propagated is undefined behavior.

Since not propagating is active by default, swapping the container leads to undefined behavior in the initial code.

Conclusion

To avoid these pitfalls, propagate_on_container_swap and propagate_on_container_move_assignment must both be std::true_type. For consistency, propagate_on_container_copy_assignment should also be true. Otherwise, moving and copying has different semantics.

I thus propose that you do not write the C++11 minimal allocator only since it uses - bad - defaults. Instead you should add the three typedefs, creating the following minimal allocator:

template <typename T>
struct min_allocator
{
	using value_type = T;

	using propagate_on_container_copy_assignment = std::true_type; // for consistency
	using propagate_on_container_move_assignment = std::true_type; // to avoid the pessimization
	using propagate_on_container_swap = std::true_type; // to avoid the undefined behavior

	// to get the C++17 optimization: add this line for non-empty allocators which are always equal
	// using is_always_equal = std::true_type;

	template <class U>
	min_allocator(const min_allocator<U>&);

	T* allocate(std::size_t n);
	void deallocate(T* ptr, std::size_t n);
};

template <typename T, typename U>
bool operator==(const min_allocator<T>&, const min_allocator<U>&);

template <typename T, typename U>
bool operator!=(const min_allocator<T>&, const min_allocator<U>&);

The allocator comparision should also only reflect whether or not memory can be allocated from one and deallocated from another object. This avoids needless copies which might be expensive.

You could also use my memory library which provides a RawAllocator model, which is simpler to write and use.

Update: A follow-up-ish post is now available.

This blog post was written for my old blog design and ported over. If there are any issues, please let me know.