3. STL——常用容器（一）

3.1.1 string基本概念

本质：string是C++风格的字符串，而string本质上是一个类

string和char*区别：

1. char*是一个指针
2. string是一个类，类内部封装了char*，管理这个字符串，是一个char*型的容器

特点：

1. string类内部封装了很多成员方法
2. 例如：查找find，拷贝copy，删除delete，替换replace，插入insert
3. string管理char*所分配的内存，不用担心复制越界和取值越界等，由类内部进行负责

3.1.2 string构造函数

构造函数原型：

1. string（）； // 创建一个空的字符串 例如string str；
2. string（const char* s）; // 使用字符串s初始化
3. string（const string& str）； // 使用一个string对象初始化另一个string对象
4. string（int n， char C)； // 使用n个字符c初始化

示例：

#include
using namespace std;
#include

// string的构造函数
//1. string（）；								// 创建一个空的字符串 例如string str；
//2. string（const char* s）;					// 使用字符串s初始化
//3. string（const string & str）；				// 使用一个string对象初始化另一个string对象
//4. string（int n， char C)；					// 使用n个字符c初始化
void test01()
{
	string s1;			//  第一种

	const char* str = "hello world";			// 第二种
	string s2(str);

	cout << "s2 = " << s2 << endl;

	string s3(s2);				// 第三种
	cout << "s3 = " << s3 << endl;

	string s4(10, 'a');
	cout << "s4 = " << s4 << endl;
}



int main()
{
	test01();

	system("pause");
	return 0;
}

总结：string的多种构造方式没有可比性，灵活使用即可

3.1.3 string赋值操作

功能描述：给string字符串进行赋值

示例：

#include
using namespace std;
#include


//	1. string& operator = (const char* s);			// char*类型字符串，赋值给当前的字符串
//	2. string& operator = (const string& s);		// 把字符串s赋给当前的字符串
//	3. string& operator = (char c);					// 字符赋值给当前的字符串
//	4. string& assign(const char* s);				// 把字符串s赋给当前的字符串
//	5. string& assign(const char* s, int n);		// 把字符串s的前n个字符赋给当前的字符串
//	6. string& assign(const string& s);				// 把字符串s赋给当前字符串
//	7. string& assign(int n, char c);				// 用n个字符c赋给当前字符串



// string的赋值操作
void test01()
{
	//  1. string& operator = (const char* s);			// char*类型字符串，赋值给当前的字符串
	string str1;
	str1 = "hello world";
	cout << "str1 = " << str1 << endl;

	//	2. string& operator = (const string& s);		// 把字符串s赋给当前的字符串
	string str2;
	str2 = str1;
	cout << "str2 = " << str2 << endl;

	//	3. string& operator = (char c);					// 字符赋值给当前的字符串
	string str3;
	str3 = 'a';
	cout << "str3 = " << str3 << endl;

	//	4. string& assign(const char* s);				// 把字符串s赋给当前的字符串
	string str4;
	str4.assign("hello C++");
	cout << "str4 = " << str4 << endl;

	//	5. string& assign(const char* s, int n);		// 把字符串s的前n个字符赋给当前的字符串
	string str5;
	str5.assign("hello C++", 5);
	cout << "str5 = " << str5 << endl;

	//	6. string& assign(const string& s);				// 把字符串s赋给当前字符串
	string str6;
	str6.assign(str5);
	cout << "str6 = " << str6 << endl;

	//	7. string& assign(int n, char c);				// 用n个字符c赋给当前字符串
	string str7;
	str7.assign(10, 'l');
	cout << "str7 = " << str7 << endl;



}



int main()
{
	test01();

	system("pause");
	return 0;
}

总结：string的赋值方式很多，operator=这种方式是比较实用

3.1.4 string字符串拼接

功能描述：实现在字符出末尾拼接字符串

示例：

#include
using namespace std;
#include


// 字符串拼接
//	1. string& operator+=(const char* str);						// 重载+=操作符
//	2. string& operator+=(const char c);						// 重载+=操作符
//	3. string& operator+=(const string& str);					// 重载+=操作符
//	4. string& append(const char* s);							// 把字符串s连接到当前字符串结尾
//	5. string& append(const char* s, int n);					// 把字符串s的前n个字符连接到当前字符串结尾
//	6. string& append(const string &s);							// 同operator+=(const string& str)
//	7. string& append(const string &s,int pos, int n);			// 字符串s中从pos开始的n个字符连接到字符串结尾


