C++STL小记

动态数组vector

#include<vector>

构造：

二维数组：

vector<vector<int>> vct(100,vector<int>()); //100行 列数未定 vector<vector<int>> vct(22,vector<int>(33,-1)) //22行33列 初值-1

常用方法：

• push_back() pop_back()
• size() empty() clear()
• 改变长度 resize()

//原本数组1 2 3 q.resize(5);//1 2 3 0 0默认增加的值为0 q.resize(5,3);//1 2 3 3 3 q.resize(2);//1 2

注意事项：

.size()返回值为size_t，具体范围根据编译器改变——>注意小心size()溢出

栈stack

#include<stack>

常用方法：

• push() pop()
• top()
• size() empty()——无clear()

注意事项：

不可用下标访问 stk[i]

队列queue

#include<queue>

常用方法：

• push() pop()
• front() back()取队首 取队尾
• size() empty()——无clear()

注意事项：

不可用下标访问 que[i]

双端队列deque

#include<deque>

常用方法：

• push_front() pop_front() push_back() pop_back()
• 访问头/尾 front() back()
• size() empty()clear()
• 可以用[i]访问内部元素

二叉堆priority_queue

#include<priority_queue>

构造：

priority_queue<int> pque1; // 储存int的大顶堆 priority_queue<int, vector<int>, greater<int>> pque2; // 储存int的小顶堆

常用方法：

• push() pop()
• top()
• size() empty()——无clear()

注意事项：

不可用下标访问 que[i]

集合set

#include<set> #include<unordered_set>

set/multiset/unordered_set区别：

构造：

////set #include<set> set<int> st1; // 储存int的集合（从小到大） set<int, greater<int>> st2; // 储存int的集合（从大到小） ////multiset #include<set> multiset<int> mts1; // 储存int的集合（从小到大） multiset<int, greater<int>> mts2; // 储存int的集合（从大到小） ////unordered_set #include<unordered_set> unordered_set<int> ust1;//无序 只这一种构造方式

遍历：

for (auto &ele : st) cout << ele << endl;

常用方法：

• 插入元素insert() 删除元素erase()
• 查找元素find() 判断是否存在count()
• size() empty() clear()

注意事项：

不可用下标访问 que[i]

元素只读，不可用下标定位修改

映射map

#include<map> #include<unordered_set>

map/multimap/unordered_map区别：

构造：

////map #include <map> map<int, int> mp1; // int->int，按键从小到大 map<int, int, greater<int>> mp2; // int->int，按键从大到小 map<string, vector<int>> mp3; // string->vector mp1.insert({2, 1}); //赋值 mp1[2]=1; //赋值 ////multimap #include <map> multimap<int, int> mmp1; // int->int，按键从小到大 multimap<int, int, greater<int>> mmp2; // int->int，按键从大到小 multimap<string, vector<int>> mmp3; // string->vector mmp1.insert({2, 1}); //赋值 不能用mmp1[2]=1; ////unordered_map unordered_map<int, int> ump1; unordered_map<string, vector<int>> ump2;

遍历：.first .second

for (auto &pr : mp) cout << pr.first << ' ' << pr.second << endl;

常用方法：

• 插入元素insert() 删除元素erase()
• 查找元素find() 判断是否存在count()
• size() empty() clear()

注意事项：

map/unordered_map可用下标访问 mp[1]——如果有对应值输出 如果没有会帮你插入这个键值对（其中值默认为0）

map<char, int> mp; cout << mp.count('a') << endl; // 0 mp['a']; // 即使什么都没做，此时mp['a']=0已经插入了 cout << mp.count('a') << endl; // 1 cout << mp['a'] << endl; // 0

字符串string

#include<string>

构造：

string s1; // 构造字符串，为空 string s2 = "awa!"; // 构造字符串，并赋值awa! string s3(10, '6'); // 构造字符串，通过构造函数构造为6666666666

