C++STL入门
发布时间：2023-09-21 14:30
目录
0、queue队列和priority_queue优先队列
queue
priority_queue
1、stack栈
2、vector向量（动态数组）
迭代器
3、set集合
4、map映射
5、string类
0、queue队列和priority_queue优先队列
queue
队列的示意图
特点：
1.先进先出（FIFO,First In First Out）
2.队头删除元素
3.队尾加入元素
基本用法：
1.创建队列对象：queue<元素类型> 队列名;
2.队列添加元素：队列名.push(元素名);
3.去掉队首元素：队列名.pop();
4.访问队首元素：队列名.front();
5.访问队尾元素：队列名.back();
6.判断是否为空：队列名.empty();
7.返回队列大小：队列名.size();
练习
int a, b , c, d;
queue q;
q.push(1);
q.pop();
q.push(2);
q.push(3);
q.push(4);
q.pop;
a = q.front();
b = q.back();
c = q.size();
d = q.empty;
cout << a << " " << b << " " << c << " " << d << endl;
//输出结果：2 3 2 0 priority_queue
priority_queue的内部本质是用堆来实现，但它有队列的特点，可以理解为queue。
每加入一个元素都会按照优先级自动排列，例如int类型默认从队首到队尾降序排列。
特点：
1.队尾加入元素
2.队头删除元素
3.每次取出的是具有最高优先权的元素（不一定先进先出，而是根据特定顺序排序）
基本用法：（大致与queue类似）
1.创建队列对象：priority_queue<元素类型> 队列名;
2.队列添加元素：队列名.push(元素名);
3.去掉队首元素：队列名.pop();
4.判断是否为空：队列名.empty();
5.返回队列大小：队列名.size();
6.访问最优元素：队列名.top();
说明：
队列没有clear之类的函数，如果想要清空一个队列，需要循环调用pop()函数。
练习1.int类型默认优先级
priority_queue q;
int temp;
q.push(2);
q.push(8);
q.push(4);
while(!q.empty()){
temp = q.top();
q.pop();
cout << temp << endl;
}
//输出结果：8 4 2 练习2.自定义优先级
struct T{
int x, y, z;
bool operator < (const T &temp) const{//重载小于号
return z < temp.z;//按z从大到小作为优先级
}
}t;
int main(){
priority_queue q;
T a = {4, 4, 3}, b = {2, 2, 5}, c = {1, 5, 4};
q.push(a);
q.push(b);
q.push(c);
while(!q.empty()){
t = q.top();
q.pop();
cout << t.x << " " << t.y << " " << t.z << endl;
}
return 0;
}
/*输出结果：
2 2 5
1 5 4
4 4 3
*/ 1、stack栈
栈的示意图
特点：
1.先进后出（LIFO,Last In First Out）
2.从栈顶删除元素
3.在栈顶加入元素
基本用法：
1.创建栈对象：stack<元素类型> 栈名;
2.栈顶添加元素：栈名.push(元素名);
3.去掉栈顶元素：栈名.pop();
4.判断是否为空：栈名.empty();
5.返回栈大小：栈名.size();
6.访问栈顶元素：栈名.top();//要确保栈非空
说明：
栈和队列一样，没有clear之类的函数，如果想要清空一个栈，需要循环调用出栈函数。
练习1.
stack s;
s.push(1);
s.push(2);
s.push(3);
s,pop();
cout << s.top() << endl;
s.top() += 3;
cout << s.top() << endl;
/*输出结果：
2
5
*/ 练习2.
stack s;
s.push(1);
s.push(1);
s.push(1);
cout << s.size() << endl;
while(!s.empty()) s.pop();
cout << s.size() << endl;
/*输出结果：
3
0
*/ 应用：HDU 1022 Train Problem I
Problem - 1022
https://acm.hdu.edu.cn/showproblem.php?pid=1022
2、vector向量（动态数组）
特点：
使用顺序结构实现的模板类，具有顺序表的特点
可以看作一个不定长的数组
1.向量的定义：vector
2.向量的初始化：
vector
vector
vector
基本用法：
1.取向量首元素的迭代器：向量名.begin();//迭代器理解为指针或地址之后介绍
2.取向量尾元素下一地址：向量名.end();
3.取向量首元素的值：向量名.front();
4.取向量尾元素的值：向量名.back();
5.以下标形式访问：int value_0 = 向量名[0];//类似于普通数组
6.往尾部添加一个元素：向量名.push_back(value);//建立数组的最基本操作
7.删除尾部第一个元素：向量名.pop_back();
8.判断向量是否为空：向量名.empty();
9.求向量元素个数：向量名.size();//实际元素个数，而不是容量
10.向量的容量：向量名.capacity();//在不分配更多内存的情况下，容器可以保存的最多元素个数
11.翻转向量：reverse(a.begin(), a.end());
12.清空向量：向量名.clear();
经典应用：邻接表储存图
struct edge{
int from, to, value;
}
const int maxn = 1e5 + 5;
vector Map[maxn];//一维向量相当于二维数组
//相对于普通二维数组储存图更节省空间 迭代器
迭代器类似于指针，可以使用*it访问相应元素。
迭代器：遍历容器中的数据的对象。对储存于容器中的数据进行处理时，迭代器能按预先定义的顺序从一个成员移向另一个成员。
也就是说，通过迭代器可以在不了解容器内部原理的情况下遍历容器。
总之，迭代器的作用就是提供一个遍历容器内部所有元素的接口，内部有一个与容器相关联的指针，然后重载各种运算操作来实现元素的遍历。
3、set集合
特点：
1.set是一个有序的容器，自动排序
2.它的内部也是用堆来实现的，所有操作时间复杂度都是logn级别，效率高
3.可以将它想象为一个树
基本用法：
1.set的声明：set
2.set的清空：s.clear();
3.插入一个元素x：s.insert(x);
//集合中没有的元素插入并自动排序，集合中已有的元素不能插入
4.查询是否有元素x：int ans = s.count(x);//返回0或1
5.查找x并返回迭代器：set
6.判断是否为空集：bool isempty = s.empty();
7.求集合元素个数：int n = s.size();
8.删除元素x：s.erase(x);
9.主要应用：自动去重并升序排序
10.set只能通过迭代器访问
定义在set类中的方法
练习1.去重且升序排列
set s;
s.insert(2);
s.insert(3);
s.insert(1);
s.insert(1);
//注意：与vector不同，set是不支持it < s.end()写法的，set是树状结构，地址不是线性保存的
//正确写法：it !=s.end(); (end()返回的是尾元素的下一个地址)
for(set::iterator it = s.begin(); it != s.end(); it++)
cout<< *it << " ";
//输出结果：1 2 3 练习2.降序排列
set> s;
set>::iterator it;//迭代器类型的定义一定要与集合定义一样
s.insert(2);
s.insert(3);
s.insert(1);
s.insert(1);
for(it = s.begin(); it != s.end(); it++)
cout << *it << " ";
//输出结果：3 2 1 4、map映射
map与set很像，但是不同的是它提供一对一的关系，map中的元素pair（键值对）是
pair p;//定义空的pair对象p
pair p(v1, v2);//定义了包含初始值v1和v2的pair对象p
//p.first和p.second来访问pair队象中的每一个成员的值
map是一个键值对(key/value)容器，对于迭代器来说，可以修改value，而不能修改key。
map会根据key自动排序。
map类型通常可以可理解为关联数组：可以用键作为下标来获取一个值。
关联的本质在于：元素的值与某个特定的键相关联，而并非通过元素在数组中的位置来获取。
基本用法：
1.定义一个空map：mag
2.返回m中键值等于k的元素的个数(1或0)：m.count(k);
3.存在则返回指向该元素的迭代器，否则返回结束地址end()：m.find(k);
4.删除m中键为k的元素，返回删除元素的个数(1或0)：m.erase(k);
5.从m中删除迭代器p所指向的元素：m.erase(p);
6.e是一个用在m上的value_type类型的值（一个pair）：m.insert(e);
//如多键e.first不在m中，则插入一个值为e.second的新元素；如果该键在m中经存在则不进行操作
7.清空map：m.clear();
8.判断是否为空：m.empty();
练习1.
map mapStudent;
mapStudent[1] = "one";
mapStudent[2] = "two";
mapStudent[3] = "three";
map::iterator it;
for(it = mapStudent.begin(); it != mapStudent.end(); it++)
cout << it->first << " " << it->second << endl;
/*输出结果：
1 one
2 two
3 three
*/ 练习2.
map mapStudent;
mapStudent["one"] = 1;
mapStudent["two"] = 2;
mapStudent["three"] = 3;
map::iterator it;
for(it = mapStudent.begin(); it != mapStudent.end(); it++)
cout << it->first << " " << it->second << endl;
/*输出结果：
one 1
three 3
two 2
*/ 5、string类
基本用法：
1.string对象的声明：
string s;
string s = "abc";2.求string对象的长度：
string s = "abc";
s.length();//结果为3
s.size();//结果为33.string对象的连接：可以使用+和+=运算符对string对象执行字符串的连接操作
4.string对象的比较：可以用<、<=、==、!=运算符比较string对象
5.求string对象的字串：
substr成员函数可以用于求子串(n, m);
调用时，如果省略m或m超过了字符串的长度，则求出来的子串就是从下标n开始一直到字符串结束的部分。
string s1 = "this is ok";
string s2 = s1.substr(2, 4);//s2 = "is i"
s2 = s1.substr(2);//s2 = "is is ok"6.插入字符串
insert成员函数可以在string对象中插入另一个字符串，返回值为对象自身的引用。
string s1("Limitless"), s2("00");
s1.insert(2, "123");//s1 = "Li123mitless"
s1.insert(3, s2);//s1 = "Li10023mitless"
s1.insert(3, 5, "X");//s1 = "Li1XXXXX0023mitless"7.删除子串：
erase成员函数可以删除string对象中的子串，返回值为对象自身的引用。
string s1("Real Steel");
s1.erase(1, 3);//s1 = "R Steel"
s1.erase(5);//s1 = "R Ste"8.交换两个string对象的内容
swap成员函数可以交换两个string对象的内容。
string s1("West"), s2("East");
s1.swap(s2);
//s1 = "East", s2 = "West"9.字符串的查找操作：
string str = "The apple thinks apple is delicious";//长度34
string key = "apple";
int pos1 = str.find(key);//4
int pos2 = str.find(key, 10);//17
//s.find(str) 查找字符串str在当前字符串s中第一次出现的位置
//s.find(str， pos) 查找字符串str在当前字符串s的[pos, end]中第一次出现的位置10.用STL算法操作string对象：
string s("afgcbed");
sort(s.begin(), s.end());
cout << s << endl;
next_permutation(s.begin(), s.end());
cout << s << endl;
reverse(s.begin(), s.end());
cout << s << endl;
/*输出结果：
abcdefg
abcdegf
fgedcba
*/