CODEWITHSUNDEEP
c++memory-managementallocator
powercat
powercat

Reputation: 99

How to use std::allocator in custom container properly?

I'm trying to develop my own container which will implement hash table. The main requirement is that this container must be compatible with STL. Now I can't catch how to allocate memory and initialize objects for internal container needs.

The main question is how to manage keys for such container? Do I need to allocate another storage for indexes produced by hash function from keys? And then link them to actual storage with node buckets?

There are template parameters for my container.

template<
    class Key, class T, class Hasher = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Alloc = std::allocator<std::pair<const Key, T>>>
class my_hashtable_v1 {

But then I use internal member types like this to allocate nodes for my container. 

template<class T>
struct ch_node_t : hash_node {
    template<class... Args>
    ch_node_t(Args&&... args) : value(std::forward<Args>(args)...) {
    }
    T value;
};

using node_type = ch_node_t<T>;
using storage_allocator_ = typename Alloc::template rebind<node_type>::other;

Is it correct to allocate nodes this way? This is piece of code from insert method.

auto node = &storage_[slot];
if(!node_traits::is_allocated(*node)) {
  new(node) node_type(v.second);
  node_traits::link_head(*node);
  --freelist_;
}

Where storage is pointer to allocated pool. That's how I allocated pool:

storage_ = storage_allocator_.allocate(size_);

And main thing that I can't understand is how to manage nodes keys using std::allocator<std::pair<const Key, T>> properly? I need to create something like index and storage separately?

Exploring std::unordered_map code is too hard to get those answers, that's why I ask you for direction in my developing custom container.

Upvotes: 2

Views: 1045

Answers (1)

eerorika
eerorika

Reputation: 238461

In order to allocate for objects of another type (let's call it Node) than std::allocator_traits<Alloc>::value_type (let's call it T), where Alloc is the possibly custom allocator type, you must rebind the allocator to get an allocator for the type Node:

using node_alloc_t = std::allocator_traits<Alloc>::rebind_alloc<Node>;
node_alloc_t node_alloc;
node_alloc.allocate(size_);

But how to deal with keys properly? Do I need to create another storage for indexes?

You don't necessarily need to create separate storage for keys. You can store them within nodes. This is how tree based containers work for example.

And my node type don't contain any key.

If you want to store the keys separately, then you do need to allocate storage for them.

Upvotes: 3

Related Questions