3、STL-常用容器

标签：容器 常用 const string STL pos int end

3、STL-常用容器

3.1string容器

3.1.1string容器的基本概念

本质

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

strting 和char * 的区别：

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

特点

string类内部封装了很多成员方法

例如：查找find， 拷贝copy， 删除delete 替换replace，插入insert

string管理char*所分配的内存，不用担心复制越界和取值越界，由类内部进行负责

3.1.2string构造函数

构造函数原型：

• string(); 创建一个空的字符串 例如 string str;
• string (const char* s) ; 使用字符串s初始化
• string(const string& str) ; 使用一个对象初始化另一个string对象
• string(int n, char c); 使用n个字符c初始化

示例：

#include<iostream>
using namespace std;
#include<string>	


void test() {
	//-string();       创建一个空的字符串  例如   string  str;
	string str1;
	str1 = "123456`";
	cout << str1 << endl;
	//-string(const char* s);   使用字符串s初始化
	/*const char* s = "abcd";*/
	string str2("abcd");
	cout << str2 << endl;
	//- string(const string & str);    使用一个对象初始化另一个string对象
	string str3(str1);
	cout << str3 << endl;
	//- string(int n, char c);         使用n个字符c初始化
	string str4(10, 'a');
	cout << str4 << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

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

3.1.3string赋值操作

功能描述：

• 给string字符串进行赋值

赋值的函数原型：

• string& operator=(const char * s); char*类型的字符串 赋值给当前字符串
• string& operator=(const string &s); 把字符串s付给当前的字符串
• string& operator=(char c); 字符赋值给当前的字符串
• string& assign(const char* s, int n); 把字符串s的前n个字符赋值给当前的字符串
• string& assign(const string &s); 把字符串s赋值给当前的字符串
• string& assifn(int n, char c); 用g个字符串c赋值给当前字符串
• string & assign(const string &s, int start, int end); 把s的子串赋给当前字符串，没有end，则默认到最后

void test() {
	/* 不能直接赋值，先定义后赋值,直接赋值，就是说在定义的时候加等号，那属于构造函数*/
	//-string & operator=(const char* s);   char* 类型的字符串  赋值给当前字符串
	string str1;
	str1= "acdc";
	cout << str1 << endl;
	//- string & operator=(const string & s);   把字符串赋值给当前的字符串
	string str2 = str1;
	////- string & operator=(char c);          字符赋值给当前的字符串  

	//char c = 'c';
	string str3;
	str3 = 'c';
	cout << str3 << endl;
	//- string & assign(const char* s, int n);   把字符串s的前n个字符赋值给当前的字符串
	// 注意用的是char*类型 不能用string类型
	string str4;
	str4.assign("world", 2);
	cout << str4 << endl;
	//- string & assign(const string & s);     把字符串s赋值给当前的字符串
	// string & assign(const string &s, int start, int end); 把s的子串赋给当前字符串，没有end，则默认到最后
	string str5;
	str5.assign(str1);
	cout << str5 << endl;
	//- string & assign(int n, char c);      用g个字符c赋值给当前字符串
	str5.assign(10, 'a');
	cout << str5 << endl;
}

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

3.1.4string字符串拼接

功能描述：

• 实现在字符串末尾拼接字符串

函数原型：

• string & operator+=(const char* str); 重载+=操作符
• string &operator+=(const char c); 重载+=操作符
• string & operator+=(const string& str); 重载+=操作符
• string& append(const char *s); 把字符串s链接到当前字符串结尾
• string& append(const char*s ,in n) 把字符串s的前n个字符连接到当前字符串结尾
• string& append(const string &s); 同operator+=(const string & str)
• string& append(const string &s, int pos, int n); 字符串中从pos开始的n个字符链接到字符串的结尾

void test() {
	string str1("abcd");
	char c = 'c';
	// -string & operator+=(const char * str);      重载 += 操作符
	string str;
	str = str1 + "efg";
	cout << str << endl;
	//- string & operator+=(const char c);            重载 += 操作符
	str = str1 + c;
	cout << str << endl;
	//- string & operator+=(const string & str);  重载 += 操作符
	//string str2(str);
	str += str1;
	cout << str << endl;

	//- string & append(const char* s)       把字符串s链接到当前字符串结尾
	str.append("a");
	cout << str << endl;
	//- string & append(const char* s, in n)   把字符串s的前n个字符连接到当前字符串结尾
	str.append("afdjaslkfgjasdklj", 5);
	cout << str << endl;
	//- string & append(const string & s);    同operator += (const string & str)
	str.append(str1);
	cout << str << endl;
	//- string & append(const string & s, int pos, int n);   字符串中从pos开始的n个字符链接到字符串的结尾
	str.append(str1, 2, 3);
	cout << str << endl;
}

3.1.5 string 查找和替换

功能描述：

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

函数原型：

• int find(const string& str, int pos=0) const; // 查找str第一次出现的位置，从下标pos开始查找
• int find(const char* s, int pos = 0)const; // 查找s第一次出现的位置，从pos开始查找
• int find(const char* s , int pos, int n) const; // 从pos开始查找前n个字符第一次出现位置
• int find(const char c, int pos = 0) const; // 查找字符c第一次出现的位置
• int rfind(const chat * s, int pos = npos) const; // 查找s最后一次出现为位置 ， 从pos开始查找
• int rfind(congst string & str, int pos = npos) const; // 查找str最后一次出现位置， 从pos开始查找
• int rfind(const char c , int pos=0)const ; // 查找字符c最后一次出现位置， 从pos开始查找
• string & replace(int pos, int n, const string& str); // 替换从pos开始n个字符为字符串str
• string& replace(int pos, int n , const char * s ); // 替换从pos开始的n个字符为字符串s

void test() {
	// 返回的下标值为-1， 表示未查询到字符或者字符串
	string str("abcdefijghijk");
	string str1 = "de";
	//-int find(const string & str, int pos = 0) const;     // 查找str第一次出现的位置，从下标pos开始查找
	int pos = str.find(str1);
	cout << pos << endl;
	//-int find(const char* s, int pos = 0)const;   // 查找s第一次出现的位置，从pos开始查找
	pos = str.find("hi");
	cout << pos << endl;
	//-int find(const char* s, int pos, int n) const;    // 从pos开始查找s的前n个字符第一次出现位置
	pos = str.find("hi", 0, 1);
	cout << pos << endl;
	//-int find(const char c, int pos = 0) const;      // 查找字符c第一次出现的位置
	pos = str.find('c', 2);
	cout << pos << endl;
	//-int rfind(const chat * s, int pos = npos) const;  // 查找s最后一次出现为位置 ， 从pos开始查找
	pos = str.rfind("ij");
	cout << pos << endl;
	//-int rfind(congst string & str, int pos = npos) const;    // 查找str最后一次出现位置， 从pos开始查找
	pos = str.rfind(str1);
	cout << pos << endl;
	//-int rfind(const char c, int pos = 0)const;    // 查找字符c最后一次出现位置， 从pos开始查找
	pos = str.rfind('c');
	cout << pos << endl;
	//-string & replace(int pos, int n, const string & str);   //  替换从pos开始n个字符为字符串str
	str.replace(2, 4, str1);
	cout << str << endl;
	//-string & replace(int pos, int n, const char* s);     // 替换从pos开始的n个字符为字符串s
	str.replace(2, 2, "小明");
	cout << str << endl;
}

总结：

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

3.1.6string字符串比较

功能描述：

• 字符串之间的比较

比较方式:

• 字符串比较是按字符的ASCII码进行对比

= 返回 0

> 返回 1

< 返回 -1

函数原型

• int compare(const string & s)const; // 与字符串s比较
• int compare(const char* s)const; // 与字符串s比较

void test() {
	string str1("abcd");
	string str2(str1);
	string str3;
	str3 = "bcda";
	//-int compare(const string & s)const;   // 与字符串s比较
	int com1 = str1.compare(str2);
	int com2 = str1.compare(str3);
	cout << com1 << endl;
	cout << com2 << endl;
	//-int compare(const char* s)const;  // 与字符串s比较
	int com3 = str1.compare("abab");
	int com4 = str1.compare("abcd");
	cout << com3 << "  " << com4 << endl;

}

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

3.1.7 string字符存取

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

• char& operator[](int n); // 通过[]下标方式取字符
• char& at(int n); // 通过at方法获取字符

可以访问，同时也可以修改访问值

void test() {
	string str1("abcd");
	// 访问
	cout << str1[1] << endl;
	// 也可用const char 类型字符 用= 替换指定下标字符
	str1[1] = 'c';
	cout << str1 << endl;

	cout << str1.at(1) << endl;
	str1.at(1) = 'd';
	cout << str1 << endl;

}

3.1.8string插入和删除

功能描述：

• 对string字符串进行插入和删除字符操作

函数原型：

• string& insert(int pos, const* s); // 插入字符串
• string& insert(int pos, const string& str);
• string& insert(int pos, int n , char c); // 在指定位置插入n个字符c ，少了直接替换，多了， 后面的后移
• string& erase(int pos, int n= npos); // 删除从pos 开始的n个字符，默认删除pos后面的所有字符

void test() {
	string str1("abcd");
	const char* s = "fgh";
	string str = "vvvvv";
	// 第一种插入方式
	str.insert(1, s);
	cout << str << endl;
	// 删除刚才插入的值
	str.erase(1, sizeof(s) / sizeof(char));
	cout << str << endl;
	// 第二种插入方法
	str.insert(0, str1);
	cout << str << endl;
	// 第三种插入方法
	str.insert(0, 2, 'b');
	cout << str << endl;

}

3.1.9 string子串

功能描述：

• 从字符串中获取想要的子串

函数原型

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

void test() {
	string str("[email protected]");
	int pos = str.find("@");
	string name = str.substr(0, pos);
	cout << name << endl;
}

3.2Vector容器

3.2.1vector基本概念

功能：

• vector数据结构和数组非常相似， 也称为单端数组

vector与普通数组区别：

• 不同之处在于数组是静态空间，而vector可以动态扩展

动态扩展：

并不是在原空间之后续接新空间， 而是找更大的内存空间，然后将元数据拷贝新空间，释放原空间

• vecto容器的迭代器是支持随机访问的迭代器

3.2.2vector构造函数

功能描述

• 创造vector容器

函数原型：

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

#include<iostream>	
#include<string>	
using namespace std;
#include<vector>	


void printVector(vector<int>& vec) {
	/*for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++) {
		cout << *it << endl;
	}*/
	vector<int>::iterator it_begin = vec.begin();
	vector<int>::iterator it_end = vec.end();
	while (it_begin != it_end) {
		cout << *it_begin << " ";
		it_begin++;
	}
	cout << endl;

}

void test() {
	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	printVector(v);

	vector<int>v1(v.begin(), v.end());
	printVector(v1);

	vector<int>v2(10, 100);
	printVector(v2);

	vector<int>v3(v2);
	printVector(v3);
}

int main() {
	test();
	system("pause");
	return 0;
}

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

3.2.3vector赋值操作

功能描述：

• 给vector容器进行赋值

函数原型：

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

void test() {
	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	printVector(v);

	vector<int> v1;
	v1 = v;
	printVector(v1);

	vector<int>v2;
	v2.assign(v.begin(), v.end());   // 顾头不顾尾
	printVector(v2);

	vector<int>v3;
	v3.assign(10, 100);
	printVector(v3);
}

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

3.2.4 vector容量和大小

功能描述：

• 对vector容器的容量和大小操作

函数原型：

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

void test() {
	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	printVector(v);
	vector<int> v1;
	bool is_empty = v1.empty();   //  bool和int类型都可以
	cout << is_empty << endl;
	// 注意capacity和size不同 ， capacity是大于等于size的
	cout << v.capacity() << endl;
	cout << v1.capacity() << endl;
	cout << v.size() << endl;
	v.resize(5);
	printVector(v);
	v.resize(20, 100);
	printVector(v);
}

3.2.5 vector插入和删除

功能描述：

• 对vector容器进行插入、删除等操作

函数原型：

• push_back(ele); // 尾部插入元素ele
• pop_back(); // 删除最后一个元素
• insert(const_iterator pos, ele); // 迭代器指向位置pos插入元素ele
• insert(const_iterator pos, int count, ele); // 迭代器指向位置pos插入count个元素ele
• erase(const_iterator pos); // 删除迭代器指向的元素
• erase(const_iterator start, const_iterator end); // 删除迭代器从start到end之间的元素
• clear(); // 清空容器中所有的元素

void test() {
	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	printVector(v);

	v.pop_back();
	printVector(v);

	v.insert(v.begin(), 100);
	printVector(v);

	v.insert(v.begin(), 3, 1000);
	printVector(v);

	v.erase(v.begin());
	printVector(v);

	// v.clear();
	v.erase(v.begin(), v.end());
	printVector(v);
}

3.2.6 vector数据存取

功能描述：

• 对vector中的数据的存取操作

函数原型：

• at(int, index); // 返回索引index所指向的数据
• operator[index];
• front(); // 返回容器中第一个数据元素
• back(); // 返回容器中最后一个数据元素

3.2.7 vector互换容器

功能描述：

• 实现两个容器内元素进行互换

函数原型：

• swap(vec); // 将vec与本身元素互换

void test() {
	vector<int> v;

	for (int i = 0; i < 1000; i++) {
		v.push_back(i);
	}
	cout << v.capacity() << endl;
	cout << v.size() << endl;
	//巧用swap收缩内存
	v.resize(3);
	cout << v.capacity() << endl;
	cout << v.size() << endl;
	// 利用匿名对象  利用v初始化匿名对象，然后交换
	vector<int>(v).swap(v);
	cout << v.capacity() << endl;
	cout << v.size() << endl;

}

3.2.8 vector预留空间

功能描述：

• 减少vector再动态扩展容量时的扩展次数

函数原型：

• reserve(int len); // 容器预留len个元素长度，预留位置不初始化，元素不可访问

void test() {
	vector<int> v;
	int num = 0;
	int* p = NULL;

	// 不加是扩展了30次， 加了扩展1次
	//v.reserve(100000);

	for (int i = 0; i < 100000; i++) {
		v.push_back(i);
		if (p != &v[0]) {  // 监测地址变化
			p = &v[0];   
			num++;
		}
	}
	cout << num << endl;

3.3deque容器

3.3.1 deque容器基本概念

功能：

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

deque与vector区别：

• vector对于头部数据的插入和删除效率极低，属于后面的所有数据后移， 数据量越大， 效率越低
• deque相对而言，对头部的插入删除速度会比vector快
• vector访问元素时的速度会比deque快，这和两者的内部实现有关

deque内部工作原理：

• deque内部有个中控器，维护每段缓冲区中的内容， 缓冲区存放真实数据

• 中控器维护的时每个缓冲区的地址，使得使用deque时像一片连续的内存空间

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

deque中控器存放缓冲区地址，如果前面的空间不够了，就在开辟一块内存，存放数据，中控器中存放其地址。后面也是一样。

3.3.2deque构造函数

功能描述：

• deque容器构造

函数原型：

• deque deqT; // 默认构造形式
• deque (beg, end); // 构造函数将（beg， end）区间中的元素拷贝为本身
• deque (n, elem); // 构造函数将n个elem拷贝给本身
• deque(const deque &deq); // 拷贝构造函数

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


void test() {
	deque<int> deq;
	deq.push_back(1);
	deq.push_back(2);
	deq.push_back(3);
	deque<int>deq1(deq.begin(), deq.end());
	deque<int>deq2(10, 100);
	deque<int>deq3(deq);

	printDeque(deq);
	printDeque(deq1);
	printDeque(deq2);
	printDeque(deq3);
}

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

3.3.3deque赋值操作

功能描述：

• 给deque容器进行赋值

函数原型：

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

printDeque(deq);
	printDeque(deq1);
	printDeque(deq2);
	printDeque(deq3);
	deq1 = deq2;
	deq.assign(deq2.begin(), deq2.end());
	deq3.assign(10, 1000);
	printDeque(deq);
	printDeque(deq1);
	printDeque(deq2);
	printDeque(deq3);

3.3.4deque大小操作

功能描述：

• 对deque容器的大小进行操作

函数原型：

• deque.empty(); // 判断容器是否为空
• deque.size(); // 返回容器中元素的个数
• deque.resize(num); // 重新指定容器的长度为num ， 若容器变长，则以默认值填充新位置。

​ // 如果如期变短， 则末尾超出容器长度的元素被删除

• deque.resize(num, elem); 指定默认值

	deque<int> deq;
	if (deq.empty()) {
		deq.push_back(10);
	}
	cout << deq.size() << endl;
	deq.resize(10);
	printDeque(deq);
	deq.resize(20, 10);
	printDeque(deq);
	deq.resize(1);
	printDeque(deq);

总结：

• deque没有容量的概念
• 判断是否为空 empty
• 返回元素个数 size
• 重新指定个数 resize

3.3.5deque插入和删除

功能描述：

• 向deque容器中插入和删除数据

两端插入操作：

• push_back(elem); // 在容器尾部添加一个数据
• push_front(elem); // 在容器头部插入一个数据
• pop_back(); // 删除容器最后一个数据
• pop_front(); // 删除容器第一个数据

指定位置操作：

• insert(pos, elem);
• insert(pos, n, elem);
• insert(pos, beg, end);
• clear();
• erase(beg, end);
• erase(pos);

	//插入和删除
	deque<int> deq;
	deq.push_back(10);
	deq.push_back(10);
	deq.push_front(20);
	deq.push_front(20);
	printDeque(deq);
	if (deq.empty()) {
		deq.push_back(10);
	}
	else {
		deq.pop_back();
	}
	printDeque(deq);
	if (!deq.empty()) {
		deq.pop_front();
	}
	printDeque(deq);
	
	deq.insert((++deq.begin()), 30);
	printDeque(deq);
	deq.insert(deq.begin(), 5, 6);
	printDeque(deq);

	deque<int> deq1(deq);
	deq.insert(deq.end()-2, deq1.begin(), deq1.end());  // 迭代器指向可以偏移
	printDeque(deq);

	deq.clear();
	printDeque(deq);
	deq1.erase(deq1.begin());
	printDeque(deq1);
	deq1.erase(deq1.begin(), deq1.end());
	printDeque(deq1);

}

总结：

注意，插入和删除提供的位置是迭代器

迭代器指向可以偏移

3.3.6 deque数据存取

功能描述：

• 对deque中的数据的存取操作

函数原型：

• at(int idx); // 返回索引idx所指向的数据
• operator[ ]; // 返回索引idx所指的数据
• front(); // 返回容器中第一个数据元素
• back(); // 返回容器中最后一个数据元素

	deque<int> deq;
	for (int i = 0; i < 10; i++) {
		deq.push_back(i);
	}
	cout << deq[1] << endl;
	deq[1] = 20;
	cout << deq.at(1) << endl;
	cout << deq.front() << endl;
	deq.front() = 10;
	cout << deq.front() << endl;
	cout << deq.back() << endl;

3.3.7 deque排序

功能描述：

• 利用算法实现对deque容器进行排序

算法：

• sort(iterator beg, iterator end); // 对beg和end区间内的元素进行排序

默认升序

#include<algorithm>


deque<int> deq;
for (int i = 0; i < 10; i++) {
	deq.push_back(9-i);
}
printDeque(deq);
sort(deq.begin(), deq.end());
printDeque(deq);

3.4案例-评委打分

3.4.1案例描述

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

3.4.2实现步骤

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

代码

3.5stack容器

3.5.1 stack基本概念

概念：stack是一种先进后出(First In Last Out, FILO)的数据结构， 它只有一个出口

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

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

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

3.5.2stack常用接口

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

构造函数：

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

赋值操作：

• stack& operator=(const stack & stk); // 重载等号运算符

数据存取：

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

大小操作：

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

#include<stack>

void test() {
	// 构造函数
	stack<int> stk1;
	stk1.push(1);
	stk1.push(2);
	stk1.push(3);

	stack<int> stk2(stk1);

	// 赋值
	stack<int> stk3;
	stk3 = stk1;

	// 其他操作
	while (!stk3.empty()) {
		cout << stk3.top() << endl;
		stk3.pop();
		cout << "栈的大小" << stk3.size() << endl;
	}

}

3.6 queue容器

3.6.1 queue基本概念

概念：Queue是一种先进先出(First In First Out, FIFO)的数据结构， 他有两个出口

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

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

队列中进数据——入队 push

队列中出数据——出队 pop

3.6.2 queue常用接口

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

构造函数：

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

赋值操作：

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

数据存取：

• push(elem); // 队尾添加元素
• pop(); // 从队头移除第一个元素
• back(); // 返回队尾元素， 也就是最后一个元素
• front(); // 返回第一个元素

大小操作;

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

示例：

#include<iostream>	
#include<queue>
#include<string>
using namespace std;


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

void test() {
	Person p1("sunwukong", 1000);
	Person p2("sunwukong", 1000);
	Person p3("sunwukong", 1000);
	// 构造
	queue<Person> q;
	q.push(p1);
	q.push(p2);
	q.push(p3);
	queue<Person> q1(q);

	// 赋值
	queue<Person>q2;
	q2 = q1;
	
	// 其他操作
	while (!q2.empty()) {
		cout << "queue front name: " << q2.front().m_name << "  queue front age: " << q2.back().m_age << endl;
		cout << "queue back name: " << q2.front().m_name << "  queue back age: " << q2.back().m_age << endl;
		
		q2.pop();
		cout << q2.size() << endl;
	}

}

void main() {
	test();
	system("pause");
}

3.7list容器

3.7.1基本概念

功能：将数据进行链式存储

链表（list）：是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表种的指针链接实现的

链表的组成：链表由一系列结点组成

结点的组成：一个是存储数据元素的数据域，另一个是存储下一个节点地址指针域

STL中的链表是一个双向循环链表

双向循环链表：节点中指针域存储两个指针，一个指向前一个节点地址，一个指向后一个节点地址

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器

list的优点：

• 采用动态存储分配，不会造成内存浪费和溢出
• 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素

list的缺点：

• 链表灵活，但是空间（指针域）和时间（遍历）额外耗费较大

List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector中是不成立的

总结：STL中List和vector是两个最常被使用的容器，各有优缺点

3.7.2构造函数

功能描述：

• 创建list容器

函数原型：

• list lst; // 采用模板类实现，对象的默认构造
• list(beg, end); // 构造函数将[beg, end]曲线中的元素拷贝给本身
• list(n, elem); // 构造函数将n个elem拷给本身
• list(const list &lst); // 拷贝构造

示例：

总结：list构造方式同其他几个stl常用容器，熟练掌握即可

3.7.3list赋值和交换

功能描述：

• 给list容器进行赋值， 以及交换list容器

函数原型：

• assign(beg, end); // 将区间内的数据拷贝给本身， 都是迭代器区间
• assign(n, elem);
• list& operator=(const list & lst); // 重载等号操作符
• swap(lst); // 将lst与本身的元素互换

3.7.4 list大小操作

功能描述：

• 对list容器的大小进行操作

函数原型：

• size(); // 返回容器中元素个数
• empty(); // 判断容器是否为空
• resize(num); // 重新指定容器的长度为num， 如果容器边长，则以默认值填充，变短，删除末尾元素
• resize(num, elem);

3.7.5list插入和删除

功能描述：

• 对list容器进行数据的插入和删除

函数原型：

• push_back(elem); // 在容器尾部加入一个元素
• pop_back(elem); // 删除容器最后一个元素
• push_front(elem); // 在容器开头插入第一个元素
• pop_front(elem); // 删除容器第一个元素
• insert(pos, elem); // 在pos位置插入elem元素的拷贝，返回新数据的位置， 位置是迭代器类型
• insert(pos, n , elem); // 无返回值
• insert(pos, beg, end); // 无返回
• clear(); // 移除容器中所有数据
• erase(beg, end); // 删除[beg, end] 区间中的数据，返回下一个数据的位置
• erase(pos); // 返回下一个数据的位置
• remove(elem); // 删除容器中所有与elem值相匹配的元素

3.7.6list数据存取

功能描述：

• 对list容器中数据进行存取

函数原型：

• front(); // 返回第一个元素
• back(); // 返回最后一个

3.7.7list反转和排序

功能描述：

• 将容器中的元素反转， 以及将容器中的数据进行排序

函数原型：

• reverse(); // 反转链表
• sort(); // 链表排序

所有不支持随机访问迭代器的容器，不可以使用标准算法

不支持随机访问迭代器的容器， 内部提供对应一些算法

list自定义排序规则使用函数，不是仿函数，注意和后面的进行区分

list以上所有基本操作代码：

#include<iostream>	
#include<list>	
#include<string>	
using namespace std;


// 排序规则函数， 注意 更改list排序规则，用的不是仿函数，用的是函数
bool myCompare(const int& l1, const int& l2) {
	return l1 > l2;
}

void printList(const list<int> &lst) {
	for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++) {
		cout << *it << "   ";
		
	}
	cout << endl;
}

