STL常用容器归纳——关联容器

目录：

• set
  集合
  包含的都是关键字, 每个都是唯一的;
  搜索, 删除 , 插入的时间复杂度是o(log(n))
• map
  映射
  包含的元素都是关键字-值, 按照关键字进行了排序
  搜索, 删除, 插入的时间复杂度是o(log(n))
  常用红黑树实现;

set

头文件

#include<set>
using namespace std;

创建

set<type_name> s 				//空集合
set<typename,greater<int> > s 	//带大于比较器的set，默认是小于

int a[3] = {1, 2, 3} ;
set<int> s2(a, a + 3) ;			//用数组初始化一个set

set<int> s1 ;
set<int> s2(s1) ;				//用拷贝构造函数初始化set

set<int> s1 ;
set<int> s2(s1.begin(), s1.end()) ;//区间初始化

常用成员函数

s.begin()     　　　　   //返回set容器的第一个元素的定位器
s.end() 　　　　 		 //返回set容器的最后一个元素之后的定位器，不是最后一个元素
s.clear()   　　  	     //删除set容器中的所有的元素
s.empty() 　　　　　	 //判断set容器是否为空
s.max_size() 　 		 //返回set容器可能包含的元素最大个数
s.size() 　　　　 		 //返回当前set容器中的元素个数
s.erase(iterator) 		 //删除定位器iterator指向的值
s.erase(first,second)	 //删除定位器[first,second)之间的值
s.erase(key_value)		 //删除键值key_value的值
s.count(elem) 		     //用来查找set中某个键值出现的次数返回0或1
s.find(elem)   			 //返回给指定元素的定位器，如果没找到则返回end()
s.insert(key_value)	 	 //将key_value插入到set中
s.inset(first,second)    //将定位器first到second之间的元素插入到set中
s.lower_bound(key_value) //返回第一个大于等于key_value的定位器
s.upper_bound(key_value) //返回最后一个大于等于key_value的定位器

测试程序

map

头文件

#include<map>
using namespace std;

创建

map<type1,type2> m; //创建一个空的map

常用成员函数

s.begin()     　　　　   //返回map容器的第一个元素的定位器
s.end() 　　　　 		 //返回map容器的最后一个元素之后的定位器，不是最后一个元素
s.clear()   　　  	     //删除map容器中的所有的元素
s.empty() 　　　　　	 //判断map容器是否为空
s.max_size() 　 		 //返回map容器可能包含的元素最大个数
s.size() 　　　　 		 //返回当前map容器中的元素个数
m.count(key)			 //返回对应某个关键字的元素的个数
s.erase(iterator) 		 //删除定位器iterator指向的值
s.erase(first,second)	 //删除定位器[first,second)之间的值
s.erase(key)			 //删除关键字为key的元素
m.find(key)				 //返回与给定关键字相等的元素的定位器没找到返回end()
m.insert(pair<type1,type2>(key,value))	//

测试程序