Is there a fixed size distributor BOOST?

Question

I want to create an unordered_map (because I specifically want a hash map). I want to highlight its maximum size (according to my limitations) at the beginning.
So, if I want to highlight 256 records, and the size of each record will be 1B (just an example. Let’s say 1Byte includes a key and a value). Then the total size of my unordered_map keys + records is 256B. I want to pre-allocate 256B in the dispenser.
Then, when unordered_map calls allocate() / deallocate() , the allocator will give it 1B of the memory already allocated.

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

Does he exist in boost? or somewhere else?

---- edit ----

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

• Deploy a allocator that contains boost::pool<> . This pool is built into the allocator constructor. When allocate() is called from unordered_map , it actually calls pool.malloc() , and when deallocate() is called from unordered_map , it actually calls pool.free() .

• Use an already implemented allocator like 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 a different next_block size than 1024 at runtime?

Answer 1

What you are describing can be achieved using something like Boost Intrusive "Maps" (in fact, installs ).

However, in order to get truly 1B-selected elements, you will need to define custom values ​​for the state properties , so you can save node-index separately from the element's payload.

However, because you claim that the element type is 1B (which obviously can never be true for a particular key and value type), I will not assume that you really wanted this contrived solution for some reason .

Instead, let me suggest three more worldly approaches:

• Using flat_map
• Using Boost Intrusive Unordered Set
• Using an Unordered Set with a Boost Pool¹ Fixed Size Spreader¹

Boost flat_map

If searching for a hash is optional, you can simplify it by simply reserving the items continuously up and saving the ordered map:

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

Print

 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 compromises. Managing the underlying item store may be error prone. Auto-linking the behavior of hooks prevents the implementation of size() and similar ( empty() for some of the disordered configurations), so this may not be your task.

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

Print

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

Fixed Pool Size Allocator¹

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

¹ You will notice that (at least with the Boost unordered_map implementation) the allocator is used for two types (bucket pointers and value nodes), and as such two fixed sizes are possible.

^{(see cleaning 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> > }