3

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

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

我不能使用std::priority_queue，因为它只支持移除头部。

目前，我使用的是未排序的std::list. 插入是通过将新元素推到后面来执行的 (O(1))。操作 2list::sort在执行实际检索之前使用 (O(N*logN))对列表进行排序。然而，去除是 O(n)，这有点贵。

有更好的数据结构的想法吗？

4

6 回答 6

4

你能颠倒集合的顺序，即按<value, key>顺序存储它们吗？

std::map然后，您可以花O(logn)时间插入O(n)删除（遍历整个集合）和O(logn)随机删除值（这将是所述映射的关键）。

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

于 2010-04-01T14:39:58.347 回答
4

当您需要订购时，请使用订购的容器。以后再支付分拣费用是没有意义的。

您当前的解决方案是：

  • 插入O(1)
  • 恢复O(N log N)
  • 删除O(N)（在不保留另一个索引的情况下尽可能好）

只需使用 astd::multi_map你就可以拥有：

  • 插入O(log N)
  • 检索O(log N)<- 好多了不是吗？我们需要找到范围的终点
  • 移动O(N)

现在，您可以使用 a 做得更好std::map< key, std::vector<value> >：

  • 插入O(log M)whereM是不同键的数量
  • 检索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)--> 在 hash map 中查找O(1)，取消引用O(1)，从向量中移除，O(N/M)因为我们需要移动大约一半的向量内容。使用 alist会产生O(1)......但可能不会更快（取决于内存权衡的元素数量）。

还要记住，哈希映射复杂性是摊销的。触发重新分配，因为您超出了负载因子，并且此特定插入将花费很长时间。

我真的会std::map<key_type, std::vector<value_type> >代替你去。这是最划算的。

于 2010-04-01T17:06:00.717 回答
1

如果您使用的是 Visual Studio，他们有 hash_multimap。我还应该补充一点，Boost 有一个无序的多图，这里。如果您需要有序多图、STL 多图或有序多集STL 多集

于 2010-04-01T14:38:28.090 回答
0

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

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

（编辑：如果你只有几个项目，比如少于 30 个，你还应该测试只使用双端队列或向量的性能）

于 2010-04-01T14:52:44.627 回答
0

如果我理解得很好，您的性能目标是快速（1）和（3），而（2）并不那么重要。在这种情况下，鉴于值是唯一的，为什么不只使用 astd::set<value>并顺序搜索 (2) 呢？(1) 和 (3) 的 O(log n) 和 (2) 的 O(n)。更好的是，如果您的 STL 具有std::hash_set，则 (1) 和 (3) 的 O(1) 接近。

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

于 2010-04-01T15:01:40.397 回答
0

好的，所以我测试了很多选项，最终得到了基于Matthieu M.想法的东西。我目前正在使用 a std::map<key_type, std::list<value_type> >，其中value_type包含 astd::list<value_type>::iterator本身，这对于删除很有用。

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

就理论复杂性（当键相同时删除的 O(N) 最坏情况）和我一直在做的实验而言，使用 astd::vector的效率较低。

于 2010-04-02T12:24:10.473 回答