C++常用STL及常用库函数
参考自AcWing的 语法基础课
/**
* vector
* queue
* stack
* deque 双端队列
* set
* map
* bitset
* pair
* 位运算
* 常用库函数：
* reverse、unique、random_shuffle、sort
* lower_bound/upper_bound、nth_element
*/
vector
#include <iostream>
#include <vector>
using namespace std;
int main() {
// 定义vector
vector<int> a; // 定义一个空vector
vector<int> b(3); // 定义一个长度为3，值全为0的vector
vector<int> c({1, 2, 3}); // 定义一个包含元素1,2,3的vector
vector<vector<int>> d(2, vector<int>(3)); // 定义一个2x3矩阵，值全为0
struct Rec {
int x, y;
};
vector<Rec> e;
// 遍历vector
for (int i = 0; i < c.size(); i++) cout << c[i] <<' ';
cout << endl;
for (vector<int>::iterator i = c.begin(); i < c.end(); i++) cout << *i << ' ';
cout << endl;
for (auto x : c) cout << x << ' ';
cout << endl;
// 获取vector第一个和最后一个元素
cout << c.front() << ' ' << c[0] << ' ' << *c.begin() << endl; // 第一个元素：c[0]常用
cout << c.back() << ' ' << c[c.size() - 1] << endl; // 最后一个元素：c.back()常用
// 在vector尾部添加、删除元素
c.push_back(4);
c.pop_back();
c.pop_back();
cout << c.size() << endl; // 2
// 清空vector
c.clear();
cout << c.size() << endl; // 0
// vector比较运算
vector<int> a1({1,2,3}), a2({1,2});
cout << (a1 >= a2) << endl; // 1
return 0;
}
queue
#include <iostream>
#include <queue>
using namespace std;
int main() {
// 定义 queue
queue<int> q;
// 入队、出队
q.push(4); // 4
q.push(3); // 4,3
q.push(7); // 4,3,7
q.pop(); // 3,7
// 获取 queue 队首和队尾元素
cout << q.front() << endl; // 返回队首元素: 3
cout << q.back() << endl; // 返回队尾元素: 7
// 清空 queue：不存在clear()，直接重新定义即可
q = queue<int>();
cout << q.size() << endl; // 0
cout << q.empty() << endl; // 1
// 定义 priority_queue
priority_queue<int> a; // 大根堆
priority_queue<int, vector<int>, greater<int>> b; // 小根堆
struct Rec {
int a, b;
bool operator< (const Rec &t) const {
return a < t.a;
}
};
priority_queue<Rec> c; // 大根堆需要重载小于号，小根堆需要重载大于号
// priority_queue 中插入元素，删除元素
c.push({1, 2}); c.push({6, 7});
c.push({5, 4}); c.push({3, 9});
c.pop();
// 返回堆顶元素
auto t = c.top();
cout << t.a << ' ' << t.b << endl; // 5 4
// 增加一点：如果结构体我们不能修改，可以按照下列方式定义 priority_queue
struct ListNode { // 不能修改这个结构体
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode *p1 = new ListNode(1), *p2 = new ListNode(3), *p3 = new ListNode(2);
struct Cmp {
// STL容器在比较的时候用的是结构体的小括号运算符
bool operator() (ListNode *a, ListNode *b) {
return a->val < b->val; // 大根堆
}
};
// 即使是大根堆，也需要如下定义，否则将会根据地址判断大小
priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
heap.push(p1); heap.push(p2); heap.push(p3);
cout << heap.top()->val << endl; // 3
return 0;
}
stack
#include <iostream>
#include <stack>
using namespace std;
int main() {
// 定义 stack
stack<int> stk;
// 入栈，出栈
stk.push(20);
stk.push(10);
stk.push(30);
stk.pop(); // 弹出30
// 返回栈顶元素
cout << stk.top() << endl; // 10
// 清空 stack：不存在clear()，直接重新定义即可
stk = stack<int>();
cout << stk.size() << endl; // 0
cout << stk.empty() << endl; // 1
return 0;
}
deque
#include <iostream>
#include <deque>
using namespace std;
int main() {
// 定义 deque
deque<int> d;
// 双端队列中插入、删除元素
d.push_back(20); d.push_back(10); // 尾部插入数据: 20,10
d.pop_back(); // 弹出一个尾部数据10: 20
d.push_front(40); d.push_front(30); // 头部插入数据: 30,40,20
d.pop_front(); // 弹出一个头部数据30: 40,20
// 遍历 deque
for (int i = 0; i < d.size(); i++) cout << d[i] << ' ';
cout << endl;
for (deque<int>::iterator i = d.begin(); i < d.end(); i++) cout << *i << ' ';
cout << endl;
for (auto x : d) cout << x << ' ';
cout << endl;
// 返回头部和尾部元素
cout << d.front() << endl; // 40
cout << d.back() << endl; // 20
// 清空 deque
d.clear();
cout << d.size() << endl; // 0
cout << d.empty() << endl; // 1
return 0;
}
set
#include <iostream>
#include <set>
using namespace std;
int main() {
// 定义 set，元素不能重复，内部实现是红黑树，可以保持有序
set<int> a;
struct Rec {
int x, y;
bool operator< (const Rec &t) const {
return x < t.x;
}
};
set<Rec> b;
// set 中插入、删除元素
a.insert(20); a.insert(3); a.insert(1); a.insert(40);
a.erase(3);
a.erase(a.find(40)); // 可以这样写，但没有必要，在multiset中有必要这样写
// 返回最后一个元素 a: 1, 20
cout << "最后一个元素：" << *a.rbegin() << endl;
// 遍历 set
for (int x : a) cout << x << ' ';
cout << endl;
for (set<int>::iterator it = a.begin(); it != a.end(); it++) // 不能用 <
cout << *it << ' ';
cout << endl;
// set 中寻找某元素，find返回第一个迭代器
if (a.find(20) != a.end()) cout << "20在a中存在" << endl;
else cout << "不存在" << endl;
// lower_bound/upper_nound
a.insert(4); a.insert(12); // a: 1, 4, 12, 20
cout << *a.lower_bound(4) << endl; // 返回大于等于4的最小元素的迭代器: 4
cout << *a.upper_bound(4) << endl; // 返回大于4的最小元素的迭代器: 12
bool flag = (a.lower_bound(521) == a.end()); // 判断是否不存在lower_bound
if (flag) cout << "不存在大于等于521的数" << endl;
else cout << "存在大于等于521的数" << endl;
// 清空 set
a.clear();
cout << a.size() << endl; // 0
cout << a.empty() << endl; // 1
cout << "==============================" << endl;
// 定义 multiset
multiset<int> s; // 有序，元素可以重复的set
// multiset 中插入、删除元素
s.insert(3); s.insert(3); s.insert(3); s.insert(2); s.insert(1);
s.erase(2); // 如果存在多个2，会全部删掉
s.erase(s.find(3)); // 删除第一个3
// 统计某个元素出现的次数
cout << s.count(3) << endl; // 此时3出现2次
// 其余同set, 省略
return 0;
}
- 另外unordered_set和set用法一致，但是unordered_set是基于哈希表实现的，内部是无序的，因此不存在lower_bound/upper_bound这两个函数
- 另外unordered_multiset和multiset用法一致，但是unordered_multiset是基于哈希表实现的，内部是无序的，因此不存在lower_bound/upper_bound这两个函数
map
#include <iostream>
#include <map>
#define x first
#define y second
using namespace std;
int main() {
// 定义 map，元素不能重复，内部实现是红黑树，可以保持有序
map<string, int> a;
// map 中插入、删除元素
a.insert({"wxx", 21}); a["hh"] = 18; a["other"] = 20;
a.erase("other");
// 返回最后一个元素 a: 1, 20
auto t = a.rbegin();
cout << t->x << ": " << t->y << endl;
// 遍历 map
for (map<string, int>::iterator p = a.begin(); p != a.end(); p++)
cout << "{" << p->x << ": " << p->y << "} ";
cout << endl;
for (auto p : a)
cout << "{" << p.x << ": " << p.y << "} ";
cout << endl;
for (auto &[k, v] : a)
cout << "{" << k << ": " << v << "} ";
cout << endl;
// map 中寻找某元素，find返回第一个迭代器
if (a.find("wxx") != a.end()) cout << "wxx在a中存在" << endl;
else cout << "不存在" << endl;
// lower_bound/upper_nound
a["c1"] = 2; a["c2"] = 4; // a: {c1: 2} {c2: 4} {hh: 18} {wxx: 21}
auto t1 = a.lower_bound("c1"), t2 = a.upper_bound("c1");
// 返回大于等于"c1"的最小元素的迭代器: {c1: 2}
cout << "{" << t1->x << ": " << t1->y << "} " << endl;
// 返回大于"c1"的最小元素的迭代器: {c2: 4}
cout << "{" << t2->x << ": " << t2->y << "} " << endl;
// 清空 map
a.clear();
cout << a.size() << endl; // 0
cout << a.empty() << endl; // 1
// multimap使用很少，这里先不做介绍
return 0;
}
- 另外unordered_map和map用法一致，但是unordered_map是基于哈希表实现的，内部是无序的，因此不存在lower_bound/upper_bound这两个函数
bitset
#include <iostream>
#include <bitset>
using namespace std;
int main() {
// 定义 bitset
bitset<1000> a, b;
// 赋值
a[0] = 1; a[1] = 1; b[2] = 1; b[200] = 1;
a.set(3); // 等价于a[3] = 1
a.reset(3); // 等价于a[3] = 0
// 位运算
a &= b;
a |= b;
// 输出1的个数
cout << a.count() << endl;
return 0;
}
pair
#include <iostream>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
int main() {
// 定义 pair
PII a = {1, 2}, b = {1, 3};
PII c = make_pair(5, 8); // c++99写法
// pair支持双关键子比较
cout << (a > b) << endl; // 0
// 输出pair
cout << "(" << a.first << ", " << a.second << ")" << endl;
return 0;
}
位运算
/*
& 与
| 或
~ 非
^ 异或
>> 右移
<< 左移
常用操作：
(1) 求x的第k位数字 x >> k & 1
(2) lowbit(x) = x & -x，返回x的最后一位1
*/
常用库函数
reverse
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 翻转 vector
vector<int> a({1, 2, 3, 4, 5});
reverse(a.begin(), a.end());
for (int x : a) cout << x << ' ';
cout << endl;
// 翻转 string
string s = "abcd";
reverse(s.begin(), s.end());
cout << s << endl; // dcba
// 翻转数组
int b[] = {1, 2, 3, 4, 5};
reverse(b, b + 5);
for (int x : b) cout << x << ' ';
cout << endl;
return 0;
}
unique
/*
返回去重之后的尾迭代器（或指针），仍然为前闭后开，即这个迭代器是去重之后末尾元素的下一个位置。
该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后的元素个数。
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 数组去重
int a[] = {1, 1, 2, 2, 3, 3, 4};
int m = unique(a, a + 7) - a; // 不同元素的个数
cout << m << endl; // 4
for (int i = 0; i < m; i++) cout << a[i] << ' ';
cout << endl;
// vector去重
vector<int> b = {1, 1, 2, 2, 3, 3, 4};
b.erase(unique(b.begin(), b.end()), b.end());
for (auto x : b) cout << x << ' ';
cout << endl;
return 0;
}
random_shuffle
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
int main() {
// 设置随机种子，使得每次结果不同
srand(time(0));
// 打乱数组
int a[] = {1, 2, 3, 4, 5};
random_shuffle(a, a + 5);
for (auto x : a) cout << x << ' ';
cout << endl;
// 打乱 vector
vector<int> b({1, 2, 3, 4, 5});
random_shuffle(b.begin(), b.end());
for (auto x : b) cout << x << ' ';
cout << endl;
return 0;
}
sort
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Rec {
int x, y;
bool operator< (const Rec &t) const { // 方式(2)
return x < t.x;
}
} r[5];
bool cmp(Rec a, Rec b) { // 返回值为：a是够应该排在b的前面
return a.x < b.x;
}
int main() {
// 对数组排序
int a[] = {3, 1, 4, 5, 2};
sort(a, a + 5); // 升序排列
for (int x : a) cout << x << ' ';
cout << endl;
sort(a, a + 5, greater<int>()); // 降序排列
for (int x : a) cout << x << ' ';
cout << endl;
// 对 vector 进行排序
cout << "=======================" << endl;
vector<int> t({3, 1, 4, 5, 2});
sort(t.begin(), t.end()); // 升序排列
for (int x : t) cout << x << ' ';
cout << endl;
sort(t.begin(), t.end(), greater<int>()); // 降序排列
for (int x : t) cout << x << ' ';
cout << endl;
// 对结构体进行排序
// 两种方式：(1) 传入比较函数; (2) 重载运算符
cout << "=======================" << endl;
for (int i = 0; i < 5; i++) r[i] = {-i, i};
sort(r, r + 5, cmp); // 方式(1)
for (int i = 0; i < 5; i++) printf("(%d, %d) ", r[i].x, r[i].y);
cout << endl;
sort(r, r + 5); // 方式(2)
for (int i = 0; i < 5; i++) printf("(%d, %d) ", r[i].x, r[i].y);
cout << endl;
return 0;
}
lower_bound/upper_bound
/*
lower_bound 的第三个参数传入一个元素x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于x的元素的位置的迭代器（指针）。
upper_bound 的用法和lower_bound大致相同，唯一的区别是查找第一个大于x的元素。当然，两个迭代器（指针）指定的部分应该是提前排好序的。
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
// 数组
int a[] = {1, 2, 4, 5, 6};
int *p = lower_bound(a, a + 5, 4); // 返回大于等于4的最小元素
cout << *p << endl; // 4
int t = upper_bound(a, a + 5, 4) - a; // 返回大于4的最小元素
cout << a[t] << endl; // 5
// vector
cout << "=======================" << endl;
vector<int> b = {1, 2, 4, 5, 6};
t = lower_bound(b.begin(), b.end(), 4) - b.begin();
cout << b[t] << endl; // 4
t = upper_bound(b.begin(), b.end(), 4) - b.begin();
cout << b[t] << endl; // 5
return 0;
}
nth_element
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
// 数组
int a[] = {6, 2, 1, 4, 3, 5};
int k = 2; // a[2]已经被排到正确的位置上(递增序)，第三小的数
nth_element(a, a + k, a + 6);
cout << a[2] << endl; // 3
for (int x : a) cout << x << ' ';
cout << endl;
// vector
cout << "=======================" << endl;
vector<int> b = {6, 2, 1, 4, 3, 5};
auto kptr = b.begin() + 2; // a[2]已经被排到正确的位置上(递增序)，第三小的数
nth_element(b.begin(), kptr, b.end());
cout << *kptr << endl; // 3
for (int x : b) cout << x << ' ';
cout << endl;
return 0;
}
爱了爱了，我直接冲了
%%%
太强了太强了