【C++】蓝桥杯必备——算法竞赛常用STL总结 [1w字]

传送门⏬⏬⏬[方便查表]

一、什么是STL？二、为什么STL重要？

✨1、原因✨2、STL的作用 三、STL知识点总结

✨0.使用说明书✨1、vector 【不定长数组】

①头文件：②初始化：③size()④a.resize( )⑤empty()⑥front()和 back()⑦倍增的思想⑧clear()⑨支持比较运算⑩push_back()和pop_back();⑪begin()和end()⑫遍历vector的三种方法⑬结合算法erase() reverse() ✨2、pair 【套娃模拟器】

①头文件②初始化③first() 和second()④嵌套（套娃）⑤实战题 ✨3、string

①头文件②初始化③ substr()④ c_str()⑤push_back() 和 insert()⑥empty()⑦size() length()⑧clear() ✨4、queue【队列】 和priority_queue 【优先队列、堆】

①头文件②初始化③共同函数④区别⑤清空 ✨5、stack 【栈】

①头文件②初始化③size()④push()⑤top()⑥pop() ✨6、deque【双向队列】

①头文件②初始化③常用函数 ✨7、set 【集合】和 multiset

①头文件②初始化③区别④常用函数⑤核心函数 ✨8、map 【映射】 /multimap

①头文件②初始化③常用函数④ 映射 [ ]⑤应用 ✨9、哈希表

①头文件②优势③缺点 ✨10、bitset 【压位】

①头文件②初始化③支持操作④常用函数 ✨待补充完善.... 四、文章参考五、结尾

---

前言：
你好啊，我最近在备战蓝桥杯，作为一名C语言选手刚入门C++ 确实有点小难，肝了五天的STL，不三连一下说不过去吧

---

一、什么是STL？

STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。

二、为什么STL重要？ ✨1、原因

C语言是一门很有用的语言，但在算法竞赛中却不流行，原因在于它太底层，缺少一 些“实用的东西”。例如，在2013年ACM/ICPC世界总决赛中，有1347份用C＋＋提交，323份 用Java提交，但一份用C提交的都没有。虽然C语言的主要内容，已经足以应付许多算法竞赛的题目了。然而，“能 写”并不代表“好写”，有些题目虽然可以用C语言写出来，但是用C＋＋写起来往往会更快， 而且更不容易出错。例如cin和cout，但是运行时间缺不如C语言，using namespace std语句，万能头文件，数组大小可以使用const声明的常数,以及黑科技STL…

✨2、STL的作用

STL的作用:加快书写速度，例如 sort使用 unique函数 这些可即以简化书写，而且运行速度和二分这些算法运行速度差不多。你可以用它来操作几乎任何数据集合，包括链表，容器和数组.vector容器简直就是数组加强版， string，deque,太多了 不多bb往下看 …

三、STL知识点总结 ✨0.使用说明书

首先先收藏这篇文章，STL确实有点多，第一次可以看代码自己敲一遍，然后今后用到忘记了查就行，主要还是要多用，用多了自然就会了，STL中六大组件：容器、迭代器、算法、仿函数
、迭代适配器、空间配制器。本文章主要涉及前三个，另外会有一些使用小技巧，和实战习题。

✨1、vector 【不定长数组】

你说它是数组吧，是，但又不完全是，还比数组好用

①头文件：

#include

②初始化：

这个初始化比较详细，后面一些容器用法类似

