I believe, much of the benefit depends on the nature of keys and values (e.g. ints vs. strings)? Is there a more detailed description of the tests and results, at different container sizes?
I'm planning to port this enough to be able to run the Boost.Container perf tests. After I do that I'll post numbers from there. Wanted to get an initial sense of interest before starting work.
Can the iterator tradeoff be made a compile time option?
One frequently used operation that generally amounts to iterating through elements is clear(). Do I understand correctly that its complexity can be O(N) where N>size()? I believe the same applies to range erase().
Also, is size() constant time?
size() is constant time, which I pay for in memory and a bit of logic to keep track of that. clear() is O(N) where N is bucket_count, though no work is done on buckets with no elements .