c++ - 有没有一种有效的方法来搜索队列中的键并覆盖它的值？

Question

我正在使用 C++ 编写一个应用程序，其中我需要实现一个消息队列，该消息队列将不断从网络接收数据(即对象)，每个对象都有一个键(例如公司名称，例如 Oracle、Google 等)。如果队列消费者速度较慢，我可以在队列中拥有大量元素(最大限制可以保持在数百万)。

要求是:如果一个带有键 XYZ 的对象是从网络到达的，并且队列中已经有带有键 XYZ 的对象，那么我需要重写该对象，并且该对象在队列中的位置应保持不变。例如，如果键为“Oracle”且值为 25 的对象是从网络到达的，并且键为“Oracle”且值为 10 的对象已存在于队列中的位置 120，那么我需要将值 10 重写为值 25位置应保持在 120。

我尝试使用线程安全队列和集合来实现这一点，当一个对象从网络到达时，我首先检查集合中是否存在键，如果不存在，我在集合中添加键并在队列中添加对象。如果存在 key ，那么我将对队列中的 key 执行线性搜索并覆盖该对象。

如果我对已在队列中的 key 进行非常频繁的更新，性能将非常缓慢。

有什么有效的方法可以实现吗？提前致谢。

Answer 1

由于队列未排序，因此没有比线性搜索更快地获取数据的真正方法。 您可以使用优先队列。 std::priority_queue 不允许快速更改优先级，您将不得不使用 boost。

你也可以试试这个算法:

• 在 unordered_map 中存储 Google、Microsoft、Apple 等 key 。 还要记录到目前为止已处理的项目数。
• 从队列中删除项目时，增加计数并从映射中删除键。
• 当一个项目到达队列时，
  • 在 map 中查看键是否存在(线性时间)
  • 如果是，则更改 queue[index -count] 的值(线性时间)
  • 如果还没有，存储 map[key] = count + index 新项目放入队列的位置(线性摊销时间)

我不提供任何保证，我没有测试过这个算法。