Is there a BOOST pool fixed-sized allocator?

Question

I want to create unordered_map(Because I specifically want a hash map). I want to allocate its max size (according to my constraints) in the beginning.
So, if I want to allocated 256 entries, and the size of each entry is 1B (just an example. Let's say 1Byte includes the Key and the Value). Then the total size of my unordered_map keys + entries is 256B. I want to pre-allocate 256B in the allocator.
Then, when the unordered_map will call allocate()/deallocate(), the allocator will give it 1B from the already-allocated memory.

typedef boost::unordered::unordered_map<int, MyClass, boost::hash<int>, std::equal_to<MyClass>, ??? > > myMap

Does it exists in BOOST? or somewhere else?

---- edit ----

As I see it (Thanks to the answers here) - there are two solutions for my problem:

1. Implement an allocator, which holds a boost::pool<>. This pool is built in the allocator constructor. When allocate() is being called from unordered_map, it actually calls pool.malloc(), and when deallocate() is called from unordered_map, it actually calls pool.free().

2. Use an already implemented allocator, such as pool_allocator like this:

typedef pool_allocator<std::pair<MyKey, MyClass>, boost::default_user_allocator_new_delete, boost::mutex, 1024 >) MyAllocator;
typedef unordered_map<MyKey, MyClass, hash, eq, MyAllocator> MyUnorderedMap;

The seconds option is still unclear to me, because:
a. Can I declare only one MyUnorderedMap?
b. How can I declare a new MyUnorderedMap with different next_block size than 1024 in run time?

Answer 1

What you describe can actually only achieved with something like Boost Intrusive "Maps" (actually, sets then).

However to get truly 1B - allocated elements you'd need to define a custom stateful value traits, so you can store the node-index metadata separately from the element payload.

However, from the fact that you claim the element type to be 1B (which can obviously never be true for a concrete key and value type), I'll not assume you actually wanted this contrived solution for "some reason".

Instead, let me suggest three more mundane approaches:

• Using a flat_map
• Using a Boost Intrusive unordered set
• Using an unordered set with Boost Pool fixed size allocator¹

Boost flat_map

If hash lookup is not mandatory, you can simplify a lot by just reserving contiguous element storage up front and storing an ordered map instead:

Live On Coliru

#include <boost/container/flat_map.hpp>
#include <iostream>

using Elements = boost::container::flat_map<std::string, std::string>;

int main() {
    Elements map;
    map.reserve(256); // pre-allocate 256 "nodes"!

    map.insert({
            { "one",   "Eins"  },
            { "two",   "Zwei"  },
            { "three", "Drei"  },
            { "four",  "Vier"  },
            { "five",  "Fuenf" },
        });

    for (auto& e : map) {
        std::cout << "Entry: " << e.first << " -> " << e.second << "\n";
    }

    std::cout << "map[\"three\"] -> " << map["three"] << "\n";
}

Prints

Entry: five -> Fuenf
Entry: four -> Vier
Entry: one -> Eins
Entry: three -> Drei
Entry: two -> Zwei
map["three"] -> Drei

Boost Intrusive

CAVEAT Intrusive containers come with their own set of trade offs. Managing the underlying storage of the elements can be error-prone. Auto-link behaviour of the hooks inhibits the constant-time implementation of size() and similar (empty() on some of the unordered set configurations) so this might not be your thing.

Live On Coliru

#include <boost/intrusive/unordered_set.hpp>
#include <boost/intrusive/unordered_set_hook.hpp>
#include <iostream>

namespace bi = boost::intrusive;

struct Element;

namespace boost {
    template <> struct hash<Element> {
        size_t operator()(Element const& e) const;
    };
}

struct Element : bi::unordered_set_base_hook<> {
    std::string key;
    mutable std::string value;

    Element(std::string k = "", std::string v = "") 
        : key(std::move(k)), value(std::move(v)) { }

    bool operator==(Element const& other) const { return key == other.key; }
};

size_t boost::hash<Element>::operator()(Element const& e) const {
    return hash_value(e.key); 
}

using Elements = bi::unordered_set<Element>;

int main() {
    std::array<Element, 256> storage;               // reserved 256 entries
    std::array<Elements::bucket_type, 100> buckets; // buckets for the hashtable

    Elements hashtable(Elements::bucket_traits(buckets.data(), buckets.size()));

    storage[0] = { "one",   "Eins"  };
    storage[1] = { "two",   "Zwei"  };
    storage[2] = { "three", "Drei"  };
    storage[3] = { "four",  "Vier"  };
    storage[4] = { "five",  "Fuenf" };

    hashtable.insert(storage.data(), storage.data() + 5);

    for (auto& e : hashtable) {
        std::cout << "Hash entry: " << e.key << " -> " << e.value << "\n";
    }

    std::cout << "hashtable[\"three\"] -> " << hashtable.find({"three"})->value << "\n";
}

Prints

Hash entry: two -> Zwei
Hash entry: four -> Vier
Hash entry: five -> Fuenf
Hash entry: three -> Drei
Hash entry: one -> Eins
hashtable["three"] -> Drei

Pool fixed size allocator¹

If you absolutely require the node-based storage, consider using a custom allocator.

¹ You'll note that (at least with Boost's unordered_map implementation) the allocator is used for two types (bucket pointers and value nodes) and as such there are two fixed size allocations possible.

^{(See the cleanup calls at the bottom of the sample)}

Live On Coliru

#include <boost/pool/pool_alloc.hpp>
#include <boost/unordered/unordered_map.hpp>
#include <iostream>

using RawMap = boost::unordered_map<std::string, std::string>;
using Elements = boost::unordered_map<
        std::string, std::string,
        RawMap::hasher, RawMap::key_equal,
        boost::fast_pool_allocator<RawMap::value_type>
    >;

int main() {
    {
        Elements hashtable;

        hashtable.insert({
                { "one",   "Eins"  },
                { "two",   "Zwei"  },
                { "three", "Drei"  },
                { "four",  "Vier"  },
                { "five",  "Fuenf" },
                });

        for (auto& e : hashtable) {
            std::cout << "Hash entry: " << e.first << " -> " << e.second << "\n";
        }

        std::cout << "hashtable[\"three\"] -> " << hashtable.find("three")->second << "\n";
    }

    // OPTIONALLY: free up system allocations in fixed size pools
    // Two sizes, are implementation specific. My 64 system has the following:
    boost::singleton_pool<boost::fast_pool_allocator_tag, 8>::release_memory();  // the bucket pointer allocation
    boost::singleton_pool<boost::fast_pool_allocator_tag, 32>::release_memory(); // the ptr_node<std::pair<std::string const, std::string> >
}