fay*_*aya 8 c++ dictionary stl set data-structures
多集如何工作？如果一个集合没有映射到一个键的值,它是否只保存键？
另外,关联容器如何工作？我的意思是内存中的向量和双端队列顺序定位意味着删除/删除(除了开始[deque]和结束[向量,双端])如果它们很大则很慢.
并且list是一组指针,它们不是顺序地位于存储器中,这导致更长的搜索但更快的删除/移除.
如何存储集,映射,多集和多图,以及它们如何工作？
MSa*_*ers 12
这4个容器通常都使用"节点"实现.节点是存储一个元素的对象.在[multi] set case中,元素只是值; 在[多]映射的情况下,每个节点存储一个密钥及其相关值.节点还存储指向其他节点的多个指针.与列表不同,集合和映射中的节点形成树.您通常会对其进行排列,使得某个节点"左侧"的分支的值小于该节点的值,而某个节点"右侧"的分支的值高于该节点.
现在,查找地图键/设定值等操作非常快.从树的根节点开始.如果匹配,那就完成了.如果根较大,请在左侧分支中搜索.如果root小于您要查找的值,请按指向右侧分支的指针.重复,直到找到值或空分支.
插入元素是通过创建一个新节点,在树中找到它应该放置的位置,然后通过调整它周围的指针插入节点来完成的.最后,有一个"重新平衡"操作,以防止您的树失去平衡.理想情况下,每个左右分支的大小大致相同.重新平衡的工作原理是将一些节点从左向右移动,反之亦然.例如,如果您有值{1 2 3}并且您的根节点将为1,则左侧分支上有2和3,右侧分支为空:
1
\
2
\
3
通过选择2作为新的根节点来重新平衡:
2
/ \
1 3
STL容器使用更智能,更快速的重新平衡技术,但这种详细程度无关紧要.它甚至没有在标准中指定应该使用更好的技术,因此实现可以有所不同.