vector和array的數(shù)據(jù)安排和操作方式非常相似，兩者的唯一差別在于空間運(yùn)用的靈活性。 array是靜態(tài)空間，vector隨元素的加入，內(nèi)部會(huì)自動(dòng)擴(kuò)充空間，以容納新元素。

v.begin()：獲取容器的起始迭代器（指向第0個(gè)元素）

v.end()? ?：獲取容器的結(jié)束迭代器（指向最后一個(gè)元素的下一個(gè)位置）?

只能尾插尾出

線性連續(xù)空間

一旦滿載，vector會(huì)開辟 現(xiàn)有空間容量?jī)杀洞笮〉目臻g（未雨綢繆機(jī)制），將原內(nèi)容復(fù)制到新空間內(nèi)

#includeusing namespace std;
#includevoid test1()
{
	//類的類型是類，類模板的類型是<類型>vectorv1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	//遍歷該容器
	//定義一個(gè)迭代器iterator 保存起始迭代器
	vector::iterator it = v1.begin();
	for (; it != v1.end(); it++)
	{
		//*it==int
		cout<< *it<< " ";
	}
	cout<< endl;
}
void test2()
{
	vectorv1;
	//可以事先預(yù)留足夠空間，省的多次開辟
	v1.reserve(1000);//3.6
	cout<< "容量："<::iterator it;

	int i = 0;
	int count = 0;

	for (i = 0; i< 1000; i++)
	{
		v1.push_back(i);
		if (it != v1.begin())//如果開辟空間，v1.begin指向新空間，迭代器仍指向舊空間，v1.begin和迭代器不相等?？梢酝ㄟ^(guò)這個(gè)來(lái)判斷是否開辟了空間。 
		{
			count++;
			cout<< "第"<< count<< "次開辟空間容量："<< v1.capacity()<< endl;
			it = v1.begin();
		}
	}
}
void printVectorInt(vector& v)
{
	vector::iterator it = v.begin();
	for (; it != v.end(); it++)
		cout<< *it<< " ";
	cout<< endl;
}
void test3()
{
	vectorv1(5,100);//1.3
	printVectorInt(v1);

	vectorv2(v1.begin(), v1.end());//1.2
	printVectorInt(v2);

	vectorv3;//1.1
	//v3=v2;       //2.3
	//v3.assign(v2.begin(),v2.end());    //2.1
	v3.assign(10, 10);
	printVectorInt(v3);

	v3.swap(v2);//2.4
	printVectorInt(v2);
	printVectorInt(v3);

	vectorv4;
	if (v4.empty())//3.2
	{
		cout<< "空"<< endl;
	}
	else
		cout<< "非空"<< endl;
	vectorv5(10,30);
	cout<< "容量："<< v5.capacity()<< " 大?。?<< v5.size()<< endl;//3.5 3.1
	printVectorInt(v5);
	//v5.resize(15);//過(guò)大 補(bǔ)零 3.3
	v5.resize(15, 2);//過(guò)大 補(bǔ)二 3.4
	v5.resize(5);//過(guò)小 刪除多余
	printVectorInt(v5);
}
void test4()
{
	vectorv1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);//10 20 30 40 50

	cout<< "頭元素："<< v1.front()<< " 尾元素："<v1;
	v1.reserve(1000);
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	cout<< "容量："<< v1.capacity()<< " 大小："<< v1.size()<< endl;
	//resize只能修改大小，不能修改容量 
	//v1.resize(4);
	vector(v1).swap(v1);//vector(v1)為匿名對(duì)象，發(fā)生拷貝構(gòu)造，用舊對(duì)象v1給新對(duì)象賦值（只有size大小的被賦值過(guò)去了，而不是capacity大小），
	//和v1 swap后，v1指向匿名對(duì)象的size大小空間
	cout<< "容量："<< v1.capacity()<< " 大?。?<< v1.size()<< endl;
}

void test6()
{
	vectorv1(5, 10);
	vectorv2(5, 100);
	vectorv3(5, 1000);

	//定義一個(gè)vector容器存放v1 V2 V3
	vector>v;
	v.push_back(v1);
	v.push_back(v2);
	v.push_back(v3);

	//遍歷
	vector>::iterator it = v.begin();
	for (; it != v.end(); it++)
	{
		//*it==vectorvector::iterator mit = (*it).begin();
		for (; mit != (*it).end(); mit++)
		{
			cout<< *mit<< " ";
		}
		cout<< endl;
	}
}

#include;
void test7()
{
	vectorv1;
	v1.push_back(20);
	v1.push_back(60);
	v1.push_back(50);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(10);
	printVectorInt(v1);

	//排序算法
	sort(v1.begin(), v1.end());
	printVectorInt(v1);
}