void test() {
	// 构造
	list<int> lst1;
	lst1.push_back(1);
	lst1.push_back(2);
	lst1.push_back(3);
	lst1.push_front(0);
	list<int> lst2(lst1.begin(), lst1.end());
	list<int> lst3(lst2);
	printList(lst3);
	list<int> lst4(6, 6);
	printList(lst4);

	// 赋值和交换
	list<int> lst5;
	lst5 = lst1;
	printList(lst5);
	list<int> lst6;
	lst6.assign(lst2.begin(), lst2.end());
	printList(lst6);
	list<int>lst7;
	lst7.assign(6, 8);
	printList(lst7);

	lst7.swap(lst6);
	printList(lst6);
	printList(lst7);

	// list 大小
	cout << lst1.size() << endl;
	if (!lst1.empty()) {
		lst1.resize(8, 6);
	}
	printList(lst1);

	// 插入和删除
	lst2.clear();
	lst2.push_back(6);
	lst2.push_front(3);
	lst2.insert(lst2.begin(), 0);
	lst2.insert(lst2.end(), 6, 8);  // 插入6个8
	lst2.insert(lst2.begin(), lst7.begin(), lst7.end());
	printList(lst2);
	lst2.pop_back();
	lst2.pop_front();
	printList(lst2);

	lst2.erase(lst2.begin());
	lst2.erase(--lst2.end());  //  注意  end处是没有值的
	printList(lst2);

	lst2.remove(8);  // 移除链表中的所有8
	printList(lst2);

	lst2.erase(lst2.begin(), lst2.end());
	printList(lst2);


	// list数据存取  不支持[], 和 at
	// 原因是list本质是链表，不是连续线性空间存储 迭代器也是不支持随机访问的
	cout << "lst6第一个元素" << lst6.front() << endl;
	cout << "lst6最后一个元素" << lst6.back() << endl;
	
	//// 验证迭代器不支持随机访问
	//list<int>::iterator it = lst6.begin();
	//it = it + 3;  // 报错


	// list 反转和排序
	lst1.reverse();  // 反转链表
	printList(lst1);

	lst1.sort();
	printList(lst1);

	// 更改排序规则，按照降序排序, 利用bool类型函数
	lst1.sort(myCompare);
	printList(lst1);
}



