C++ STL学习(一)——容器

琐记1．STL初识

1.1 STL基本概念1.2 STL六大组件1.3 STL中容器、算法、迭代器

1.3.1 容器1.3.2 算法1.3.3 迭代器 1.4容器算法迭代器初识

1.4.1 vector存放内置数据类型1.4.2 vector存放自定义数据类型1.4.3 vector容器嵌套容器 2. STL常用容器

2.1 string容器

2.1.1 string基本概念2.1.2 string构造函数2.1.3 string赋值操作2.1.4 string字符串拼接2.1.5 string查找与替换2.1.6 string字符串的比较2.1.7 string字符存取2.1.8 string插入和删除2.1.8 string子串获取 2.2 vector容器

2.2.1 vector基本概念2.2.2 vector构造函数2.2.3 vector赋值操作2.2.4 vector容量和大小2.2.5 vector插入和删除2.2.6 vector容器数据存取2.2.6 vector互换容器2.2.6 vector预留空间 2.3 deque容器

2.3.1 deque容器基本概念2.3.2 deque构造函数与迭代器2.3.3 deque赋值操作2.3.4 deque大小操作2.3.5 deque插入和删除2.3.6 deque数据存取2.3.7 deque排序 2.4 stack容器

2.4.1 stack基本概念2.4.2 stack常用接口 2.5 queque容器

2.5.1 queque基本概念2.5.2 queque常用接口2.5.3 queque示例 2.6 list

2.6.1 list基本概念2.6.2 list构造函数3.7.3 list赋值和交换3.7.4 list大小操作2.7.5 list插入和删除2.7.6 list 数据存取2.7.7 list 反转和排序2.7.8 list 排序案例 2.8 set/multiset容器

2.8.1 set基本概念2.8.2 set构造和赋值2.8.3 set容器大小和交换2.8.4 set容器插入和删除2.8.5 set查找和统计2.8.6 set和multiset区别2.8.7 pair对组的创建2.8.8 set容器排序 2.9 map/multimap容器

(1) map基本概念(2) map常用函数

黑马程序员匠心之作|C++教程从0到1入门编程,学习编程不再难

