2009/11/23 Christopher Jefferson <chris@bubblescope.net>:
One way to significantly reduce this problem is to use a different hash function, which shuffles the values more.
That will improve things, but not by much as there'll still be a lot more buckets than elements. That would need to combined with regularly manually rehashing the container (ie. calling 's.rehash(0)') as elements are erased. 2009/11/23 Daniel James <daniel_james@fmail.co.uk>:
I could apply another hash function to the hash value to make this less likely, or perhaps store a pointer to the last non-empty bucket. I'll think about it.
Neither of those will work, there will still be other similar cases. With the current interface the only way to deal with this that I can think of is by changing the data structure, which will require more memory use. And there's been opposition to that. It could possibly use an iterator which only finds the next element when used, although that'll make a lot of other operations more expensive. Daniel