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

问题描述

多集如何工作？如果一个集合不能有一个值映射到一个键，它只保存键？

关联容器如何工作？我的意思是存储器中的向量和deque顺序地位于它意味着删除/删除（除了开始[deque]和结束[vector，deque]）是缓慢的，如果他们是大的。

并且列表是一组指针，它们不是顺序地位于存储器中，这导致较长的搜索但是更快地删除/删除。

如何集，地图，多集

解决方案

这4个容器通常都是使用nodes来实现的。节点是存储一个元素的对象。在[multi] set情况下，元素只是值;在[多]图的情况下，每个节点存储一个键及其相关值。节点还存储到其他节点的多个指针。与列表不同，集合和映射中的节点形成树。您通常会将其排列为使得某个节点的左上的分支具有小于该节点的值，而某个节点的右上的分支具有比该节点更高的值。

查找地图键/值的操作现在相当快。从树的根节点开始。如果匹配，你就完成了。如果根较大，在左侧分支中搜索。如果根小于您要查找的值，请按照指针指向正确的分支。重复此操作，直到找到一个值或一个空分支。

插入元素是通过创建一个新节点，在树中找到应放置的位置，然后通过调整节点周围的指针将节点插入。最后，有一个重新平衡操作，以防止你的树结束了所有失去平衡。理想地，每个右和左分支具有大约相同的大小。重新平衡通过将一些节点从左向右移动或反之亦然。例如。如果你有值{1 2 3}，你的根节点是1，你左边分支上有2和3，右边有一个空的分支：

  1 
 \ 
 2 
 \ 
 3 
  

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

  2 $ b $ STL容器使用更智能，更快速的重新平衡技术，但是，那个层次的细节不要紧。它甚至没有在标准中指定更好的技术，因此实现可能不同。
 
How do multisets work? If a set can't have a value mapped to a key, does it only hold keys?

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?
解决方案
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.

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
This is rebalanced by picking 2 as the new root node:
  2
 / \
1   3
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屋！