【STL】容器分类及用法(图文+代码详解)_图解c++中的stl容器用例

STL容器

• 顺序容器（sequence containers）

  1.vector
  结构如下图所示
  
  只可通过push_back()从尾部添加元素

  vector<int> vec;
  	vec.push_back(2);
  	vec.push_back(1);
  	vec.push_back(8);
  1
  2
  3
  4

  获取元素时

  cout<<vec[2];//不会有范围检查
  	cout<<vec.at(2);//at()如果超出容器范围会抛出范围错误提示越池
  1
  2

  遍历vector的三种操作

  	//vector可以像遍历数组一样被遍历
  	for(int i=0;i<vec.size();++i)cout<<vec[i]<<endl;
  	//但最规范的遍历vector的方式是使用迭代器,更标准，遍历速度更快
  	//这种方式也适用于所有类型容器的遍历
  	for(vector<int>::iterator itr=vec.begin();itr!=vec.end();++itr)cout<<*itr<<endl;
  	//C++11 引入的新遍历方法
  	for(it:vec)cout<<it<<endl;
  1
  2
  3
  4
  5
  6
  7

  所有容器都具备的5个功能函数

  if(vec.empty()){
  		cout<<"impossible"<<endl;//1)容器是否为空
  	}
  	cout<<vec.size()<<endl;//2)求容器大小
  	
  	vector<int> vec2(vec);//3)复制整个容器
  	
  	vec.clear();//4)清除容器中所有元素，此时vec.size()==0
  	
  	vec2.swap(vec);//5)交换两个数组中的元素
  	//此时vec2.size()==0,vec.size()==3
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

  2.deque(double-ended queue)
  结构如英文，是一个双端队列
  
  deque可从两端添加元素，效率极高，复杂度为O(1),但从中间添插入元素的复杂度为O(n),查询的时间复杂度也为O(n)

  //deque详解-------------------------------
  	
  	//deque与vector的区别就是vector只能从尾部添加元素，而deque可以从两端添加
  	deque<int> deq={4,1,7};
  	
  	deq.push_front(2);//deq:{2,4,1,7}
  	
  	deq.push_back(10);//deq:{2,4,1,7,10}
  	
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

  deque特点:慢插入（中间）O(n)/慢查询 O(n)

  3.list
  结构如图
  
  如图，list是一个双向链表

  //List详解--------------------------------
  	//--double linked list
  	list<int> mylist = {5,2,9};
  	mylist.push_back(6);//mylist:{5,2,9,6}
  	mylist.push_front(4);//mylist:{4,5,2,9,6}
  	list<int>::iterator itr = find(mylist.begin(),mylist.end(),2);//itr 此时指向mylist中2的位置
  	mylist,insert(itr,8);//mylist:{4,5,8,2,9,6}//list插入的复杂度是O(1)，快插入
  	itr++;//插入是在itr所指向的2的前一个位置发生的，itr扔指向2，itr++后itr指向9
  	mylist.erase(itr);//删除itr所指向的元素9，mylist:{4,5,8,2,6}	
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

  list特征：快插入，慢查询O(n)
  没有像vector、deque一样的[]操作符；
  因为list的存储结构是链表，不是顺序存储，使用list时，高速缓存cache命中率低，list的查询时间复杂度虽然是O(n)但实际上更慢。
  由于list的每一个元素都包含了两个指针，所以list的内存占用相比vector更多
  list有一个独占的优势功能，splice切分mylist2中itr_a到itr_b中的元素并复制到mylist1,并指向itr

  		
  		mylist1.splice(itr,mylist2,itr_a,itr_b);//O(1)，
  		
  1
  2
  3

  4.forward list：单向链表，只有一个后继指针

  5.array比普通数组更安全，功能更强大

  //Array详解------------------------------
  	
  	int a[3] = {3,4,5};
  	array<int,3> a = {3,4,5};
  	//array的大小不可变
  	
  1
  2
  3
  4
  5
  6

