第十九章-创新互联

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<