123291Sbde// -*- C++ -*- 223291Sbde 323291Sbde// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. 423291Sbde// 523291Sbde// This file is part of the GNU ISO C++ Library. This library is free 623291Sbde// software; you can redistribute it and/or modify it under the terms 723291Sbde// of the GNU General Public License as published by the Free Software 823291Sbde// Foundation; either version 3, or (at your option) any later 923291Sbde// version. 1023291Sbde 1123291Sbde// This library is distributed in the hope that it will be useful, but 1223291Sbde// WITHOUT ANY WARRANTY; without even the implied warranty of 1323291Sbde// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1423291Sbde// General Public License for more details. 1523291Sbde 1623291Sbde// You should have received a copy of the GNU General Public License 1723291Sbde// along with this library; see the file COPYING3. If not see 1823291Sbde// <http://www.gnu.org/licenses/>. 1923291Sbde 2023291Sbde 2123291Sbde// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 2223291Sbde 2323291Sbde// Permission to use, copy, modify, sell, and distribute this software 2423291Sbde// is hereby granted without fee, provided that the above copyright 2523291Sbde// notice appears in all copies, and that both that copyright notice 2623291Sbde// and this permission notice appear in supporting documentation. None 2723291Sbde// of the above authors, nor IBM Haifa Research Laboratories, make any 2823291Sbde// representation about the suitability of this software for any 2923291Sbde// purpose. It is provided "as is" without express or implied 3090039Sobrien// warranty. 3123291Sbde 3290039Sobrien/** 3390039Sobrien * @file hash_resize_example.cpp 3490039Sobrien * An example of externally resizing a map. 3523291Sbde */ 3623291Sbde 3723291Sbde/** 3823291Sbde * This example shows how to externally manipulate the size of a hash-based 3923291Sbde * container object throught its resize-policy object. 40101651Smux **/ 41101651Smux 4223291Sbde#include <functional> 4323291Sbde#include <cassert> 4423291Sbde#include <ext/pb_ds/assoc_container.hpp> 45101651Smux#include <ext/pb_ds/hash_policy.hpp> 4623291Sbde 47101651Smuxusing namespace std; 4823291Sbdeusing namespace __gnu_pbds; 4923291Sbde 50101651Smux// A simple hash functor. 5123291Sbde// hash could serve instead of this functor, but it is not yet 52101651Smux// standard everywhere. 5323291Sbdestruct int_hash : public unary_function<int, size_t> 54101651Smux{ 5523291Sbde inline size_t 56101651Smux operator()(const int& r_i) const 5723291Sbde { return r_i; } 58101651Smux}; 59101651Smux 60101651Smuxint main() 61101651Smux{ 62101651Smux // A probing hash table mapping ints to chars. 63101651Smux typedef 64101651Smux gp_hash_table< 65101651Smux int, 66101651Smux char, 67101651Smux int_hash, 68101651Smux equal_to< 69101651Smux int>, 70101651Smux // Combining function. 7123291Sbde direct_mask_range_hashing<>, 7223291Sbde // Probe function. 73101651Smux linear_probe_fn<>, 7423291Sbde // Resize policy. 7523291Sbde hash_standard_resize_policy< 7623291Sbde 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