//  string字符串拼接
void test01()
{
	//	1. string& operator+=(const char* str);						// 重载+=操作符
	string str1 = "我";
	str1 += "爱玩游戏";
	cout << "str1 = " << str1 << endl;

	//	2. string& operator+=(const char c);						// 重载+=操作符
	str1 += ":";
	cout << "str1 = " << str1 << endl;

	//	3. string& operator+=(const string& str);					// 重载+=操作符
	string str2 = "LOL DNF";
	str1 += str2;
	cout << "str1 = " << str1 << endl;

	//	4. string& append(const char* s);							// 把字符串s连接到当前字符串结尾
	string str3 = "I";
	str3.append("love");
	cout << "str3 = " << str3 << endl;

	//	5. string& append(const char* s, int n);					// 把字符串s的前n个字符连接到当前字符串结尾
	str3.append("game abcde", 4);
	cout << "str3 = " << str3 << endl;

	//	6. string& append(const string &s);							// 同operator+=(const string& str)
	str3.append(str2);
	cout << "str3 = " << str3 << endl;

	//	7. string& append(const string &s,int pos, int n);			// 字符串s中从pos开始的n个字符连接到字符串结尾
	str3.append(str2, 0, 3);
	cout << "str3 = " << str3 << endl;



}



int main()
{
	test01();

	system("pause");
	return 0;
}

3.1.5 string查找与替换

功能描述：

1. 查找：查找指定字符串是否存在
2. 替换：在指定的位置替换字符串

示例：

#include
using namespace std;
#include

// 字符串查找与替换
//	1. int find(const string& str, int pos = 0)const;			// 查找str第一次出现位置，从pos开始查找
//	2. int find(const char* s, int pos = 0)const;				// 查找s第一次出现位置，从pos开始查找
//	3. int find(const char* s, int pos, int n)const;			// 从pos位置查找s的前n个字符第一次位置
//	4. int find(const char* c, int pos = 0)const;				// 查找字符c第一次出现位置
//	5. int rfind(const string& str, int pos = npos)const;		// 查找str最后一次位置，从pos开始查找
//	6. int rfind(const char* s, int pos = npos)const;			// 查找s最后一次出现位置，从pos开始查找
//	7. int rfind(const char* s, int pos, int n )const;			// 从pos查找s的前n个字符最后一次位置
//	8. int rfind(const char c, int pos = 0)const;				// 查找字符c最后一次出现位置
//	9. string& replace(int pos, int n, const string& str);		// 替换从pos开始n个字符为字符串str
//	10. string& replace(int pos, int n, const char* s);			// 替换从pos开始n个字符为字符串s




// 1. 查找
void test01()
{
	//	1. int find(const string& str, int pos = 0)const;			// 查找str第一次出现位置，从pos开始查找
	string str1 = "abcdefg";
	int pos1 = str1.find("de");
	cout << "pos = " << pos1 << endl;
	int pos2 = str1.find("df");
	cout << "pos = " << pos2 << endl;

	//	5. int rfind(const string& str, int pos = npos)const;		// 查找str最后一次位置，从pos开始查找
	// rfind和find区别
	// rfind从右往左查找 find从左往右查找
	pos1 = str1.rfind("de");
	cout << "pos1 = " << pos1 << endl;
}
// 2. 替换
void test02()
{

	//	9. string& replace(int pos, int n, const string& str);		// 替换从pos开始n个字符为字符串str
	string str1 = "abcdefg";
	// 从1号位置起3个字符，替换为"1111"
	str1.replace(1, 3, "1111");
	cout << "str1 = " << str1 << endl;



}



int main()
{
	test02();

	system("pause");
	return 0;
}

总结：

1. find查找是从左往右，rfind是从右往左
2. find找到字符串后返回查找的第一个字符位置，找不到返回-1
3. replace在替换时，要指定从那个位置起，多少个字符，替换成什么样的字符

3.1.6 string字符串比较

功能描述： 字符串之间的比较

比较方式：字符产比较是按字符的ASCII码进行对比

1. = 返回 0
   

2. > 返回 1
   

3. < 返回 -1
   

函数原型

1. int compare(const string &s) const； // 与字符串s比较
2. int compare(const char *s) const； // 与字符串s比较

示例：

#include
using namespace std;
#include

// 字符串比较
void test01()
{
	string str1 = "aello";
	string str2 = "hello";

	if (str1.compare(str2) == 0)
	{
		cout << "str1 等于 str2" << endl;
	}
	else if (str1.compare(str2) > 0)
	{
		cout << "str1 大于 str2" << endl;
	}
	else
	{
		cout << "str1 小于 str2" << endl;
	}
}


int main()
{
	test01();

	system("pause");
	return 0;
}

总结：字符串对比主要是用于比较两个字符串是否相等，判断谁大谁小的意义并不是很大

3.1.7 string字符存取

string中单个字符存取方式有两种

1. char& operator[](int n); // 通过[]方式取字符
2. char& at(int n ); // 通过at方法获取字符

示例：

#include
using namespace std;
#include


