C++模板库（STL）

C++模板库（STL）

哈哈哈，今天新创立的账号，我深受安然影响，终于要开始更新博文了，也许我会写的很好吧，我相信自己，今天要更新的内容是我从一本名为《算法笔记》的书中摘取总结的，这本书还是挺有意思的，这本书相对于紫书来说，内容要易懂一些，我跟你说，这是我在准备算法编程竞赛中学习的，这肯定不是STL的全部，安然告诉我，这个知识解析，很适合编程竞赛了

目录

vector容器

1、vector概念及常见用法

vector定义

2、vector容器中的访问

2.1通过下标进行访问

2.2通过迭代器访问

3、vector的常用函数

3.1、push_back

3.2、pop_back

3.3、size()

3.4、clear

3.5、insert

3.6、erase

4、vector的构造函数

4.1、 vector v(n,elem)将n个元素拷贝给本身

4.2、 将v1中的v[begin(),end()]中的元素拷贝给本身

4.3、//拷贝构造函数,直接将v1中的元素拷贝到v4中

5、vector的容量和大小

6、vector数据存取

6.1、利用v.at()访问数据

6.2、front、back访问容器中元素

7、vector互换容器

string容器

1、string的定义

2、string的访问

2.1通过下标访问

2.2通过迭代器访问

3、string常用函数

3.1、operator+=

3.2、compare operator

3.3、length()和size()

3.4、insert()

3.5、erase和clear

3.6、substr()

3.7、find()和string::npos

3.8、replace

set容器/multiset容器

1、set的定义

2、set容器内元素的访问

3、set的常用函数

3.1、insert()

3.2、find(value)

3.3、erase

3.4、size()

3.5、clear（）

map容器

1、map的定义

2、map容器内元素的访问

3、map的常用函数

queue和priority_queue容器

1、queue的定义

2、queue容器内元素的访问

3、queue的常用函数

3.1、push

3.2、front、back

3.3、pop

3.4、empty

3.5、size

priority_queue介绍

stack容器

1.stack的定义

2.stack容器内元素的访问

3.stack常用函数实例解析

3.1push

3.2、top

3.3、pop

3.4、empty

3.5size

algorithm

1、algorithm头文件下的常用函数

1.1、max()、min()和abs()

1.2、swap()

1.3、reverse()

1.4、next_permutation()

1.5、fill()

6.sort()

---

vector容器 1、vector概念及常见用法

vector翻译为向量，可以看做"变长数组"，更容易理解,即“长度根据需要自动改变的数组”，可以动态扩展。

动态扩展：并不是在原空间之后续接新空间，而是找更大的内存空间，将原数据拷贝到新空间，释放原空间

使用vector，需要添加vector的头文件，即#include.

vector定义

vector定义：vectorname;

和一维数组一样，这里的可以是任意基本类型，例如int,double,char、结构体等，也可以是STL标准容器，，例如vector,set,queue等。

在这里如果是一个STL容器的话，定义的时候要记得在>>符号之间加上空格。

下面分别是两种定义方式：

vector;//int可以替换为double,char,node等基本类型。

vector>v1;//>>之间要记得加空格

2、vector容器中的访问 2.1通过下标进行访问

和普通的数组一样，对一个定义为vector vi的vector容器来说，可以直接访问vi[0]-vi[size-1]中的任何一个元素。

当然，不能访问这个范围外的其他元素。

2.2通过迭代器访问

2.2.1、通过下标和指针访问数组的方式访问

 #include`
 using namespace std;
 #include`
 ​
 int main()
 {
     vectorv;
 for (int i = 0; i < 10; i++)
 {
     v.push_back(i);
 }
 vector::iterator it = v.begin();
 for (int i = 0; i < 10; i++)
 {
     cout << *(it + i)<<" ";
 }
 cout << endl;
 ​
     system("pause");
     return 0;
 ​
 }

输出结果：

0 1 2 3 4 5 6 7 8 9