• 关联容器（associative containers）
  是基于红黑树来实现的，没有push_back/front操作且不会有重复元素，容器有序
  1.set
  
  set详解（代码举例介绍）

  int main(){
  	set<int> myset;
  	//set的插入时间复杂度是O(logn)
  	myset.insert(3);//myset:{3}
  	myset.insert(1);//myset:{1,3}
  	myset.insert(7);//myset:{1,3,7}
  	set<int>::iterator it;
  	//set的查找(search)时间复杂度也是O(logn)
  	it = myset.find(7);//it->7,顺序容器没有find函数
  	pair<set<int>::iterator,bool> ret;
  	ret = myset.insert(3);//因为 myset中已经有 3，所以插入失败，没有新元素被插入
  	if(ret.second==false){//因为插入失败，所以现在ret.second==false
  		it=ret.first;//it现在指向myset中的3
  	}
  	myset.insert(it,9);//成功插入，此时myset:{1,3,7,9}，不会插入在it指向的位置，而是9在排序后应该在的位置，跟it指向哪没有关系
  	//但如果it正好指向应该插入的地方，那么会大大降低复杂度，O(logn)->O(1)
  	myset.erase(it);//此时myset:{1,7,9}
  	myset.erase(7);//此时myset:{1,9}
  	//能够直接删除值而不是迭代器，这是顺序容器所不具有的删除方式
  
  	//set:元素的值是不能被修改的
  	*it = 10;//*it类型为只读类型
  	//set的遍历相对于vector和deque会慢很多，且没有[]操作符，元素都有序
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23

  2.map
  
  map详解

  //map详解--------------------------------------------------------------------
  	//map维护一个键值对，第一个元素为key值，map没有重复的键值
  	map<char,int> mymap;
  	mymap.insert(pair<char,int>('a',100));//类模板需要声明数据类型
  	mymap.insert(make_pair('z',200));//函数模板不需要声明数据类型
  	map<char,int>::iterator it = mymap.begin();
  	mymap.insert(it,pair<char,int>('b',300));
  	it = mymap.find('z'); //O(logn)
  	for(it=mymap.begin();it!=mymap.end();it++){
  		cout<<(*it).first<<"=>"<<(*it).second<<endl;
  	}
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11

  3.multiset/multimap

  		//multiset允许有重复元素
  		//set/multiset:元素的值是不能被修改的
  		*it = 10;//*it类型为只读类型
  		//set/multiset的遍历相对于vector和deque会慢很多，且没有[]操作符，元素都有序
  		//与multiset类似，multimap允许有重复的键值，且键值都只读，不可被修改*it:pair<const char,int>
  1
  2
  3
  4
  5

• 无序容器（unordered containers ）
  C++11新增的容器，通过哈希表实现
  

  1.unordered_set
  详解

  	unordered_set<string> myset = {"res","green","blue"};
  	unordered_set<string>::const_iterator itr = myset.find("green");//查找时间复杂度O(1)
  	if(itr!=myset.end()){
  		cout<<*itr<<endl;
  	}
  	myset.insert("yellow");//插入时间复杂度O(1)
  	vector<string> vec={"purple","pink"};
  	myset.insert(vec.begin(),vec.end());
  	//哈希表独有的api
  	cout<<myset.load_factor()<<endl;//输出myset中的负载系数，也就是容器中元素的数量与桶的数量(bucket_count)之间的比率:越大越容易发生哈希碰撞
  	string x = "red";
  	cout<<x<<"is in bucket"<<myset.bucket(x)<<endl;//输出x所在的桶的值
  	cout<<"总桶数"<<myset.bucket_count()<<endl;//输出myset的总桶数
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13

  哈希冲突会导致性能下降，性能会从O(1)下降到O(n)（最坏的情况就是当所有元素都放在一个桶里），因此不如map、set稳定，因为map,set用的是平衡树。
  2.unordered_map

  //无序set和map的键值和元素值都不能被修改
  	//例如：
  	unordered_map<char,string> day={{'S',"Sunday"},{'M',"Monday"}};
  	cout<<day['S']<<endl;//没有范围检测
  	cout<<day.at('S')<<endl;//有范围检测
  	
  	//类比vector
  	vector<int> vec = {1,2,3};
  	vec[5]=5;//编译错误
  	day['W']="Wednesday";//编译成功，插入{'W',"Wednesday"}
  	day.insert(make_pair('F',"Friday"));//插入{'F',"Friday"}
  	cout<<"测试"<<endl;
  	cout<<day['M']<<endl;
  	day.insert(make_pair('M',"MONDAY"));//会报错，因为已经有唯一的'M'值的桶了,key值是只读的，不能被修改
  	day['M']="MONDAY";//通过这种方式可以修改'M'指向的值
  	cout<<day['M']<<endl;//输出值是"MONDAY"
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

  对于const类型的unorder_map，在访问值时必须要使用迭代器

  void foo(const unordered_map<char,string> &m){
  	m['S']="SUNDAY";//会报错，因为const所以不能修改
  	cout<<m['S']<<endl;//也会报错提示不能修改，这是因为如果m中没有'S'的话，在指向cout时仍然会试图在m中生成'S'再输出，这与const相矛盾
  	//编译器看见有下标[]操作符，其返回的右值提供了写操作，会认为我们要往里面写入m['s']再输出
  	auto itr = m.find('S');
  	if(itr!=m.end()){//注意判断
  		cout<<*itr<<endl;//正确方法，用迭代器访问
  	}
  }
  foo(day);
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

基于基础容器类型拓展的适配器类

1.stack,栈：后进先出，有push(),pop(),top()操作
2.queue,队列：先进先出，有push(),pop(),front(),back()操作
3.priority queue,优先队列：最高级别的元素先进先出，有push(),pop(),top()操作

容器总结：顺序存储（vector,deque），链表存储（list,associate,unordered）

试分析下列代码

vector<int> vec={1,2,3,4};
int *p=&vec[2];//*p=3
vec.insert(vec.begin(),0);//此时vec:{0,1,2,3,4}
cout<<*p<<endl;
1
2
3
4

此时会输出什么？
第一次运行结果

第二次运行：

可以看出输出的值似乎是随机的，因为STL的内存管理机制会因为vector内存不足开辟新内存并将vec中的值复制到新内存中，导致p指针指向不确定
如果运气好，*p会输出2，如果发生了内存复制，*p的值会是一个随机值（如上所示的两次运行），甚至有可能导致程序崩溃
这种行为是不可预测的，这也是顺序存储结构的缺点，而链表存储就不会有这种问题