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

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

集合，所有元素都会根据元素的值自动被排序，且不允许重复。

底层实现：红黑树

set 底层是通过红黑树（RB-tree）来实现的，由于红黑树是一种平衡二叉搜索树，自动排序的效果很不错，所以标准的 STL 的 set 即以 RB-Tree 为底层机制。又由于 set 所开放的各种 *** 作接口，RB-tree 也都提供了，所以几乎所有的 set *** 作行为，都只有转调用 RB-tree 的 *** 作行为而已。

适用场景：有序不重复集合

2、map

映射。map 的所有元素都是 pair，同时拥有实值（value）和键值（key）。pair 的第一元素被视为键值，第二元素被视为实值。所有元素都会根据元素的键值自动被排序。不允许键值重复。

底层：红黑树

适用场景：有序键值对不重复映射