// string 字符存取
void test01()
{
	string str = "hello";
	cout << "str = " << str << endl;

	// 1. 通过[]访问单个字符
	for (int i = 0; i < str.size(); i++)
	{
		cout << str[i] << "  ";
	}
	cout << endl;


	// 2. 通过at方式访问单个字符
	for (int i = 0; i < str.size();i++)
	{
		cout << str.at(i) << "  ";
	}
	cout << endl;

	// 修改单个字符
	str[0] = 'x';
	// xello
	cout << "str = " << str << endl;

	str.at(1) = 'x';
	// xxllo
	cout << "str = " << str << endl;

}


int main()
{
	test01();

	system("pause");
	return 0;
}

总结：string字符串中单个字符存取有两种方式，利用[]或at

3.1.8 string插入和删除

功能描述：对string字符串进行插入和删除字符操作

示例：

#include
using namespace std;
#include


// string& insert(int pos, const char* s);					// 插入字符串
// string& insert(int pos, cosnt string& str);				// 插入字符串
// string& insert(int pos, int n, char c);					// 在指定位置插入n个字符c
// string& erase(int pos, int n = npos);					// 删除从pos开始的n个字符

// 字符串 插入和删除
void test01()
{
	string str = "hello";

	// 插入
	str.insert(1, "111");
	cout << "str = " << str << endl;

	// 删除
	str.erase(1, 3);
	cout << "str = " << str << endl;
}


int main()
{
	test01();

	system("pause");
	return 0;
}

总结：插入和删除的起始下标都是从0开始的

3.1.9 string子串

功能描述：从字符串中获取想要的子串

示例：

#include
using namespace std;
#include


// string substr(int pos = 0; int n = npos)const;			// 返回由pos开始的n个字符组成的字符串

// string求子串
void test01()
{
	string str = "abcdef";
	string subStr = str.substr(1, 3);
	cout << "subStr = " << subStr << endl;
}

// 实用操作
void test02()
{
	string email = "lisi@sina.com";

	// 从邮件地址中 获取 用户名信息
	int pos = email.find("@");
	string userName = email.substr(0, pos);
	cout << userName << endl;

}
int main()
{
	test02();

	system("pause");
	return 0;
}

总结：灵活的运用求子串功能，可以实际开发中获取有效的信息

3.2 vector容器 3.2.1 vector基本概念

功能：vector数据结构和数组非常相似，也成为单端数组

vector与普通数组区别：不同之处在于数组是静态空间，而vector可以动态扩展

动态扩展：

1. 并不是在原空间之后续接新空间，而是找到更大的内存空间，然后将原数据拷贝到新空间，释放原空间
2. vector容器的迭代器是支持随机访问的迭代器

3.2.2 vector构造函数

功能描述：创建vector容器

示例：

#include
using namespace std;
#include
#include

// vector容器构造

// 1. vector v;							// 采用模板实现类实现，默认构造函数
// 2. vector(v.begin(), v.end());			// 将v[begin(), end()]区间中的元素拷贝给本身
// 3. vector(n, elem);						// 构造函数将n个elem拷贝给本身
// 4. vector(const vector &vec);			// 拷贝构造函数


void printVector(vector&v)
{
	for (vector::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << "  ";
	}
	cout << endl;
}

void test01()
{
	// 1. vector v;							// 采用模板实现类实现，默认构造函数
	vectorv1;			// 默认构造 无参构造
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);

	// 2. vector(v.begin(), v.end());			// 将v[begin(), end()]区间中的元素拷贝给本身
	// 通过区间方式进行构造
	vectorv2(v1.begin(), v1.end());
	printVector(v2);

	// 3. vector(n, elem);						// 构造函数将n个elem拷贝给本身
	// n个elem方式构造
	vectorv3(10,100);
	printVector(v3);

	// 4. vector(const vector &vec);			// 拷贝构造函数
	// 拷贝构造
	vectorv4(v3);
	printVector(v4);
	

}


int main()
{
	test01();

	system("pause");
	return 0;
}

总结：vector的多种构造方式没有可比性，灵活使用即可

3.2.3 vector赋值操作

功能描述：给vector容器进行赋值

示例：

#include
using namespace std;
#include
#include

// vector赋值操作
// 1. vector& operator = (const vector &vec);			// 重载等号操作符
// 2. assign(beg, end);									// 将[beg, end)区间中的数据拷贝赋值给本身
// 3. assign(n, elem);									// 将n个elem拷贝赋值给本身

void printVector(vector& v)
{
	for (vector::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << "  ";

	}
	cout << endl;
}
void test01()
{
	vectorv1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);

	// 1. vector& operator = (const vector &vec);			// 重载等号操作符
	// 赋值		operator=
	vectorv2;
	v2 = v1; 
	printVector(v2);

	// 2. assign(beg, end);									// 将[beg, end)区间中的数据拷贝赋值给本身
	vectorv3;
	v3.assign(v1.begin(), v1.end());
	printVector(v3);

	// 3. assign(n, elem);									// 将n个elem拷贝赋值给本身
	// n个elem 方式赋值
	vectorv4;
	v4.assign(10, 100);
	printVector(v4);
}


