获取 unordered_set 中最右边的元素（或反向打印内容）
我有一个 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--;
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:
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--;
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
根据我从您的评论中收集到的信息，使用 std::bitset 或其动态对应 boost::dynamic_bitset 应该是适合用在这里。插入和删除的复杂度为 O(1)，确定最大元素的复杂度为 O(N)（通过线性搜索）。有人甚至可能会争辩说，找到最大值的分摊时间为 O(1)，因为您最多必须执行与删除操作一样多的搜索步骤。
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.
无序集旨在无序。您应该假设您在使用其迭代器时看到的元素的顺序是任意/不确定的。这意味着任何有关顺序的特定行为根据定义都是不可移植的并且完全特定于实现。现在可能是按顺序排列的，但经过足够的操作后，它可能会按另一种顺序排列。他们给你一个迭代器的唯一原因是允许你以某种任意顺序逐个元素地处理它。
为什么不从一开始就使用 std::vector 呢？
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?
你不能鱼与熊掌兼得。
无序容器以无序方式存储其元素（通常在哈希表内），因此您无法迭代以可预测的方式覆盖它们。特别是，它们不按照插入的顺序存储元素。
如果您不关心顺序，那么您最好使用
std::deque或std::vector（如果您必须在正面）。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::dequeorstd::vector(prefer the former if you have to insert at the front).将删除的项目存储在向量中。完成后，转换为堆。 （O(n)，其中n是删除的项数）然后重复从堆中删除最大值，直到找到未删除的最高元素。这是 O(m log n)，其中 m 是最大值与答案之间的差。
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.