C++常用STL的一些基本用法
C++STL
1. vector
-
简述:采用了倍增思想的变长数组
-
函数:
- size():返回元素个数 (几乎所有容器都有)
- empty():返回是否为空(几乎所有容器都有)
- clear():清空
- front()/back():返回vector中第一个/最后一个元素
- push_back()/pop_back():向vector后插入一个元素/删除vector最后一个元素
- begin()/end():返回vector第一个元素的位置/返回vector最后一个元素的后面一个位置
-
补:可以像数组一样使用[]进行存取
-
使用:
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> using namespace std; int main(void) { vector<int> a(10, -1); // 定义一个长度为10的vector并把每个值赋为-1 a.size(); // 容器长度,O(1) 所有容器都有 a.empty(); // 容器是否为空,O(1) 所有容器都有 for (auto x : a) cout << x << endl; vector<int> b; for (int i = 1; i < 10; ++i) b.push_back(i); for (int i = 0; i < b.size(); ++i) cout << b[i] << endl; // 第一种遍历方式 for (vector<int>::iterator i = b.begin(); i != b.end(); ++i) cout << *i << endl; // 第二种遍历方式 for (auto x : b) cout << x << endl; // 第三种遍历方式,C++11中新的遍历方式 return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
2. 误入的pair
-
简述:将两个数据整合成一个数据
-
使用:
- first:第一个元素
- second:第二个元素(支持比较运算,以first为第一关键字,以second为第二关键字)
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> using namespace std; int main(void) { pair<int, string> p; // 创建pair的两种方式 p = make_pair(1, "moyan"); p = { 1, "moyan" }; // C++11 cout << p.first << " " << p.second << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
3. string
-
简述:字符串
-
函数:
- size():返回字符串长度
- empty():返回字符串是否为空
- clear():清空字符串
- substr():返回一个子串,第一个参数是起始位置,第二个参数是长度(下标从0开始)
- c_str():返回一个c语言风格的字符串,用于printf输出string类型的字符串
-
使用:
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <string> using namespace std; int main(void) { string a = "abc"; a += "def"; cout << a << endl; cout << a.substr(1, 2) << endl; printf("%%s ", a.c_str()); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
4. queue
-
简述:队列,先进先出
-
函数:
- size():返回元素个数 (几乎所有容器都有)
- empty():返回是否为空(几乎所有容器都有)
- push():向队尾插入一个元素
- front():返回队头元素
- back():返回队尾元素
- pop():弹出队头元素
-
使用:
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <queue> using namespace std; int main(void) { queue<int> q; q.push(1); q.push(2); q.push(3); while (!q.empty()) { int tmp = q.front(); q.pop(); cout << tmp << endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
5. priority_queue
-
简述:优先队列,也称堆,默认是大根堆。
-
函数:
- size():返回元素个数 (几乎所有容器都有)
- empty():返回是否为空(几乎所有容器都有)
- push():插入一个元素
- top():返回堆顶元素
- pop():弹出堆顶元素
-
使用:
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <queue> using namespace std; int main(void) { priority_queue<int> q; // 大根堆 q.push(1); q.push(2); q.push(3); while (!q.empty()) { int tmp = q.top(); q.pop(); cout << tmp << endl; } priority_queue<int, vector<int>, greater<int> >heap; // 小根堆,从顶向下依次增大 heap.push(1); heap.push(2); heap.push(3); while (!heap.empty()) { int tmp = heap.top(); heap.pop(); cout << tmp << endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
6. stack
-
简述:栈,先进后出,也称后进先出
-
函数:
- size():返回元素个数 (几乎所有容器都有)
- empty():返回是否为空(几乎所有容器都有)
- push():向栈顶插入一个元素
- top():返回栈顶元素
- pop():弹出栈顶元素
-
使用:
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <queue> #include <stack> using namespace std; int main(void) { stack<int> s; s.push(1); s.push(2); s.push(3); while (!s.empty()) { int tmp = s.top(); s.pop(); cout << tmp << endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
7. deque
- 简述:双端队列,可以说是加强版vector,就是比较慢,即效率较低
- 函数:
- size():返回元素个数 (几乎所有容器都有)
- empty():返回是否为空(几乎所有容器都有)
- clear():清空
- front()/back():返回deque中第一个/最后一个元素
- push_back()/pop_back():向deque最后插入一个元素/删除vector最后一个元素
- push_front()/pop_front():向deque最前面插入一个元素/删除deque最前面一个元素
- begin()/end():返回vector第一个元素的位置/返回vector最后一个元素的后面一个位置
- 补:也可以使用[]进行随机存取
8. set,map,multiset,multimap
-
简述:基于平衡二叉树(红黑树),动态维护序列
-
函数:
- size():返回元素个数 (几乎所有容器都有)
- empty():返回是否为空(几乎所有容器都有)
- clear():清空
- begin()/end():返回容器第一个元素的迭代器/返回vector最后一个元素的后面一个的迭代器
-
set/multiset:
- insert():插入一个数
- find():查找一个数
- count():返回一个数的个数
- erase():有一个参数。若该参数是一个数x,则删除该容器中的所有x (时间复杂度O(k+logn),k是x的个数)。若该参数是一个迭代器,则删除这个迭代器
- lower_bound()/upper_bound():最核心的两个函数。lower_bound(x)返回大于等于x的最小的数的迭代器,upper_bound(x)返回大于等于x的最大的数的迭代器。
-
map/multimap:
- insert():插入的数是一个pair
- erase():输入的参数是pair或者迭代器
- find()
- [](时间复杂度是O(log n))
- lower_bound()/upper_bound()
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <queue> #include <stack> #include <map> using namespace std; int main(void) { map<int, string> m; m.insert({ 1, "张三" }); m.insert({ 2, "李四" }); cout << (*m.find(1)).second << endl; cout << m[1] << endl; return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
9. unordered_set, unordered_map,unordered_multiset,unordered_multimap
- 和上面set,map…类似,但增删改查的时间是O(1)且不支持lower_bound/upper_bound
- 基于哈希表实现
10. bitset
- 简述:压位
- 使用:
bitset<10000> s
(10000是位数) - 支持以下操作:
- ~,&,|,^
>>
,<<
- ==,!=
- []
- count()返回有多少个1
- any()判断是否至少有一个1
- none()判断是否全为0
- set()把所有位置成1
- set(k, v)将第k位变成v
- reset()把所有位变成0
- flip()等价于~
- flip()把第k位取反
推荐阅读