int main()
{
	test01();

	system("pause");
	return 0;
}

总结：vector赋值方式比较简单，使用operator=，或者assign都可以

3.2.4 vector容量和大小

功能描述：对vector容器的容量和大小操作

示例：

#include
using namespace std;
#include
#include

// vector容量和大小
// 1. empty();					// 判断容器是否为空
// 2. capacity();				// 容器的容量
// 3. size();					// 返回容器中元素的个数
// 4. resize(int num);			// 重新指定容器的长度为num，若容器变长，则以默认值填充新位置
								// 如果容器变短，则末尾超出容器长度的元素被删除
// 5. resize(int num, elem);	// 重新指定容器的长度为num，若容器变长，则以elem值填充新位置
								// 如果容器变短，则末尾超出容器长度的元素被删除

void printVector(vector& v)
{
	for (vector::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << "  ";
	}
	cout << endl;
}

void test01()
{
	vectorv1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	printVector(v1);

	// 1. empty();					// 判断容器是否为空
	if (v1.empty())			// 为真 代表容器为空
	{
		cout << "v1为空" << endl;
	}
	else
	{
		cout << "v1不为空" << endl;
		// 2. capacity();				// 容器的容量
		cout << "v1的容量为：" << v1.capacity() << endl;
		// 3. size();					// 返回容器中元素的个数
		cout << "v1的元素个数：" << v1.size() << endl;
	}


	// 4. resize(int num);			// 重新指定容器的长度为num，若容器变长，则以默认值填充新位置
									// 如果容器变短，则末尾超出容器长度的元素被删除
	// 5. resize(int num, elem);	// 重新指定容器的长度为num，若容器变长，则以elem值填充新位置
									// 如果容器变短，则末尾超出容器长度的元素被删除
	// 重新指定大小
	v1.resize(15);
	printVector(v1);				// 如果重新指定的比原来长了，默认用0填充新的位置  
	v1.resize(20,100);
	printVector(v1);	

	v1.resize(5);
	printVector(v1);				// 如果重新指定的比原来的短了，超出部分会删除掉
}

int main()
{
	test01();

	system("pause");
	return 0;
}

总结：

1. 判断是否为空：empty
2. 返回元素个数：size
3. 返回容器容量：capacity
4. 重新指定大小：resize

3.2.5 vector插入和删除

功能描述：对vector容器进行插入，删除操作

示例：

#include
using namespace std;
#include
#include

// vector插入和删除
// 1. push_back(ele);										// 尾部插入元素ele
// 2. pop_back();											// 删除最后一个元素
// 3. insert(const_iterator pos, ele);						// 迭代器指向位置pos插入元素ele
// 4. insert(const_iterator pos, int count, ele);			// 迭代器指向位置pos插入count个元素ele
// 5. erase(const_iterator pos);							// 删除迭代器指向的元素
// 6. erase(const_iterator start, const_iterator end);		// 删除迭代器从start到end之间的元素
// 7. clear();												// 删除容器中所有元素

void printVector(vector&v)
{
	for (vector::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << "  ";
	}
	cout << endl;
}

void test01()
{
	vectorv1;
	// 1. push_back(ele);										// 尾部插入元素ele
	// 尾插
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	// 遍历
	printVector(v1);

	// 2. pop_back();											// 删除最后一个元素
	v1.pop_back();
	printVector(v1);

	// 3. insert(const_iterator pos, ele);						// 迭代器指向位置pos插入元素ele
	// 第一个参数是迭代器
	v1.insert(v1.begin(), 100);
	printVector(v1);
	// 4. insert(const_iterator pos, int count, ele);			// 迭代器指向位置pos插入count个元素ele
	v1.insert(v1.begin(), 2, 1000);
	printVector(v1);
	// 5. erase(const_iterator pos);							// 删除迭代器指向的元素
	v1.erase(v1.begin());
	printVector(v1);
	// 6. erase(const_iterator start, const_iterator end);		// 删除迭代器从start到end之间的元素
	v1.erase(v1.begin(), v1.end());
	printVector(v1);
	// 7. clear();												// 删除容器中所有元素
	v1.insert(v1.begin(), 2, 1000);
	printVector(v1);
	v1.clear();
	printVector(v1);

}


int main()
{
	test01();

	system("pause");
	return 0;
}

总结：

1. 尾插：push_back
2. 尾删：pop_back
3. 插入：insert（位置迭代器）
4. 删除：erase（位置迭代器）
5. 清空：clear

3.2.6 vector数据存取

功能描述：对vector中的数据的存取操作

示例：

#include
using namespace std;
#include
#include

// vector数据存取
// 1. at(int idx);			// 返回索引idx所指的数据
// 2. operator[];			// 返回索引idx所指的数据
// 3. front();				// 返回容器中第一个数据元素
// 4. back();				// 返回容器中最后一个数据元素

