1// -*- C++ -*- 2 3// Copyright (C) 2005-2015 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_resize_example.cpp 34 * An example of externally resizing a map. 35 */ 36 37/** 38 * This example shows how to externally manipulate the size of a hash-based 39 * container object through its resize-policy object. 40 **/ 41 42#include <functional> 43#include <cassert> 44#include <ext/pb_ds/assoc_container.hpp> 45#include <ext/pb_ds/hash_policy.hpp> 46 47using namespace std; 48using namespace __gnu_pbds; 49 50// A simple hash functor. 51// hash could serve instead of this functor, but it is not yet 52// standard everywhere. 53struct int_hash : public unary_function<int, size_t> 54{ 55 inline size_t 56 operator()(const int& r_i) const 57 { return r_i; } 58}; 59 60int main() 61{ 62 // A probing hash table mapping ints to chars. 63 typedef 64 gp_hash_table< 65 int, 66 char, 67 int_hash, 68 equal_to< 69 int>, 70 // Combining function. 71 direct_mask_range_hashing<>, 72 // Probe function. 73 linear_probe_fn<>, 74 // Resize policy. 75 hash_standard_resize_policy< 76 hash_exponential_size_policy<>, 77 hash_load_check_resize_trigger<>, 78 /* Allow external access to size. 79 * Without setting this to true, external resizing 80 * is not possible. 81 */ 82 true> > 83 map_t; 84 85 map_t g; 86 87 // Check the actual size of the container object. In this case, this 88 // should be the initial size given by the size policy object. 89 assert(g.get_actual_size() == 8); 90 91 // Insert some elements. 92 g[1] = 'a'; 93 g[2] = 'b'; 94 g[3] = 'c'; 95 96 // Now resize the table upward. 97 g.resize(200); 98 99 // Check the actual size of the container object. 100 // For the policy used in this example, the nearest larger size than 101 // 200 is 256. 102 assert(g.get_actual_size() == 256); 103 104 g[67] = 'g'; 105 g[22] = 'f'; 106 107 // Regardless of the internal size, the logical size should be 5. 108 assert(g.size() == 5); 109 110 // Now resize the table downward. 111 g.resize(106); 112 113 // Check the actual size of the container object. 114 // For the policy used in this example, the nearest larger size than 115 // 106 is 128. 116 assert(g.get_actual_size() == 128); 117 118 g[37] = 'f'; 119 120 // Regardless of the internal size, the logical size should be 5. 121 assert(g.size() == 6); 122 123 return 0; 124} 125 126