Какой правильный термин для «объединяющей» очереди событий?

Question

Скажем, у меня есть очередь объектов "события", где каждый объект имеет "тип события" и какое-то поле данных.В C ++ это может выглядеть следующим образом:

enum class EventType
{
    A,
    B,
    C
};

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

Скажем, я хотел очередь этих событий, и я хочу, чтобы очередь имела следующие свойства:

• Когда событиепомещается в очередь, все существующие события того же EventType удаляются.Поэтому, когда событие извлекается из очереди, оно всегда является самым недавно добавленным экземпляром его EventType
• События различных EventType извлекаются вчтобы их толкнули.(pop() не будет ожидать никаких аргументов).

Следовательно, очередь FIFO относительно Event и 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 s.
• Если число типов событий ограничено, могут быть применены несколько соображений, потому что (для обычных архитектур) сложность времени выполнения O(N) может быть приблизительно равна O(1).В таком случае std::vector в качестве базовой структуры данных, вероятно, более эффективен из-за кэшей.
• В простом примере, о котором я сообщил, push - это O(N).Если у вас есть несколько типов EventType s, вы можете сделать структуру данных более эффективной в операции push.Короче говоря, вы можете использовать вспомогательную std::unordered_map<EventType, list::iterator> (то есть хэш-карту ), чтобы избежать линейного поиска.После удаления std::list не делает недействительными итераторы, поэтому хеш-таблица остается согласованной.