参考链接:
[C++ STL] vector使用详解 - fengMisaka - 博客园 (cnblogs.com)
[C++ STL] deque使用详解 - fengMisaka - 博客园 (cnblogs.com)
[C++ STL] list使用详解 - fengMisaka - 博客园 (cnblogs.com)
[C++ STL] set使用详解 - fengMisaka - 博客园 (cnblogs.com)
[C++ STL] map使用详解 - fengMisaka - 博客园 (cnblogs.com)
[C++ STL] 常用算法总结 - fengMisaka - 博客园 (cnblogs.com)
Acwing算法基础课
std::string
cplusplus.com/reference/string/string/substr/
string substr (size_t pos = 0, size_t len = npos) const;
cplusplus.com/reference/string/string/find/
size_t find (const string& str, size_t pos = 0) const noexcept;
cplusplus.com/reference/string/string/erase/
string& erase (size_t pos = 0, size_t len = npos);
cplusplus.com/reference/string/to_string/
string to_string (int val);
string to_string (long val);
string to_string (long long val);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val);
cplusplus.com/reference/string/stoi/
// stoi example
#include <iostream> // std::cout
#include <string> // std::string, std::stoi
int main () {
std::string str_dec = "2001, A Space Odyssey";
std::string str_hex = "40c3";
std::string str_bin = "-10010110001";
std::string str_auto = "0x7f";
std::string::size_type sz; // alias of size_t
int i_dec = std::stoi (str_dec,&sz);
int i_hex = std::stoi (str_hex,nullptr,16);
int i_bin = std::stoi (str_bin,nullptr,2);
int i_auto = std::stoi (str_auto,nullptr,0);
std::cout << str_dec << ": " << i_dec << " and [" << str_dec.substr(sz) << "]\n";
std::cout << str_hex << ": " << i_hex << '\n';
std::cout << str_bin << ": " << i_bin << '\n';
std::cout << str_auto << ": " << i_auto << '\n';
return 0;
}
cplusplus.com/reference/string/stod/
// stod example
#include <iostream> // std::cout
#include <string> // std::string, std::stod
int main () {
std::string orbits ("365.24 29.53");
std::string::size_type sz; // alias of size_t
double earth = std::stod (orbits,&sz);
double moon = std::stod (orbits.substr(sz));
std::cout << "The moon completes " << (earth/moon) << " orbits per Earth year.\n";
return 0;
}
vector
变长数组,倍增的思想
- size() 返回元素个数(所有容器都有,时间复杂度为O(1))
- empty() 返回是否为空(所有容器都有,时间复杂度为O(1))
- clear() 清空
- front()/back() 返回第一个数a[0]/最后一个数a[a.size()-1]
- push_back()/pop_back() 插入/弹出最后一个数
- begin()/end() 迭代器第一个数a[0]/最后一个数的后面一个数a[a.size()]
- [] 支持随机访问(下标)
- 支持比较运算,按字典序比较
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
// vector 初始化
vector<int> a;
vector<int> a(10); // 定义一个长度为10的vector
vector<int> a(10, 3); // 定义一个长度为10的vector,每个元素都初始化为3
// vector 添加元素
for (int i = 0; i < 10; i++) {
a.push_back(i);
}
// vector遍历
// 下标访问vector
for (int i = 0; i < a.size(); i++) {
cout << a[i] << ' ';
}
// 迭代器访问vector
for (vector<int>::iterator i = a.begin(); i != a.end(); i++) {
cout << *i << ' ';
}
// 范围遍历
for (auto x: a) {
cout << x << ' ';
}
// vector 支持比较运算,按字典序比较
vector<int> a(4, 3), b(3, 4);
if (a < b) {
puts("a < b");
}
return 0;
}
pair
存储一个二元组,前后两个变量的类型可以是任意的。
某个东西有两种不同的属性,有一个属性需要排序,可以将需要排序的属性放到first中,将不需排序的关键字放到second中。
嵌套的pair可以用于存储一个三元组。
- first 第一个元素
- second 第二个元素
- 支持比较运算,按字典序,以first为第一关键字,以second为第二关键字
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main() {
// pair 初始化
pair<int, int> p1;
pair<int, string> p2;
p2 = make_pair(10, "yxc");
p2 = {20, "abc"};
// 嵌套的pair可以用于存储三元组
pair<int, pair<int, int>> p3;
return 0;
}
string
字符串,substr(),c_str()
-
size()
-
length()
-
empty()
-
clear()
-
支持加法运算
-
substr() 第一个参数是位置,第二个参数是长度
如果长度大于string则一直输出到最后一个字母
第二个参数可省略,省略时也是从pos开始一直输出到最后一个字母
-
c_str() 返回字符数组的起始地址
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main() {
// 初始化
string a = "yxc";
// 支持加法运算
a += "def";
a += "c";
cout << a.substr(1, 2) << endl; // 输入字符串从1开始的两个字符
cout << a.substr(1, 10) << endl; // 输入字符串从1开始到最后一个字符
cout << a.substr(1) << endl; // 输入字符串从1开始到最后一个字符
printf("%s\n", a.c_str());
return 0;
}
queue
队列
-
size()
-
empty()
-
push() 向队尾插入一个元素
-
front() 返回队头元素
-
back() 返回队尾元素
-
pop() 弹出队头元素
-
没有clear() 函数,如果想清空队列,可以重新构造一个队列
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int main() {
// 初始化
queue<int> q;
// 没有clear()函数,如果想清空,可以重新构造一个队列
q = queue<int>();
return 0;
}
priority_queue
优先队列,默认是大根堆
-
size()
-
empty()
-
没有clear()函数
-
push() 插入一个元素
-
top() 返回堆顶元素
-
pop() 返回堆顶元素
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int main() {
// 初始化,默认为大根堆
priority_queue<int> heap;
int x;
cin >> x;
// 定义小根堆的两种方式
// 方式1:直接插入一个负数
heap.push(-x);
// 方式2:多加两个参数
priority_queue<int, vector<int>, greater<int>> heap;
return 0;
}
stack
栈
-
size()
-
empty()
-
没有clear()函数
-
push() 向栈顶插入一个元素
-
top() 返回栈顶元素
-
pop() 弹出栈顶元素
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
int main() {
// 初始化
stack<int> s;
// 没有clear()函数
while (!s.empty()) {
s.pop();
}
return 0;
}
deque
双端队列,两端都能插入删除,支持随机访问,缺点是速度慢
- size()
- empty()
- clear()
- front()/back()
- push_back()/pop_back()
- push_front()/pop_front()
- begin()/end()
- [] 支持随机访问
set, map, multiset, multimap
set, map, multiset, multimap, 基于平衡二叉树(红黑树), 动态维护有序序列
- size()
- empty()
- clear()
- begin()/end() ++, -- 返回前驱和后继,时间复杂度O(logn)
set 无重复元素,插入重复元素会被忽略
multiset 有重复元素
-
insert() 插入一个数
-
find() 查找一个数
-
count() 返回某一个数的个数
-
erase()
对multiset,如果输入一个数x,则删除所有x,时间复杂度O(k + logn),k是x的个数
如果输入一个迭代器,则删除这个迭代器
-
lower_bound() 返回大于等于x的最小的数的迭代器,如果不存在返回end()
-
upper_bound() 返回大于x的最小的数的迭代器
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
int main() {
set<int> s;
multiset<int> ms;
return 0;
}
map
multimap
- insert() 插入的数是一个pair
- erase() 输入的参数是pair或者迭代器
- find()
- [] 时间复杂度O(logn)
- lower_bound()/upper_bound() 返回大于x的最小的数的迭代器
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
int main() {
map<string, int> a;
a["yxc"] = 1;
cout << a["yxc"] << endl;
return 0;
}
unordered_set, unordered_map, unordered_multiset, unordered_multimap
哈希表,和上面类似,增删改查的时间复杂度是O(1)
不支持lower_bound()/upper_bound(),迭代器的++,--
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
using namespace std;
int main() {
unordered_map<string, int> a;
a["yxc"] = 1;
cout << a["yxc"] << endl;
unordered_multimap<string, int> b;
return 0;
}
bitset
压位,省8倍空间
-
bitset<10000>s;
-
~
,&
,|
,^
-
>>
,<<
-
==
,!=
-
[]
-
count() 返回有多少个1
-
any() 返回是否至少有一个1
-
none() 判断是否全为0
-
set() 把所有位置成1
-
set(k, v) 将第k位变成v
-
reset() 把所有位变成0
-
flip() 等价于~
-
flip(k) 把第k位取反