STL关联容器类——set、multiset、map、multimap详解

1、关联容器：
set, multiset, map, multimap  是一种非线性的树结构，具体的说采用的是一种比较高效的特殊的平衡检索二叉树—— 红黑树结构。
set  又称集合，实际上就是一组元素的集合，但其中所包含的元素的值是唯一的，且是按一定顺序排列的，集合中的每个元素被称作集合中的实例。因为其内部是通过链表的方式来组织，所以在插入的时候比vector  快，但在查找和末尾添加上比vector  慢。 
multiset  是多重集合，其实现方式和set  是相似的，只是它不要求集合中的元素是唯一的，也就是说集合中的同一个元素可以出现多次。 
map 提供一种“键- 值”关系的一对一的数据存储能力。其“键”在容器中不可重复，且按一定顺序排列（其实我们可以将set  也看成是一种键- 值关系的存储，只是它只有键没有值。它是map 的一种特殊形式）。由于其是按链表的方式存储，它也继承了链表的优缺点。   
multimap  和map 的原理基本相似，它允许“键”在容器中可以不唯一。 

基于以上特点，   
1、关联容器对元素的插入和删除操作比vector 要快，因为vector 是顺序存储，而关联容器是链式存储；比list  要慢，是因为即使它们同是链式结构，但list是线性的，而关联容器是二叉树结构，其改变一个元素涉及到其它元素的变动比list  要多，并且它是排序的，每次插入和删除都需要对元素重新排序；   
2、关联容器对元素的检索操作比vector 慢，但是比list  要快很多。vector  是顺序的连续存储，当然是比不上的，但相对链式的list  要快很多是因为list  是逐个搜索，它搜索的时间是跟容器的大小成正比，而关联容器 查找的复杂度基本是Log(N)  ，比如如果有1000 个记录，最多查找10 次，1,000,000 个记录，最多查找20  次。容器越大，关联容器相对list  的优越性就越能体现；   
3、在使用上set  区别于vector,deque,list  的最大特点就是set  是内部排序的，这在查询上虽然逊色于vector ，但是却大大的强于list  。   
4、在使用上map 的功能是不可取代的，它保存了“键- 值”关系的数据，而这种键值关系采用了类数组的方式。数组是用数字类型的下标来索引元素的位置，而map 是用字符型关键字来索引元素的位置。在使用上map 也提供了一种类数组操作的方式，即它可以通过下标来检索数据，这是其他容器做不到的，当然也包括set  。（STL  中只有vector  和map 可以通过类数组的方式操作元素，即如同ele[1]  方式） 

2、set与multiset  
增：
set.insert() //添加

删：
set.erase(value)
set.erase(iterator)；//删除某值
set.clear()；//删除所有

改：查：
set.empty(); //是否为空
set.size()；//元素个数
set.count(value) 返回某个值元素的个数 

iterator find( const key_type &key ); //返回key的位置
pair equal_range(const Key& key) const: //回容器中元素值等于key的迭代指针[first, last)， *p.first,*p.second，获取迭代器值

iterator lower_bound( const key_type &key ); //返回一个指向大于或者等于key值的第一个元素的迭代器 
iterator upper_bound( const key_type &key ); //返回一个指向大于key值的第一个元素的迭代器 

3、map和multimap  
map> lt;
lt.insert(make_pair("**", *));
map>::iterator it;  it->first;;;it->second ；获取指针的键值对