int main() {
	test();
	system("pause");
	return 0;
}

3.7.8排序案例

案例描述：

将Person自定义数据类型进行排序， Person中属性有姓名，年龄，身高

排序规则：按照年龄进行升序， 如果年龄相同，按照身高排序

代码：

#include<iostream>
#include<string>
#include<list>
using namespace std;

class Person {
public:
	Person(string name, int age, int height) {
		this->m_name = name;
		this->m_age = age;
		this->m_height = height;
	}

	string m_name;
	int m_age;
	int m_height;
};

void printList(const list<Person>& lst) {
	cout << "list_start" << endl;
	for (list<Person>::const_iterator it = lst.begin(); it != lst.end(); it++) {
		cout << (*it).m_name << "  " << (*it).m_age << "  " << it->m_height << endl;
	}
	cout << "list_end" << endl;
}



bool myCompare(Person& p1, Person& p2) {
	// 按照年龄排序升序， 年龄一样按照身高，升序
	if (p1.m_age == p2.m_age) {
		return p1.m_height < p2.m_height;
	}
	else {
		return p1.m_age < p2.m_age;
	}
}

void test1() {
	list<Person> L;
	Person p1("刘备", 35, 185);
	Person p2("曹操", 35, 180);
	Person p3("赵云", 30, 190);
	Person p4("张飞", 32, 187);
	Person p5("关羽", 35, 189);
	L.push_back(p1);
	L.push_back(p2);
	L.push_back(p3);
	L.push_back(p4);
	L.push_back(p5);
	printList(L);
	L.sort(myCompare);
	printList(L);
}


int main() {
	test1();
	system("pause");
	return 0;
}

3.8 set/multiset容器

3.8.1 set基本概念

简介：

• 所有元素都会在插入时自动被排序

本质：

• set/multiset属于关联式容器，底层结构用的是二叉树实现

set和multiset区别：

• set不允许容器中有重复的元素
• multiset允许容器中有重复的元素

3.8.2 构造和赋值

功能描述：创建set容器以及赋值

构造：

• set st;
• set(const set & st); // 拷贝构造函数

赋值：

• set& operatror=(const set &st); // 重载等号操作符

没有其他构造和assign赋值方式，注意区别， 且插入数据只有insert方式

3.8.3 set大小和交换

功能描述：

• 统计set容器的大小以及交换set容器

函数原型：

• size(); // 返回容器中元素的数目
• empty(); // 判断容器是否为空
• swap(st); // 交换两个集合容器

3.8.4 set插入和删除

功能描述：set容器进行插入数据和删除数据

函数原型：

• insert(elem); // 在容器中插入元素
• clear(); // 清除所有元素
• erase(pos); // 删除pos迭代器所指的元素， 返回下一个元素的迭代器
• erase(beg, end); // 删除区间内元素， 返回下一个元素的迭代器
• erase(elem); // 删除容器中值为elem的元素 类似于list容器中的remove