#includeclass Person
{
	friend bool comparePerson(Person ob1, Person ob2);
	friend void printVectorPerson(vector&v);
private:
	int num;
	string name;
	float score;
public:
	Person() {}
	Person(int num, string name, float score)
	{
		this->num = num;
		this->name = name;
		this->score = score;
	}
};

void printVectorPerson(vector&v)
{
	vector::iterator it = v.begin();
	for (; it != v.end(); it++)
	{
		//*it==Person
		cout<< (* it).num<< " "<<(*it).name<<" "<<(*it).score<v1;
	v1.push_back(Person(100,"lucy",77.7f));
	v1.push_back(Person(103, "bob", 77.7f));
	v1.push_back(Person(101, "tom", 77.7f));
	v1.push_back(Person(104, "德瑪", 77.7f));
	v1.push_back(Person(105, "小法", 77.7f));

	printVectorPerson(v1);

	//對(duì)自定義類型的vector類型排序，需要修改排序規(guī)則
	sort(v1.begin(),v1.end(),comparePerson);
	printVectorPerson(v1);

}
int main(int argc,char *argv[])
{
	test8();
	return 0;
}

double ended queue，雙端隊(duì)列

vector與deque容器的大差異:

（1）deque允許在 頭尾兩端 分別做元素的插入和刪除操作,且 所用時(shí)間 僅 常數(shù)項(xiàng)時(shí)間。

【vector也可以頭部插入，但效率太低】

（2）沒(méi)有容量的概念。它是動(dòng)態(tài)的，以 分段定量連續(xù)空間 組合而成，隨時(shí)可以增加一段新的空間并連接起來(lái)，不存在容量限制。

【也就是說(shuō)，

像vector那樣 “空間不足而重新配置一塊更大空間，然后復(fù)制元素，再釋放舊空間” 的事情在deque這不存在。

因此deque不需要空間保留（reserve）功能，雖然deque容器也提供了Random Access Iterator，但它的迭代器并不是普通的指針，其復(fù)雜度和vector不是一個(gè)量級(jí)。

因此，除非有必要，盡量使用vector而不是deque。

對(duì)deque進(jìn)行排序操作，為了提高效率?？梢詫eque完整復(fù)制到一個(gè)vector中，對(duì)vector容器進(jìn)行排序，再?gòu)?fù)制回deque。】

array無(wú)法擴(kuò)張

vector尾端假擴(kuò)張：申請(qǐng)更大空間-->原數(shù)據(jù)復(fù)制新空間-->釋放原空間

deque雙端真擴(kuò)張

deque采取一塊map作為主控（注意不是STL的map容器，是一小段連續(xù)的內(nèi)存空間），其中每一個(gè)元素（結(jié)點(diǎn)）都是一個(gè)指針，指向另一段連續(xù)性內(nèi)存空間，稱作緩沖區(qū)。緩沖區(qū)才是deque的存儲(chǔ)空間主體。

Deque由一段段定量連續(xù)空間構(gòu)成。當(dāng)在deque前端或尾端增加新空間時(shí)，便串接一段連續(xù)定量的空間。

deque避開了重新配置空間、復(fù)制、釋放的輪回，代價(jià)就是復(fù)雜的迭代器架構(gòu)和數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。

#includeusing namespace std;
#includevoid printDequeInt(deque& d)
{
	deque::iterator it = d.begin();
	for (; it != d.end(); it++)
	{
		cout<< *it<< " ";
	}
	cout<< endl;
}

void test1()
{	
	dequed1;
	d1.push_back(1);//4.1
	d1.push_back(2);
	d1.push_back(3);
	d1.push_front(4);//4.2
	d1.push_front(5);
	d1.push_front(6);
	printDequeInt(d1);
	cout<< "大?。?<< d1.size()<< endl;
	d1.pop_front();//4.4
	printDequeInt(d1);
	d1.pop_back();//4.3
	printDequeInt(d1);

	d1.insert(d1.begin() + 1, 3, 100);//6.2
	printDequeInt(d1);
}

//8
#include#include
class Person
{
public:
	string name;
	float score;
public:
	Person() {}
	Person(string name, float score)
	{
		this->name = name;
		this->score = score;
	}
};

void createPerson(vector& v)
{
	string tmpName = "ABCDE";
	int i = 0;
	for (i = 0; i< 5; i++)
	{
		string name = "選手";
		name += tmpName[i];
		v.push_back(Person(name, 0.0f));
	}
}

void showPerson(vector&v)
{
	vector::iterator it = v.begin();
	for (; it != v.end(); it++)
	{
		//*it==Person
		cout<< (*it).name<< " "<< (*it).score<< endl;
		//以下寫法也可以，但是是把迭代器看成了指針,容易出錯(cuò),其他迭代器上可能就不能用了。 
		//cout<< it->name<< " "<< it->score<< endl;
	}
}

