Getting the rightmost element in an unordered_set (or print the contents in reverse)

I have an unordered_set as follow:

unordered_set <long> valueSet;

/*the following insertion is done in order (from 1 to 10000), 
 *unordered_set will keep the elements based on the insertion order, right, 
 *just like in a vector ?
**/

for(long i = 1; i <= 10000;++i)
{
        valueSet->insert(i);
}

Then I performed another function which erased about 85% of the elements in that unordered_set. (The elements which are to be erased depend on the logic of this function, but it doesn't matter since all the elements were initially inserted in order).

Now after erasing some of the elements in the unordered_set, I want to print the last element which still remains in that unordered_set. For instance, element 9997, 9998, 9999, and 10000 have been erased, so the largest remaining element in this set is 9996. How to do this?

If using a basic set, I can do the following:开发者_JS百科

set <long>::reverse_iterator it = valueSet.rbegin();
cout << *it << endl;

In a set, we have the reverse_iterator and also rbegin(), but this does not exist in unordered_set. The reason why I did not the basic set is that I need the element size to scale up to 10^8. Using the regular set (which is based on red black trees) will kill the performance indeed (especially when it deals to insertion and deletion). How can I do this? Copying the final remaining unordered_set to a vector will work, but of course this will take time. How can I achieve this by using a smarter way? I notice that I also cannot do something like :

unordered_set <long>::iterator it = valueSet.end();
//operator -- does not exist here in the unordered_set
it--;

---

From what I've gathered from your comments, using a std::bitset or its dynamic counterpart boost::dynamic_bitset should be appropiate here. You get O(1) insertion and deletion and O(N) for determining the maximum element (by linear search). One could even argue that finding the maximum is amortized O(1), as you have to do at most as many search steps as deletion operations.

---

The unordered set is intended to be unordered. You are supposed to assume that the order that you see it's elements in using it's iterator is arbitrary/nondeterministic. This means any specific behavior regarding order is by definition unportable and wholly implementation specific. It may happen to be in order now, but after enough manipulations it could be in another order. The only reason they give you an iterator at all is to allow you to deal with it element by element in some arbitrary order.

Why not just use std::vector from the start?

---

You cannot have your cake and eat it.

Unordered containers store their elements in an unordered fashion (typically inside a hash table), so you cannot iterate over them in a predictable way. In particular, they don't store the elements in the order they are inserted.

If you don't care about the order, then you're better with std::deque or std::vector (prefer the former if you have to insert at the front).

---

Store the deleted items in a vector. When done, convert to a heap. (O(n), where n is the number of deleted items) Then repeatedly remove the maximum value from the heap until you find the highest element not deleted. That's O(m log n), where m is the difference between your maximum value and the answer.