c++ - c++ 数据结构建议

Question

我正在寻找 C++ 中的数据结构，我需要一个建议。

我有节点，每个节点都有 unique_id 和 group_id:

1 1.1.1.1
2 1.1.1.2
3 1.1.1.3

4 1.1.2.1
5 1.1.2.2
6 1.1.2.3

7 2.1.1.1
8 2.1.1.2

我需要一个数据结构来回答这些问题:

1. 节点4的group_id是什么
2. 给我属于组 1.1.1 的 unique_id 的列表(可能是 vector )
3. 给我属于组 1.1 的 unique_id 的列表(可能是 vector )
4. 给我属于第 1 组的 unique_id 的列表(可能是 vector )

是否有一种数据结构可以回答那些问题(插入和回答的复杂时间是多少)？还是我应该实现它？

我会很感激一个例子。

编辑:

一开始，我需要建立这个数据结构。大多数操作是按组 ID 读取。插入会发生但比读取少。

时间复杂度比内存空间更重要

Answer 1

对我来说，像组 ID 这样的分层数据需要树结构。 (我假设对于 500 个元素，这并不是真正必要的，但它看起来很自然并且可以很好地扩展。)

树的前两层中的每个元素只包含子 ID 的 vector (如果它们是有序的)或映射(如果它们是无序的)。

树层次结构中的第三层将保存指向叶子的指针，同样在 vector 或映射中，其中包含第四组 ID 部分和唯一 ID。

问题 2-4 可以通过导航树轻松快速地回答。

对于问题 1，需要一个从唯一 ID 到树中叶子的额外映射；插入到树中的每个元素也有一个指向它的指针插入到映射中。