void test01()
{
	vectorv1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	
	// 2. operator[];			// 返回索引idx所指的数据
	// 利用[]方式访问数组中元素
	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1[i] << "  ";
	}
	cout << endl;

	// 1. at(int idx);			// 返回索引idx所指的数据
	// 利用at方式访问元素
	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1.at(i) << "  ";
	}
	cout << endl;

	// 3. front();				// 返回容器中第一个数据元素
	// 获取第一个元素
	cout << "第一个元素为：" << v1.front() << endl;

	// 4. back();				// 返回容器中最后一个数据元素
	// 获取最后一个元素
	cout << "最后一个元素为：" << v1.back() << endl;
}


int main()
{
	test01();

	system("pause");
	return 0;
}

3.2.7 vector互换容器

功能描述：实现两个容器元素进行互换

#include
using namespace std;
#include
#include


// vector容器互换
// 1. swap(vec);		// 将vec与本身的元素互换

void printVector(vector&v)
{
	for (vector::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << "  ";
	}
	cout << endl;
}


// 1. 基本使用
void test01()
{
	vectorv1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	vectorv2;
	for (int i = 10; i > 0; i--)
	{
		v2.push_back(i);
	}

	cout << "交换前：" << endl;
	printVector(v1);
	printVector(v2);

	cout << "交换后：" << endl;
	v1.swap(v2);
	printVector(v1);
	printVector(v2);

}

// 2. 实际用途
// 巧用swap可以收缩内存空间
void test02()
{
	vectorv;
	for (int i = 0; i < 100000; i++)
	{
		v.push_back(i);
	}
	cout << "v的容量为：" << v.capacity() << endl;
	cout << "v的大小为：" << v.size() << endl;

	v.resize(3);			// 重新指定大小
	cout << "v的容量为：" << v.capacity() << endl;
	cout << "v的大小为：" << v.size() << endl;

	// 巧用swap收缩内存
	vector(v).swap(v);				// 匿名对象
	cout << "v的容量为：" << v.capacity() << endl;
	cout << "v的大小为：" << v.size() << endl;


}

int main()
{
	//test01();
	test02();


	system("pause");
	return 0;
}

总结：swap可以使两个容器互换，可以达到实用的收缩内存效果

3.2.7 vector预留空间

功能描述：减少vector在动态扩展容量时的扩展次数

#include
using namespace std;
#include
#include

// 1. reserve（int len);		// 容器预留len个元素长度，预留位置不初始化，元素不可访问
void test01()
{
	vectorv;

	// 利用reserve预留空间
	v.reserve(100000);

	int num = 0;			// 统计开辟次数
	int* p = NULL;
	for (int i = 0; i < 100000; i++)
	{
		v.push_back(i);
		if (p != &v[0])
		{
			p = &v[0];
			num++;
		}
	}
	cout << "num = " << num << endl;
}


int main()
{
	//test01();
	test01();


	system("pause");
	return 0;
}

总结：如果数据量较大，可以一开始利用 reserve预留空间

3.3 deque容器 3.3.1 deque容器基本概念

功能：双端数组，可以对头端进行插入删除操作

deque与vector区别：

1. vector对于头部的插入删除效率低，数据量越大，效率越低
2. deque相对而言，对头部的插入删除速度会比vector快
3. vector访问元素时的速度会比deque快，这和两者内部实现有关

deque内部工作原理：

deque容器的迭代器也是支持随机访问的

3.3.2 deque构造函数

deque容器构造

#include
using namespace std;
#include
#include

// deque 构造函数
// 1. dequedeqT;					// 默认构造形式
// 2. deque(beg, end);				// 构造函数将[beg, end)区间中的元素拷贝给本身
// 3. deque(n, elem);				// 构造函数将n个elem拷贝给本身
// 4. deque(const deque &deq)		// 拷贝构造函数

void printDeque(const deque&d)
{
	for (deque::const_iterator it = d.begin(); it != d.end(); it++)
	{
		// *it = 100;		// 容器中的数据现在是不可以修改的
		cout << *it << "  ";
	}
	cout << endl;
}

void test01()
{
	// 1. dequedeqT;					// 默认构造形式
	dequed1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);

	// 2. deque(beg, end);				// 构造函数将[beg, end)区间中的元素拷贝给本身
	dequed2(d1.begin(), d1.end());
	printDeque(d2);

	// 3. deque(n, elem);				// 构造函数将n个elem拷贝给本身
	dequed3(10, 100);
	printDeque(d3);

	// 4. deque(const deque &deq)		// 拷贝构造函数
	dequed4(d3);
	printDeque(d3);
}


int main()
{
	//test01();
	test01();


	system("pause");
	return 0;
}

总结：deque容器和vector容器的构造方式几乎一致，灵活使用即可

3.3.3 deque赋值操作

