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

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

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++STL部分，这样能够省下来不少的时间；这篇笔记是看B站上黑马程序员的课程的时候记得：

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

1．STL初识 1.1 STL基本概念

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. 空间配置器：负责空间的配置与管理

1.3 STL中容器、算法、迭代器 1.3.1 容器

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

1.3.2 算法

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

1.3.3 迭代器

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

  常用迭代器种类有：双向迭代器、随机访问迭代器 1.4容器算法迭代器初识

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

1.4.1 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;//降序排列
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5720618.html