...

Besides an out of line boost :) dynamic_bitset

Could you please explain that?

Basically this: template <typename Key, typename Value, typename HashFn> class PerfectHash { dynamic_bitset foo; std::vector<std::pair<Key, Value> > bar; Value get(Key k) { if (foo[HashFn::baz(k)] && bar[HashFn::baz(k)].first == k ) { return bar[HashFn::baz(k)].second; } else { throw; } } }; out of line means the information whether a certain slot in the underlying container holds a valid value is not stored in the container, as it would be the case if i used boost::optional<std::pair<Key, Value> > as the parameter to the std::vector template.