功能描述：给deque容器进行赋值

示例：

#include
using namespace std;
#include
#include



// deque容器赋值操作
// 1. deque& operator = (const deque &deq);				// 重载等号操作符
// 2. assign(beg, end);									// 将[beg, end)区间中的数据拷贝赋值给本身
// 3. assign(n, elem);									// 将n个elem拷贝赋值给本身

void printDeque(const deque& d)
{
	for (deque::const_iterator it = d.begin(); it != d.end(); it++)
	{
		cout << *it << "  ";
	}
	cout << endl;

}
void test01()
{
	dequed1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);

	// 1. deque& operator = (const deque &deq);				// 重载等号操作符
	dequed2;
	d2 = d1;
	printDeque(d2);

	// 2. assign(beg, end);									// 将[beg, end)区间中的数据拷贝赋值给本身
	dequed3;
	d3.assign(d1.begin(), d1.end());
	printDeque(d3);

	// 3. assign(n, elem);									// 将n个elem拷贝赋值给本身
	dequed4;
	d4.assign(10, 100);
	printDeque(d4);


}



int main()
{
	//test01();
	test01();


	system("pause");
	return 0;
}

总结：deque赋值操作也与vector相同，需要熟练掌握

3.3.4 deque大小操作

功能描述：对deque容器的大小进行操作

#include
using namespace std;
#include
#include

//  deque容器大小操作
//	1. deque.empty();				// 判断容器是否为空
//  2. deque.size();				// 返回容器中元素个数
//	3. deque.resize(num);		    // 重新指定容器的长度为num，若容器边长，则以默认值填充新位置
									// 如果容器变短，则末尾超出容器长度的元素被删除
//  4. deque.resize(num, elem);		// 重新指定容器的长度为num，若容器边长，则以elem值填充新位置
									// 如果容器变短，则末尾超出容器长度的元素被删除

void printDeque(const deque&d)
{
	for (deque::const_iterator it = d.begin(); it != d.end(); it++)
	{
		cout << *it << "  ";
	}
	cout << endl;
}

void test01()
{
	dequed1;
	for (int i = 0; i < 10; i++)
	{
		d1.push_back(i);
	}
	printDeque(d1);

	if (d1.empty())
	{
		cout << "d1为空！" << endl;
	}
	else
	{
		cout << "d1不为空" << endl;
		cout << "d1的大小为：" << d1.size() << endl;
		// deque容器没有容量的概念
	}

	// 重新指定大小
	d1.resize(15);
	printDeque(d1);

	d1.resize(20,1);
	printDeque(d1);

	d1.resize(5);
	printDeque(d1);
}


int main()
{
	
	test01();


	system("pause");
	return 0;
}

总结：

1. deque没有容量的概念
2. 判断是否为空：empty
3. 返回元素个数：size
4. 重新指定个数：resize

3.3.5 deque插入和删除

功能描述：向deque容器中插入和删除数据

#include
using namespace std;
#include
#include


// deque容器插入和删除
// 两端插入操作：
//	1. push_back(elem);				// 在容器尾部添加一个数据
//	2. push_front(elem);			// 在容器头部插入一个数据
//	3. pop_back();					// 删除容器最后一个数据
//	4. pop_front();					// 删除容器第一个数据

// 指定位置操作：
//	1. insert(pos, elem);			// 在pos位置插入一个elem元素的拷贝，返回新数据的位置
//	2. insert(pos, n, elem);		// 在pos位置插入n个elem数据，无返回值
//	3. insert(pos, beg, end);		// 在pos位置插入[beg, end)区间的数据，无返回值
//	4. clear();						// 清空容器的所有数据
//	5. erase(beg, end);				// 删除[beg, end)区间的数据，返回下一个数据的位置
//	6. erase(pos);					// 删除pos位置的数据，返回下一数据的位置

void printDeque(const deque& d)
{
	for (deque::const_iterator it = d.begin(); it != d.end(); it++)
	{
		cout << *it << "  ";
	}
	cout << endl;
}

// 两端操作
void test01()
{
	dequed1;

	// 尾插
	d1.push_back(10);
	d1.push_back(20);


	// 头插
	d1.push_front(100);
	d1.push_front(200);

	// 200 100 10 20
	printDeque(d1);

	// 尾删
	d1.pop_back();
	// 200 100 10 
	printDeque(d1);

	// 头删
	d1.pop_front();
	// 100 10
	printDeque(d1);

}

void test02()
{
	dequed1;
	d1.push_back(10);
	d1.push_back(20);
	d1.push_front(100);
	d1.push_front(200);
	
	// 200 100 10 20
	printDeque(d1);

	// insert插入
	d1.insert(d1.begin(), 1000);
	printDeque(d1);

	d1.insert(d1.begin(), 2, 10000);
	// 10000 10000 1000 200 100 10 20
	printDeque(d1);

	// 按照区间进行插入
	dequed2;
	d2.push_back(1);
	d2.push_back(2);
	d2.push_back(3);

	d1.insert(d1.begin(), d2.begin(), d2.end());
	// 1 2 3 10000 10000 1000 200 100 10 20
	printDeque(d1);

}

