顺序容器（sequence containers）

1.vector
结构如下图所示

只可通过push_back()从尾部添加元素

vectorvec;
	vec.push_back(2);
	vec.push_back(1);
	vec.push_back(8);

获取元素时

cout<

遍历vector的三种操作

//vector可以像遍历数组一样被遍历
	for(int i=0;i::iterator itr=vec.begin();itr!=vec.end();++itr)cout<<*itr<

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

if(vec.empty()){cout<<"impossible"<vec2(vec);//3)复制整个容器
	
	vec.clear();//4)清除容器中所有元素，此时vec.size()==0
	
	vec2.swap(vec);//5)交换两个数组中的元素
	//此时vec2.size()==0,vec.size()==3

2.deque(double-ended queue)
结构如英文，是一个双端队列

deque可从两端添加元素，效率极高，复杂度为O(1),但从中间添插入元素的复杂度为O(n),查询的时间复杂度也为O(n)

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

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

3.list
结构如图

如图，list是一个双向链表

//List详解--------------------------------
	//--double linked list
	listmylist = {5,2,9};
	mylist.push_back(6);//mylist:{5,2,9,6}
	mylist.push_front(4);//mylist:{4,5,2,9,6}
	list::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}	

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)，
		

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

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

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

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

set详解（代码举例介绍）

int main(){setmyset;
	//set的插入时间复杂度是O(logn)
	myset.insert(3);//myset:{3}
	myset.insert(1);//myset:{1,3}
	myset.insert(7);//myset:{1,3,7}
	set::iterator it;
	//set的查找(search)时间复杂度也是O(logn)
	it = myset.find(7);//it->7,顺序容器没有find函数
	pair::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会慢很多，且没有[]操作符，元素都有序

2.map

map详解

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

3.multiset/multimap

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

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


1.unordered_set
详解

unordered_setmyset = {"res","green","blue"};
	unordered_set::const_iterator itr = myset.find("green");//查找时间复杂度O(1)
	if(itr!=myset.end()){cout<<*itr<vec={"purple","pink"};
	myset.insert(vec.begin(),vec.end());
	//哈希表独有的api
	cout<

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

//无序set和map的键值和元素值都不能被修改
	//例如：
	unordered_mapday={{'S',"Sunday"},{'M',"Monday"}};
	cout<vec = {1,2,3};
	vec[5]=5;//编译错误
	day['W']="Wednesday";//编译成功，插入{'W',"Wednesday"}
	day.insert(make_pair('F',"Friday"));//插入{'F',"Friday"}
	cout<<"测试"<

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

void foo(const unordered_map&m){m['S']="SUNDAY";//会报错，因为const所以不能修改
	cout<//注意判断
		cout<<*itr<