void playGame(vector&v)
{
	//每人逐個(gè)比賽
	vector::iterator it = v.begin();
	for (; it != v.end(); it++)
	{
		//定義一個(gè)deque容器存放10個(gè)評(píng)委的分?jǐn)?shù)
		dequed;
		int i = 0;
		for (i = 0; i< 10; i++)
		{
			d.push_back((float)(rand() % 41 + 60));//rand() % 41:生成0-41間的一個(gè)隨機(jī)數(shù)。 
		}
		//對(duì)deque排序
		sort(d.begin(), d.end());

		//去掉最低最高分
		d.pop_back();
		d.pop_front();
		//求平均分
		(*it).score = (float)accumulate(d.begin(), d.end(),0)/d.size();
	}
}
#includevoid test2()
{
	vectorv;
	//srand設(shè)置隨機(jī)數(shù)種子
	srand(time(NULL));
	//創(chuàng)建五名選手
	createPerson(v);

	//比賽
	playGame(v);
	//顯示選手成績(jī)
	showPerson(v);
}

int main(int argc, char* argv[])
{
	test2();
	return 0;
}

stack是一種 先進(jìn)后出 的數(shù)據(jù)結(jié)構(gòu)，stack容器只能 新增、刪除、取得 棧頂元素。

stack不允許 遍歷，沒(méi)有迭代器?！局挥幸粋€(gè)出口，除了最頂端外，沒(méi)有其他方法可以存取stack的其他元素】

queue是一種 先進(jìn)先出 的數(shù)據(jù)結(jié)構(gòu)，允許元素從隊(duì)尾新增入隊(duì)，從隊(duì)頭移除出隊(duì)。

list容器是一個(gè)雙向鏈表。

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

插入和刪除元素是常數(shù)時(shí)間，無(wú)需像靜態(tài)鏈表（數(shù)組）那樣移動(dòng)大量元素。

采用動(dòng)態(tài)存儲(chǔ)分配。靈活，但消耗了空間和時(shí)間。

list容器的迭代器是雙向迭代器，

• 不支持 +2 這種（隨機(jī)訪問(wèn)迭代器支持，像vector的），支持++（因?yàn)?+運(yùn)算符可以重載）；
• 不支持 STL提供的算法（STL提供的算法（像sort）只支持隨機(jī)訪問(wèn)迭代器）

【可以寫(對(duì)象)h1.sort();】

特征：set的所有元素會(huì)根據(jù) 鍵值 自動(dòng)排序。

• set的元素既是鍵值又是實(shí)值，或者可以認(rèn)為它只有鍵值。
• set不允許兩個(gè)元素有相同的鍵值。multiset 特性及用法 與 set 完全相同，唯一差別在于它允許鍵值重復(fù)（即可以插入相同元素）。
• set迭代器 是 只讀迭代器，不允許修改鍵值，會(huì)破壞set的內(nèi)存布局?！疽?yàn)閟et插入元素時(shí)才排序，如果修改元素內(nèi)容，就無(wú)序了，容器布局就變了】

因?yàn)閟et插入元素就自動(dòng)排序好了，所以沒(méi)有push_back/push_front這種。

修改排序規(guī)則：

• 應(yīng)該在定義類對(duì)象時(shí)修改，set

【先定義類對(duì)象，再插入元素。因?yàn)椴迦霑r(shí)就自動(dòng)排序了，所以應(yīng)該在插入之前修改排序規(guī)則，也就是在定義類對(duì)象時(shí)修改】

• 因?yàn)樵诩饫ㄌ?hào)內(nèi)，排序規(guī)則須是一個(gè)類，同時(shí)也是一個(gè)函數(shù)，所以我們用 仿函數(shù) 來(lái)寫規(guī)則。

【仿函數(shù)：重載函數(shù)調(diào)用運(yùn)算符（）的類】

• set存放自定義數(shù)據(jù)必須修改排序。

【同vector實(shí)操最后面出現(xiàn)的。自定義類型不指定排序規(guī)則的話，sort不知道你是依據(jù)哪個(gè)成員變量來(lái)排序】

將一對(duì)值組合成一個(gè)值，這一對(duì)值可以具有不同的數(shù)據(jù)類型，兩個(gè)值可以分別用pair的兩個(gè)公用屬性 first 和 second 。

模板：templatestruct pair

void test()
{
//方式一：
pairp1(10086,"移動(dòng)");
pairp2(10010,"聯(lián)通");
pairp3(10000,"電信");

//方式二：（推薦）
pairp4=make_pair(9527,"星爺");

cout<