【STL-set与map】

set和map都是关联式容器，底层实现都是红黑树，先要了解红黑树的实现，明白了红黑树，可以更好的理解set和map。
首先，红黑树插入和删除操作都是在O(logn)时间内完成的

首先，一个节点中key和data加一起是value。
几个优点，也是set和map要使用rb_tree来实现的原因
1.利用平衡二叉树的特性，排列规则有助于search和insert，并保持适度平衡：没有一个节点过深
2.提供遍历以及iterators，按照++iter遍历，能够获取排序的装填
3.两种insertion：insert_unique()表示key一定在整个tree中独一无二，否则插入失败。insert_equal()表示节点的key可以重复。
另外：我们不应该使用rb_tree的iterators改变元素值。但是map运行data改变，而key是不可变的。所以并未阻止我们去改变元素的值。
部分源码：

template
class rb_tree{
protected:
	typedef_rb_tree_noderb_tree_node;
	...
public:
	typedef rb_tree_node* link_type;
	....
protected: // 数据，红黑树的类对象本身的大小只是这个三个数据的大小
	size_type node_count;  // rb_tree的大小（节点数量）
	link_type header;  // 虚拟头节点
	Compare key_compare; // key的大小比较准则
};

几个需要熟记的点：
1.set和multiset都是以rb_tree为底层机构，因此有元素自动排序特性，排序的依据是key，而set和multiset的value和key合一：value就是key
2.我们无法使用set/multiset的iterator改变元素值，iterator底层是rb_tree的const-iterator，就是为了禁止user对元素赋值
3.set和multiset的区别：set的key必须独一无二，因此insert用的是rb_tree的insert_unnique；而multiset的key可以重复，因此其insert用的是rb_tree的insert_equal。
部分源码

template, class Alloc=alloc>
class set{
public:
	typedef Key key_type;
	typedef Key value_type;
	typedef Compare key_compare;
	typedef Compare value_compare;
private:
	typedef rb_tree,key_compare,Alloc>rep_type;
	rep_type t; // 红黑树变量t
public:
	typedef typename rep_type::const_iterator iterator; // 迭代器是const
	...
}
// 使用set
setiset; // 默认了一部分
set,alloc>;
tmplate,less,alloc>class rb_tree;

需要熟记的点：
1.map/multimap以rb_tree为底层结构，因此有自动排序的特性，排序的依据还是key
2.允许修改data，不允许修改key，通过将key设定为const类型
3.map和multimap的区别：map的key必须独一无二，因此Insert用的是rb_tree的insert_unique；而multimap的key可以重复，因为其insert用的是rb_tree的insert_equal。

1.set, map分别和multiset，multimap的区别：在于元素可不可以重复，插入元素的时候调用insert_unique还是insert_equal
2.set的key是通过设置迭代器为const类型来是的不能改变key的值，而map是通过利用pair类型，来设置key为const类型，使得不能改变key的值，但是可以改变data的值。
3.使用时根据具体情况选择合适的容器。

参考：侯捷STL课程
博客：https://blog.csdn.net/qq_44559016/article/details/117434703