41 #ifndef PB_DS_HASH_POLICY_HPP 42 #define PB_DS_HASH_POLICY_HPP 56 #define PB_DS_CLASS_T_DEC template<typename Size_Type> 57 #define PB_DS_CLASS_C_DEC linear_probe_fn<Size_Type> 60 template<
typename Size_Type = std::
size_t>
64 typedef Size_Type size_type;
67 swap(PB_DS_CLASS_C_DEC& other);
77 #undef PB_DS_CLASS_T_DEC 78 #undef PB_DS_CLASS_C_DEC 80 #define PB_DS_CLASS_T_DEC template<typename Size_Type> 81 #define PB_DS_CLASS_C_DEC quadratic_probe_fn<Size_Type> 84 template<
typename Size_Type = std::
size_t>
88 typedef Size_Type size_type;
91 swap(PB_DS_CLASS_C_DEC& other);
101 #undef PB_DS_CLASS_T_DEC 102 #undef PB_DS_CLASS_C_DEC 104 #define PB_DS_CLASS_T_DEC template<typename Size_Type> 105 #define PB_DS_CLASS_C_DEC direct_mask_range_hashing<Size_Type> 108 template<
typename Size_Type = std::
size_t>
116 typedef Size_Type size_type;
119 swap(PB_DS_CLASS_C_DEC& other);
123 notify_resized(size_type
size);
133 #undef PB_DS_CLASS_T_DEC 134 #undef PB_DS_CLASS_C_DEC 136 #define PB_DS_CLASS_T_DEC template<typename Size_Type> 137 #define PB_DS_CLASS_C_DEC direct_mod_range_hashing<Size_Type> 140 template<
typename Size_Type = std::
size_t>
145 typedef Size_Type size_type;
148 swap(PB_DS_CLASS_C_DEC& other);
152 notify_resized(size_type
size);
165 #undef PB_DS_CLASS_T_DEC 166 #undef PB_DS_CLASS_C_DEC 168 #define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type> 169 #define PB_DS_CLASS_C_DEC hash_load_check_resize_trigger<External_Load_Access, Size_Type> 170 #define PB_DS_SIZE_BASE_C_DEC detail::hash_load_check_resize_trigger_size_base<Size_Type, External_Load_Access> 174 template<
bool External_Load_Access = false,
typename Size_Type = std::
size_t>
178 typedef Size_Type size_type;
192 float load_max = 0.5);
211 notify_insert_search_start();
214 notify_insert_search_collision();
217 notify_insert_search_end();
220 notify_find_search_start();
223 notify_find_search_collision();
226 notify_find_search_end();
229 notify_erase_search_start();
232 notify_erase_search_collision();
235 notify_erase_search_end();
243 notify_erased(size_type num_entries);
255 notify_externally_resized(size_type new_size);
258 is_resize_needed()
const;
261 is_grow_needed(size_type
size, size_type num_entries)
const;
265 do_resize(size_type new_size);
267 typedef PB_DS_SIZE_BASE_C_DEC size_base;
269 #ifdef _GLIBCXX_DEBUG 271 assert_valid(
const char* file,
int line)
const;
276 size_type m_next_shrink_size;
277 size_type m_next_grow_size;
278 bool m_resize_needed;
283 #undef PB_DS_CLASS_T_DEC 284 #undef PB_DS_CLASS_C_DEC 285 #undef PB_DS_SIZE_BASE_C_DEC 287 #define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type> 288 #define PB_DS_CLASS_C_DEC cc_hash_max_collision_check_resize_trigger<External_Load_Access, Size_Type> 292 template<
bool External_Load_Access = false,
typename Size_Type = std::
size_t>
296 typedef Size_Type size_type;
311 swap(PB_DS_CLASS_C_DEC& other);
393 calc_resize_needed();
399 bool m_resize_needed;
404 #undef PB_DS_CLASS_T_DEC 405 #undef PB_DS_CLASS_C_DEC 407 #define PB_DS_CLASS_T_DEC template<typename Size_Type> 408 #define PB_DS_CLASS_C_DEC hash_exponential_size_policy<Size_Type> 412 template<
typename Size_Type = std::
size_t>
416 typedef Size_Type size_type;
423 size_type grow_factor = 2);
426 swap(PB_DS_CLASS_C_DEC& other);
430 get_nearest_larger_size(size_type
size)
const;
433 get_nearest_smaller_size(size_type
size)
const;
436 size_type m_start_size;
437 size_type m_grow_factor;
442 #undef PB_DS_CLASS_T_DEC 443 #undef PB_DS_CLASS_C_DEC 445 #define PB_DS_CLASS_T_DEC 446 #define PB_DS_CLASS_C_DEC hash_prime_size_policy 462 swap(PB_DS_CLASS_C_DEC& other);
477 #undef PB_DS_CLASS_T_DEC 478 #undef PB_DS_CLASS_C_DEC 480 #define PB_DS_CLASS_T_DEC template<typename Size_Policy, typename Trigger_Policy, bool External_Size_Access, typename Size_Type> 482 #define PB_DS_CLASS_C_DEC hash_standard_resize_policy<Size_Policy, Trigger_Policy, External_Size_Access, Size_Type> 485 template<
typename Size_Policy = hash_exponential_size_policy<>,
486 typename Trigger_Policy = hash_load_check_re
size_trigger<>,
487 bool External_Size_Access = false,
488 typename Size_Type = std::
size_t>
490 :
public Size_Policy,
public Trigger_Policy
493 typedef Size_Type size_type;
494 typedef Trigger_Policy trigger_policy;
495 typedef Size_Policy size_policy;
499 external_size_access = External_Size_Access
514 const Trigger_Policy& r_trigger_policy);
520 swap(PB_DS_CLASS_C_DEC& other);
535 const Trigger_Policy&
546 resize(size_type suggested_new_size);
550 notify_insert_search_start();
553 notify_insert_search_collision();
556 notify_insert_search_end();
559 notify_find_search_start();
562 notify_find_search_collision();
565 notify_find_search_end();
568 notify_erase_search_start();
571 notify_erase_search_collision();
574 notify_erase_search_end();
577 notify_inserted(size_type num_e);
580 notify_erased(size_type num_e);
586 notify_resized(size_type new_size);
589 is_resize_needed()
const;
601 do_resize(size_type new_size);
603 typedef Trigger_Policy trigger_policy_base;
605 typedef Size_Policy size_policy_base;
612 #undef PB_DS_CLASS_T_DEC 613 #undef PB_DS_CLASS_C_DEC
A resize trigger policy based on a load check. It keeps the load factor between some load factors loa...
A probe sequence policy using square increments.
Trigger_Policy & get_trigger_policy()
Access to the Trigger_Policy object used.
void notify_find_search_end()
Notifies a search ended.
hash_prime_size_policy(size_type start_size=8)
Default constructor, or onstructor taking a start_size The policy will use the sequence of sizes appr...
A size policy whose sequence of sizes form an exponential sequence (typically powers of 2...
Size_Policy & get_size_policy()
Access to the Size_Policy object used.
std::size_t size_type
Size type.
void resize(size_type suggested_new_size)
Resizes the container to suggested_new_size, a suggested size (the actual size will be determined by ...
bool is_grow_needed(size_type size, size_type num_entries) const
Queries whether a grow is needed. This method is called only if this object indicated is needed...
bool is_resize_needed() const
Queries whether a resize is needed.
void notify_resized(size_type new_size)
Notifies the table was resized as a result of this object's signifying that a resize is needed...
A mod range-hashing class (uses the modulo function).
float get_load() const
Returns the current load.
size_type get_new_size(size_type size, size_type num_used_e) const
Queries what the new size should be, when the container is resized naturally. The current __size of t...
Specifies whether the load factor can be accessed externally. The two options have different trade-of...
void notify_find_search_collision()
Notifies a search encountered a collision.
A probe sequence policy using fixed increments.
void notify_erase_search_end()
Notifies a search ended.
size_type operator()(size_type i) const
Returns the i-th offset from the hash value.
cc_hash_max_collision_check_resize_trigger(float load=0.5)
Default constructor, or constructor taking load, a __load factor which it will attempt to maintain...
void notify_resized(size_type new_size)
Notifies the table was resized as a result of this object's signifying that a resize is needed...
A resize policy which delegates operations to size and trigger policies.
A resize trigger policy based on collision checks. It keeps the simulated load factor lower than some...
Specifies whether the load factor can be accessed externally. The two options have different trade-of...
A mask range-hashing class (uses a bitmask).
Struct holding two objects of arbitrary type.
void notify_inserted(size_type num_entries)
Notifies an element was inserted. The total number of entries in the table is num_entries.
size_type operator()(size_type hash) const
Transforms the __hash value hash into a ranged-hash value (using a modulo operation).
A size policy whose sequence of sizes form a nearly-exponential sequence of primes.
size_type operator()(size_type i) const
Returns the i-th offset from the hash value.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
void set_loads(std::pair< float, float > load_pair)
Sets the loads through a pair of the minimal and maximal loads, respectively.
hash_standard_resize_policy()
Default constructor.
hash_exponential_size_policy(size_type start_size=8, size_type grow_factor=2)
Default constructor, or onstructor taking a start_size, or constructor taking a start size and grow_f...
size_type operator()(size_type hash) const
Transforms the __hash value hash into a ranged-hash value (using a bit-mask).
void notify_erase_search_start()
Notifies an erase search started.
void notify_erase_search_collision()
Notifies a search encountered a collision.
void notify_cleared()
Notifies the table was cleared.
hash_load_check_resize_trigger(float load_min=0.125, float load_max=0.5)
Default constructor, or constructor taking load_min and load_max load factors between which this poli...
size_type get_actual_size() const
Returns the actual size of the container.
std::pair< float, float > get_loads() const
Returns a pair of the minimal and maximal loads, respectively.
void notify_externally_resized(size_type new_size)
Notifies the table was resized externally.
void notify_insert_search_end()
Notifies a search ended.
void notify_cleared()
Notifies the table was cleared.
void notify_insert_search_start()
Notifies an insert search started.
GNU extensions for policy-based data structures for public use.
void notify_find_search_start()
Notifies a find search started.
void set_load(float load)
Sets the load; does not resize the container.
void notify_insert_search_collision()
Notifies a search encountered a collision.
void notify_inserted(size_type num_entries)
Notifies an element was inserted.
void notify_erased(size_type num_entries)
Notifies an element was erased.