c++ - 获取 unordered_set 中最右边的元素(或反向打印内容)

Question

我有一个 unordered_set 如下:

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);
}

然后我执行了另一个函数，删除了 unordered_set 中大约 85% 的元素。 (要删除的元素取决于此函数的逻辑，但这并不重要，因为所有元素最初都是按顺序插入的)。

现在，在删除 unordered_set 中的一些元素后，我想打印仍保留在该 unordered_set 中的最后一个元素。例如，元素 9997、9998、9999 和 10000 已被删除，因此该集合中剩余的最大元素是 9996。 如何做到这一点？
如果使用基本集，我可以执行以下操作:

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

在集合中，我们有reverse_iterator和rbegin()，但这在unordered_set中不存在。我没有基本集的原因是我需要将元素大小放大到10^8。使用常规集(基于红黑树)确实会降低性能(尤其是在涉及插入和删除时)。 我怎样才能做到这一点？将最后剩余的 unordered_set 复制到 vector 中是可行的，但这当然需要时间。我怎样才能通过更聪明的方式实现这一目标？我注意到我也不能做类似的事情:

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

Answer 1

根据我从您的评论中收集到的内容，使用 std::bitset或其动态对应物 boost::dynamic_bitset放在这里应该是合适的。插入和删除的复杂度为 O(1)，确定最大元素的复杂度为 O(N)(通过线性搜索)。有人甚至可能会争辩说，找到最大值的分摊时间为 O(1)，因为您最多必须执行与删除操作一样多的搜索步骤。