3.8.5 set查找和统计

功能描述：

• 对set容器进行查找数据以及统计数据

函数原型：

• find(key); // 查找key是否存在，若存在， 返回该键的元素的迭代器， 若不存在，返回set.end()
• cout(key); // 统计key的元素个数

set<int>::iterator pos = s.find(1);

int num = s1.count(2);

3.8.6 set和multiset的区别

区别：

• set不可以插入重复数据， 而multiset可以
• set插入数据的同时会返回插入结果，表示插入是否成功 返回的是一个对组，第一个是迭代器位置，第二个是bool值
• multiset不会检测数据，因此可以插入重复数据

pair<set<int>::iterator, bool> ret = s.insert(10);

以上所有操作汇总：

#include<iostream>
#include<set>
using namespace std;


void printSet(const set<int>& st) {
	for (set<int>::const_iterator it = st.begin(); it != st.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

void test() {
	// 构造函数
	set<int> st1;
	// set 只能通过insert加入新数据  有返回值pair<iterator, bool> insert(value_type&& _Val)
	// 返回一个对组，pos  bool
	st1.insert(1);
	st1.insert(2);
	st1.insert(3);
	pair<set<int>::iterator, bool>ret = st1.insert(4);
	cout << "插入的元素" << *ret.first << "  插入结果：" << ret.second<< endl;
	set<int> st2(st1);
	printSet(st2);

	// 插入和删除
	set<int> st3(st2);
	set<int>::iterator pos = st3.erase(st3.begin());
	// 删除pos位置的元素， 返回下一个元素的迭代器
	cout <<"删除元素的下一个元素：" << *pos << endl;
	printSet(st3);
	// 删除元素值
	st3.erase(2);
	printSet(st3);

	st3.clear();


	//大小和交换
	cout << st1.size() << endl;
	if (st3.empty()) {
		st3.swap(st1);
		cout << st1.size() << endl;
		printSet(st3);
	}

	// 查找和统计  统计对于set不是1就是0
	// 查找find返回迭代器，若存在返回该键的迭代器，不存在返回set.end()
	set<int>::iterator pos2 = st3.find(30);
	if (pos2 != st3.end()) {
		cout << "找到元素：" << *pos2 << endl;
	}
	else {
		cout << "未找到元素" << endl;
	}
	// 统计，返回个数
	int num = st3.count(3);
	cout << "3的个数: " << num << endl;


	// multiset
	multiset<int> m1;
	m1.insert(1);
	m1.insert(1);
	m1.insert(1);
	m1.insert(1);
	for (multiset<int>::iterator it = m1.begin(); it != m1.end(); it++) {
		cout << *it << "  ";
	}
	cout << endl;
}

int main() {
	test();
	system("pause");
	return 0;
}

3.8.7 pair对组创建

功能描述：

• 成对出现的数据，利用对组可以返回两个数据

两种创建方式：

• pair<type, type> p(value1, value2);
• pair<type, type> p = make_pair(value1, value2);

pair<string, int> p("tom", 15);

pair<string, int> p2 = make_pair("jay", 14);

cout<<p.first<<"  "<< p.second<<endl;

3.8.8 set容器排序

set容器默认排序规则为从小到大， 掌握如何改变排序规则

主要技术点：利用仿函数，可以改变排序规则

排序规则要在创建set容器的时候指定，因为没有sort方法， 且迭代器不支持随机访问

示例：自定义类型数据排序 自定义类型的数据，set必须指定排序规则才可以插入数据

注意：自定义排序规则的时候， 重载operator()的时候注意在参数列表后面加const

有 const 修饰的成员函数（指 const 放在函数参数表的后面，而不是在函数前面或者参数表内），只能读取数据成员，不能改变数据成员；没有 const 修饰的成员函数，对数据成员则是可读可写的。

示例1

//set容器默认排序为从小到大,掌握如何改变排序规则
//利用仿函数,可以改变排序规则
#include<iostream>
#include<set>
using namespace std;
//仿函数:用类调用函数
//仿函数设计:
class MyCompare {
public:
	//有 const 修饰的成员函数
	//（指 const 放在函数参数表的后面，而不是在函数前面或者参数表内），
	//只能读取数据成员，不能改变数据成员；没有 const 修饰的成员函数，
	//对数据成员则是可读可写的。
	//下一行末尾加上const
	/*bool operator()(int v1, int v2){
		return v1 > v2;
	}*/
	bool operator()(int v1, int v2)const {
		return v1 > v2;
	}
};
void test01() {
	set<int>s1;
	s1.insert(10);
	s1.insert(40);
	s1.insert(30);
	s1.insert(50);
	s1.insert(20);
	for (set<int>::iterator it = s1.begin(); it != s1.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

	//指定排序规则为从大到小
	//重新指定第一步,更改第二个默认值
	//注意:这里第二个默认值需求为类型,不可以是函数(函数名),故使用仿函数
	set<int, MyCompare>s2;
	s2.insert(10);
	s2.insert(40);
	s2.insert(30);
	s2.insert(50);
	s2.insert(20);
	for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}
int main() {
	test01();
}

示例二

#include<iostream>
#include<string>
#include<set>
using namespace std;

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

	string m_name;
	int m_age;
};

// 仿函数指定排序规则
class myCompare {
public:
	bool operator()(const Person& p1, const Person& p2)const {
		return p1.m_age > p2.m_age;
	}
};


//void printSet(const set<Person, myCompare>& s) {
//	for (set<Person, myCompare>::const_iterator it = s.begin(); it != s.end(); it++) {
//		cout << it->m_name << "  " << it->m_age << endl;
//	}
//}

void test1() {
	Person p1("刘备", 35);
	Person p2("关羽", 34);
	Person p3("张飞", 33);
	Person p4("曹操", 36);
	Person p5("孙权", 20);

	set<Person, myCompare> s;
	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);
	s.insert(p5);
	for (set<Person, myCompare>::iterator it = s.begin(); it != s.end(); it++) {
		cout << it->m_name << "  " << it->m_age << endl;
	}
}


int main() {
	test1();
	system("pause");
	return 0;
}

注意定义排序规则的时候仿函数重载参数列表后面加const

在设计类的时候，一个原则就是对于不改变数据成员的成员函数都要在后面加 const，而对于改变数据成员的成员函数不能加 const。所以 const 关键字对成员函数的行为作了更加明确的限定：有 const 修饰的成员函数（指 const 放在函数参数表的后面，而不是在函数前面或者参数表内），只能读取数据成员，不能改变数据成员；没有 const 修饰的成员函数，对数据成员则是可读可写的。

在类的成员函数后面加 const 还有什么好处呢？那就是常量（即 const）对象可以调用 const 成员函数，而不能调用非const修饰的函数。正如非const类型的数据可以给const类型的变量赋值一样，反之则不成立。

详细解释：

https://blog.csdn.net/whyglinux/article/details/602329

3.9 map/multimap容器

3.9.1 map基本概念

简介：

• map中所有元素都是pair
• pair中第一个元素为key键值，起到索引作用，第二个元素为value（实值）
• 所有元素都会根据元素的键值自动排序

类似于python中的字典

本质：

• map/multimap属于关联式容器，底层用的是二叉树数据结构实现

优点：

• 可以根据key快速找到value

map/multimap的区别：

• map不允许容器中有重复的key值
• multimap中允许容器中有重复的key值

3.9.2 map构造和赋值

功能描述：

• 对map容器进行构造和赋值操作

函数原型：

构造：

• map<T1, T2> mp;
• map<T1,T2>mp(const map &m);

赋值

• map& operator=(const map & mp); // 重载等号操作符

3.9.3大小和交换

• empty();
• swap();

3.9.4 插入和删除

功能描述：

map容器进行插入数据和删除数据

函数原型：

• insert(elem); // 在容器中插入元素 插入有四种方式
• clear(); // 清楚所有元素
• erase(pos); // 删除pos迭代器所指的元素，返回下一个元素的迭代器
• erase(beg, end); // 删除区间内的所有元素，返回下一个元素的迭代器
• erase(key); // 删除容器中键为key的元素

3.9.5 map查找和统计

功能描述：

• 对map容器进行查找数据以及统计数据

函数原型：

• find(key); // 查找key是否存在，若存在，返回该键元素的迭代器， 若不存在，返回set.end()
• count(key); // 统计key的元素个数

3.9.6 map容器排序

map容器默认排序规则按照key值进行，从小到大排序，找我如何改变排序规则， 这也就是说如果键值是自定义数据类型，必须使用更改排序规则

主要技术点：

利用仿函数，可以改变排序规则

#include<iostream>
#include<string>
#include<map>	
using namespace std;

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

	string m_name;
	int m_age;
};