//解释一下，这里的v.begin()是v的首元素地址，而it是指向这个地址后面还会经常用到v.end(),这里一并介绍了，end()取得是v的尾元素地址的下一个地址。end（）是迭代器末尾标志。

2.2.2、通过找到迭代器末尾的方式访问

 #include
 using namespace std;
 #include
 ​
 int main()
 {
     vectorv;
     for (int i = 0; i < 10; i++)
     {
         v.push_back(i);
     }
     //vector的迭代器不支持it::iterator it = v.begin(); it != v.end(); it++)
     {
         cout << *it << " ";
 ​
     }
     cout << endl;
     system("pause");
     return 0;
 }

输出结果：

0 1 2 3 4 5 6 7 8 9

3、vector的常用函数 3.1、push_back

有学过数据结构的读者可能会知道，pushback顾名思义就是尾插，在vector的后面插入一个元素，时间复杂度为O（1）。

 #include
 using namespace std;
 #include
 ​
 int main()
 {
     vectorv;
     for (int i = 1; i <=10; i++)
     {
         v.push_back(i);//vector元素尾插
     }
     for (int i = 0; i < v.size(); i++)
     {
         cout << v[i]<<" ";
     }
     cout << endl;
     
     system("pause");
     return 0;
 }

输出结果：

1 2 3 4 5 6 7 8 9 10

3.2、pop_back

有插入就会有删除，pop_back用来删除vector中的尾元素，时间复杂度O（1）。

 #include
 using namespace std;
 #include
 ​
 int main()
 {
     vectorv;
     for (int i = 1; i <=10; i++)
     {
         v.push_back(i);//尾插
     }
     v.pop_back();//删除10
     v.pop_back();//删除9
     for (int i = 0; i < v.size(); i++)
     {
         cout << v[i]<<" ";
     }
     cout << endl;
     
     system("pause");
     return 0;
 }

输出结果：

1 2 3 4 5 6 7 8

3.3、size()

用来获的vectorz中的元素个数，时间复杂度为O（1）。一般来说，size（）返回unsigned类型，不过用%d不会有大问题。

 #include
 using namespace std;
 #include
 ​
 int main()
 {
     vectorv;
     for (int i = 1; i <=10; i++)
     {
         v.push_back(i);
     }
 ​
     cout << "vector中的元素个数为：" << v.size() << endl;
     
     system("pause");
     return 0;
 ​
 }

输出结果：

vector中的元素个数为：10

3.4、clear

clear用来清空vector中的所有元素。

 #include
 using namespace std;
 #include
 ​
 int main()
 {
     vectorv;
     for (int i = 1; i <=10; i++)
     {
         v.push_back(i);
     }
     v.clear();
     cout << "vector中的元素个数为：" << v.size() << endl;
     
     system("pause");
     return 0;
 ​
 }

输出结果：

vector中的元素个数为：0

3.5、insert

insert(it,x)用来向vector中任意迭代器it处插入一个元素x，时间复杂度为O(N)。

