C++

发布于2021-01-10

上次编辑2021-04-19

STL 自定义比较

auto gt_cmp = [](int lhs, int rhs) { return lhs > rhs; };
auto lt_cmp = [](int lhs, int rhs) { return lhs < rhs; };

vector<int> A;
sort(A.begin(), A.end());           // 升序：默认
sort(A.begin(), A.end(), less<>()); // 升序：库
sort(A.begin(), A.end(), lt_cmp);   // 升序：自定义

sort(A.begin(), A.end(), greater<>()); // 降序：库
sort(A.begin(), A.end(), gt_cmp);      // 降序：自定义

// multiset、map 同理 
set<int> B(A.begin(), A.end());                           // 升序：默认
set<int, less<>> B(A.begin(), A.end());                   // 升序：库
set<int, decltype(lt_cmp)> B(A.begin(), A.end(), lt_cmp); // 升序：自定义

set<int, greater<>> B(A.begin(), A.end());                // 降序：库
set<int, decltype(lt_cmp)> B(A.begin(), A.end(), lt_cmp); // 降序：自定义

priority_queue<int> C(less<int>(), A);                           // 大根堆：默认
priority_queue<int, vector<int>, less<>> C(less<>(), A);         // 大根堆：库
priority_queue<int, vector<int>, decltype(lt_cmp)> C(lt_cmp, A); // 大根堆：自定义

priority_queue<int, vector<int>, greater<>> C(greater<>(), A);   // 小根堆：库
priority_queue<int, vector<int>, decltype(gt_cmp)> C(gt_cmp, A); // 小根堆：自定义

Tricks

Warning

在 std::set 中二分查找元素时，要使用 set::upper_bound 或 set::lower_bound，不要使用 std::upper_bound 和 std::lower_bound，对于非随机访问对象，std::lower_bound 和 std::upper_bound 的时间复杂度是线性的。

Warning

priority_queue 中取 top 时，不要使用 auto &top = q.top();，因为地址不会改变。

Tip

获取三个数 a,b,c 的最大值（或最小值），可以不用 max(max(a,b),c)，可以直接 max({a,b,c})。

---

1. C++ 参考手册 ↩

2. https://stackoverflow.com/a/46128321 ↩

返回顶部

在手机上阅读