c++ - 在O(1)中用minValue和maxValue实现MinMax PriorityQueue

Question

我正在std :: multimap上实现MinMax Priority Queue，并且可能在一个键上具有多个值，并且我已经具有以O（1）时间复杂性编写的minKey和maxKey函数（使用begin（）和end（）） 。

现在，我在实现minValue和maxValue时遇到问题。显而易见的解决方案之一是使用仅该pqueue的值并访问O（1）中的min和max的数据结构（例如，使用std :: set）。

显然，此解决方案的缺点是重复的内存大小，我当然不希望这样做。

我正在考虑分别使用指向minValue和maxValue的指针的解决方案。插入到PQ会很容易，只需与这些指针进行比较...现在删除该怎么办？

插入：我可以在某个键上有多个值

删除：从某个键中删除任何值（如果键不存在，则引发异常）。

您对如何在O（1）时间复杂度中实现minValue和maxValue有任何建议吗？

提前致谢

Answer 1

让我们回顾一下你想要的。您想为必须根据两个不同比较函数排序的键值对实现一个双头优先级队列。一个比较一对的关键部分，另一个比较值的部分。

我认为，单个容器的职责太多。我建议您实现一个仅使用单个比较的优先级队列，并使用两个具有相同内容但比较功能不同的单独优先级队列。当然，这就像您的并行std::set想法一样重复了数据结构，但是您将要实现的更简单的一次比较优先级队列通常会（再）有用。即使用户只需要存储简单的非配对类型并且不需要多次排序，也可以使用它。如果单个对象的大小很大，则可以将指针存储在一个对象中，以节省重复使用的空间。

忽略诸如间隔堆之类的非常不同的解决方案，我建议使用键值对的std::mutiset而不是std::multimap，因为映射永远不会用于通过键查找任意元素。您只需要找到第一个和最后一个元素。

如果您对多比较规则设计一无所知，那么可以用来实现队列的是多索引容器。 Boost具有此类容器的库。