void test03()
{
	dequed1;
	d1.push_back(10);
	d1.push_back(20);
	d1.push_front(100);
	d1.push_front(200);

	// 删除
	deque::iterator it = d1.begin();
	it++;
	d1.erase(it);
	// 200 10 20
	printDeque(d1);

	// 按区间方式删除
	// d1.erase(d1.begin(), d1.end());
	// 清空
	d1.clear();
	printDeque(d1);


}


int main()
{
	
	//test01();

	//test02();

	test03();

	system("pause");
	return 0;
}

总结：

1. 插入和删除提供的位置是迭代器
2. 尾插：push_back
3. 尾删：pop_back
4. 头插：push_front
5. 头删：pop_front

3.3.6 deque数据存取

功能描述：对deque中的数据的存取操作

#include
using namespace std;
#include
#include


// deque容器数据存取
//	1. at(int idx);				// 返回索引idx所指的数据
//	2. operator[];				// 返回索引idx所指的数据
//	3. front();					// 返回容器中第一个数据元素
//  4. back();					// 返回容器中最后一个数据元素

void test01()
{
	dequed;
	d.push_back(10);
	d.push_back(20);
	d.push_back(30);
	d.push_front(100);
	d.push_front(200);
	d.push_front(300);

	// 通过[]方式访问元素
	// 300 200 100 10 20 30
	for (int i = 0; i < d.size(); i++)
	{
		cout << d[i] << "  ";
	}
	cout << endl;

	// 通过at方式访问元素
	for (int i = 0; i < d.size(); i++)
	{
		cout << d.at(i) << "  ";
	}
	cout << endl;

	cout << "第一个元素为：" << d.front() << endl;
	cout << "最后一个元素为：" << d.back() << endl;

}


int main()
{
	
	test01();


	system("pause");
	return 0;
}

总结：

1. 除了用迭代器获取deque容器中元素，[]和at也可以
2. front返回容器第一个元素
3. back返回容器最后一个元素

3.3.7 deque排序

功能描述：利用算法实现对deque容器进行排序

#include
using namespace std;
#include
#include
#include


void printDeque(const deque&d)
{
	for (deque::const_iterator it = d.begin(); it != d.end(); it++)
	{
		cout << *it << "  ";
	}
	cout << endl;
}

// deque容器排序
void test01()
{
	dequed;
	d.push_back(10);
	d.push_back(20);
	d.push_back(30);
	d.push_front(100);
	d.push_front(200);
	d.push_front(300);

	// 300 200 100 10 20 30
	printDeque(d);

	// 排序  默认排序规则 从小到大 升序
	// 对于支持随机访问的迭代器的容器，都可以利用sort算法直接对其进行排序
	// vector容器也可以利用sort进行排序
	sort(d.begin(), d.end());
	cout << "排序后： " << endl;
	printDeque(d);

}


int main()
{
	 
	test01();


	system("pause");
	return 0;
}

总结：sort算法非常实用，使用时包含头文件algorithm即可

3.4 案例——评委打分 3.4.1 案例描述

有5名选手：选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分。

3.4.1 实现步骤

1. 创建五名选手，放到vector中
2. 遍历vector容器，取出来每一个选手，执行for循环，可以把10个评分打分到deque容器中
3. sort算法对deque容器中分数排序，去除最高分和最低分
4. deque容器遍历一遍，累加总分
5. 获取平均分

示例：

#include
using namespace std;
#include
#include
#include
#include

// 有5名选手：选手ABCDE，10个评委分别对每一名选手打分，去除最高分，去除评委中最低分，取平均分。

class Person
{
public:
	Person(string name, int score)
	{
		this->m_Name = name;
		this->m_Score = score;
	}

	string m_Name;		// 姓名
	int m_Score;		// 平均分
};

void createPerson(vector< Person>& v)
{
	string nameSeed = "ABCDE";
	for (int i = 0; i < 5; i++)
	{
		string name = "选手";
		name += nameSeed[i];

		int score = 0;
		Person p(name, score);

		// 将创建的Person对象 放入到容器中
		v.push_back(p);
	}
}

// 打分
void setScore(vector& v)
{
	for (vector::iterator it = v.begin(); it != v.end(); it++)
	{
		// 将评委的分数 放入到deque容器中
		dequed;
		for (int i = 0; i < 10; i++)
		{
			int score = rand() % 41 + 60;
			d.push_back(score);
		}

		//cout << "选手：" << it->m_Name << "打分：" << endl;
		//for (deque::iterator dit = d.begin(); dit != d.end(); dit++)
		//{
		//	cout << *dit << " ";
		//}
		//cout << endl;


		// 排序
		sort(d.begin(), d.end());

		// 去除最高分和最低分
		d.pop_back();
		d.pop_front();

		// 取平均分
		int sum = 0;
		for (deque::iterator dit = d.begin(); dit != d.end(); dit++)
		{
			sum += *dit;		// 累加每个评委的分数
		}

		int avg = sum / d.size();

		// 将平均分 赋值给选手身上
		it->m_Score = avg;
	}
}

