关于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的列表(可能是向量)
3. 给我属于1.1组的unique_id的列表(可能是向量)
4. 给我属于组1的unique_id的列表(可能是向量)

是否有可以回答这些问题的数据结构(插入和回答的复杂时间是多少)？或者我应该实施它？

我会很感激一个例子.

编辑:

在开始时,我需要构建这个数据结构.大部分动作都是按组ID阅读.插入会发生但不会再读.

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

Answer 1

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

树的前两个级别中的每个元素将仅保存向量(如果它们是有序的)或子ID的映射(如果它们是无序的).

树层次结构中的第三级将保留指向叶子的指针,同样在向量或映射中,其包含第四组ID部分和唯一ID.

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

对于问题1,需要从树中的唯一ID到树叶的附加地图; 插入到树中的每个元素也都有一个指向它的指针插入到地图中.

Answer 2

我不确定是否有适合此目的的完美 DS。但我想利用地图。对于问题 1、插入和删除，它的效率为 O(1)。问题 2、3、4 出现了问题，其中效率将为 O(n)，其中 n 是节点数。