C++ – fixed size unordered_map, how to define

cfixed-size-typesunordered-map

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.

Best Answer

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.

Setting a bit

Use the bitwise OR operator (|) to set a bit.

number |= 1UL << n;

That will set the nth bit of number. n should be zero, if you want to set the 1st bit and so on upto n-1, if you want to set the nth bit.

Use 1ULL if number is wider than unsigned long; promotion of 1UL << n doesn't happen until after evaluating 1UL << n where it's undefined behaviour to shift by more than the width of a long. The same applies to all the rest of the examples.

Clearing a bit

Use the bitwise AND operator (&) to clear a bit.

number &= ~(1UL << n);

That will clear the nth bit of number. You must invert the bit string with the bitwise NOT operator (~), then AND it.

Toggling a bit

The XOR operator (^) can be used to toggle a bit.

number ^= 1UL << n;

That will toggle the nth bit of number.

Checking a bit

You didn't ask for this, but I might as well add it.

To check a bit, shift the number n to the right, then bitwise AND it:

bit = (number >> n) & 1U;

That will put the value of the nth bit of number into the variable bit.

Changing the nth bit to x

Setting the nth bit to either 1 or 0 can be achieved with the following on a 2's complement C++ implementation:

number ^= (-x ^ number) & (1UL << n);

Bit n will be set if x is 1, and cleared if x is 0. If x has some other value, you get garbage. x = !!x will booleanize it to 0 or 1.

To make this independent of 2's complement negation behaviour (where -1 has all bits set, unlike on a 1's complement or sign/magnitude C++ implementation), use unsigned negation.

number ^= (-(unsigned long)x ^ number) & (1UL << n);

unsigned long newbit = !!x;    // Also booleanize to force 0 or 1
number ^= (-newbit ^ number) & (1UL << n);

It's generally a good idea to use unsigned types for portable bit manipulation.

number = (number & ~(1UL << n)) | (x << n);

(number & ~(1UL << n)) will clear the nth bit and (x << n) will set the nth bit to x.

It's also generally a good idea to not to copy/paste code in general and so many people use preprocessor macros (like the community wiki answer further down) or some sort of encapsulation.

C++ – How to retrieve all keys (or values) from a std::map and put them into a vector

While your solution should work, it can be difficult to read depending on the skill level of your fellow programmers. Additionally, it moves functionality away from the call site. Which can make maintenance a little more difficult.

I'm not sure if your goal is to get the keys into a vector or print them to cout so I'm doing both. You may try something like this:

std::map<int, int> m;
std::vector<int> key, value;
for(std::map<int,int>::iterator it = m.begin(); it != m.end(); ++it) {
  key.push_back(it->first);
  value.push_back(it->second);
  std::cout << "Key: " << it->first << std::endl();
  std::cout << "Value: " << it->second << std::endl();
}

Or even simpler, if you are using Boost:

map<int,int> m;
pair<int,int> me; // what a map<int, int> is made of
vector<int> v;
BOOST_FOREACH(me, m) {
  v.push_back(me.first);
  cout << me.first << "\n";
}

Personally, I like the BOOST_FOREACH version because there is less typing and it is very explicit about what it is doing.