pb_ds 是GNU-C++自帶的一個C++的擴展庫，其中實現了很多數據結構，比STL里面的功能更強大

#include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> // 用tree #include<ext/pb_ds/hash_policy.hpp> // 用hash #include<ext/pb_ds/trie_policy.hpp> // 用trie #include<ext/pb_ds/priority_queue.hpp>// 用priority_queue using namespace __gnu_pbds; --- #include<bits/extc++.h> using namespace __gnu_pbds; //bits/extc++.h與bits/stdc++.h類似，bits/extc++.h是所有拓展庫，bits/stdc++.h是所有標準庫

哈希表

其中cc開頭為拉鏈法，gp開頭為探測法，個人實測探測法稍微快一些。

啥？操作？其實就和map差不多，支持[ ]和find。

#include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/hash_policy.hpp> using namespace __gnu_pbds;cc_hash_table<string,int>mp1;//拉鏈法 gp_hash_table<string,int>mp2;//查探法(快一些)

說明：

在不允許使用C++11的時候，pb_ds庫中的兩種hash函數比map的效率大大提高 ，可以代替map作為一個哈希工具,使用方法和map完全一樣,一般來說查探法的效率更高

可并堆

需要的頭文件:

用法和普通的優先隊列一樣

#include<ext/pb_ds/priority_queue.hpp> using namespace __gnu_pbds; __gnu_pbds::priority_queue<int>q;//因為放置和std重復，故需要帶上命名空間 __gnu_pbds::priority_queue<int,greater<int>,pairing_heap_tag> q;//最快 __gnu_pbds::priority_queue<int,greater<int>,binary_heap_tag> q; __gnu_pbds::priority_queue<int,greater<int>,binomial_heap_tag> q; __gnu_pbds::priority_queue<int,greater<int>,rc_binomial_heap_tag> q; __gnu_pbds::priority_queue<int,greater<int>,thin_heap_tag> q; __gnu_pbds::priority_queue<int,greater<int> > q;

pb_ds庫的堆提供了五種tag，分別是binary_heap_tag，binomal_heap_tag，pairing_heap_tag，thin_heap_tag，rc_binomal_heap_tag。 因為重名的原因一定要加上 __gnu_pbds::

常用操作:

push() //會返回一個迭代器 top() //同 STL size() //同 STL empty() //同 STL clear() //同 STL pop() //同 STL join(priority_queue &other) //合并兩個堆,other會被清空 split(Pred prd,priority_queue &other) //分離出兩個堆 modify(point_iterator it,const key) //修改一個節點的值

平衡樹

#include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/hash_policy.hpp>using namespace __gnu_pbds; template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;// rb_tree_tag 和 splay_tree_tag 選擇樹的類型(紅黑樹和伸展樹) T // 自定義數據類型 null_type//無映射（老版本g++為null_mapped_type） less<T>//Node的排序方式從小到大排序 tree_order_statistics_node_update//參數表示如何更新保存節點信息 tree_order_statistics_node_update會額外獲得order_of_key()和find_by_order()兩個功能。ordered_set<Node> Tree; // Node 自定義struct 注意重載less Tree.insert(Node); // 插入 Tree.erase(Node); // 刪除 Tree.order_of_key(Node); // 求Node的排名:當前數小的數的個數 +1 Tree.find_by_order(k); // 返回排名為k+1的iterator 即有k個Node比*it小 Tree.join(b); // 將b并入Tree，前提是兩棵樹類型一致并且二沒有重復元素 Tree.split(v, b); // 分裂，key小于等于v的元素屬于Tree，其余屬于b Tree.lower_bound(Node); // 返回第一個大于等于x的元素的迭代器 Tree.upper_bound(Node); // 返回第一個大于x的元素的迭代器//以上的所有操作的時間復雜度均為O(logn) //注意，插入的元素會去重，如set ordered_set<T>::point_iterator it=Tree.begin(); // 迭代器 //顯然迭代器可以++，--運算

P3369 【模板】普通平衡樹

因為tree里不能有相同的數，但是實際會插入相同的數，所以把這些數左移20位在加上一個常數操作（$n<2^{20}$，如果$a<b$，那么一定有$\{(a<<20)+n\}<\{b<<20\}$，這樣就保證了在不影響相對大小關系的情況下，消除了相同的數。

別的操作看代碼就可以理解了，非常巧妙的搞定了相同數的情況。

rb_tree_tag

#include<bits/stdc++.h> #include<ext/pb_ds/tree_policy.hpp> #include<ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; using ll=long long;template <class T=int> T rd() {T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg; } template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;const int N=100010; int n,m; ll k,ans; ordered_set<ll> T; int main() {n=rd();for(int i=1;i<=n;i++){int op=rd();k=rd<ll>();if(op==1) T.insert((k<<20)+i);if(op==2) T.erase(T.lower_bound(k<<20));if(op==3) printf("%d\n",T.order_of_key((k<<20))+1);if(op == 4)ans=*T.find_by_order(k-1),printf("%lld\n",ans>>20);if(op == 5)ans=*--T.lower_bound(k<<20),printf("%lld\n",ans>>20);if(op == 6)ans=*T.upper_bound((k<<20)+n),printf("%lld\n",ans>>20);}return 0; }

splay_tree_tag

Code from

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <map> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define Node pair<int,int> map <int,int> s; tree< Node ,null_type,less< Node >,splay_tree_tag,tree_order_statistics_node_update> T; int n,op,x; int main() {scanf("%d",&n);for(register int i = 1; i <= n; i++)switch(scanf("%d%d",&op,&x), op){case 1 :T.insert(Node(x,s[x]++));break;case 2 :T.erase(Node(x,--s[x]));break;case 3 :printf("%d\n",(int)T.order_of_key(Node(x,0))+1);break;case 4 :printf("%d\n",T.find_by_order(x-1)->first);break;case 5 :printf("%d\n",T.find_by_order(T.order_of_key(Node(x,0))-1)->first);break;case 6 :printf("%d\n",T.find_by_order(T.order_of_key(Node(x,s[x]-1))+(T.find(Node(x,0)) == T.end() ? 0 : 1))->first);break;default:break;}return 0; }

底層代碼

---

參考以及進階

比STL還STL？——平板電視
pb_ds庫的一些常用方法
C++ __gnu_pbds（平板電視）超詳細教程（C++內置的平衡樹，字典樹，hash）

總結

以上是生活随笔為你收集整理的C++ __gnu_pbds（hash，可并堆，平衡树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。