順序容器（sequence containers）

1.vector
結構如下圖所示

只可通過push_back()從尾部添加元素

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

獲取元素時

cout<

遍歷vector的三種操作

//vector可以像遍歷數(shù)組一樣被遍歷
	for(int i=0;i::iterator itr=vec.begin();itr!=vec.end();++itr)cout<<*itr<

所有容器都具備的5個功能函數(shù)

if(vec.empty()){cout<<"impossible"<vec2(vec);//3)復制整個容器
	
	vec.clear();//4)清除容器中所有元素，此時vec.size()==0
	
	vec2.swap(vec);//5)交換兩個數(shù)組中的元素
	//此時vec2.size()==0,vec.size()==3

2.deque(double-ended queue)
結構如英文，是一個雙端隊列

deque可從兩端添加元素，效率極高，復雜度為O(1),但從中間添插入元素的復雜度為O(n),查詢的時間復雜度也為O(n)

//deque詳解-------------------------------
	
	//deque與vector的區(qū)別就是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的前一個位置發(fā)生的，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有一個獨占的優(yōu)勢功能，splice切分mylist2中itr_a到itr_b中的元素并復制到mylist1,并指向itr

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

4.forward list：單向鏈表，只有一個后繼指針

5.array比普通數(shù)組更安全，功能更強大

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

關聯(lián)容器（associative containers）
是基于紅黑樹來實現(xiàn)的，沒有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函數(shù)
	pair::iterator,bool>ret;
	ret = myset.insert(3);//因為 myset中已經有 3，所以插入失敗，沒有新元素被插入
	if(ret.second==false){//因為插入失敗，所以現(xiàn)在ret.second==false
		it=ret.first;//it現(xiàn)在指向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));//類模板需要聲明數(shù)據(jù)類型
	mymap.insert(make_pair('z',200));//函數(shù)模板不需要聲明數(shù)據(jù)類型
	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新增的容器，通過哈希表實現(xiàn)


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穩(wěn)定，因為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<