vector和array的數據安排和操作方式非常相似，兩者的唯一差別在于空間運用的靈活性。 array是靜態空間，vector隨元素的加入，內部會自動擴充空間，以容納新元素。

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

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

只能尾插尾出

線性連續空間

一旦滿載，vector會開辟 現有空間容量兩倍大小的空間（未雨綢繆機制），將原內容復制到新空間內

#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);

	//遍歷該容器
	//定義一個迭代器iterator 保存起始迭代器
	vector::iterator it = v1.begin();
	for (; it != v1.end(); it++)
	{
		//*it==int
		cout<< *it<< " ";
	}
	cout<< endl;
}
void test2()
{
	vectorv1;
	//可以事先預留足夠空間，省的多次開辟
	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和迭代器不相等。可以通過這個來判斷是否開辟了空間。 
		{
			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);//過大 補零 3.3
	v5.resize(15, 2);//過大 補二 3.4
	v5.resize(5);//過小 刪除多余
	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)為匿名對象，發生拷貝構造，用舊對象v1給新對象賦值（只有size大小的被賦值過去了，而不是capacity大小），
	//和v1 swap后，v1指向匿名對象的size大小空間
	cout<< "容量："<< v1.capacity()<< " 大小："<< v1.size()<< endl;
}

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

	//定義一個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);

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

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

double ended queue，雙端隊列

vector與deque容器的大差異:

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

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

（2）沒有容量的概念。它是動態的，以 分段定量連續空間 組合而成，隨時可以增加一段新的空間并連接起來，不存在容量限制。

【也就是說，

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

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

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

對deque進行排序操作，為了提高效率。可以將deque完整復制到一個vector中，對vector容器進行排序，再復制回deque。】

array無法擴張

vector尾端假擴張：申請更大空間-->原數據復制新空間-->釋放原空間

deque雙端真擴張

deque采取一塊map作為主控（注意不是STL的map容器，是一小段連續的內存空間），其中每一個元素（結點）都是一個指針，指向另一段連續性內存空間，稱作緩沖區。緩沖區才是deque的存儲空間主體。

Deque由一段段定量連續空間構成。當在deque前端或尾端增加新空間時，便串接一段連續定量的空間。

deque避開了重新配置空間、復制、釋放的輪回，代價就是復雜的迭代器架構和數據結構設計。

#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;
		//以下寫法也可以，但是是把迭代器看成了指針,容易出錯,其他迭代器上可能就不能用了。 
		//cout<< it->name<< " "<< it->score<< endl;
	}
}

void playGame(vector&v)
{
	//每人逐個比賽
	vector::iterator it = v.begin();
	for (; it != v.end(); it++)
	{
		//定義一個deque容器存放10個評委的分數
		dequed;
		int i = 0;
		for (i = 0; i< 10; i++)
		{
			d.push_back((float)(rand() % 41 + 60));//rand() % 41:生成0-41間的一個隨機數。 
		}
		//對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設置隨機數種子
	srand(time(NULL));
	//創建五名選手
	createPerson(v);

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

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

stack是一種 先進后出 的數據結構，stack容器只能 新增、刪除、取得 棧頂元素。

stack不允許 遍歷，沒有迭代器。【只有一個出口，除了最頂端外，沒有其他方法可以存取stack的其他元素】

queue是一種 先進先出 的數據結構，允許元素從隊尾新增入隊，從隊頭移除出隊。

list容器是一個雙向鏈表。

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。

插入和刪除元素是常數時間，無需像靜態鏈表（數組）那樣移動大量元素。

采用動態存儲分配。靈活，但消耗了空間和時間。

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

• 不支持 +2 這種（隨機訪問迭代器支持，像vector的），支持++（因為++運算符可以重載）；
• 不支持 STL提供的算法（STL提供的算法（像sort）只支持隨機訪問迭代器）

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

特征：set的所有元素會根據 鍵值 自動排序。

• set的元素既是鍵值又是實值，或者可以認為它只有鍵值。
• set不允許兩個元素有相同的鍵值。multiset 特性及用法 與 set 完全相同，唯一差別在于它允許鍵值重復（即可以插入相同元素）。
• set迭代器 是 只讀迭代器，不允許修改鍵值，會破壞set的內存布局。【因為set插入元素時才排序，如果修改元素內容，就無序了，容器布局就變了】

因為set插入元素就自動排序好了，所以沒有push_back/push_front這種。

修改排序規則：

• 應該在定義類對象時修改，set

【先定義類對象，再插入元素。因為插入時就自動排序了，所以應該在插入之前修改排序規則，也就是在定義類對象時修改】

• 因為在尖括號內，排序規則須是一個類，同時也是一個函數，所以我們用 仿函數 來寫規則。

【仿函數：重載函數調用運算符（）的類】

• set存放自定義數據必須修改排序。

【同vector實操最后面出現的。自定義類型不指定排序規則的話，sort不知道你是依據哪個成員變量來排序】

將一對值組合成一個值，這一對值可以具有不同的數據類型，兩個值可以分別用pair的兩個公用屬性 first 和 second 。

模板：templatestruct pair

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

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

cout<