STL库：set和map的使用和原理

set和map是C++标准库中的关联容器，它们中的所有元素都会根据元素的键值（key）自动被排序，又由于红黑树（RB-tree）是一种平衡二叉搜索树，自动排序效果非常好，所以标准的STL中的set和map容器都是以红黑树（RB-tree）为底层机制，又由于map和set所开放的各种操作接口，RB-tree也提供了，所以它们几乎所有的操作行为，都只是转调RB-tree的操作行为。

set介绍：set是存储已排序的无重复的元素，它有过滤重复功能，它元素的键值（key）就是实值（value），实值就是键值，所以set的迭代器不能改变其元素值，否则会严重破坏其set有序的组织，所以其迭代器被定义为底层RB-tree的const_iterator,杜绝写入操作。

set源码：

template< class Key,	      class Compare = less<Key>,  //缺省情况下采用递增排序		  class Alloc = alloc>class set;
set几个重要操作行为接口：
首先要了解接口各元素类型：
其中pair是一个结构体，定义如下：
template <class T1,class T2>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) {}}在上插入返回值pair<iterator,bool>则代表插入时第一个返回迭代器即插入位置，第二个插入成功则返回true,插入失败返回false.
使用练习：
#include <iostream>#include <cstdlib>#include <set>using namespace std;void TestSet(){	set<int> s;	//insert使用	for(size_t i=0;i<5;++i)		s.insert(i);	pair<set<int>::iterator,bool> ret=s.insert(3);	if(ret.second==false)	{		s.insert(ret.first,7);		s.insert(ret.first,5);		s.insert(ret.first,8);		s.insert(ret.first,9);	}	int arr[]={10,1,9,11,6,13,14};	s.insert(arr,arr+7);	set<int>::iterator it;	for (it=s.begin(); it!=s.end(); it++)        cout << " " << *it;    cout << endl;	//erase与find使用	s.erase(0);	s.erase(14);	it=s.find(7);	s.erase(it);	s.erase(s.find(8));	it=s.begin();	++it;	s.erase(it,s.find(4));	for (it=s.begin(); it!=s.end(); it++)        cout << " " << *it;    cout << endl;}int main(){	TestSet();	system("pause");	return 0;}运行结果：
map介绍：map的所有元素为pair,同时拥有实值（value）和键值（key），pair第一元素为键值，第二元素为实值，它不允许两个元素拥有相同的键值，其中可以通过map迭代器修改其元素实值（value）,但不能修改键值（key）,会破坏map有序组织。
map源码：其中Key为键值（key）类型，T为实值（value）类型
template <class Key,class T,          class Compare = less<Key>, //缺省采用递增排序		  class Alloc = alloc>class map;map几个重要操作行为接口：
接口各元素类型：
Operator[]实现原理：返回实值（value）的引用
使用练习：
void TestMap(){	map<char,int> m;	//inset使用	m.insert(pair<char,int> ('a',10));	m.insert(pair<char,int> ('b',10));	m.insert(pair<char,int> ('d',20));	m.insert(pair<char,int> ('c',30));	pair<map<char,int>::iterator,bool> ret=m.insert(pair<char,int> ('d',40));	if(ret.second==false)	{		cout<<"Key:"<<ret.first->first<<" value:"<<ret.first->second;		cout<<endl;	}	map<char,int>::iterator it=m.begin();	++it;	m.insert(it,pair<char,int>('f',40));	m.insert(it,pair<char,int> ('e',10));	for ( it=m.begin() ; it != m.end(); it++ )		cout << (*it).first << " :: " << (*it).second << endl;	//erase使用	it=m.begin();	++it;	++it;	++it;    m.erase (it); 	m.erase('e');	it=m.begin();	map<char,int>::iterator it2=m.end();	--it2;    m.erase ( it, it2 ); 	cout<<endl<< "erase使用：";	for ( it=m.begin() ; it != m.end(); it++ )		cout <<(*it).first << " :: " << (*it).second << endl;		//operator[]使用	m['a']=10;	m['b']=20;	m['c']=30;	m['d']=40;	m['e']=50;	m['f']=60;	it2=m.find('f');	m.erase(it2);	cout<<endl;	for ( it=m.begin() ; it != m.end(); it++ )	{		cout << (*it).first << " :: " << (*it).second << endl;	}}
运行结果：