diff options
| -rw-r--r-- | datastructures/pbds.cpp | 18 | ||||
| -rw-r--r-- | datastructures/stlPriorityQueue.cpp | 8 |
2 files changed, 26 insertions, 0 deletions
diff --git a/datastructures/pbds.cpp b/datastructures/pbds.cpp new file mode 100644 index 0000000..c2b44cc --- /dev/null +++ b/datastructures/pbds.cpp @@ -0,0 +1,18 @@ +#include <ext/pb_ds/assoc_container.hpp> +using namespace __gnu_pbds; +template<typename T> +using Tree = tree<T, null_type, less<T>, rb_tree_tag, + tree_order_statistics_node_update>; +// T.order_of_key(x): number of elements strictly less than x +// *T.find_by_order(k): k-th element + +template<typename T> +struct chash { + const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd + size_t operator()(T o) const { + return __builtin_bswap64(hash<T>()(o) * C); +}}; +template<typename K, typename V> +using hashMap = gp_hash_table<K, V, chash<K>>; +template<typename T> +using hashSet = gp_hash_table<T, null_type, chash<T>>; diff --git a/datastructures/stlPriorityQueue.cpp b/datastructures/stlPriorityQueue.cpp new file mode 100644 index 0000000..32b2455 --- /dev/null +++ b/datastructures/stlPriorityQueue.cpp @@ -0,0 +1,8 @@ +#include <ext/pb_ds/priority_queue.hpp> +template<typename T> +using pQueue = __gnu_pbds::priority_queue<T>; //<T, greater<T>> + +auto it = pq.push(5); +pq.modify(it, 6); +pq.join(pq2); +// push, join are O(1), pop, modify, erase O(log n) amortized |