map的实现机制、map与set的区别

淡淡的烟草味﹌ 2023-05-29 03:35 10阅读 0赞

首先需要知道，STL中标准关联容器set、multiset、map、multimap的内部采用的是一种非常高效的平衡检索二叉树，即红黑树。红黑树是一种平衡二叉树，但是红黑树的统计性能要好于一般的平衡二叉树。红黑树与一般的平衡二叉树相比，红黑树基本上是平衡的，而AVL树是完全平衡的。而为什么map和set的底层使用红黑树呢？那是因为红黑树是平衡二叉树，其插入和删除的效率都是logn，与AVL树相比，红黑树的插入和删除最多只需要3次旋转，而AVL树为了维持其完全平衡性，在最坏的情况下要旋转的次数太多。

关于map的实现，我们需要知道，map中的所有元素都是以键值对形式出现的，同时拥有实值value和键值key。底层是通过红黑树来实现的，其中的key值是经过排序的，而且map不允许两个元素拥有相同的键值，map的插入和删除操作不会使迭代器失效。增加和删除结点对于迭代器的影响很小，除了正在进行操作的结点，对其他的结点都没有什么影响。对于迭代器来说，可以修改value，但不能修改key。既然map的底层是红黑树，那么红黑树插入和查找的优点map也具备。map可以根据key值快速查找记录，查找的时间复杂度基本上是logn。

**为什么map和set的插入删除效率要比其他顺序容器高？**

对于关联容器说，不需要做内存拷贝和内存移动。map和set容器内所有的元素都是以结点的方式来存储，其结点结构和链表差不多，指向父结点和子结点。因此插入的时候只需要稍微做变换，把结点的指针指向新的结点就可以了。删除的时候也类似，把待删除结点的指针指向其他的结点即可。也就是说，map和set的插入删除操作只是简单的将指针换来换去，和内存移动并没有关系。

**为什么每次插入之后，以前保存的迭代器不会失效？**

迭代器就相当于指向结点的指针，内存没有变，指向内存的指针当然也不会变，因此迭代器不会失效。对于vector容器来说，每一次的插入和删除，指针都有可能失效，调用push\_back在尾部插入时也可能会导致迭代器失效，因为vector容器内的数据是连续存放的，所以为了保证内部数据的连续存放，迭代器指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者已经被释放了。即使是push\_back的时候，容器内部空间可能不够，需要一块更大的内存，只有把以前的内存释放，申请更大的内存，复制已有的数据元素到新的内存中，最后再把新元素插入到最后，那么以前的内存指针就不可用了。

**为什么map和set不能像vector一样有个reserve()函数来预分配数据？**

因为在map和set中存储的已经不是元素本身，而是包含元素的结点。其实在map和set中往往使用的是allocator分配器。

**当数据元素增多时（10000和20000个比较），map和set的插入和搜索如何变化？**

在map和set中查找使用的是二分查找法，即当有16个元素时，最多需要比较4次就能找到。当有10000个元素时，最多需要14次，而20000个元素的时候，最多需要15次。可见，当数据量增加一倍的时候，搜索的次数只不过多了1次而已。

**map和set的区别**

（1）map中的元素是key-value（关键字-值）对：关键字起到索引的作用，值则表示与索引相关联的数据。set只是关键字的简单集合，set中每个元素只包含一个关键字。

（2）set的迭代器是const的，不允许修改元素的值，map允许修改value，但是不允许修改key值。因为map和set是根据关键字排序来保证其有序型的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map和set的结构，导致迭代器失效。所以STL中将set的迭代器设置为const的，不允许修改迭代器的值，而map的迭代器则不允许修改key值，允许修改value值。

（3）map支持下标操作，set不支持下标操作。map可以用key做下标，map的下标运算符\[ \]将关键码作为下标去执行查找，如果关键码不存在，则插入一个具有该关键码和mapped\_type类型默认值的元素至map中，因此下标运算符\[ \]在map中需要慎用。