Is one allowed to call allocator::deallocate() in a different order than one called allocator::allocate()?

Question

N3485 20.6.9.1 [allocator.members]/1 says:

Calls to these functions that allocate or deallocate a particular unit of storage shall occur in a single total order, and each such deallocation call shall happen before the next allocation (if any) in this order.

This last requirement confuses me. It looks like the standard is saying that if one allocates a block of memory (let's call it block a), and then allocates another block (let's call it block b), then it is not allowed to deallocate block a until it has deallocated block b.

If this is indeed what this paragraph entails, I don't see how one could implement something like vector's growing in a space efficient manner; because one couldn't allocate a bigger buffer and then deallocate the previously allocated (too small) buffer.

Is this actually what this paragraph means, or am I misreading this section?

Answer 1

Calls to these functions that allocate or deallocate a particular unit of storage shall occur in a single total order, and each such deallocation call shall happen before the next allocation (if any) in this order.

From what it seems to me, it only establishes a happens-before relationship between allocations and deallocations (to prevent concurrency issues arising from incorrect compiler optimisations, possibly). It definitely does not establish a relationship between a and b where a and b are different allocated regions.

Remember that compilers follow the specification, not human logic. The specification aids the compiler programmers remember all the details that need to be taken care of (if it follows specification, it's correct). This is why the specification contains details that one would consider obvious. One of the details is that the deallocation/allocation constitutes a memory barrier.

Compare

reads -> deallocation -> allocation -> writes

with

reads -> deallocation
allocation -> writes

Without a happens-before relationship, two threads may use the same memory region (unit of storage) concurrently, as observed by the memory region. With a happens-before relationship, all access from the deallocating thread must be flushed before the allocating thread gets to use it.