class myCompare {
public:
	bool operator()(const Person& p1, const Person& p2)const {
		return p1.m_age > p2.m_age;
	}
};

void test() {
	Person p1("liubei", 35);
	Person p2("caocao", 38);
	Person p3("sunquan", 25);

	map<Person, int, myCompare> m;
	m.insert(pair<Person, int>(p1, 1));
	m.insert(pair<Person, int>(p2, 1));
	m.insert(pair<Person, int>(p3, 1));

	for (map<Person, int>::iterator it = m.begin(); it != m.end(); it++) {
		cout << it->first.m_name << "  " << it->first.m_age <<"  "<<it->second<<endl;
	}
}

int main() {
	test();
	system("pause");
	return 0;
}

注意：

• 利用仿函数可以指定map容器的排序规则
• 对于自定义数据类型，map必须要指定排序规则，同set容器

3.10案例-员工分组

案例描述：

• 公司招聘10名员工(ABCDEFGHIJK), 10名员工进入公司之后，需要指派员工在那个部门工作
• 员工信息有：姓名 工资组成；部门分为策划， 美术， 研发
• 随机给10名员工分配部门和工资
• 通过multimap进行信息的插入，key部门编号， value员工
• 分部门显示员工信息

实现步骤：

1. 创建10名员工，放到vector中
2. 遍历vector容器，取出每个员工，进行随机分组
3. 分组后，将员工部门编号作为key，具体员工为value， 放入到multimap容器中
4. 分部门显示员工信息

