Is there a faster way to remove and store an element from an unordered set

  • A+
Category:Languages

I have an unordered set like below:

[1,2,3,4,6,7,5] 

I want to remove and store an element from my unordered set and I don't care which element is removed.

I am currently doing the following. Is there a faster way to do it?

auto it = set_of_ints.begin(); set_of_ints.erase(it); ..... ..... std::cout << "removed element is: " << *it << std::endl; 

I meant to paste the print statement before the erase but many answers discuss that issue. So I am leaving it as is.

 


No, the std::unordered_set::erase member function is the only function meant to be used when erasing elements from the set, and the docs say:

Complexity
Given an instance c of unordered_set:
1) Average case: constant, worst case: c.size()
[...]

So why is it c.size() in the worst case? Note that erase has a return value:

Return value
1-2) Iterator following the last removed element.
[...]

The function has to find the "next element". std::unordered_set stores its data in so called bucket lists. Ideally, this is the next available slot in the same bucket list as the one which accommodates the element which you erase. Worst case, it is the last available slot in some other bucket (and hence it scales with the size of the container). This depends on the insert/erase history of the container. You can have a look at the libcxx implementation here, there is a loop traversing the nodes in the bucket list (the mechanism is well explained by @eeroika's answer).


Besides, not that (also from the docs on erase):

References and iterators to the erased elements are invalidated

So dereferencing the iterator it after you erased it from the set is undefined behavior. You can fix it by

auto it = set_of_ints.begin(); const int value = *it;  set_ot_ints.erase(it);  std::cout << "removed element is: " << value << "/n"; 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: