常用STL
约 1290 字大约 4 分钟
cpp
2025-02-23
写在开头
随机数
#include <random>
using namespace std;
mt19937 rnd(time(0)); // 使用时间戳,使得每次生成的种子不同方法耗时
#include <format> // 格式化输出
void benchmark(const string &name, const auto &func) {
auto start = chrono::high_resolution_clock::now();
func();
auto end = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
cout << format("{} execution time: {} ms\n", name, duration.count());
}sort
基于快速排序的混合排序(堆排序,插入排序),性能相当出色。
sort(Iterator begin, Iterator end, Function comp)
复杂度:O(NlogN)
nth_element
采用分治,将nth小的数字移到nth位。
nth_element(Iterator begin, Iterator nth, Iterator end, Function comp)
复杂度:O(N)
速度对比:
int n = 10000000;
vector<int> a(n);
for (int i = 0; i < n; i++) a[i] = rnd();
vector<int> b = a;
int k = rnd() % n;
benchmark("[sort]", [&]() {
ranges::sort(a);
cout << a[k] << endl;
});
benchmark("[nth_element]", [&]() {
nth_element(b.begin(), b.begin() + k, b.end());
cout << b[k] << endl;
});输出内容
801552353
[sort] execution time: 467 ms
801552353
[nth_element] execution time: 35 mslower_bound & upper_bound
基于二分搜索
lower_bound在有序数组中找到第一个大于等于v的迭代器
lower_bound(Iterator begin, Iterator end, Type v, Function comp)
upper_bound在有序数组中找到第一个大于v的迭代器
upper_bound(Iterator begin, Iterator end, Type v, Function comp)
复杂度:O(logN)
典型例子:
1 1 2 2 2 2 3 3
l u
范围int n = 10000000;
vector<int> a(n);
for (int i = 0; i < n; i++) a[i] = rnd();
ranges::sort(a);
vector<int> targets(1000);
for (auto &x : targets) x = rand();
vector<int> ans1, ans2;
benchmark("[for]", [&]() {
for (auto &x : targets) {
for (int i = 0; i < n; i++) {
if (a[i] >= x) {
ans1.push_back(i);
break;
}
}
}
});
benchmark("[lower_bound]", [&]() {
for (auto &x : targets) {
ans2.push_back(ranges::lower_bound(a, x) - a.begin());
}
});
for (size_t i = 0; i < ans1.size(); i++) {
if (ans1[i] != ans2[i]) {
cout << "error" << endl;
}
}输出内容
[for] execution time: 987 ms
[lower_bound] execution time: 0 msnext_permutation & prev_permutation
生成下一个排列,在原数组中直接修改
如果已经是最后一个排列,则修改为最小的排列后,返回false
next_permutation(Iterator begin, Iterator end)
复杂度:O(N)
prev_permutation则是从后往前生成
unique
“移除”相邻的相同元素,并返回新序列的尾部。(不会直接删除,需要自行删除)
unique(Iterator begin, Iterator end, Function matcher)
复杂度:O(N)
// 不手动删除
vector<int> a = {1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1};
ranges::unique(a);
for (auto &x : a) cout << x << ' ';
cout << endl;
// 输出
// 1 2 1 1 2 2 2 1 1 1 1// 手动删除
vector<int> a = {1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1};
a.erase(unique(a.begin(), a.end()), a.end());
for (auto &x : a) cout << x << ' ';
cout << endl;
// 输出
// 1 2 1离散化
1 1 1 1000000000
-> 1 1000000000
-> 1 2自定义“相同”
vector<int> a = {1, 1, 10, 20, 30, 200, 2, 1, 10, -5, -8};
a.erase(
unique(a.begin(), a.end(), [](int a, int b) { return abs(a - b) <= 10; }),
a.end());
for (auto &x : a) cout << x << ' ';
cout << endl;
// 输出
// 1 20 200 2vector
时间复杂度:
push_back/emplace_back:O(1)
pop_back:O(1)
insert:O(N)
erase:O(N)
int n = 100000;
vector<int> a;
benchmark("push_back", [&]() {
for (int i = 0; i < n; i++) a.push_back(rnd());
});
benchmark("pop_back", [&]() {
for (int i = 0; i < n; i++) a.pop_back();
});
vector<int> b;
benchmark("insert", [&]() {
for (int i = 0; i < n; i++) b.insert(b.begin(), rnd());
});
benchmark("erase", [&]() {
for (int i = 0; i < n; i++) b.erase(b.begin());
});
// 输出
// push_back execution time: 0 ms
// pop_back execution time: 0 ms
// insert execution time: 249 ms
// erase execution time: 176 msint n = 100000000;
benchmark("push_back", [&]() {
vector<int> a;
for (int i = 0; i < n; i++) a.push_back(rnd());
});
benchmark("init", [&]() {
vector<int> a(n);
for (int i = 0; i < n; i++) a[i] = rnd();
});
// 输出
// push_back execution time: 268 ms
// init execution time: 192 msint n = 100000000;
benchmark("push_back", [&]() {
vector<int> a;
for (int i = 0; i < n; i++) a.push_back(rnd());
});
benchmark("init", [&]() {
vector<int> a(n);
for (auto &x : a) x = rnd();
});
benchmark("reserve", [&]() {
vector<int> a;
a.reserve(2 * n);
for (int i = 0; i < n; i++) a.push_back(rnd());
cout << a.size() << '\n';
});
// 输出
// push_back execution time: 272 ms
// init execution time: 187 ms
// 100000000
// reserve execution time: 180 msqueue & stack & dequeue
queue与stack都是基于dequeue实现的。
deque VS vector
deque虽然在两端的push、pop操作十分优秀,但是下标访问性能不如vector。
int n = 100000000;
deque<int> dq;
vector<int> v;
benchmark("push_back", [&]() {
for (int i = 0; i < n; i++) dq.push_back(rnd());
});
benchmark("vector push_back", [&]() {
for (int i = 0; i < n; i++) v.push_back(rnd());
});
benchmark("access", [&]() {
for (int i = 0; i < n; i++) dq[i] = i;
});
benchmark("vector access", [&]() {
for (int i = 0; i < n; i++) v[i] = i;
});
// 输出
// push_back execution time: 356 ms
// vector push_back execution time: 377 ms
// access execution time: 91 ms
// vector access execution time: 39 mspriority_queue
本质:堆
默认为大顶堆,top永远是最大的元素。
如果想要使用小顶堆,请使用priority_queue<int, vector<int>, greater<int>>
若想要实现自定义,可以priority_queue<int, vector<int>, decltype([](int a, int b){ return a > b; })>
priority_queue<int> pq;
int n = 10000000;
vector<int> a(n);
for (auto &x : a) x = rnd();
vector<int> sorted(n);
benchmark("push & pop", [&]() {
for (int i = 0; i < n; i++) pq.push(a[i]);
for (int i = 0; i < n; i++) {
sorted[i] = pq.top();
pq.pop();
}
});
benchmark("sort", [&]() { ranges::sort(a, greater<int>()); });
for (int i = 0; i < n; i++) {
if (sorted[i] != a[i]) cout << "error\n";
}
// 输出
// push & pop execution time: 1144 ms
// sort execution time: 453 msset
set
multiset
unordered_set
set<int> s{1, 1, 8, 4, 2, 2, 4, 8};
multiset<int> ms{1, 1, 8, 4, 2, 2, 4, 8};
unordered_set<int> us{1, 1, 8, 4, 2, 2, 4, 8};
for (auto &x : s) cout << x << ' ';
cout << '\n';
for (auto &x : ms) cout << x << ' ';
cout << '\n';
for (auto &x : us) cout << x << ' ';
cout << '\n';
// 输出
// 1 2 4 8
// 1 1 2 2 4 4 8 8
// 2 4 8 1map
map
multiamp
unordered_map