1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009 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_shift_mask_example.cpp 34 * An example showing how to write a range-hasing functor. 35 */ 36 37/** 38 * In some rare cases, advance knowledge of the distribution of keys allows 39 * writing more efficient hash-related policies. 40 * In the rather simplistic case of the example, it is known in advance that 41 * all keys have 0 two lowest bits. The example shows how to write 42 * a range-hashing function disregarding the two lowest bits of the hash value. 43 */ 44 45#include <functional> 46#include <ext/pb_ds/assoc_container.hpp> 47#include <ext/pb_ds/hash_policy.hpp> 48 49using namespace std; 50using namespace __gnu_pbds; 51 52// A simple hash functor. hash could serve instead of this functor, 53// but it is not yet standard everywhere. 54struct simple_int_hash : public unary_function<int, size_t> 55{ 56 inline size_t 57 operator()(int i) const 58 { return i; } 59}; 60 61// A range-hashing function which shifts 2 bits right and then masks. 62class shift_two_mask_range_hashing : private direct_mask_range_hashing<> 63{ 64public: 65 typedef size_t size_type; 66 67 // Swaps with a different instant. 68 void 69 swap(shift_two_mask_range_hashing& other) 70 { direct_mask_range_hashing<>::swap(other); } 71 72 // Called by the container when internally resized. 73 void 74 notify_resized(size_type size) 75 { direct_mask_range_hashing<>::notify_resized(size); } 76 77 // Given a hash value, returns a number in the range of the internal 78 // size of the container. 79 inline size_type 80 operator()(size_type hash) const 81 { return direct_mask_range_hashing<>::operator()(hash >> 2); } 82}; 83 84int 85main() 86{ 87 // A collision-chaining hash table mapping ints to chars. 88 typedef 89 cc_hash_table< 90 int, 91 char, 92 // Hash function. 93 simple_int_hash, 94 equal_to<int>, 95 // Range hashing function. 96 shift_two_mask_range_hashing> 97 map_t; 98 99 map_t h; 100 101 // Use normally. 102 h[16] = 'a'; 103 h[256] = 'e'; 104 h[4] = 'z'; 105 106 return 0; 107} 108 109