“合并”事件队列的正确术语是什么？

Question

假设我有一个“事件”对象队列，其中每个对象都有一个“事件类型”和某种数据字段。在 C++ 中可能是这样的：

enum class EventType
{
    A,
    B,
    C
};

struct Event
{
     EventType type;
     std::string message;
};

比如说，我想要一个这些事件的队列，并且我希望该队列具有以下属性：

• 将事件推送到队列时，相同

  EventType

  的任何现有事件都将被删除。因此，当一个事件从队列中弹出时，它始终是其 EventType

   的最新

  最近添加
实例
• different

  EventType

  的事件按照推送的顺序弹出。 （

  pop()

  不会有任何争论）。

因此，队列对于

Event

而言是 FIFO，对于

LIFO

而言是

EventType

。

示例：

以下事件被推送到队列中（字母为事件类型，数字为实例编号）

A1 A2 C1 C2 C3 B1 B2 A3

如果随后调用 pop() 3 次，则按顺序返回的项目将为

C3 B2 A3

这种类型的数据结构有名称吗？有实现示例吗？

Answer 1

---

免责声明：非常有效的数据结构的设计，它与域（架构）和数据上下文严格相关。以下解决方案旨在理论上对一般情况有效。有关更多详细信息，请参阅最终考虑因素。

---

结构设计

这个想法很简单。

保留代表队列的底层数据结构。

每次插入新事件时，检查该类型是否已存在。在这种情况下，我们可以删除该元素。通过这种方式，我们维护第一个属性（每个类型只有一个实例，这意味着我们总是弹出该类型的最新属性）。

最后，我们将新实例插入队列末尾。因此，我们保留第二个属性。

---

简单实现的示例

#include <algorithm>
#include <list>
#include <utility>

class QueueWithAGoodName {
 public:
  using reference = Event&;

  void push(Event event) {
    if (const auto finder =
            std::find_if(queue_.begin(),
                         queue_.end(),
                         [eventType = event.type](const Event& event) {
                           return event.type == eventType;
                         });
        finder != queue_.end()) {
      queue_.erase(finder);
    }
    queue_.push_back(std::move(event));
  }

  reference front() { return queue_.front(); }

  void pop() { queue_.pop_front(); }

 private:
  std::list<Event> queue_;
};

实例

---

思考与分析

• 对于我的示例，我使用了

  std::list

  作为底层数据结构。事实上，如果您经常在“中间”删除，

  std::list

  会很方便。而且，删除后，迭代器不会失效。如果我们想改善队列，这是一个很好的属性。

• QueueWithAGoodName::push

  的运行时间复杂度为：

  O(N)

  （因为我们应用线性扫描来查找类型）。其中

  N

  是队列的大小。

• QueueWithAGoodName::pop

  和

  QueueWithAGoodName::front

  是

  O(1)

  。

进一步考虑

• 对于这种类型的数据结构，有一个重要的属性。每种类型我们有一个实例。这意味着

  N

  （队列的大小）的上限是

  EventType

  的数量。
• 如果事件类型的数量有限，则可以应用多种考虑因素，因为（对于常见架构）运行时复杂度

  O(N)

  可以近似为

  O(1)

  。在这种情况下，由于缓存，

  std::vector

  作为底层数据结构可能会更有效。
• 在我报告的简单示例中，

  push

  是

  O(N)

  。如果您有多种类型的

  EventType

  ，您可以使数据结构在推送操作中更加高效。简而言之，您可以使用辅助

  std::unordered_map<EventType, list::iterator>

  （即哈希图）来避免线性搜索。擦除后，

  std::list

  不会使迭代器失效，因此哈希表保持一致。

Answer 2

对于合并队列的高性能 Java 实现，您可以检查 LMAX 中的 CoalescingRingBuffer