std::unordered_map with custom allocator / local allocator does not compile

I have a pretty simple custom/local allocator. My goal is to use an array on the stack as the allocating portion of memory. It appears to work in std::vector but when I try to plug it in to std::unordered_map it fails to compile. gcc 7.4.0's error messages are pretty impenetrable. Something along the lines of:

hashtable_policy.h:2083:26: error: no matching function for call to
‘MonotonicIncreasingAllocator<std::pair<const int, std::string>, 500>::
MonotonicIncreasingAllocator(std::__detail::_Hashtable_alloc<MonotonicIncreasingAllocator
<std::__detail::_Hash_node<std::pair<const int, std::string>, false>, 500> >::
__node_alloc_type&)’
   
    __value_alloc_type __a(_M_node_allocator());

Clang 7.1.0 is a bit more manageable. Scrolling from an error like error: no matching conversion for functional-style cast from 'const std::_Hashtable . . . I find:

hashmap_custom_alloc.cpp:11:5: note: candidate constructor not viable: no known conversion from
    'MonotonicIncreasingAllocator<std::__detail::_Hash_node<std::pair<const int,
    std::__cxx11::basic_string<char> >, false>, [...]>' to 'const
    MonotonicIncreasingAllocator<std::__detail::_Hash_node_base *, [...]>' for 1st argument
  MonotonicIncreasingAllocator(const MonotonicIncreasingAllocator& rhs) = default;
  ^

Makes it a bit clearer this std::__detail::_Hash_node_base bit is getting in the way. Here is the code, neither unordered_map declaration compiles:

#include <array>
#include <stdexcept>
#include <unordered_map>
#include <vector>

template<class T, std::size_t max_size>
class MonotonicIncreasingAllocator
{
public:
    MonotonicIncreasingAllocator() : _index{0} {}

    using type = MonotonicIncreasingAllocator<T, max_size>;
    using other = MonotonicIncreasingAllocator<T, max_size>;

    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using propagate_on_container_move_assignment = std::true_type;
    using is_always_equal = std::true_type;
        
    template<class U> 
    using rebind = MonotonicIncreasingAllocator<U, max_size>;

    T* allocate(std::size_t n)
    {
        T* r = _data.begin() + _index;
        _index += n;
        return r;
    }

    constexpr void deallocate(T* p, std::size_t n)
    {
        throw std::runtime_error("MontonicIncreasingAllocator can never deallocate()!");
    }

private:
    std::size_t _index;
    std::array<T, max_size> _data;
};

int main()
{
    using namespace std;

    using key = int;
    using value = string;
    using item = pair<key, value>;

    using alloc = MonotonicIncreasingAllocator<item, 500>;
    alloc a0;
    alloc a1;
    vector<item, alloc> v0(a0);
    vector<int, alloc> v1;
    // unordered_map<key, value, hash<key>, equal_to<key>, alloc> m; // doesn't compile
    // unordered_map<key, value, hash<key>, equal_to<key>, alloc> m(500, a1); // doesn't compile

    return 0;
}

Solution

An allocator of type T must be rebindable to an allocator of type U -- this is why there is the rebind template.

To do this you must offer a way to conversion-construct from a type U to a type T e.g. a constructor that constructs from MonotonicIncreasingAllocator<U, ...>&, such as:

template <typename U>
MonotonicIncreasingAllocator( const MonotonicIncreasingAllocator<U, max_size>& )

You might notice a problem that immediately comes from this: an array<U,max_size> cannot necessarily be copied to an array<T,max_size>; and due to this, you will want to rethink your allocator design.^[1]

For legacy reasons, the C++ "Allocator" model is meant to be copyable. This requirement makes it difficult to work with allocators that itself contain state, rather than indirectly point to state.

Note: The reason this may have worked for vector is because an allocator of type T doesn't get rebound on a vector<T>, since it only needs to allocate n instances of T. This is not true for more complex data structures like a map, set, unordered_map, etc -- since there may be nodes of objects or other contiguous sequences internally used.

^[1] Stateful allocators are stored directly into the containers that use them. This means that a vector<T,MonotonicIncreasingAllocator<T,N>> will now also store the allocator itself, containing an array<T,N>, directly inside of the vector class, in addition to its own data -- which is wasteful. Copying or even moving a container with this allocator would be an extremely expensive operation.

Additionally, by storing the data directly inside of the allocator, conversion-construction requires a copy of the entire internal std::array object, which means that the rebinding constructs a new object that refers to a different monotonic structure than the allocator that was being rebound -- which isn't ideal.

You should look into the architecture that's used in std::pmr::polymorphic_allocator for better inspiration. The std::pmr::polymorphic_allocator holds onto 1 data type: a std::memory_resource pointer, which makes rebinding cheap, and storage of this allocator cheap. The memory_resource is type-ambiguous and passed by indirection, which allows for allocators after being rebound to use and refer to the same memory pool.