[C++17] AllocatorAwareContainer notes

Reference:
AllocatorAwareContainer: Introduction and pitfalls of propagate_on_container_XXX defaults



AllocatorAwareContainer concepts:
http://en.cppreference.com/w/cpp/concept/AllocatorAwareContainer
http://en.cppreference.com/w/cpp/memory/allocator_traits



An AllocatorAwareContainer is a Container that holds an instance of an Allocator
and uses that instance to allocate and deallocate memory in all of its member functions.

The following rules apply to object construction:
Copy constructors of AllocatorAwareContainers obtain their instances of the allocator by calling      
    std::allocator_traits<allocator_type>::select_on_container_copy_construction
on the allocator of the container being copied.

Move constructors obtain their instances of allocators by move-constructing from the allocator belonging to the old container.

All other constructors take an allocator parameter.


Beware of propagate_on_container_XXX


The only way to replace an allocator is *copy-assignment, *move-assignment, and *swap:
Copy-assignment will replace the allocator only if
    std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value
is true.

Move-assignment will replace the allocator only if
    std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value
is true.

Swap will replace the allocator only if
    std::allocator_traits<allocator_type>::propagate_on_container_swap::value
is true.

Specifically, it will exchange the allocator instances through an unqualified call to the non-member function swap,
see Swappable.

Note: swapping two containers with unequal allocators if
    propagate_on_container_swap
is false is undefined behavior.

The accessor get_allocator() obtains a copy of the allocator that was used to construct
the container or installed by the most recent allocator replacement operation.


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

2. Starting with C++17, own allocator classes can specify a typedef is_always_equal.
--
is_always_equal is one of those C++17 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.


3. 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.

4. Move, 用move constructor.

5. Copy, 用std::allocator_traits<allocator_type>::select_on_container_copy_construction
on allocator from the container.

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.

Signature:
Alloc select_on_container_copy_construction(const Alloc& a);

select_on_container_copy_construction() allows an Allocator writer to keep
track of container copies and/or modifies state in the copied allocator.

Do not provide select_on_container_move_construnction() if that's the kind of consistency you want.


***
6. Assignment operators:
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.
     1.The container first needs to destroy the old objects.
     2.Deallocates their memory with the old allocator.
     3.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??
        Options:
        1.(Default)Don't assign the allocator. A container simply uses the same allocator as before.
        2.Assign the allocator using a copy/move of the other allocator object. // base Allocator's typedef flag.
        3.(This is not possible)Assign the allocator to a completely different object.
     
        Use those 2 defined type inside Allocator to choose which default behavior is choosen:
        propagate_on_container_copy_assignment // must be boolean typedef, e.g <type_traits> std::true_type std::false_type
        propagate_on_container_move_assignment

     
7.There is no select_on_container_copy_assignment() like select_on_container_copy_construction()

8.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.

9. Containter:
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.
 
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.
**

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

11.
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.


12. e.g:

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);
};

Container Implementation.