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

Question

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.

Answer 1

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";

Answer 2

No, there is no faster way to remove an element of a set than erase. Unless your intention is to transfer the element into another set in which case extract may be faster as a whole.

The choice of element is irrelevant; except if you don't have an iterator at hand, the fastest iterator to get is begin.

---

In case you're wondering the case where erasure might have linear complexity: If the buckets are implemented as singly linked list (as is typical), and all elements have the same key (or the keys happen to have the same hash value) and the erased element happens to be the last in the bucket, then the entire container would need to be traversed.

The constant average assumes an even distribution of keys and a good hash function.

---

However, erasure invalidates the iterator, so behaviour of directing through it after erasure is undefined.