fixed size unordered_map, how to define?

Question

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.

Answer 1

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.

Answer 2

It is not logically possible for a map to have resize() member function, the way other sequence containers has. It is a map, whose every key has to be unique. If you resize it to some size, then it has to fill the newly created entries with some (default) values. What values should it generate for the keys? How would it ensure the uniqueness of the keys? That decision cannot be made by the map, so it simpley doesn't have resize() member function.

Answer 3

If your goal is to resize map to the known size to avoid further possibly unefficient rehashing, you can use std::unordered_map:: reserve. It will set number of buckets, so map could contain given count of elements according to the load factor.