#include
 using namespace std;
 #include
 int main()
 {
     vectorv;
     for (int i = 1; i <= 10; i++)
     {
         v.push_back(i);
     }
     for (int i = 0; i  
输出结果：
 
1 2 3 4 5 6 7 8 9 10 
 
1 2 3 1000 4 5 6 7 8 9 10
 
3.6、erase 
 
 
erase有两种用法：（一）删除单个元素（二）删除一个区间内的元素
 
 
(一)erase（it）
 
 #include
 using namespace std;
 #include
 int main()
 {
     vectorv;
     for (int i = 1; i <= 10; i++)
     {
         v.push_back(i);
     }
     for (int i = 0; i < v.size(); i++)
     {
         cout << v[i] << " ";
     }
     cout << endl;
     v.erase(v.begin() + 5);//删除的是  6 v.begin从数组0号位置开始
     for (int i = 0; i < v.size(); i++)
     {
         cout << v[i] << " ";
     }
 ​
     cout << endl;
     system("pause");
     return 0;
 }
 
输出结果：
 
1 2 3 4 5 6 7 8 9 10 
 
1 2 3 4 5 7 8 9 10
 
(二)erase(first,last)
 
 
 
erase（first，last）就是删除[first,last）中的所有元素
 
 
 #include
 using namespace std;
 #include
 int main()
 {
     vectorv;
     for (int i = 1; i <= 10; i++)
     {
         v.push_back(i);
     }
     for (int i = 0; i < v.size(); i++)
     {
         cout << v[i] << " ";
     }
     cout << endl;
     v.erase(v.begin() +2 ,v.begin()+7);//清除一整行元素最方便的方法还是v.clear
     for (int i = 0; i < v.size(); i++)
     {
         cout << v[i] << " ";
     }
     cout << endl;
     system("pause");
     return 0;
 }
 
输出结果：
 
1 2 3 4 5 6 7 8 9 10
 
1 2 8 9 10
 
4、vector的构造函数 
 
 4.1、 vector v(n,elem)将n个元素拷贝给本身 
 4.2、 将v1中的v[begin(),end()]中的元素拷贝给本身 
 4.3、//拷贝构造函数,直接将v1中的元素拷贝到v4中 
 
 
 
#include
 using namespace std;
 #include
 void print(vector&v)
 {
     for (vector::iterator it = v.begin(); it != v.end(); it++)//通过迭代器来访问元素
     {
         cout << *it << " ";
     }
     cout << endl;
 }
 int main()
 {
     vectorv1;//无参构造
     for (int i = 1; i <=10; i++)
     {
         v1.push_back(i);
     }
     print(v1);
     //vector v(n,elem)将n个元素拷贝给本身
     vector v2(5, 100);
     print(v2);
     //将v1中的v[begin(),end()]中的元素拷贝给本身
     vectorv3(v1.begin() + 3, v1.begin() + 7);
     print(v3);
     //拷贝构造函数
     //直接将v1中的元素拷贝到v4中
     vectorv4(v1);
     print(v4);
     system("pause");
     return 0;
 ​
 }
 
输出结果：
 
1 2 3 4 5 6 7 8 9 10 
 
100 100 100 100 100 4 5 6 7 
 
1 2 3 4 5 6 7 8 9 10
 
 
 
另外，用assign给vector进行赋值也是一个很好的选择。
 
 
 
 
#include
 using namespace std;
 #include
 void print(vector&v)
 {
     for (vector::iterator it = v.begin(); it != v.end(); it++)
     {
         cout << *it << " ";
     }
     cout << endl;
 }
 ​
 ​
 int main()
 {
 ​
     vectorv1;//无参构造
     for (int i = 1; i <=10; i++)
     {
         v1.push_back(i);
     }
     print(v1);
 //用法同上，将v[begin(),end()]的元素拷贝给自身
     vectorv2;
     v2.assign(v1.begin(), v1.end());
     print(v2);
 //将n个elem拷贝给自身
     vectorv3;
     v3.assign(5,100);
     print(v3);
     system("pause");
     return 0;
 ​
 }
 
输出结果：
 
1 2 3 4 5 6 7 8 9 10
 
1 2 3 4 5 6 7 8 9 10 
 
100 100 100 100 100
 
5、vector的容量和大小 
 
 
1、判断是否为空-----empty
 
 
2、返回元素个数-----size
 
 
3、返回容器容量-----capacity
 
 
4、重新指定大小-----resize
 
 
 #include
 using namespace std;
 #include
 void print(vector&v)
 {
     for (vector::iterator it = v.begin(); it != v.end(); it++)
     {
         cout << *it << " ";
     }
     cout << endl;
 }
 int main()
 {
     vectorv1;
     for(int i = 1; i <= 10; i++)
     {
         v1.push_back(i);
     }
     if (v1.empty())
     {
         cout << "v1为空" << endl;
     }
     else
     {
         cout << "v1不为空" << endl;
         cout << "v1的容量=" << v1.capacity() << endl;
         cout << "v1的大小=" << v1.size() << endl;
     }
     //resize重新指定大小,若指定的更大，默认用0填充位置
     //若指定的更小，超出部分元素被删除
     v1.resize(15, 10);
     print(v1);
     v1.resize(5);
     print(v1);
     system("pause");
     return 0;
 ​
 }
 
输出结果：
 
v1不为空 v1的容量=13
 
v1的大小=10
 
1 2 3 4 5 6 7 8 9 
 
10 10 10 10 10 10 
 
1 2 3 4 5
 
6、vector数据存取 
 
 6.1、利用v.at()访问数据 
 
 
 
#include
 using namespace std;
 #include
 int main()
 {
     vectorv;
     for (int i = 1; i <= 10; i++)
     {
         v.push_back(i);
     }
     //利用v.at(i)访问数据
     for (int i = 0; i < v.size(); i++)
     {
         cout << v.at(i) << " ";
     }
     cout << endl;
     system("pause");
     return 0;
 ​
 }
 
输出结果：
 
1 2 3 4 5 6 7 8 9 10
 
 
 6.2、front、back访问容器中元素 
 
front返回容器中第一个元素
 
 
back返回容器中最后一个元素
 
 
#include
using namespace std;
#include
int main()
{
	vectorv;
	for (int i = 1; i <= 10; i++)
	{
		v.push_back(i);
	}
	//利用v.at(i)访问数据
	for (int i = 0; i < v.size(); i++)
	{
		cout << v.at(i) << " ";
	}
	cout << endl;
	cout << "容器中第一个元素是：" << v.front() << endl;

	cout << "容器中最后一个元素是：" << v.back() << endl;
	system("pause");
	return 0;

}
 
输出结果：
 
1 2 3 4 5 6 7 8 9 10 
 
容器中第一个元素是：1
 
容器中最后一个元素是：10
 
7、vector互换容器 
 
 
swap(vector)//将容器与本身的元素互换
 
 
 
 
#include
 using namespace std;
 #include
 void print(vector& v)
 {
     for (vector::iterator it = v.begin(); it != v.end(); it++)
     {
         cout << *it << " ";
     }
     cout << endl;
 }
 int main()
 {
     vectorv1;
     for (int i = 1; i <= 10; i++)
     {
         v1.push_back(i);
     }
     vectorv2;
     for (int i = 10; i > 0; i--)
     {
         v2.push_back(i);
     }
     cout << "互换前" << endl;
     print(v1);
     print(v2);
     cout << "互换后" << endl;
     v1.swap(v2);
     cout << "v1的值为" << endl;
     print(v1);
     cout << "v2的值为" << endl;
     print(v2);
 ​
     system("pause");
     return 0;
 ​
 }
 
输出结果：
 
互换前 1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1 
 
互换后 v1的值为 10 9 8 7 6 5 4 3 2 1 
 
v2的值为 1 2 3 4 5 6 7 8 9 10
 
string容器 
 
 
要使用string要加入string头文件，即#include
 
 
1、string的定义 
 
 
string str;
 
 
2、string的访问 
 
 2.1通过下标访问 
 
可以像字符数组一样访问string
 
 
 #include
 using namespace std;
 #include
 int main()
 {
     string str = "abcd";
     for (int i = 0; i < str.length(); i++)
     {
         cout<< str[i]<<" ";
     }
     cout << endl;
     system("pause");
     return 0;
 }
 
输出结果：
 
a b c d
 
 
 
还能够读入和输出整个字符串
 
 
 
 
#include
 using namespace std;
 #include
 int main()
 {
     string str;
     cout<<"输入的str为：";
     cin >> str;
     cout<<"输出的str为";
     cout << "str=" << str;
     cout << endl;
     system("pause");
     return 0;
 }
 
输出结果：
 
输入的str为：abcdefghi
 
输出的str为：str=abcdefghi
 
 
 
在C语言中，可以用c_str将string型str转换为字符数组进行输出
 
 
2.2通过迭代器访问 
 
 
string迭代器并不像vector等容器那样还要有参数，可以直接定义
 
 
string::iterator it
 
 
可以直接通过*it访问string中的每一位
 
 
 #include
 using namespace std;
 #include
 int main()
 {
     string str = "abcd";
     for (string::iterator it = str.begin(); it != str.end(); it++)
     {
         cout << *it <<“ ”;
     }
     cout << endl;
     system("pause");
     return 0;
 }
 
 
 
string和vector一样，都可以进行str.begin()+elem的 *** 作，例如，str.begin()+3.
 
 
3、string常用函数 
 
 3.1、operator+= 
 
可以直接将两个string拼接起来
 
 
 
 
#include
 using namespace std;
 #include
 int main()
 {
 ​
     string str1 = "abcd";
     string str2 = "efgh";
     str1 += str2;//直接将两个string拼接
     cout << "str1=" << str1;
 ​
 ​
     cout << endl;
     system("pause");
     return 0;
 }
 
输出结果：
 
str1=abcdefgh
 
 
 3.2、compare operator 
 
按照字典序的规则，两个string可以直接用==、!=、<、<=、>、>=比较大小
 
 
 
 #include
 using namespace std;
 #include
 int main()
 {
 ​
     string str1 = "abcd";
     string str2 = "efgh";
     string str3 = "abc";
     string str4 = "fghi";
     if (str1 < str2)
         cout << "str1= str2)
         cout << "str4>=str2" << endl;//如果str4>=str2,输出str4>=str2
 ​
     cout << endl;
     system("pause");
     return 0;
 }
 
输出结果：
 
str1 
str1!=str3 
 
str4>=str2
 
 
 3.3、length()和size() 
 
length和size基本相同，都是string长度
 
 
 #include
 using namespace std;
 #include
 int main()
 {
     string str1 = "abcd";
     string str2 = "efgh";
     str1 += str2;//直接将两个string拼接
     cout << "str1的长度为："<< str1.length()< 
输出结果：
 
str1的长度为：8 
 
str1的长度为：8
 
3.4、insert() 
insert有很多写法：
 
 
 
3.4.1、insert(pos,string)
 
 
在pos位置插入字符串
 
 
 
 
#include
 using namespace std;
 #include
 int main()
 {
     string str1 = "abcd";
     cout << "str1=" << str1 << endl;
     str1.insert(3, "love");//在3号位置插入love字符串
     cout << "str1=" << str1 << endl;
 ​
     system("pause");
     return 0;
 }
 
输出结果：
 
str1=abcd 
 
str1=abcloved
 
 
 
3.4.2、insert(it,it2,it3)
 
 
it为原字符要插入的位置，it2和it3为待插字符串的首尾迭代器，用来表示串[it2,it3)将被插在it的位置上
 
 
 
 
 
#include
 using namespace std;
 #include
 int main()
 {
     string str1 = "fall";
     string str2 = "in love";
     
     str1.insert(str1.begin() + 4, str2.begin(), str2.end());
     cout << "str1=" << str1 << endl;
 ​
     system("pause");
     return 0;
 }
 
输出结果：
 
str1=fallin love
 
3.5、erase和clear 
 
 
erase和clear都是删除元素，erase可以删除指定区间内的元素，clear则是全部清空
 
 
str.earse(it)//删除单个元素
 
 
str.earse(first,last)//删除指定区间元素
 
 
str.earse(pos,length)//删除某一个位置后length长度的元素
 
 
 
 
#include
 using namespace std;
 #include
 int main()
 {
     string str1 = "abcdefgh";
     str1.erase(str1.begin() + 3);//删除下标为3的元素
     cout << "str1=" << str1 << endl;
 ​
     string str2 = "abcdefgh";
     str2.erase(str2.begin(), str2.begin() + 3);//删除从0号位到3号位的字符
     cout << "str2=" << str2 << endl;
 ​
     string str3 = "abcdefgh";
     str3.erase(0, 3);//删除从0号位开始的3个字符
     cout << "str3=" << str3 << endl;
     
     string str4 = "abcdefg";
     str4.clear();
     cout << "str4的长度为：" << str4.size() << endl;
     system("pause");
     return 0;
 }
 
输出结果：
 
str1=abcefgh
 
str2=defgh 
 
str3=defgh
 
`str4的长度为：0
 
3.6、substr() 
 
 
substr(pos,length)返回从pos位置开始，长度为length的子串，时间复杂度为O（len），相信大家有前面的基础，这里应该很容易理解
 
 
3.7、find()和string::npos 
 
 
string::npos作为find函数失配时候的返回值，是一个unsigned_int类型，，等于-1或者4294967295
 
 
str1.find(str2)当str2是str1的子串的时候，返回str2在str1中第一次出现的位置，如果str2不是str1的子串，则返回string::npos
 
 
 #include
 using namespace std;
 #include
 int main()
 {
     string str1 = "Thank you for your smile";
     string str2 = "your";
     if (str1.find(str2) != string::npos)
     {
         cout << str1.find(str2) << endl;
     }
 ​
     system("pause");
     return 0;
 }
 
输出结果：
 
14
 
3.8、replace 
 
 
str1.replace(pos,length,str2) str1的pos号位开始、长度为length的子串替换为str2
 
 
str1.replace(it1,it2,str2) str1的迭代器[it1,it2)范围的子串替换为str2
 
 
set容器/multiset容器 
set容器是一个自动排序且不含重复元素的容器
 
set容器/multiset容器都属于关联式容器，底层结构是用二叉树实现
 
区别是set内不能有重复元素，multiset可以有重复元素
 
 
1、set的定义 
 
 
使用set的时候，需要添加set头文件，即#include
 
 
 
 
setname;
 
 
和vector一样，如果typename是一个容器，假的在定义的时候在>>符号之间加入空格
 
即set >st;//中间要加入空格
 
2、set容器内元素的访问 
set只能通过迭代器iterator访问
 
 
 
#include
 using namespace std;
 #include
 int main()
 {
     setst;
     st.insert(3);//insert(x)将x插入到set中
     st.insert(5);
     st.insert(2);
     st.insert(3);
     for (set::iterator it = st.begin(); it != st.end(); it++)
     {
         cout << *it << " ";
     }
     cout << endl;
     return 0;
 }
 
输出结果：
 
2 3 5
 
3、set的常用函数 
3.1、insert() 
 
 
将x插入到set容器中，并自动排序和去重，使用情况请看set容器内元素的访问
 
 
3.2、find(value) 
 
 
找到对应值为value的迭代器
 
 
 
 
#include
 using namespace std;
 #include
 int main()
 {
     setst;
     for (int i = 1; i <= 9; i++)
     {
         st.insert(i);
     }
     set::iterator it = st.find(4);
     cout << *(st.find(4)) << endl;//打印迭代器中4
     system("pause");
     return 0;
 }
 
3.3、erase 
erase有两种用法，
 
 
 
1、删除单个元素
 
 
2、删除一个区间内的所有元素
 
 
3.3.1、erase(it)
 
 
 
与vector的相似，不过多赘述
 
 
3.3.2、erase(first,last)
 
 
 
与vector的相似，不过多赘述
 
 
3.4、size() 
size()用来获得set内元素的个数
 
 #include
 using namespace std;
 #include
 int main()
 {
     setst;
     for (int i = 1; i <= 9; i++)
     {
         st.insert(i);
     }
     cout << "set容器内元素的个数:" << st.size() << endl;
 ​
 ​
     system("pause");
     return 0;
 }
 
输出结果：
 
set容器内元素的个数:9
 
3.5、clear（） 
 
 
清除set内的所有元素
 
 
map容器 
map可以将任何基本类型映射到任何基本类型，包括STL容器
 
使用map时，需要添加map的头文件，即#include
 
1、map的定义 
 
 
mapmp;
 
 
其中typename1是键key,typename2对应映射后的类型value值
 
如果是字符串到整型的映射，必须使用string而不能用char数组，因为char数组作为数组，是不能作为键值的
 
2、map容器内元素的访问 
2.1通过下标访问
 
 
 
map中键的值是唯一的
 
 
 #include
 using namespace std;
 #include