C++STL入门

目录

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 - 1022https://acm.hdu.edu.cn/showproblem.php?pid=1022

2、vector向量（动态数组）

特点：

使用顺序结构实现的模板类，具有顺序表的特点

可以看作一个不定长的数组

1.向量的定义：vector a;

2.向量的初始化：

vector a;//初始化size为0的vector。

vector a(10);//初始化size为10的vector，每个元素默认值为零。

vector a(10, 1);//初始化size为10的vector，每个元素默认值为1。

基本用法：

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 s;

2.set的清空：s.clear();

3.插入一个元素x：s.insert(x);

//集合中没有的元素插入并自动排序，集合中已有的元素不能插入

4.查询是否有元素x：int ans = s.count(x);//返回0或1

5.查找x并返回迭代器：set::iterator it = s.find(x);

6.判断是否为空集：bool isempty = s.empty();

7.求集合元素个数：int n = s.size();

8.删除元素x：s.erase(x); 

9.主要应用：自动去重并升序排序

10.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为内部类型，pair的首元素key被称为关键字，并且是唯一的，次元素value被称为关键字的值。

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 m;

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();//结果为3

3.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
*/