集合、多重集、映射和多重映射如何在内部工作 [英] How sets, multisets, maps and multimaps work internally

问题描述

多重集如何工作?如果一个集合不能有一个值映射到一个键，它是否只包含键?

How do multisets work? If a set can't have a value mapped to a key, does it only hold keys?

另外，关联容器是如何工作的?我的意思是内存中的向量和双端队列是顺序定位的，这意味着如果它们很大，删除/删除(除了开始[deque]和结束[vector，deque])会很慢.

Also, how do associative containers work? I mean vector and deque in the memory is located sequentially it means that deleting/removing (except beginning [deque] and end [vector, deque]) are slow if they are large.

而列表是一组指针，它们不是按顺序位于内存中的，这会导致更长的搜索但更快的删除/删除.

And list is a set of pointers which are not sequentially located in the memory which causes longer search but faster delete/remove.

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

How are sets, maps, multisets and multimaps stored and how do they work?

推荐答案

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

These 4 containers are typically all implemented using "nodes". A node is an object that stores one element. In the [multi]set case, the element is just the value; in the [multi]map case each node stores one key and its associated value. A node also stores multiple pointers to other nodes. Unlike a list, the nodes in sets and maps form a tree. You'd typically arrange it such that branches on the "left" of a certain node have values less than that node, while branches on the "right" of a certain node have values higher than that node.

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

Operations like finding a map key/set value are now quite fast. Start at the root node of the tree. If that matches, you're done. If the root is larger, search in the left branch. If the root is smaller than the value you're looking for, follow the pointer to the right branch. Repeat until you find a value or an empty branch.

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

Inserting an element is done by creating a new node, finding the location in the tree where it should be placed, and then inserting the node there by adjusting the pointers around it. Finally, there is a "rebalancing" operation to prevent your tree from ending up all out of balance. Ideally each right and left branch is about the same size. Rebalancing works by shifting some nodes from the left to the right or vice versa. E.g. if you have values {1 2 3} and your root node would be 1, you'd have 2 and 3 on the left branch and an empty right branch:

1
 
  2
   
    3

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

This is rebalanced by picking 2 as the new root node:

  2
 / 
1   3

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

The STL containers use a smarter, faster rebalancing technique but that level of detail should not matter. It's not even specified in the standard which better technique should be used so implementations can differ.

这篇关于集合、多重集、映射和多重映射如何在内部工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！