Hello everyone. Here I have a simple idea about allocator in C++, especially in user-defined allocator.

When using the memory pool based on the first fit or other similar algorithm, it is easilly to point out whether the "next" or "last" memory block is free and is able to join these two blocks together to get a larger continuous memory block. It has benifit on std::vector. Here is my design about this.

Given Alloc<T> is the type of allocator , these alternative member function will have such meaning.

bool Alloc<T>::reallocate_after(T* ptr, size_t n);

The pointer ptr here must be a pointer returned by Alloc<T>::allocate or Alloc<T>::allocate_at_least. When the return value is false, nothing will happen. When the return value is true, it means it is well defined to use the bytes between ptr and ptr+n, but even n is smaller than the value passed to Alloc<T>::allocate, using ptr+n+1 will cause undefined behavior.

bool Alloc<T>::reallocate_before(T* ptr, size_t n);

The pointer ptr here must be a pointer returned by Alloc<T>::allocate or Alloc<T>::allocate_at_least, or ptr-n after calling this function and return true. When the return value is false, nothing will happen. When the return value is true, it means the "head" of the memory allocated by this alllocator will become ptr-n. When deallocate the memory we must use ptr-n.

There will also be functions have the same name in std::allocator_traits with the same name, and will always return false when there is no such member function. In addition, it's also possible to point out whether these function is provided in compilation time.

With these functions, std::vector will move the elements less times.