1 // -*- C++ -*-
2
3 // Copyright (C) 2005-2021 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
9 // version.
10
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
15
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING3. If not see
18 // <http://www.gnu.org/licenses/>.
19
20
21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
22
23 // Permission to use, copy, modify, sell, and distribute this software
24 // is hereby granted without fee, provided that the above copyright
25 // notice appears in all copies, and that both that copyright notice
26 // and this permission notice appear in supporting documentation. None
27 // of the above authors, nor IBM Haifa Research Laboratories, make any
28 // representation about the suitability of this software for any
29 // purpose. It is provided "as is" without express or implied
30 // warranty.
31
32 /**
33 * @file hash_load_set_change_example.cpp
34 * An example of setting and changing the load factor of a hash-based
35 * container object.
36 */
37
38 /**
39 * This example shows how to set and change the load-factor of
40 * a hash-based container object through its resize-policy object.
41 */
42
43 #include <functional>
44 #include <cassert>
45 #include <ext/pb_ds/assoc_container.hpp>
46 #include <ext/pb_ds/hash_policy.hpp>
47
48 using namespace std;
49 using namespace __gnu_pbds;
50
51 // A simple hash functor.
52 // hash could serve instead of this functor, but it is not yet
53 // standard everywhere.
54 struct int_hash
55 {
56 size_t
operator ()int_hash57 operator()(int i) const
58 { return i; }
59 };
60
main()61 int main()
62 {
63 // A trigger policy type.
64 typedef hash_load_check_resize_trigger< true> trigger_t;
65
66 // A resize policy type.
67 typedef
68 hash_standard_resize_policy<
69 hash_exponential_size_policy<>,
70 // Trigger type.
71 trigger_t,
72 /* Allow external access to size.
73 * This is not necessary for setting the load factor,
74 * but it allows to call get_actual_size.
75 */
76 true>
77 resize_t;
78
79 // A collision-chaining hash table mapping ints to chars.
80 typedef
81 cc_hash_table<
82 int,
83 char,
84 int_hash,
85 equal_to<int>,
86 // Combining function.
87 direct_mask_range_hashing<>,
88 // Resize policy.
89 resize_t>
90 map_t;
91
92 // A trigger policy object with load between 0.3 and 0.8.
93 trigger_t trigger(static_cast<float>(0.3), static_cast<float>(0.8));
94
95 // A resize policy object with the above trigger.
96 resize_t resize(hash_exponential_size_policy<>(),
97 trigger);
98
99 map_t r_c(int_hash(),
100 equal_to<int>(),
101 direct_mask_range_hashing<>(),
102 resize);
103
104 r_c[1] = 'a';
105
106 // Check the loads and sizes.
107 assert(r_c.get_loads().first == static_cast<float>(0.3));
108 assert(r_c.get_loads().second == static_cast<float>(0.8));
109 assert(r_c.get_actual_size() == 8);
110 assert(r_c.size() == 1);
111
112 // Note that there is a discrepancy between the loads of the policy
113 // object and the actual size of the container object. This is
114 // because the container's construction performs an implicit
115 // external resize.
116 r_c[2] = 'b';
117 r_c[3] = 'c';
118 r_c[4] = 'd';
119
120 assert(r_c.get_actual_size() == 8);
121
122 // Change the loads. This causes (potentially) a resize.
123 r_c.set_loads(make_pair(static_cast<float>(0.01),
124 static_cast<float>(0.05)));
125
126 // The actual size should really change in this case.
127 assert(r_c.get_actual_size() > 8);
128
129 return 0;
130 }
131
132