STL|C++ STL（第十四篇（Set 和 Map）） set|multiset|multimap|map

1、Set 【STL|C++ STL（第十四篇（Set 和 Map））】set 的特性是，所有元素都会根据元素的键值自动被排序。set 的元素不像 map 那样可以同时拥有实值（value）和键值（key），set 元素的键值就是实值，实值就是键值。 set 不允许两个元素有相同的键值。
因为 set 元素值就是其键值，关系到 set 元素的排列规则，如果任意改变 set 元素值，会严重破坏 set 组织。所以 set 的迭代器是 const_iterator，杜绝写入操作。
set 拥有与 list 相同的某些性质：当客户端对它进行元素新增操作或删除操作时，操作之前的所有迭代器，在操作之后都依然有效。当然，被删除的那个元素的迭代器必然是个例外。
由于 RB-tree 是一种平衡二叉搜索树，自动排序的效果很不错，所以标准 STL set 即以 RB-tree 为底层机制。又由于 set 所开放的各种操作接口， RB-tree 也都提供了，所以几乎所有的 set 操作行为，都只是转调用 RB-tree 的操作行为而已。大概的代码如下：

template, class Alloc = alloc> class set { public: typedef Key key_type; typedef Key value_type; typedef Compare key_compare; // key 的比较函数 typedef Compare value_compare; // value 的比较函数 typedef rb_tree<......> rep_type; typedef typename rep_type::const_pointer pointer; //一堆跟萃取有关的类型，都是 const 的 ...... rep_type t; // 底层采用红黑树来表现 set public: set()；//一系列重载函数 iterator begin() const { return t.begin(); } iterator end() const { return t.end(); } bool empty() const { return t.empty(): } size_type size() const { return t.size(); } xxx insert( ... ){ return t.xxxx(); } xxx erase(...) { return t.xxxx(); } };

2、Map map 特性是，所有元素都会根据元素的键值自动被排序。map 的所有元素都是pair，同时拥有实值（value）和键值（key）。pair的第一个元素被视为键值，第二元素被视为实值。map不允许两个元素拥有相同的键值。

template struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair() : first(T1()), second(T2()) {} pair(const T1& a, const T2& b) : first(a), second(b){} };

我们不能更改 map 的键值，因为键值关系到 map 的排序规则。但是我们可以修改元素的实值，因为实值并不影响 map 元素的排列规则。
和 set 一样 map 底层也使用的是 RB-tree 来实现的。只是比较元素大小时，map 比较的是 pair 的第一个元素。大概代码如下：

template<......> class map { public: typedef Key key_type; //键值类型 typedef T data_type; //实值类型 typedef T mapped_type; typedef pair value_type; //元素型别 typedef Compare key_compare; //键值比较函数 Compare comp; public: //比较时，使用pair 的第一个元素 bool operator()( const value_type& x, const value_type& y ) const { return comp( x.first, y.first); }private: typedef rb_tree, key_compare, Alloc> rep_type; rep_type t; //以红黑树作为底层，表现map //剩下的函数跟 set 基本是一样的 };

3、multiset 和 multimap multiset 特性以及用法和 set 完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制 RB-tree 的 insert_equal() 而非 insert_unique()。
而multimap 和 map 完全相同，唯一的差别也是允许键值的重复，也是使用了 RB-tree 的 insert_equal() 而非 insert_unique() 函数。
感谢大家，我是假装很努力的YoungYangD（小羊）。
参考资料：
《STL源码剖析》