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_mod_example.cpp 34 * An example showing how to use a mod range-hasing function 35 */ 36 37/** 38 * This example shows how to use a hash-based container employing 39 * a modulo-based range-hashing function. 40 */ 41 42#include <functional> 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()(int i) const 56 { return i; } 57}; 58 59int main() 60{ 61 // In this case, we are worried that the key distribution will be 62 // skewed. We wish to use a more robust combining function. 63 64 // A collision-chaining hash table mapping ints to chars. 65 typedef 66 cc_hash_table< 67 int, 68 char, 69 int_hash, 70 equal_to<int>, 71 // Combining function. 72 direct_mod_range_hashing<> > 73 map_t; 74 75 map_t r_c; 76 77 // Use regularly. 78 r_c[32] = 'b'; 79 r_c[1024] = 'c'; 80 r_c[4096] = 'd'; 81 82 // The above keys are all powers of 2. A mask combining function 83 // would hamper performance in such a case. 84 return 0; 85} 86 87