一个优先队列的变体

Question

我需要一种优先级队列来存储键值对<key, value>。其中，value是唯一的，但key并不唯一。我将执行以下操作（最常见的在前）：

1. 随机插入；
2. 检索并删除所有具有最小键的元素。
3. 随机删除（通过值）；

由于std::priority_queue只支持删除头部，因此无法使用它。

现在，我正在使用未排序的std::list。将新元素推到后面可实现O(1)的插入。在执行实际检索之前，操作2会使用list::sort对列表进行排序（O(N*logN)）。然而，删除的复杂度为O(n)，这有点昂贵。

是否有更好的数据结构？

- Giovanni Funchal

---

使用 vector 而不是 list，除非你确实拥有大量元素。 - Matthieu M.

你是否希望保证value的唯一性，或者有其他东西来处理它？ - Matthieu M.

无需保证value的唯一性。 - Giovanni Funchal

Answer 1

当您需要排序时，请使用有序容器。事后对排序进行付出费用是毫无意义的。

您目前的解决方案是：

插入 O(1) 检索 O(N log N) 删除 O(N) (这是在不保留另一个索引的情况下得到的最好结果)

仅仅使用 std::multi_map，您可以实现：

插入 O(log N) 检索 O(log N) <-- 很大程度上比现有方案更好。我们需要找到范围的末尾。 删除 O(N)

现在，您可以通过 std::map< key, std::vector > 实现稍微更好的性能：

插入 O(log M)，其中 M 是不同键的数目 检索 O(1) (begin 保证平摊常数时间) 删除 O(N)

您真正不能优化随机删除…除非您愿意保留另一个索引。例如：

typedef std::vector<value_type> data_value_t;
typedef std::map<key_type, data_value_t> data_t;

typedef std::pair<data_t::iterator,size_t> index_value_t;
  // where iterator gives you the right vector and size_t is an index in it

typedef std::unordered_map<value_type, index_value_t> index_t;

但是，保持第二个索引的最新状态容易出错...并且会以其他操作为代价！例如，使用此结构，您将拥有：

- 插入 O(log M) --> 哈希映射中插入的复杂度为 O(1) - 检索 O(N/M) --> 需要取消索引向量中的所有值，平均有 N/M 个 - 删除 O(N/M) --> 在哈希映射中查找 O(1)，取消引用 O(1)，从向量中删除 O(N/M)，因为我们需要移动向量约一半的内容。使用 list 将产生 O(1)...但可能不会更快（取决于元素数量，因为存在内存权衡）。

另外，请记住，哈希映射复杂度是分摊的。触发重新分配，因为您超过了负载因子，这个特定的插入将花费很长时间。

我真的建议您使用 std::map>。这是性价比最高的选择。

- Matthieu M.

---

Boost有多索引容器。所以如果你要走这条路，最好使用别人已经调试过的代码。 - Eric H.

不幸的是，我不知道如何使用MultiIndex容器获取最终结构。我的意思是，您可以要求在键上使用multiset和在值上使用带有唯一约束的hash_map，但那不是我设计的最终方案。可能足够好了。 - Matthieu M.

Answer 2

你能否反转集合的顺序，即按<value, key>的顺序存储它们？

然后你可以使用std::map，它具有O(logn)的插入时间，O(n)的删除时间（遍历整个集合），以及O(logn)的随机值（这将是所述映射的键）的删除时间。

如果你能找到一个基于哈希而不是树的map实现（如std::map），那么时间会更好：O(1)，O(n)，O(1)。

- pajton

---

或者非标准容器hash_map/即将成为标准的std::unordered_map。 - Billy ONeal

它需要按键排序和检索，所以我不确定这会起作用。 - Mark B

@BillyONeal 是的， hashmap 会产生更好的时间复杂度 O(1),O(n), O(1)。@MarkB 他没有在任何地方声明，那你为什么这么想？ - pajton

实际上，我更喜欢你的答案——除非你有非常好的理由，否则应该使用标准容器而不是非标准容器，因为标准容器就是标准容器。哈希容器不能保证O(1)的最坏情况性能，但平均情况可以。对于某些应用程序来说，平摊分析是不可允许的做法。 - Billy ONeal

Answer 3

如果您正在使用Visual Studio，它们有hash_multimap。我还应该补充一点，Boost有一个无序的multimap，在这里。如果您需要一个有序的multimap，STL multimap或有序的multiset STL multiset

- wheaties

---

我认为在大多数情况下，标准容器应该是默认选项，即使没有其他原因，因为它是标准容器。 - Billy ONeal

呸，标准容器。如果人们使用这些，程序就会更少崩溃。那么像我这样的人就不必向老板解释为什么一个无关的代码部分会影响新功能的生产，我们只是“幸运”以前从未发生过。然后我们就永远不必雇佣高价顾问来编写“更好”的容器，直到它们崩溃。你看到你试图破坏的生命周期循环了吗？ - wheaties

@Helltone multimap 按顺序保存项目，但可以每个键接受多个值。插入操作的时间复杂度为 O(log)，而检索操作的时间复杂度最多可达到 O(N)。我认为你应该选择 multimap。 - wheaties

Answer 4

std::multimap 似乎是您正在寻找的。

它将按键存储您的对象，允许您检索最低/最高键值（begin()，rbegin()）和具有给定键的所有对象（equal_range，lower_bound，upper_bound）。

（编辑：如果您只有少量项目，例如少于30个，则还应测试仅使用deque或vector的性能）

- baol

Answer 5

如果我理解正确，您的性能目标是快速完成（1）和（3），而（2）并不那么重要。在这种情况下，考虑到值是唯一的，为什么不只使用std::set<value>，并对（2）进行顺序搜索呢？您将获得（1）和（3）的O(log n)，以及（2）的O(n)。更好的是，如果您的STL有std::hash_set，则（1）和（3）将接近O(1)。

如果您需要比O(n)更好的（2），一个替代方案是拥有一组优先队列。

- Fabio Ceconello

---

我说过操作应该是最常见的优先。我的初始解决方案比你的更好，因为它在插入时是O(1)。 - Giovanni Funchal

我认为如果不在（1）上做出一些让步，你将无法加速其他操作，这里没有什么魔法。无论如何，如果您有std :: hash_set实现，则插入操作非常接近O（1）。 - Fabio Ceconello

你的解决方案“Helltone”尚未计时，因此您不知道它是否更好。特别是，您忘记考虑速度的内存方面，例如缓存和堆使用情况。除非您计时它，否则无法确定它是否更快。对于小值的n，大O（1）比O（log（n））更差。 - Matthieu M.

Answer 6

好的，所以我测试了很多选项，最终采用了基于 Matthieu M. 的想法。我目前正在使用一个 std::map<key_type, std::list<value_type> >，其中 value_type 包含一个指向自身的 std::list<value_type>::iterator，这对于删除非常有用。

删除必须检查向量是否为空，这意味着需要进行 map 查询，可能需要调用 erase。最坏情况下的复杂度是当键是不同的时候，插入的复杂度为 O(logN)，检索的复杂度为 O(1)，删除的复杂度为 O(logN)。与我在测试机上尝试的其他替代方案相比，我得到了非常好的实验结果。

使用 std::vector 在理论复杂度（当键相同时，最坏情况下的删除复杂度为 O(N)）和我所做的实验方面都不如此方法高效。

- Giovanni Funchal