#include
#include
using namespace std;
int main () {
	//几种初始化的方法
    vector a;//定义一个vector  未初始化 输出》 0
    
    vector a(3);//定义一个长度为3的vector  未初始化 输出》0 0 0
    
    vector a(10, 3); //定义一个长度为10，且每个数赋值为3
    
	//将向量b中从下标0 1 2（共三个）的元素赋值给a，a的类型为int型
	vectora(b.begin(),b.begin+3);

	//从数组中获得初值
	int b[7]={1,2,3,4,5,6,7};
	vector a(b,b+7）;
	
    for(auto x : a) {//遍历输出 
        cout << x << " ";
    }
    return 0;
}

③size()

a.size( )//返回元素个数

④a.resize( )

a.resize( )//改变大小

⑤empty()

a.empty();
//判断a是否为空，空则返回true，非空则返回false

⑥front()和 back()

a.front();
//返回a的第1个元素,当且仅当a存在
a.back(); 
//返回vector的最后一个数

⑦倍增的思想

[C++]系统为某一程序分配空间的所需时间，与空间大小无关，与申请次数有关如申请一个空间为1000 和 空间为1 申请1000次的所需时间差别是很大的，申请次数越多，越耗时间

⑧clear()

a.clear();
//清空a中的元素

⑨支持比较运算

比较操作==，！=，<，<，<=，>，>=

int main () {
    //支持比较运算
    vector a(4, 3), b(3, 4);
    //a: 3 3 3 3   b:4 4 4 
    //比较原理字典序 (根据最前面那个判断，如果一样就往后比较)
    if (a < b) {
        puts("a < b"); 
    } 
    return 0;
}

⑩push_back()和pop_back();

a.pop_back();
//删除a向量的最后一个元素
a.push_back(5);
//在a的最后一个向量后插入一个元素，其值为5

⑪begin()和end()

a.begin();// vector的第0个数
a.end();// vector的最后一个的数的后面一个数
//通常与for循环结合使用

⑫遍历vector的三种方法

int main () {
    vector a;
    for (int i = 0; i < 10; i ++) {
        a.push_back(i);
    }
    //三种遍历vector的方法
    for (int i = 0; i < a.size(); i ++) {
        cout << a[i] << ' ';
    }
    cout << endl;

    for (auto i = a.begin(); i != a.end(); i ++) {
        cout << *i << ' ';
    }
    cout << endl;

    //C++11的新语法
    for (auto x : a) {
        cout << x << ' ';
    }
    cout << endl;  
    return 0;
}

⑬结合算法erase() reverse()

#include

a.erase(p)//从a中删除迭代器p指定的元素，p必须指向c中的一个真实元素，不能是最后一个元素end()
a.erase(b,e)//从a中删除迭代器对b和e所表示的范围中的元素，返回e

vector a={1,2,3,4,5};
reverse(a.begin(),a.end());//a的值为5，4，3，2，1  倒置

✨2、pair 【套娃模拟器】

可以理解为（x,y）数学中的坐标表示
小技巧：使用typedef定义 typedef pair PII

①头文件

#include(#include

②初始化

pair中只有两个元素，first和second。

//俩种方法初始化
pair p("hello",1);
p = make_pair("hello",1);

③first() 和second()

p.first(); //第一个元素
p.second(); //第二个元素

④嵌套（套娃）

vector< vector > >//与vector结合【再写个vector结合即可】

//套娃操作 用pair存储3个数据
 pair> p(1,{2,3});

⑤实战题

可以做下这道题离散化 AcWing 802

✨3、string

支持比较操作符>,>=,<,<=,==,!=

①头文件

#include 

②初始化

string a = "ac";

③ substr()

#include 
#include
using namespace std;

int main () {
    string a = "ac";
    a += "w";//支持比较操作符>,>=,<,<=,==,!=
    cout << a << endl; //输出子串a :acw

    a += "ing";  
    cout << a << endl;
    //以字符串数组理解
    cout << a.substr(0, 3) << endl; //当第一个数是0 则后一位数:输出从头开始的长度为3的子串
    cout << a.substr(0, 3) << endl; //当第一个数是1 则输出下标为1 到下标为3的子串  
    cout << a.substr(0, 9) << endl;//如果超出长度范围 则输出原子串
    cout << a.substr(1) << endl; //从下标为1开始输出
    cout << a.substr(0) << endl; //原子串
    printf("%sn", a.c_str());//如果用printf输出  

    return 0;
}  

④ c_str()

// 返回这个string对应的字符数组的头指针
string s = "Hello World!";
printf("%s", s.c_str()); //输出 "Hello World!"

⑤push_back() 和 insert()

// 尾插一个字符
    a.push_back('a');
// insert(pos,char):在制定的位置pos前插入字符char
    a.insert(a.begin(),'1');

⑥empty()

判断a是否为空，空则返回true，非空则返回false

⑦size() length()

都是 返回字母个数

string s = "cpt";
 cout << a.size()<< endl; //输出3
printf("%s", a.length()); //输出 3

⑧clear()

把字符串清空

可以发现string 和vector这些还是有很多共同的函数的

✨4、queue【队列】 和priority_queue 【优先队列、堆】

队列是一种数据结构 原理：先进先出，元素从一端入队，从另一端出队，就像是排队。
优先队列和队列特性不同：按优先级排序 和 获取
参考文章

①头文件

#include < queue >//都在这个头文件

②初始化

//queue <类型> 变量名  
//priority_queue <类型> 变量名;
queue  q; //定义一个名为q队列
priority_queue  q; //默认是大根堆
//定义小根堆
小根堆：priority_queue <类型,vecotr <类型>,greater <类型>> 变量名

③共同函数

q.size();// 这个队列的长度
q.empty();//用于判断这个队列是否为空，空则返回true，非空则返回false
q.push(); //往队尾插入一个元素
q.pop(); //队列：把队头弹出  优先队列 ：弹出堆顶元素

④区别

队列：

q.front();// 返回队头元素
q.back(); //返回队尾元素

优先队列：

 q.top();// 返回堆顶元素

⑤清空

注意：队列和堆没有clear函数
所以清空的方法就是重新初始化

q = queue  ();

✨5、stack 【栈】 ①头文件

include

②初始化

//stack<类型> 名字;
stack s;

③size()

返回这个栈的长度

④push()

向栈顶插入一个元素

⑤top()

返回栈顶元素

⑥pop()

弹出栈顶元素

✨6、deque【双向队列】

好用，几乎其他容器的都有，就是慢一点

①头文件

#include 

②初始化

deque dq;//定义一个int类型的双向队列

③常用函数

        dq.size(); //返回这个双端队列的长度
        dq.empty(); //返回这个队列是否为空，空则返回true，非空则返回false
        dq.clear(); //清空这个双端队列
        dq.front(); //返回第一个元素
        dq.back(); //返回最后一个元素
        dq.push_back(); //向最后插入一个元素
        dq.pop_back(); //弹出最后一个元素
        dq.push_front(); //向队首插入一个元素
        dq.pop_front();//弹出第一个元素
        dq.begin(); //双端队列的第0个数
        dq.end(); //双端队列的最后一个的数的后面一个数

✨7、set 【集合】和 multiset

集合与映射也是两个常用的容器,set类似于数学上的集合

①头文件

include

②初始化

set s;//string 集合

③区别

set不允许元素重复，如果有重复就会被忽略，但multiset允许.

④常用函数

            size();// 返回元素个数
            empty(); //返回set是否是空的
            clear(); //清空
            begin(); //第0个数，支持++或--，返回前驱和后继
            end(); //最后一个的数的后面一个数，支持++或--，返回前驱和后继
            insert(); //插入一个数
            find(); //查找一个数
            count(); //返回某一个数的个数
            erase(x); //删除所以x  时间复杂度 O(k + logn)
             erase(s.begin(),s.end());//删除一个迭代器

⑤核心函数

 		lower_bound(x); //返回大于等于x的最小的数的迭代器  核心操作
        upper_bound(x); //返回大于x的最小的数的迭代器  不存在返回end()

✨8、map 【映射】 /multimap

map就是从键（key）到值（value）的映射。因为重载了[ ]运算符，map像是数组的“高 级版”。例如可以用一个mapmonth_name来表示“月份名字到月份编号”的映射， 然后用month_name["July"]=7这样的方式来赋值

①头文件

include 

②初始化

这个初始化有点不同 还是小技巧搭配typedef简化

map m = { "A", 10 };

③常用函数

	insert(); //插入一个数，插入的数是一个pair
    erase(); 
        //（1）输入是pair
        //（2）输入一个迭代器，删除这个迭代器
    find(); //查找一个数
    lower_bound(x); //返回大于等于x的最小的数的迭代器
    upper_bound(x); //返回大于x的最小的数的迭代器

④ 映射 [ ]

时间复杂度 O(logn)

#include 
#include 
#include

⑤应用

#include 
#include 
#include