crashing allocator for std.:unordered_map

[dailydols]

When trying to invoke a custom templated PoolAllocator<T> for std::unordered_map<T>, I get segfaults when accessing the map with the operator[]. Using this allocator with std::map, std::vector and also a placed new() (as functor with overloaded operator to allocate memory for single elements of type T) is stable.

To use the allocator for my planned purpose for std::map and std::unordered_map, I typedef it as:
typedef PoolAllocator<std::pair<unsigned int, MyClass> > MapAllocator;

I observed the following:

When defining the types

struct { unsigned data[10]; } MyClass;
typedef std::pair<const unsigned, MyClass> MyPair;
typedef PoolAllocator<MyPair> MapAllocator;

I get sizeof(MyPair) as 44 bytes, which is reasonable.

Now I attempt to use one of the the two maps

std::unsorted_map<unsigned, MyClass, std::hash<unsigned>, std::equal_to<unsigned>, MapAllocator> myUnorderedMap;
std::map<unsigned, MyClass, std::less<unsigned>, MapAllocator> myMap;

The constructor of MapAllocator for myMap reports a sizeof(T) of unexpected 60 bytes, and using myMap causes no crash.
The constructor of MapAllocator for myUnorderedMap reports a sizeof(T) of 44 bytes, as expected, but using myUnorderedMap crashes. But If I "cheat" the MapAllocator for myUnorderedMap to be typedef PoolAllocator<char[60]> MapAllocator instead, the code compiles and myUnorderedMap also works without crashes!

Where do the extra 16 bytes come from?

There must be something fundamental I did not understand here, and I really appreciate the help!

[kbw]

What is PoolAllocator?

[dailydols]

My allocator ;)
Edited.

[Peter87]

I don't know how it accomplish this but it seems like the template type T is not actually MyPair as you specified in the typedef but instead some other type that contains a MyPair plus any extra data that the container needs.

[JLBorges]

> Where do the extra 16 bytes come from?

Let us say we want to implement a doubly linked list containing values of type double.
a la std::list<double> where the allocator specified as the template argument is std::allocator<double>

Say, the link in out linked list is defined as:

struct link // node in a linked list of double
{
    double value = 0 ;
    link* next = nullptr ;
    link* previous = nullptr ;

    // ...
};

The list needs storage for objects of type Link;
however, the allocator type for its value_type is std::allocator<double>
The list, internally has to use std::allocator<link>

Ergo, the need for rebinding an allocator (The allocator must support rebind; this alows the container to get a compatible allocator which can allocate storage for the internal type that it needs).
http://en.cppreference.com/w/cpp/memory/allocator_traits

For example:

#include <iostream>
#include <memory>
#include <type_traits>

int main() {

    // std::allocator<double> allocates storage for objects of type double
    static_assert( std::is_same_v< std::allocator<double>::value_type, double > ) ;
    std::cout << sizeof(std::allocator<double>::value_type) << ' ' << sizeof(double) << '\n' ;

    struct link // node in a linked list of double
    {
        double value = 0 ;
        link* next = nullptr ;
        link* previous = nullptr ;

        // ...
    };

    // in a linked list of double, though the value_type of the list is double,
    // the allocator used internally must allocate storage of objects of type link.
    // this is achieved by rebinding the allocator (for the value_type double)
    // rebinding the original allocator yields linked_list_allocator 
    // which can allocate storage for objects of type link
    using linked_list_allocator = std::allocator_traits< std::allocator<double> >::rebind_alloc<link> ;
    static_assert( std::is_same_v< linked_list_allocator::value_type, link > ) ;
    std::cout << sizeof(linked_list_allocator::value_type) << ' ' << sizeof(link) << '\n' ;
}

http://coliru.stacked-crooked.com/a/d4c60d477e3cd8ac

Some more information: http://www.cplusplus.com/forum/general/127466/

If the custom allocator causes a crash, check if it meets the requirements of a standard library compatible allocator (in particular, check the rebind operation):
http://en.cppreference.com/w/cpp/concept/Allocator

A ready made standard library compatible pool allocator is available in Boost;
boost::fast_pool_allocator<> can be used with lists, maps etc.
http://www.boost.org/doc/libs/1_66_0/libs/pool/doc/html/boost_pool/pool/introduction.html

[dailydols]

I have a rebind, which should explain why std::map works and using the allocator with it reports a sizeof(T) different to sizeof(std::pair<const unsigned, MyType>).