void showScore(vector& v)
{
	for (vector::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "姓名：" << it->m_Name << "t平均分：" << it->m_Score << endl;
	}
}

int main()
{
	// 随机数种子
	srand((unsigned int)time(NULL));

	// 1. 创建5名选手
	vectorv;
	createPerson(v);

	// 测试
	//for (vector::iterator it = v.begin(); it != v.end(); it++)
	//{
	//	cout << "姓名：" << (*it).m_Name << "t分数：" << (*it).m_Score<< endl;
	//}

	// 2. 给5名选手打分
	setScore(v);

	// 3.显示最后得分
	showScore(v);


	system("pause");
	return 0;
}

3.5 stack容器 3.5.1 stack基本概念

概念：stack是一种先进先出的数据结构，它只有一个出口

栈中只有顶端的元素才可以被外界使用，因此栈不允许有遍历行为

栈中进入数据成为——入栈 push

栈中弹出数据称为——出栈pop

3.5.2 stack常用接口

功能描述：栈容器常用的对外接口

#include
using namespace std;
#include

// 栈stack容器
// 构造函数
// stack stk;							// stack采用模板类实现，stack对象的默认构造形式
// stack(const stack &stk);				// 拷贝构造函数

// 赋值操作
// stack& operator = (const stack &stk);		// 重载等号操作符

// 数据存取
// push(elem);								// 向栈顶添加元素
// pop();									// 从栈顶移除第一个元素
// top();									// 返回栈顶元素

// 大小操作：
// empty();									// 判断堆栈是否为空
// size();									// 返回栈的大小


void test01()
{
	// 特点：符合先进后出数据结构
	stacks;

	// 入栈
	s.push(10);
	s.push(20);
	s.push(30);
	s.push(40);
	cout << "栈的大小：" << s.size() << endl;

	// 只要栈不为空，查看栈顶，并且执行出栈操作
	while (!s.empty())
	{
		// 查看栈顶元素
		cout << "栈顶元素为：" << s.top() << endl;

		// 出栈
		s.pop();
	}
	cout << "栈的大小：" << s.size() << endl;


}

int main()
{
	test01();

	system("pause");
	return 0;
}

总结：

1. 入栈：push
2. 出栈：pop
3. 返回栈顶：top
4. 判断栈是否为空：empty
5. 返回栈大小：size

3.6 queue容器 3.6.1 queue基本概念

概念：Queue时一种先进先出的数据结构，它有两个出口

队列容器允许从一端新增元素，从另一端移除元素

队列中只有队头和队尾才可以被外界使用，因此队列不允许有遍历行为

队列中进数据称为：入队 push

队列中出数据称为：出队 pop

#include
using namespace std;
#include
#include


// 队列 Queue
// 构造函数
// queue que;								// queue采用模板类实现，queue对象的默认构造形式
// queue(const queue &que);						// 拷贝构造函数

// 赋值操作
// queue& operator=(const queue &que);			// 重载等号操作符

// 数据存取
// push(elem);									// 往队尾添加元素
// pop();										// 从队头移除第一个元素
// back();										// 返回最后一个元素
// front();										// 返回第一个元素

// 大小操作
// empty();										// 判断堆栈是否为空
// size();										// 返回栈的大小

class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	string m_Name;
	int m_Age;
};

void test01()
{
	// 创建队列
	queueq;

	// 准备数据
	Person p1("唐僧", 30);
	Person p2("孙悟空", 1000);
	Person p3("猪八戒", 900);
	Person p4("沙僧", 800);

	// 入队
	q.push(p1);
	q.push(p2);
	q.push(p3);
	q.push(p4);

	cout << "队列大小为：" << q.size() << endl;

	// 判断只要队列不为空，查看队头，查看队尾，出队
	while (!q.empty())
	{
		// 查看队头
		cout << "队头元素 --- 姓名：" << q.front().m_Name << "年龄：" << q.front().m_Age << endl;

		// 查看队尾
		cout << "队尾元素 --- 姓名：" << q.back().m_Name << "年龄：" << q.back().m_Age << endl;

		// 出队
		q.pop();
	}

	cout << "队列大小为：" << q.size() << endl;


}

int main()
{
	test01();


	system("pause");
	return 0;
}

总结：

1. 入队：push
2. 出队：pop
3. 返回队头元素：front
4. 返回队尾元素：back
5. 判断队列是否为空 ：empty
6. 返回队列大小：size