c++ - sets、multisets、maps 和 multimaps 如何在内部工作

Question

多重集如何运作？如果集合不能将值映射到键，它是否只包含键？

此外，关联容器如何工作？我的意思是内存中的 vector 和 deque 是按顺序放置的，这意味着如果它们很大，删除/删除(除了开始 [deque] 和结束 [vector, deque])会很慢。

而 list 是一组指针，它们在内存中没有按顺序定位，这导致搜索时间更长但删除/删除速度更快。

集合、映射、多重集合和多重映射如何存储以及它们如何工作？

Answer 1

这 4 个容器通常都是使用“节点”实现的。节点是存储一个元素的对象。在 [multi]set 的情况下，元素就是值；在 [multi]map 情况下，每个节点存储一个键及其相关值。一个节点还存储多个指向其他节点的指针。与列表不同，集合和映射中的节点形成一棵树。您通常会对其进行安排，使某个节点“左侧”的分支的值小于该节点，而某个节点“右侧”的分支的值高于该节点。

查找 map 键/设置值等操作现在非常快。从树的根节点开始。如果匹配，你就完成了。如果根较大，则在左分支中搜索。如果根小于您要查找的值，请按照指向右分支的指针进行操作。重复直到找到值或空分支。

插入一个元素是通过创建一个新节点，在树中找到应该放置它的位置，然后通过调整它周围的指针来插入该节点来完成的。最后，还有一个“重新平衡”操作来防止你的树最终失去平衡。理想情况下，每个左右分支的大小大致相同。重新平衡的工作原理是将一些节点从左移到右，反之亦然。例如。如果你有值 {1 2 3} 并且你的根节点是 1，你将在左分支上有 2 和 3 以及一个空的右分支:

1
 \
  2
   \
    3

这是通过选择 2 作为新的根节点来重新平衡的:

  2
 / \
1   3

STL 容器使用更智能、更快速的重新平衡技术，但细节级别应该无关紧要。标准中甚至没有指定应该使用哪种更好的技术，因此实现可能会有所不同。