c++unordered-mapfixed-size-types

fixed size unordered_map, how to define?


Is it possible to define a fixed size unordered_map?

Looking at the member functions, there is no resize() similar to std::vector and std::list. Also, google didn't help me.


Solution

  • Yes, it is possible but there is no such map in the STL. What you can do is write your own class containing an std::array< std::pair<Key, Value>, N> and provide most of the find(), insert() functionality using std::hash yourself. If you use a std::vector< std::pair<Key, Value> > as data member, you could even have a resize() function to only expand the table explicitly, but not implicitly after an insert().

    An important thing to realize is that you also need to provide a way to iterate over the various elements, in order to satisfy all the container requirements. Typically this is done by having auxiliary data that implements a linked list over all the stored elements.

    One issue you need to resolve, however, is which replacement policy you use to replace items if your array is full. The std::unorderd_map uses so-called chaining, with -for each entry- a dynamically sized bucket (with at least forward iteration, so at least equivalent to forward_list). Most chess programs have a fixed-size hash table with a replacement policy to always replace an item if a particular table entry is already occupied.