algorithm - 多级遍历的数据结构

Question

我有一个处理以下结构中数据的应用程序:

struct Message
{
   int    time;
   string name;
   string details;
};

例如，我可能有一个如下所示的数据集:

9:00:00 Bob  <Info>
9:01:00 John <Info>
9:05:00 Bob  <Info>
9:11:00 Mary <Info>
9:17:00 John <Info>
9:25:00 Mary <Info>
9:30:00 Bob  <Info>

我将有一个 Message 结构列表，代表数据集中的每一行。

我需要对此数据执行的一些操作包括:

• 按时间顺序收集所有数据并dostuff()
• 按时间顺序从 John(或其他人)那里收集所有数据，然后 dostuff()

所以，我需要一种遍历列表的方法，这样我就可以按时间顺序传递每条消息，还可以选择一个人，然后按时间顺序只传递他们的消息。

我的想法是有一个这样的结构:

struct Node
{
   Message* message;
   Node*    next_time;
   Node*    next_name;
};

其中next_time按时间顺序指向下一个Node，next_name指向下一个Node属于 message->name。 Root 结构指向每个类型的第一个。

struct Root 
{
   Node* first_time;
   Node* first_bob;
   Node* first_john;
   Node* first_mary;

   Node* last_time;
   Node* last_bob;
   Node* last_john;
   Node* last_mary;
};

这是一张图片来说明这一点。

这种结构使我能够相当轻松地遍历每条消息，或者只遍历 Bob 的消息，或者只遍历 John 的消息，等等。

但是，我担心这可能比需要的更复杂。我也担心维护(见下文)。我需要搜索/选择/读取操作非常快，我认为它们是。而且我需要插入操作相当快。但是现在，对于我插入的每个 Message，我必须 (1) 更新一些 next_time 指针和 (2) 更新一些 next_name 指针。

我的问题是: 是否存在已经提供此类功能的数据结构？如果不是，我是否正确地解决了这个问题？

如果可能，请提供任何 C++ 或 C# 代码示例。

谢谢。

附加:假设稍后我想添加到我的 Message 结构中。假设我添加了一个名为 City 的字段。现在，我可能想这样做:

• 按时间顺序收集来自特定城市的所有数据和dostuff()

这需要添加一个 next_city，然后对于每次插入，我都必须更新 next_time、next_name 和 下一个城市。

进一步，假设我想这样做:

• 按时间顺序从特定的City 和特定的name 收集所有数据和dostuff()

我认为这会使问题变得异常困难，除非我选择遍历每个 Message 并跳过我不关心的那些。

Answer 1

所有消息的简单链表(按时间排序)。

struct Node
{
   Message* message;
   Node*    next_name;
};

这将满足要求 1。您可以在 O(1) 中添加 () 和 getAll()

一个单独的 hashmap，以 User 为键，以 Node* 列表为值。

Hashmap
{key = User, value = List(Message*)}

这将满足要求 2。您可以将新条目添加到特定用户列表的末尾 O(1) 并且 getAllOfUser() 也可以在 O(1) 中运行