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_initial_size_example.cpp 34 * An example of setting an initial size for a container object. 35 */ 36 37/** 38 * This example shows how to set the initial size of a hash-based 39 * container object through its resize-policy object. 40 */ 41 42#include <cassert> 43#include <ext/pb_ds/assoc_container.hpp> 44#include <ext/pb_ds/hash_policy.hpp> 45 46using namespace std; 47using namespace __gnu_pbds; 48 49// A simple hash functor. 50// hash could serve instead of this functor, but it is not yet 51// standard everywhere. 52struct int_hash : public unary_function<int, size_t> 53{ 54 inline size_t 55 operator()(const int& r_i) const 56 { return r_i; } 57}; 58 59int main() 60{ 61 // Resize policy type. 62 typedef 63 hash_standard_resize_policy< 64 // Size-policy type. 65 hash_exponential_size_policy<>, 66 // Trigger-policy type. 67 hash_load_check_resize_trigger<>, 68 /* Allow external access to size. 69 * This is just used in this example for using the 70 * get_actual_size method (which won't be accessible without 71 * this flag. 72 */ 73 true> 74 resize_policy_t; 75 76 // A collision-probing hash table mapping ints to chars. 77 typedef 78 gp_hash_table< 79 int, 80 char, 81 int_hash, 82 equal_to< 83 int>, 84 // Combining function. 85 direct_mask_range_hashing<>, 86 // Probe function. 87 linear_probe_fn<>, 88 // Resize policy. 89 resize_policy_t> 90 map_t; 91 92 // A resize-policy object with suggested initial size 256. 93 resize_policy_t res(hash_exponential_size_policy<>(256)); 94 95 map_t g(int_hash(), 96 equal_to<int>(), 97 direct_mask_range_hashing<>(), 98 linear_probe_fn<>(), 99 res); 100 101 // Check the actual size of the container object. In this case, this 102 // should be the initial size given by the size policy object. 103 assert(g.get_actual_size() == 256); 104 105 // The logical size of g, though is 0 (it does not contain any elements). 106 assert(g.size() == 0); 107 108 return 0; 109} 110 111