standard_policies.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041 #ifndef PB_DS_STANDARD_POLICIES_HPP
00042 #define PB_DS_STANDARD_POLICIES_HPP
00043
00044 #include <memory>
00045 #include <ext/pb_ds/hash_policy.hpp>
00046 #include <ext/pb_ds/list_update_policy.hpp>
00047 #include <ext/pb_ds/tree_policy.hpp>
00048 #include <ext/pb_ds/detail/basic_tree_policy/null_node_metadata.hpp>
00049 #include <ext/pb_ds/trie_policy.hpp>
00050 #include <ext/pb_ds/tag_and_trait.hpp>
00051 #include <tr1/functional>
00052
00053 namespace __gnu_pbds
00054 {
00055 namespace detail
00056 {
00057 template<typename Key>
00058 struct default_hash_fn
00059 {
00060 typedef std::tr1::hash<Key> type;
00061 };
00062
00063 template<typename Key>
00064 struct default_eq_fn
00065 {
00066 typedef std::equal_to<Key> type;
00067 };
00068
00069 enum
00070 {
00071 default_store_hash = false
00072 };
00073
00074 struct default_comb_hash_fn
00075 {
00076 typedef __gnu_pbds::direct_mask_range_hashing<> type;
00077 };
00078
00079 template<typename Comb_Hash_Fn>
00080 struct default_resize_policy
00081 {
00082 private:
00083 typedef typename Comb_Hash_Fn::size_type size_type;
00084
00085 typedef __gnu_pbds::direct_mask_range_hashing<size_type> default_fn;
00086 typedef is_same<default_fn, Comb_Hash_Fn> same_type;
00087 typedef __gnu_pbds::hash_exponential_size_policy<size_type> iftrue;
00088 typedef __gnu_pbds::hash_prime_size_policy iffalse;
00089 typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type;
00090 typedef typename cond_type::__type size_policy_type;
00091
00092 typedef __gnu_pbds::hash_load_check_resize_trigger<false, size_type> trigger;
00093
00094 public:
00095 typedef __gnu_pbds::hash_standard_resize_policy<size_policy_type, trigger, false, size_type> type;
00096 };
00097
00098 struct default_update_policy
00099 {
00100 typedef __gnu_pbds::move_to_front_lu_policy<> type;
00101 };
00102
00103 template<typename Comb_Probe_Fn>
00104 struct default_probe_fn
00105 {
00106 private:
00107 typedef typename Comb_Probe_Fn::size_type size_type;
00108
00109 typedef __gnu_pbds::direct_mask_range_hashing<size_type> default_fn;
00110 typedef is_same<default_fn, Comb_Probe_Fn> same_type;
00111 typedef __gnu_pbds::linear_probe_fn<size_type> iftrue;
00112 typedef __gnu_pbds::quadratic_probe_fn<size_type> iffalse;
00113 typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type;
00114
00115 public:
00116 typedef typename cond_type::__type type;
00117 };
00118
00119 template<typename Key>
00120 struct default_trie_e_access_traits;
00121
00122 template<typename Char, class Char_Traits>
00123 struct default_trie_e_access_traits<std::basic_string<Char, Char_Traits, std::allocator<char> > >
00124 {
00125 private:
00126 typedef std::basic_string<Char, Char_Traits, std::allocator<char> > string_type;
00127
00128 public:
00129 typedef __gnu_pbds::string_trie_e_access_traits<string_type> type;
00130 };
00131
00132 }
00133 }
00134
00135 #endif // #ifndef PB_DS_STANDARD_POLICIES_HPP
00136