unsorted_set::erase not O(1) when nearly empty

[ShaunJ]

unsorted_set::erase should be O(1) complexity in time. It also returns
a pointer to the next element in the data structure. For most
implementations of a hashtable, this means iterating through all the
empty buckets looking for the next element. If the hashtable is empty,
this means checking every single bucket. If there's a large number of
buckets, this takes a really long time.

Of course this is implementation specific, but most implementations I
can think of would be affected by this.

Cheers,
Shaun

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Maxim Yegorushkin]

On 06/11/09 05:13, ShaunJ wrote:
> unsorted_set::erase should be O(1) complexity in time. It also returns
> a pointer to the next element in the data structure. For most
> implementations of a hashtable, this means iterating through all the
> empty buckets looking for the next element. If the hashtable is empty,
> this means checking every single bucket. If there's a large number of
> buckets, this takes a really long time.
>
> Of course this is implementation specific, but most implementations I
> can think of would be affected by this.

There are interesting new (concurrent) implementations of hash tables
based on split-ordered lists. They store all elements in one long list,
so that iterating such a hash is the same as iterating a list. Google
for split-ordered list.

--
Max