1

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;
}
Improve this question
1
  • Just an FYI: Allocators are meant to return memory for unconstructed objects which will then later be constructed using std::allocator_traits::construct (effectively placement new). If you are using a std::array<T,...>, then this means you are returning constructed objects -- and for non-trivially-destructible type Ts such as std::string, you would be overwriting a valid object without calling its destructor, which is UB. Most allocators work directly with byte sequences, not T sequences. Commented Nov 12, 2020 at 14:46

2 Answers 2

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

"Non-stateless" :D
Changed to "Stateful" so it doesn't sound as weird :P
I'm totally confounded. How am I supposed to convert an arbitrary type U into an arbitrary type T? This rebind business makes no sense to me.
The C++ allocator model always deals out T pointers, which is why rebinding exists. It doesn't mean that the allocator logic is only implemented in terms of T everywhere. This would be bad for code-bloat on expensive allocator logic. This is why most allocators extract their common allocation logic into some other class that is indirectly pointed to by the allocator. This is what polymorphic_allocator does with memory_resource. The resource isn't tied to any type, but polymorphic_allocator just copies around the resource pointer
It's a lot easier to write allocator logic as something non-type specific managing void* data. If you do this, then you can write an allocator wrapper template that deals specifically in T types that internally uses a pointer to your underlying allocator logic. Rebinding in this case is just a pointer-copy. The C++ Allocator model is easier to think of as being a "handle to a memory resource", rather than as itself an allocator
0

As @Human-Compiler talked about in his answer, one should not couple the allocated data with the allocator. The solution is rather simple: pass in a pointer from the desired array-on-the-stack. You needn't bother with all the allocator-wrapper nonsense one finds in this thread and elsewhere. In SOLID terms, the data is injected as a dependency into the allocator.

I still find the rebind interface awfully curious. It's clearly poor design that we're stuck with. Beyond writing the struct rebind { other... archaic alias, one must also provide a copy constructor from a rebound type. The latter is hardly documented, if at all.

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

struct SharedArray 
{
    uint8_t* data;
    uint64_t index;
};
template<class T>
class MonotonicIncreasingAllocator
{
public:
    MonotonicIncreasingAllocator(SharedArray& a) : _data{a} {}

    template<class U>
    MonotonicIncreasingAllocator(const MonotonicIncreasingAllocator<U>& rhs)
     : _data{const_cast<MonotonicIncreasingAllocator<U>&>(rhs).data()} {}

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

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

    T* allocate(std::size_t n)
    {
        T* r = _data.data + _data.index;
        _data.index += n * sizeof(T);
        return r;
    }

    constexpr void deallocate(T* p, std::size_t n)
    {
        return;
    }

    SharedArray& data()
    {
        return _data;
    }


private:
    SharedArray& _data;
};

int main()
{
    using namespace std;

    using key = int;
    using value = string;
    using item = pair<key, value>;
    std::array<uint8_t, 4096> arr; // allocate enough, here but a page
    SharedArray sharr;
    sharr.index = 0;
    sharr.data = arr.begin();

    using alloc = MonotonicIncreasingAllocator<item>;
    alloc a0(sharr);
    alloc a1(sharr);
    vector<item, alloc> v0(a0);
    unordered_map<key, value, hash<key>, equal_to<key>, alloc> m(500, a1);

    return 0;
}
Improve this answer

2 Comments

Following error on GCC; ``` Required from here /usr/include/c++/11.2.0/bits/hashtable.h:191:21: error: static assertion failed: unordered container must have the same value_type as its allocator ```
Also another error: error: cannot convert ‘uint8_t*’ {aka ‘unsigned char*’} to ‘std::__detail::_Hash_node_base**’ in initialization 129 | T* r = _data.data + _data.index

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.