如何实现C++多图表容器？

Question

例如,使用动态数组实现C++向量,其中每个元素使用连续的内存空间.

我知道C++多图是一对多的关系,但内部结构是什么？

Answer 1

C++标准没有定义标准容器应该如何实现,它只给出了某些约束,就像你对向量所说的那样.

multimaps具有一定的运行时复杂度(O(lg n)用于有趣的操作)和其他保证,并且可以实现为红黑树.这是它们在GNU标准C++库中的实现方式.

@MikeSeymour:实现一个解除引用键/值对引用的迭代器是很棘手的,除非每个节点都有自己的密钥.这也解释了lower_bound/upper_bound. (4认同)
@Chris：我没有考虑太多，但我认为 B、C、D 和 E 可以聚集在一个节点上，也可以表示为单独的节点。不过，我不知道“可搜索”是什么意思。您可以迭代它们，但由于它们具有相同的键，您不能直接选择其中之一（通过值的任何属性）。多重映射仅提供按键查找。 (2认同)
@Chris：我最近查看了 GCC 的实现，发现具有相同键的元素位于不同的节点中。不过，我认为其他实现没有任何理由不选择对它们进行集群。 (2认同)

Answer 2

通常,红黑树.参见例如来自Dobb博士的STL的红黑树.