c++ - 键值数据结构在 O(1) 中搜索键并在 O(1) 中获取最大值

Question

我需要实现一个键值数据结构，在 O(lgn) 或 O(1)中搜索唯一键并在 O(1) 中获取最大值。我在考虑

boost::bimap< unordered_set_of<key> ,multiset_of<value> >

请注意，我的键值数据集中没有重复键。但是，两个键可能具有相同的值。因此我使用 multiset 来存储值。

我需要经常插入/删除/更新键值对

听起来怎么样？

Answer 1

这取决于你想做什么。所以很明显，您想将它用于一些获取最大值的迭代构造。

问题 1：您是否也通过它们的键访问元素？

• 如果是，我可以为您想出两种解决方案：

  1. 使用boost::bimap- 具有对数运行时的简单、经过测试的解决方案。

  2. 创建一个自定义容器，其中包含一个std::map（或更快的按键访问std::unordered_map）和一个堆实现（例如std::priority_queue<std::map<key, value>::iterator>+ 自定义比较器），使它们保持同步等。这是困难的方法，但可能更快。两者上的大多数操作都是 O(logn) （插入、get&pop max、按键获取、删除），但常数有时很重要。虽然您使用std::unordered_map按键操作的访问将是 O(1)。

     您可能还想为新容器编写测试，并针对您最常使用的操作对其进行优化。

• 如果否，您实际上只是使用使用最大值的元素进行访问

  问题2：您是随机插入/删除/更新元素，还是先将所有元素放入一轮，然后逐个删除？

  • 用于随机插入/删除/更新使用std::priority_queue<std::pair<value, key>>

  • 如果您先放入元素，然后将它们一个一个删除，请在第一次删除操作之前使用 andstd::vector<std::pair<value, key>>和it 。std::sort()不要实际删除元素，只需对其进行迭代。

Answer 2

您可以使用 astd::map和 a构建它std::set。

1. 一张地图来保存实际值，即std::map<key, value> m;. 这是存储您的值的地方。将元素插入地图是 O(log n)。

2. 一组指向地图的迭代器；该集合按相应映射条目的值排序，即std::set<std::map<key, value>::iterator, CompareBySecondField> s;类似于（未经测试）：

   template <class It>
   struct CompareBySecondField : std::binary_function<It, It, bool> {
       bool operator() ( const T &lhs, const T &rhs ) const {
           return lhs->second > rhs->second;
       }
   };
   

   然后，您可以使用 获取具有最大值的映射条目的迭代器*s.begin();。

这很容易构建，但是您必须确保在添加/删除元素时更新两个容器。