2

我有一个 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 复制到向量中会起作用，但这当然需要时间。我怎样才能通过使用更智能的方式来实现这一目标？我注意到我也不能做类似的事情：

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

4 回答 4

1

无序集旨在无序。您应该假设您在使用它的迭代器时看到它的元素的顺序是任意/不确定的。这意味着有关订单的任何特定行为根据定义都是不可移植的并且完全是特定于实现的。它现在可能恰好是有序的，但经过足够的操作后，它可能是另一个顺序。他们给你一个迭代器的唯一原因是允许你以任意顺序逐个元素地处理它。

为什么不从一开始就使用 std::vector 呢？

于 2011-10-07T18:27:48.607 回答
1

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

于 2011-10-07T18:58:41.807 回答
1

你不能吃你的蛋糕。

无序容器以无序的方式存储它们的元素（通常在哈希表中），因此您无法以可预测的方式迭代它们。特别是，它们不会按照插入的顺序存储元素。

如果您不关心顺序，那么您最好使用std::dequeor std::vector（如果您必须在前面插入，则更喜欢前者）。

于 2011-10-07T19:01:26.940 回答
0

将删除的项目存储在向量中。完成后，转换为堆。（O(n)，其中 n 是已删除项的数量）然后重复从堆中删除最大值，直到找到未删除的最高元素。那是 O(m log n)，其中 m 是您的最大值与答案之间的差。

于 2011-10-08T18:49:16.577 回答