常用方法：

• 连接+ 尾接+=
• 取子串 substr(a,b)——a是起始值(0开始)，b是字串长度
• 查找字符串 find(“子串”)——返回子串的起始下标，如果不存在返回npos值

string s1="abcabcd"; cout << s1.substr(3,3); //abc cout << s1.find("bca"); //1 if (s1.find("bbb") != npos) cout << "YES"<< endl; //验证s1中不存在bbb子串

数值与字符串互转（C++11）

string s="123"; int x=stoi(s); cout<<x; //123

二元组pair

#include<utility>

和unordered_map区别：

pair只能存一对（first，second）,unordered_map可以存很多对

构造/方法：

pair<int,int> p1={1,2}; pair<char,int> p1={'a',1}; //取值 char x=p2.first; int y=p2.second; //判同 pair<int, int> p1 = {1, 2}; pair<int, int> p2 = {1, 3}; if (p1 == p2) { ... } // false

常用算法：

swap(a,b);//a b无论什么类型都可以

sort()

默认从小到大排序

vector<int> arr{1, 9, 1, 9, 8, 1, 0}; sort(arr.begin(), arr.end());//默认从小到大排序 arr = [0, 1, 1, 1, 8, 9, 9] sort(arr.begin(), arr.end(), greater<int>());// arr = [9, 9, 8, 1, 1, 1, 0]

特殊排序要手写比较器（返回值true/false）

//希望pair里面第二个数从小到大排序，如果第二个数相同则第一个数从大到小 bool cmp(pair<int, int> a, pair<int, int> b) { if (a.second != b.second) return a.second < b.second; return a.first > b.first; } int main() { vector<pair<int, int>> arr{{1, 9}, {2, 9}, {8, 1}, {0, 0}}; sort(arr.begin(), arr.end(), cmp); // arr = [(0, 0), (8, 1), (2, 9), (1, 9)] }

lower_bound() / upper_bound()

• lower_bound(): 寻找 >=x 的第一个元素的位置
• upper_bound(): 寻找 >x 的第一个元素的位置

怎么找 小于（等于）x 的第一个元素呢？

• >x 的第一个元素的前一个元素（如果有）便是 =x 的第一个元素
• >=x 的第一个元素的前一个元素（如果有）便是 <x 的第一个元素

vector<int> arr{0,1,1,1,8,8,9}; int pos = lower_bound(arr.begin(), arr.end(), 8) - arr.begin(); //4 int pos = upper_bound(arr.begin(), arr.end(), 8) - arr.begin(); //6 int pos = lower_bound(arr.begin()+4, arr.end(), 8) - arr.begin(); //5 ---+4则从第四个开始找 int pos = lower_bound(arr.begin(), arr.end(), 999) - arr.begin(); //7 找不到就返回尾迭代器

reverse()

vector<int> arr{0,1,1,1,8,8,9}; reverse(arr.begin(), arr.end()); //9 8 8 1 1 1 0 reverse(arr.begin()+2, arr.begin()+5); //0 1 8 1 1 8 9 ----虽然是+5但是是翻转到第四位就结束

max() / min()

unique()

把重复元素挤到最后面，只用unique时数组元素个数不变。

unique返回的是重复元素的起始位置

vector<int> arr{1,1,4,3,6,6,8,4}; sort(arr,begin(), arr.end()); //1 1 3 4 4 6 6 8 cout << unique(arr.begin(), arr.end()); //1 3 4 6 8 1 4 6 --返回6 arr.erase(unique(arr.begin(), arr.end()) , arr.end()); //1 3 4 6 8

数学函数

所有函数参数均支持int/long long/float/double/long double

• pow(2, 1.0/3)
• round是四舍五入

算特别大的数的时候，根号/幂会不准

gcd() / lcm()返回最大公约数/最小公约数

int x = gcd(8, 12); // 4 int y = lcm(8, 12); // 24