请你说一说stl里面set和map怎么实现的

[问答题]

崔照旭

首先map和set都是C++的关联容器，***其底层实现都是红黑树（***RB-Tree）。

set是一种关联式容器，其特性如下：

1 set以RBTree作为底层容器

2 所得元素的只有key没有value，value就是key

3 不允许出现键值重复

4 所有的元素都会被自动排序

5 不能通过迭代器来改变set的值，因为set的迭代器是const的

6 set不支持下标操作

multiset相对于set来说，区别就是multiset允许键值重复，在multiset中调用的是RBTree的insert_equal函数，其他的基本与set相同

map和set一样是关联式容器，它们的底层容器都是红黑树，区别就在于map的值不作为键，键和值是分开的。它的特性如下：

1 map以RBTree作为底层容器

2 所有元素都是键+值存在

3 不允许键重复

4 所有元素是通过键进行自动排序的

5 map的键是不能修改的，但是其键对应的值是可以修改的

multimap和map的关系就跟multiset和set的关系一样，multimap允许键的值相同，因此在插入操作的时候用到insert_equal()，除此之外，基本上与map相同。

宗上map和set是根据关键字排序来保证其有序性的，如果允许修改key的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了map和set的结构，导致iterator失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值；而map的迭代器则不允许修改key值，允许修改value值。

发表于 2021-08-27 15:31:16 回复(0)