我正在寻找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

我需要一个数据结构来回答这些问题:
  • 节点4
  • 的group_id是什么
  • 给我列出属于组1.1.1的unique_id的列表(可能是 vector )
  • 给我列出属于组1.1
  • 的unique_id的列表(可能是 vector )
  • 给我列出属于组1
  • 的unique_id的列表(可能是 vector )

    是否存在可以回答这些问题的数据结构(插入和回答的复杂时间是多少?)?还是应该实现?

    我将不胜感激。

    编辑:

    在开始时,我需要构建此数据结构。大多数操作是按组ID进行读取。插入会发生,但会少于阅读。

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

    最佳答案

    对我来说,诸如组ID之类的分层数据需要树结构。 (我认为对于500个元素来说,这并不是真正必要的,但是看起来很自然并且可以很好地扩展。)

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

    树层次结构中的第三级将再次在 vector 或映射中保留指向叶子的指针,这些指针包含第四组ID部分和唯一ID。

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

    对于问题1,需要一张从唯一ID到树上叶子的映射。插入到树中的每个元素还具有指向它插入到 map 中的指针。

    09-10 08:46
    查看更多