#include<iostream>
#include<string>
#include<vector>	
#include<map>
using namespace std;


class Worker {
public:

	string m_name;
	int salary;
};

void createWorker(vector<Worker> &v) {
	string nameSeed = "ABCDEFGHIJK";
	for (int i = 0; i < 10; i++) {
		Worker worker;
		worker.m_name = "员工";
		worker.m_name += nameSeed[i];
		worker.salary = rand() % 10000 + 10000;
		v.push_back(worker);
	}
}

void setGroup(vector<Worker>& v, multimap<int, Worker>& mp) {
	for (vector<Worker>::iterator it = v.begin(); it != v.end(); it++) {
		int deptId = rand() % 3;
		mp.insert(pair<int, Worker>(deptId, *it));
	}
}


void showWorker(multimap<int, Worker>& mp) {
	// 策划部门
	cout << "策划部门" << endl;
	multimap<int, Worker>::iterator pos = mp.find(0);
	int sum = mp.count(0);
	for (int index = 0; index < sum; index++, pos++) {
		cout << pos->second.m_name << "  " << pos->second.salary << endl;
	} 
	cout << "-------------------------------" << endl;
	cout << "美术部门" << endl;
	pos = mp.find(1);
	sum = mp.count(1);
	for (int index = 0; index < sum; index++, pos++) {
		cout << pos->second.m_name << "  " << pos->second.salary << endl;
	}
	cout << "-------------------------------" << endl;
	cout << "研发部门" << endl;
	pos = mp.find(2);
	sum = mp.count(2);
	for (int index = 0; index < sum; index++, pos++) {
		cout << pos->second.m_name << "  " << pos->second.salary << endl;
	}
}

void test() {
	// 创建员工4.3
	vector<Worker> v;
	createWorker(v);

	// 员工分组
	multimap<int, Worker> mp;
	setGroup(v, mp);

	// 分组显示
	showWorker(mp);

}

int main() {
	test();
	system("pause");
	return 0;
}

标签：容器,常用,const,string,STL,pos,int,end
From： https://www.cnblogs.com/fuxingming/p/16750742.html