STL(Standard Template Library,标准模板库)STL从广义上分为：①容器(container） ②算法（algorithm) ③迭代器(iterator）容器和算法之间通过迭代器连接STL几乎所有的代码都采用了模板类或者模板函数 1.2 STL六大组件

 STL大体分为六种：容器、算法、迭代器、仿函数、适配器(配接器)、空间配置器。

  1. 容器：各种数据结构，如vector、list、deque、set、map等，用来存放数据
  2. 算法：各种常用的算法，如sort、find、copy等
  3. 迭代器：容器和算法之间连接器
  4. 仿函数：行为类似函数，作为算法的某种策略
  5. 适配器：用来修饰容器或者仿函数或迭代器接口
  6. 空间配置器：负责空间的配置与管理

 容器：放置数据
 STL容器就是运用最广泛的一些数据结构实现
 常用的数据结构：数组、链表、树、队列、集合、映射表
 这些容器分为序列式容器和关联式容器两种：
  序列式容器：强调值的顺序，每个元素都有固定的位置
  关联式容器：二叉树结构，没有严格上的物理上的顺序关系

 算法：有限的步骤解决逻辑/数学问题
 算法分为：质变算法，非质变算法
 质变：会更改元素内容的算法、删除拷贝
 非质变：运算不会改变元素内容，计数 查找

 迭代器：算法要通过迭代器才能访问容器中的数据
 每个容器都有自己的迭代器
 用法类似于指针

 在了解STL容器算法迭代器概念后，利用代码来加深理解
 下面用最常用的容器：Vector，可以理解为数组来演示

 容器：vector
 算法：for_each
 迭代器：vector< int>::iterator

#include
#include
#include
using namespace std;

void myPrint(int val){
	printf("%dn",val);
}
void test01(){
	vector v;//创建vector容器对象，通过模板参数指定容器中存放的数据类型 
	
	v.push_back(10); //放入数据 
	v.push_back(20);
	v.push_back(30);
	
	
	vector::iterator itBegin = v.begin();	//itBegin指向第一个元素 
	vector::iterator itEnd = v.end();		//itEnd指向最后一个元素的下一位 
	while(itBegin != itEnd){
		cout<<*itBegin<::iterator it = v.begin();it!=v.end();it++){
		cout<<*it< 
1.4.2 vector存放自定义数据类型 
(*it)到最后是什么类型，可以直接看迭代器尖括号里面的东西即可
就像下面的
函数1，(*it)是Person类型
函数2，(*it)是Person * 类型
 
#include
#include
#include
#include
using namespace std;

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

void test01(){
	vector v;
	
	Person p1("zhao",1);
	Person p2("qina",2);
	Person p3("swun",3);
	
	//存放数据 
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	
	//遍历数据 
	for(vector::iterator it=v.begin();it!=v.end();it++){
		cout<<(*it).name<<" "<<(*it).age< v;
	
	Person p1("zhao",1);
	Person p2("qina",2);
	Person p3("swun",3);
	
	//存放数据 
	v.push_back(&p1);
	v.push_back(&p2);
	v.push_back(&p3);
	
	//遍历数据 
	/ 
	for(vector::iterator it=v.begin();it!=v.end();it++){
		cout<<(*it)->name<<" "<<(*it)->age< 
1.4.3 vector容器嵌套容器 
 学习目标：容器中嵌套容器，将所有数据遍历输出
  例：
 
#include
#include
using namespace std;

//容器嵌套容器 
void test01(){
	vector< vector >v;	

	vector v1;
	vector v2;
	vector v3;

	for(int i = 0;i<3;i++){
		v1.push_back(i);
		v2.push_back(i+1);
		v3.push_back(i+2);		
	}
	
	//将小容器插入到大容器中 
	v.push_back(v1); 
	v.push_back(v2); 
	v.push_back(v3); 
	
	//通过大容器，将数据遍历
	for(vector >::iterator it=v.begin();it!=v.end();it++){
		//(*it) ----------容器 vector 
		for(vector::iterator vit=(*it).begin();vit != (*it).end();vit++){
			cout<< *vit <<" "; 
		}
		cout< 
 
 
 
 
 
2. STL常用容器 
2.1 string容器 
2.1.1 string基本概念 
本质：
 
 - string是C++风格的字符串，而string本质上是一个类
 
  string和char *的区别：   
 - char *是一个指针
 - string是一个类，类内部封装了char*，是char*型的容器
 
特点：
 
 - string类内部封装了许多成员方法（例如：find,copy,delete）
 - string管理char*所分配的空间，不用担心下标越界
 
2.1.2 string构造函数 
构造函数原型：
 
 - string();				//创建空的字符串
 - string(const char* s);	//使用字符串s初始化
 - string(const string& str);//使用字符串对象来初始化另一个string对象
 - string(int n,char c);	//使用n个字符c初始化
 
#include
#include
using namespace std;

//string初始化 
void test01(){
	string str1;
	string str2("字符串2");
	string str3(str2);
	string str4(6,'a');

	cout << str1 << endl; 
	cout << str2 << endl;
	cout << str3 << endl;
	cout << str4 << endl;
}
int main(){
	test01();
	return 0;
}
 
2.1.3 string赋值操作 
功能描述：
 
 - 给string字符串赋值(= 或者assign)
 
赋值操作原型函数
 
赋值操作一共有两种：一种是直接用等号=，原型如下
 - string& operator=(const char* s);//char* 类型字符串，赋值给当前字符串
 - string& operator=(const string &s);//把字符串赋值给当前的字符串
 - string& operator=(char c);//字符赋值给当前的字符串

另一种是assign()
 - string& assign(const char *s); //把字符串s赋给当前的字符串
 - string& assign(const char *s, int n); //把字符串s的前n个字符赋给当前的字符串
 - string& assign(const string &s); //把字符串s赋给当前字符串
 - string& assign(int n, char c); //用n个字符c赋给当前字符
 
#include
using namespace std;

//string初始化 
void test01(){
	string str1;
	string str2;
	string str3;
	string str4;
	string str5;
	string str6;
	string str7;
	
	
	str1 = "hello world"; 
	str2 = str1;
	str3 = "a";
	
	str4.assign("helloworld");
	str5.assign("string5",3);
	str6.assign(str1);
	str7.assign(5,'a');
	
	cout< 
总结：
  string赋值方式很多，但是用 operator= 号是较为实用的方法
 
2.1.4 string字符串拼接 
功能描述：
 
 - 实现在字符串的末尾拼接字符串
 
函数原型：
 
 - 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, int n); //把字符串s的前n个字符连接到当前字符串结尾
 - string& append(const string &s); //同operator+=(const string& str)
 - string& append(const string &s, int pos, int n);//字符串s中从pos开始的n个字符连接到字符串结尾
 
	string str1 = "I";
	string str2 = "you,li ming";
	string str3 = "Life";
	
	str1 += "love";	//追加字符串
	str1 += " ";	//追加单个字符
	str1 += str2;	//拼接字符串对象
	cout< 
总结:
 
如果使用append(const string &s, int pos, int n)函数，
应当弄明白字符的位置是从0开始的
 
2.1.5 string查找与替换 
功能描述：
 
查找：查找指定字符串是否存在
替换：在指定的位置替换字符串
 
函数原型：
 
 - int find(const string &str,int pos=0) const; 	从pos位置开始查找str第一次出现的位置
 - int find(const char *s,int pos=0) const;			从pos位置开始查找s第一次出现位置
 - int find(const char *s,int pos=0,int n) const; 	从pos位置查找s的前n个字符第一次位置
 - int find(const char c,int pos=0)  const; 		从pos位置查找字符c的第一次出现位置
 - int rfind(const string &str,int pos=npos) const; 从pos开始查找str最后一次位置，
 - int rfind(const char *s,int pos=npos) const; 	从pos开始查找s最后一次出现位置，
 - int rfind(const char *s,int pos,int n) const; 	从pos查找s的前n个字符最后一次位置
 - int rfind(const char c,int pos=0) const;			查找字符c最后一次出现位置
 - string &replace(int pos,int n,const string &str);替换从pos开始的n个字符为str
 - string &replace(int pos,int n,const char *s);	替换从pos开始的n个字符为字符串s

rfind和find的区别：find默认从左往右查找，而rfind则代表从右往左查；
find找到字符串后返回查找到的字符串的第一个字符的下标，找不到则返回-1；
replace替换时要指定从哪儿个位置开始起，其后有多少个字符，替换成什么样的字符串。
 
  tips:C++在函数声明时，后面跟个const是限定函数类型为常成员函数, 常成员函数是指不能改变成员变量值的函数。例如“double d() const;”，其中的其中的“const”限定了d()函数中不能有任何改变其所属对象成员变量值的功能，如果有则会在编译阶段就报错。它的主要作用就是能使成员函数的意义更加清楚，我们可在不改变对象的成员函数的函数原型中加上const说明。在需要增加可读性和减少逻辑出错的情况下，就可以用这种形式。
 
void test01(){
	string str1 = "zainashandenaoyouyiqunljl";
	int pos = str1.find("i");
	if (pos == -1)
		cout << "未找到" << endl;
	else
		cout << pos << endl;
	pos = str1.rfind("i");
	cout< 
2.1.6 string字符串的比较 
比较方式：
 
比较字符的ASCII码值
	= return 0
	> return 1
	< return -1
 
函数原型：
 
在string类内部有这两个操作：
int compare(const string &s) const; //与string对象字符串s比较
int compare(const char *s) const; //与字符串s比较
 
string str1 = "hello!";
string str2 = "hillo!";
if (str1.compare(str2) == 0){
	cout << "str1和str2相同！" << endl;
}else if(str1.compare(str2) ==-1){
	cout << "str1小于str2！" << endl;
}else
	cout<<"str1大于str2"< 
总结：
 
一般用来比较字符串是否相等
 
2.1.7 string字符存取 
string中单个字符存取的方式有两种
 
在string类内部有这两个操作：
    char& operator[](int n); //通过[]方式取字符
    char& at(int n); //通过string类内部at方法获取字符
 
string str = "hello world";
cout< 
2.1.8 string插入和删除 
函数原型：
 
在string类内部有这两个操作：
	string& insert(int pos, const char* s);//通过指向字符常量区域的指针对调用该成员函数的对象来插入字符
	string &insert(int pos,const string &str); //通过string类型的对象插入字符
	string &insert(int pos,int n,char c); //在指定位置插入n个字符c
	string &erase(int pos,int n=npos); //删除从pos开始的n个字符 
 
str.insert(1,"ag")
 
总结
 
	通常情况下直接str.insert(1,"ag")就行；
 
2.1.8 string子串获取 
函数原型：
 
string substr(int pos = 0;int n=npos) const;
 
void test02(){
	string str;
	cin >> str;
	string userName = str.substr(0,str.find("@"));
	cout< 
 
 
 

 下面是第二种容器：vector
 
 
2.2 vector容器 
2.2.1 vector基本概念 
功能：
   vector数据结构和数组非常相似，也称为单端数组
 vector与普通数组区别：
   不同之处在于数组是静态空间，而vector可以动态扩展
 动态扩展：
   ①并不是在原空间之后续接新空间，而是找更大的内存空间，然后将原数据拷贝新空间，释放原空间。
   ②vector容器的迭代器是支持随机访问的迭代器
 
2.2.2 vector构造函数 
函数原型：
 
vector v; //采用模板实现类实现，默认构造函数
vector(v.begin(), v.end()); //将v[begin(), end()]区间中的元素拷贝给本身
vector(n, elem); //构造函数将n个elem拷贝给本身
vector(const vector &vec); //拷贝构造函数
 
vectorv1;  					 // 1.默认构造
vector v2(v1.begin(), v1.end());//2.区间方式进行构造
vector v3(10, 100);			 //3.n个elem方式构造
vector v4(v3);					 //拷贝构造
 
2.2.3 vector赋值操作 
函数原型：
 
vector &operator = (const vector &vec); //重载等号操作符
assign(begin,end);//将[ begin, end ]区间的数据拷贝赋值给本身
assign(n,elem); //将n个elem拷贝赋值给本身 
 
示例：
 
vectorv1 = v;
vectorv2;
v2.assign(v.begin(),v.end());
vector v3;
v3.assgin(12,1001);
 
2.2.4 vector容量和大小 
函数原型：
 
empty(); //判断容器是否为空
capacity(); //容器的容量
size(); //返回容器中元素的个数
resize(int num); //重新指定容器的长度为num，若容器变长，则以默认值0填充新位置。
​ 				 //如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。
​ 					   //如果容器变短，则末尾超出容器长度的元素被删除

总结：
 - 判断是否为空--- empty()
 - 返回元素个数--- size()
 - 返回容量个数--- capacity()
 - 重新指定大小--- resize()
 
示例：
 
#include
#include
using namespace std;

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

void test02(){
	vectorv;
	for(int i=0;i<10;i++){
		v.push_back(i);
	}
	cout< 
2.2.5 vector插入和删除 
函数原型：
 
push_back(ele) //尾部插入元素
pop_back() 	   //删除尾部元素
insert(const_iterator pos,ele) //迭代器指向位置pos插入ele
insert(const_iterator pos,int count,ele) //迭代器指向pos插入count个元素ele
erase(const_iterator start,const_iterator end) //删除迭代器从start到end之间的元素
clear() //删除容器中所有元素
 
 总结： 插入有尾部插入、通过迭代器插入某个元素、通过迭代器插入区间的元素； 删除有尾部删除，通过迭代器删除某个元素、通过迭代器删除区间的元素； 清空元素。 
示例：
 
v.push_back(12);
v.pop_back();
v.insert(v.begin(),100);
v.insert(v.begin(),2,1000);
v.erase(v.begin());
v.erase(v.begin(),v.begin()++);
v.clear();
 
2.2.6 vector容器数据存取 
函数原型：
 
at(int idx); //返回索引idx所指的数据
operator[]; //返回索引idx所指的数据
front(); //返回容器中第一个数据元素
back();　//返回容器中最后一个数据元素
 
示例：
 
for(int i = 0;i < v.size();i++){
	cout << v[i] << endl;
	cout << v.at(i) < 
2.2.6 vector互换容器 
函数原型：
 
swap(vec): //将vec与本身的元素互换
 
示例：
 
v1.swap(v2);
 
妙用：
 
有一说一，这个里面的那个利用匿名对象来收缩空间的方法胎牛皮了!!!!!!
#include
#include
using namespace std;
 
void printvector(vector &v)
{
	for(vector::iterator it=v.begin();it!=v.end();it++)
		cout<<*it<<" ";
	cout< v1;
	for(int i=0;i<10;i++)
		v1.push_back(i);
	printvector(v1);
 
	vector v2;
	for(int i=9;i>=0;i--)
		v2.push_back(i);
	printvector(v2);
	
	cout<<"交换之后的两个容器："< v;
	for(int i=0;i<10000;i++)
		v.push_back(i); 
	cout<<"v的容量为："<(v).swap(v); //vector(v): 匿名对象 
	cout<<"v的容量为："< 
2.2.6 vector预留空间 
功能描述：
 
减少vector在动态扩展容量时的扩展次数
 
函数原型：
 
reserve(int len);　　
容器预留len个元素长度，预留位置不初始化，元素不可访问
 
示例：
 
v.reserve(100000);
 
 
 
 
 
 

 下面是deque
   
 
2.3 deque容器 
2.3.1 deque容器基本概念 
 
 
特性：
 
 
 
  
双端数组，可以对头端进行插入删除操作
 deque容器的迭代器也是支持随机访问的
 使用的时候需要包含头文件：#include
 
 
 
 
与vector区别：
 
 
vector对于头部的插入删除效率低，数据量越大，效率越低
deque相对而言，对头部的插入删除速度回比vector快
vector访问元素时的速度会比deque快,这和两者内部实现有关
 
 
deque内部工作原理:
 
 
deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实数据
中控器维护的是每个缓冲区的地址，使得使用deque时像一片连续的内存空间
 
 
 
 
 
  
  
 
2.3.2 deque构造函数与迭代器 
函数原型：
 
deque deqT;            默认构造形式
deque(beg,end);           构造函数将[beg,end)区间中元素拷贝给本身
deque(n,elem);            构造函数将n个elem拷贝给本身
deque(const deque &deq);  拷贝构造函数
 
示例1：
 
dequedl;
for(int i=0;i<10;i++)
	dl.push_back(i);
dequed2(dl.begin(),dl.end());
dequed3(10,100);
dequed4=d3;
 
迭代器：
 
 
 
当仅仅是为了遍历，而不需修改时候，应当加上const关键字
 const类型的容器需要const_iterator 迭代器才不会报错
 
 
示例2：
 
void printDeque(const deque&d){
	for(deque::const_iterator it = d.begin();it!=d.end();it++){
		cout<<*it< 
 
 
2.3.3 deque赋值操作 
函数原型：
 
deque& operator=(const deque &deq);      重载等号操作符
assign(beg,end);                         将[beg,end)区间中的数据拷贝赋值给本身
assign(n,elem);                          将n个elem拷贝赋值给本身
 
示例：
 
dequed2;
d2=dl;

//assign赋值
dequed3;
d3.assign(dl.begin(),dl.end());

dequed4;
d4.assign(10,100);
 
2.3.4 deque大小操作 
需要注意的点：
 
deque容器是没有容量这个概念的,
所以不像vector中有capacity函数
 
函数原型：
 
deque.empty();            判断容器是否为空
deque.size();             返回容器中元素的个数
deque.resize(num);        重新指定容器的长度为num，若容器变长，则默认值填充新位置，
                          若容器变短，则末尾值超出容器长度的元素被删除
deque.resize(num,elem);   重新指定容器的长度为num,若容器边长，则以elem值填充新位置，
                          如果容器变短，则末尾超出容器长度的元素被删除
 
总结：
 
判断是否为空 --- empty
返回元素个数 --- size
重新指定个数 --- resize
 
2.3.5 deque插入和删除 
函数原型：
 
 两端插入操作： 
 push_back(elem);             在容器尾部添加一个数据
 push_front(elem);            在容器头部插入一个数据
 pop_back();                  删除容器最后一个数据
 pop_front();                 删除容器第一个数据
 
指定位置操作：
insert(pos,elem);             在pos位置插入一个elem元素的拷贝，返回新数据的位置
insert(pos,n,elem);           在pos位置插入n个elem数据，无返回值
insert(pos,beg,end);          在pos位置插入[beg,end）区间的数据，无返回值
clear();                      清空容器的所有数据
erase(beg,end);               删除[beg,end)区间的数据，返回下一个数据的位置
erase(pos);                   删除pos位置的数据，返回下一个数据的位置
 
示例：
 
d.push_back(10);
d.pop_front();
 
 
 
2.3.6 deque数据存取 
函数原型：
 
at(int idx);        返回索引idx所指的数据
operator[];         返回索引idx所指的数据
front();            返回容器中第一个数据
back();             返回容器中最后一个数据
 
示例：
 
for(i=0; i 
 
 
2.3.7 deque排序 
注意：
 
注意包含头文件；
sort算法默认升序;
对于支持随机访问的迭代器的容器，都可以利用sort算法直接对其进行排序;
 
算法：
 
sort(iterator beg, iterator end);
 
示例：
 
sort(d1.begin(), d1.end());
 
 
 
 
 
 

 下面是stack
   
 
2.4 stack容器 
2.4.1 stack基本概念 
 
 
 概念: stack是一种先进后出(first in first out)的数据结构,
   它只有一个出口;
  栈中只有栈顶的元素才能被访问到。
  stack不提供遍历功能，也不提供迭代器。
  入栈-push
  出栈-pop
 
 
 
2.4.2 stack常用接口 
函数原型：
 
stack构造函数
	stack stkT;//stack采用模板类实现， stack对象的默认构造形式：
	stack(const stack &stk);//拷贝构造函数

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

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

stack大小操作
	empty();//判断堆栈是否为空
	size();//返回堆栈的大小
 
示例：
 
s.top();//查看栈顶元素
s.pop();//出栈
 
 
 
 
 
 

 下面是queque
   
 
2.5 queque容器 
2.5.1 queque基本概念 
概念：
 
 
 
Queue是一种先进先出(First In First Out,FIFO)的数据结构，它有两个出口
 队列容器允许从一端新增元素，从另一端移除元素
 队列中只有队头 front()和队尾 back()才可以被外界使用，因此队列不允许有遍历行为
 队列中进数据称为 — 入队 push
 队列中出数据称为 — 出队 pop
 
 
 
2.5.2 queque常用接口 
构造函数：
queue que; //queue采用模板类实现，queue对象的默认构造形式
queue(const queue &que); //拷贝构造函数

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

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

大小操作：
empty(); //判断堆栈是否为空
size(); //返回栈的大小
 
总结：
 
 
 
入队：push
 出队：pop
 返回队头元素
 返回队尾元素：back
 判断队是否为空：empty
 返回队列大小：size
 
 
2.5.3 queque示例 
#include 
#include 
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	string m_Name;
	int m_Age;
};

void test01() {

	//创建队列
	queue q;

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

	//向队列中添加元素  入队操作
	q.push(p1);
	q.push(p2);
	q.push(p3);
	q.push(p4);

	//队列不提供迭代器，更不支持随机访问	
	while (!q.empty()) {
		//输出队头元素
		cout << "队头元素-- 姓名： " << q.front().m_Name 
              << " 年龄： "<< q.front().m_Age << endl;
        
		cout << "队尾元素-- 姓名： " << q.back().m_Name  
              << " 年龄： " << q.back().m_Age << endl;
        
		cout << endl;
		//弹出队头元素
		q.pop();
	}
	cout << "队列大小为：" << q.size() << endl;
}

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

 下面是list
   
 
2.6 list 
2.6.1 list基本概念 
 
 
优缺点:
 
 
 
  
优点:
  可以对任意位置快速插入或者删除元素;
 缺点:
  容器的遍历速度,没有数组快;
  占用空间比数组大;
 
 
 
 
STL中的链表
 
 
 
  
STL中的链表是一个双向循环链表,迭代器只支持前移和后移,属于双向迭代器
 
 
 
 
 
总结:在STL中list和vector属于两个被最常使用的容器,各有优缺点。
 
 
2.6.2 list构造函数 
函数原型
 
list lst; //list采用采用模板类实现,对象的默认构造形式;
list(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem); //构造函数将n个elem拷贝给本身。
list(const list &lst); //拷贝构造函数。
 
示例:
 
list l1; //默认构造
list l2(l1.begin(), l1.end()); //区间方式构造(也属于拷贝)
list l3(l2); //拷贝构造
list l4(10, 999); //10个999(也属于拷贝)
 
3.7.3 list赋值和交换 
函数原型：
 
 
 
assign(begin, end); //将[beg, end)区间中的数据拷贝赋值给本身.assign(n, elem);//将n个elem拷贝赋值给本身list& operator=(const list &lst); //重载等号操作符swap(lst); //将lst与本身的元素互换。 
 
例
 
listl1;
l2 = l1;
l3.assign(l2.begin(),l2.end());
l4.assign(10,100);
l4.swap(l3);
 
3.7.4 list大小操作 
函数原型
 
 
 
size(); //返回容器中元素的个数
 empty(); //判断容器是否为空
 resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
 resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
 
 
#include
#include
#include
#include
using namespace std;

class Person//容器中要存放的数据类型
{
public:
	Person() {}
	Person(string name, int age)
	{
		m_name = name;
		m_age = age;
	}

	string m_name;
	int m_age;
};


void PrintList(const list &l)//打印容器中的数据
{
	for (list::const_iterator it = l.begin(); it != l.end(); it++)
	{
		cout << it->m_name << " " << it->m_age << endl;//用*it访问也可以，用指针也可以
	}
	cout << endl;
}



void test01(){//list大小操作
	list l;

	string Name = "ABC";
	for (int i = 0; i < 3; i++){//往容器里边插入三个数据
		string name = "李";
		name += Name[i];
		Person p(name, i + 20);
		l.push_back(p);
	}

	if (!l.empty()){
		cout << "容器不为空,大小为："< 
2.7.5 list插入和删除 
函数原型：
 
* push_back(elem);			//在容器尾部加入一个元素
* pop_back();				//删除容器中最后一个元素
* push_front(elem);			//在容器开头插入一个元素
* pop_front();				//从容器开头移除第一个元素
* insert(pos,elem);			//在pos位置插elem元素的拷贝，返回新数据的位置。
* insert(pos,n,elem);		//在pos位置插入n个elem数据，无返回值。
* insert(pos,beg,end);		//在pos位置插入[beg,end)区间的数据，无返回值。
* clear();					//移除容器的所有数据
* erase(beg,end);			//删除[beg,end)区间的数据，返回下一个数据的位置。
* erase(pos);				//删除pos位置的数据，返回下一个数据的位置。
* remove(elem);				//删除容器中所有与elem值匹配的元素。
 
2.7.6 list 数据存取 
函数原型：
 
 
 
l.front();返回容器第一个元素
 l.back();返回容器最后一个元素
 注意：
 
 
 
  
不能用[]访问list容器中的元素
 不能用at()方式访问list容器的元素
 原因是：list本质链表，不适用连续线性空间存储数据，迭代器不支持随机访问（it = it+1错误），支持双向访问（it–）
 
 
 
 
l1.front();
l2.back();
 
2.7.7 list 反转和排序 
函数原型:
 
 
 
reverse();翻转链表
 sort()排序(成员函数, 默认升序, 可用仿函数来实现降序操作)
 
 
重要提示:
 
 
 
所有不支持随机访问迭代器的容器,不可以用标准算法
 不支持随机访问迭代器的容器,内部会提供一些算法
 list自带的排序算法默认是从小到大升序,如果要从大到小,利用回调函数或仿函数实现降序(此处为回调函数)
 
 
#include 
#include 
using namespace std;

template
void printList(const list& L)
{
	for (list::const_iterator it = L.begin(); it != L.end(); it++)
	{
		cout << *it << 't';
	}
	cout << endl;
}

bool myCompare(int v1, int v2)
{
	//降序 让 第一个数 > 第二个数
	return v1 > v2;
}

//排序
void test2()
{
	listL1;
	L1.push_back(20);
	L1.push_back(10);
	L1.push_back(50);
	L1.push_back(40);
	L1.push_back(30);

	cout << "排序前：" << endl;
	printList(L1);

	L1.sort();  //默认升序
	cout << "排序后：" << endl;
	printList(L1);

	L1.sort(myCompare);
	printList(L1);
}

int main()
{
	test2();
}

 
2.7.8 list 排序案例 
#include
#include
#include
#include
using namespace std;


class Person{
public:
	Person(string name,int age,int height){
		this->m_Name = name; 
		this->m_Age = age;
		this->m_Hight = height;
	}
	
	string printInfo()
    {
        stringstream temp;
        temp << "姓名：" << this->m_Name << "t年龄：" << this->m_Age << "t身高：" << this->m_Hight;
        return temp.str();
    }
	
	string m_Name;
	int m_Age;
	int m_Hight;
	
}; 
//指定排序规则
bool comparePerson(Person &p1, Person &p2){
	if(p1.m_Age == p2.m_Age){
		return p1.m_Hight < p2.m_Hight;
	}
	return p1.m_Age < p2.m_Age;
} 

void test01(){
	listL;
	
	Person p1("刘备", 35, 175);
    Person p2("曹操", 45, 180);
    Person p3("孙权", 40, 170);
    Person p4("赵云", 25, 190);
    Person p5("张飞", 35, 160);
    Person p6("关羽", 35, 200);
    
    L.push_back(p1);
    L.push_back(p2);
    L.push_back(p3);
    L.push_back(p4);
    L.push_back(p5);
    L.push_back(p6);
    
    for(list::iterator it = L.begin();it != L.end();it++){
		cout<< it->printInfo()<::iterator it = L.begin();it != L.end();it++){
		cout<< it->printInfo()< 
 
 
 对于自定义数据类型,必须指定排序规则,否则不知道如何进行排序
  高级排序只是在排序规则上再进行一次逻辑规则的指定,并不复杂
 
 
2.8 set/multiset容器 
2.8.1 set基本概念 
 
 
 简介:所有元素都会在插入的时候自动排序
  本质:set/multiset属于关联式容器,底层结构是用二叉树实现.
  区别:set中不允许有重复的元素, multiset中允许有重复的元素
 
 
 
2.8.2 set构造和赋值 
 
 
构造函数:
 set< T> st; //默认构造函数：
 set(const set &st); //拷贝构造函数
 
 
赋值:
 set& operator=(const set &st); //重载等号操作符
 插入数据:
 insert();
 
 
set s2(s1);
set s3;
s3 = s2;
 
2.8.3 set容器大小和交换 
 
 
函数原型:
 size(); //返回容器中元素的数目
 empty(); //判断容器是否为空
 swap(st); //交换两个集合容器
 
 
2.8.4 set容器插入和删除 
 
 
函数原型: 
 insert(elem); //在容器中插入元素。
 clear(); //清除所有元素
 erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。
 erase(beg, end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
 erase(elem); //删除容器中值为elem的元素。
 
 
s1.erase(s1.begin());
s1.erase(30);
 
2.8.5 set查找和统计 
 
 
函数原型: 
 find(key); //查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
 count(key); //统计key的元素个数,对于set来说只有0或1; 对于multiset能够大于1;
 
 
set::iterator pos = s1.find(12);
if(pos != s1.end())
	cout << "找到元素" << endl;
else
	cout << "未找到元素" << endl;
 
2.8.6 set和multiset区别 
区别:
 
 
 
 set不可以插入重复数据，而multiset可以
  set插入数据的同时会返回插入结果，表示插入是否成功
  multiset不会检测数据，因此可以插入重复数据
 
 
2.8.7 pair对组的创建 
功能简介:
 
 
 
成对出现的数据，利用对组可以返回两个数据,其中第一个数据是first,第二个数据是second;
 
 
函数原型:
 
 
 
 pair p ( value1, value2 );
 pair p = make_pair( value1, value2 );
 
 
示例: 
 
 //test func of pair
void test4() {
    pair p(string("tom"), 20);
    cout << "name： " << p.first << " " << " age: " << p.second << endl;

    pair p2 = make_pair("jerry", 10);
    cout << "name： " << p2.first << " " <<  " age: " << p2.second << endl;
}
 
2.8.8 set容器排序 
 
 
 set容器默认排序规则是从小到大,利用仿函数可以改变排序规则
  不能在放入数据之后才指定排序方式, 应当在创建的时候指定排序方式
 
 
示例:创建了一个MyCompare类，重载函数调用运算符，并且在创建set容器时用类名作为第二个参数。
 
class myCompare{
public:
	bool operator()(int v1, int v2){
		return v1 > v2;
	}
};

sets1;
下面插入的时候就会按照从大到小排列
 
 
   
    
  
  
 
2.9 map/multimap容器 
C++STL之map容器:发现的一篇挺好的文章
 
(1) map基本概念 
 
 
简介:
 
 
 
  
 map中的所有元素都是pair
  pair中第一个元素为key(键值)起到索引作用,第二个元素为value(值)
  所有的元素都会根据元素的键值自动排序
 
 
 
 
本质:
 
 
 
  
 map/multimap属于关联式容器,底层结构是用二叉树实现
 
 
 
 
优点:
 
 
 
  
可以根据key值快速找到value值
 
 
 
 
map和multi的区别:
 
 
 
  
map不允许容器中有重复key值元素
 multimap允许容器中有重复key值得元素
 
 
 
 
其他
 
 
 
  
对于自定义数据类型, map必须指定排序规则,和set容器相同;
 
 
 
 
(2) map常用函数 
构造函数
 
map mp;		//map默认构造函数: 
map(const map &mp);	//拷贝构造函数
 
赋值和交换
 
map& operator=(const map &mp);//重载等号操作符
swap(mp);			//交换两个集合容器
 
map大小操作
 
size();//返回容器中元素的数目
empty();//判断容器是否为空
 
map插入操作
 
 
 
为什么不建议用第四种方式?
  假如用第四种方式查找一个不存在的key,会自动新建一个键值对,值为零;因此用此种方式输出的时候应当确定此键值对已经存在了
 
 
map.insert(...); 
	//往容器插入元素，返回pair
 
//1 map的四种插入方法
void MapInsert(map &m) {
	//1 通过模板pair对组.返回一个对组对象.其中：对组对象的模板参1为:被插入容器的(此处为map)迭代器类型;模板参2为:布尔类型,用于判断是否插入成功.
	std::pair::iterator,bool> pairIt = m.insert(std::pair(1,1));
	if(pairIt.second == false){
		std::cout << "1 insert map failed" << std::endl;
		return;
	}

	//2 通过make_pair()函数.同样返回一个对组对象
	pairIt = m.insert(std::make_pair(2, 2));
	if (pairIt.second == false) {
		std::cout << "2 insert map failed" << std::endl;
		return;
	}

	//3 通过map模板类中的value_type()函数.同样返回一个对组对象
	pairIt = m.insert(map::value_type(3, 3));
	if (pairIt.second == false) {
		std::cout << "3 insert map failed" << std::endl;
		return;
	}

	//4 下标法插入.注:map中,key不存在,以默认值0插入map;key存在,修改该key的值.
	m[4] = 4;
	m[5];//默认为0.
	std::cout << m[6] << std::endl;//下标打印时不存在的key会默认被初始化为0.且会被插入到map中

	//所以此时map中共有6个元素
}
 
删除
 
clear();//删除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg,end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(keyElem);//删除容器中key为keyElem的对组。
 
查找统计
 
find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；
		  //若不存在，返回map.end();
count(keyElem);
		 返回容器中key为keyElem的对组个数。
		 对map来说，要么是0，要么是1。
		 对multimap来说，值可能大于1。
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
 
排序
 
 
 
map容器默认是升序排列, 利用仿函数来改变map容器的排序方式
 
 
class myCompare{
public:
	bool operator()(int v1, int v2){
			//降序:
			return v1 > v2;
			//升序
			//return v1 < v2;
	}
};
mapm;//降序排列