1 // 2 // Copyright (C) 2010 Codership Oy <info@codership.com> 3 // 4 5 //! 6 // @file gu_unordered.hpp unordered_[multi]map definition 7 // 8 // We still have environments where neither boost or std unordered 9 // stuff is available. Wrapper classes are provided for alternate 10 // implementations with standard semantics. 11 // 12 // For usage see either boost or tr1 specifications for unordered_[multi]map 13 // 14 15 #ifndef GU_UNORDERED_HPP 16 #define GU_UNORDERED_HPP 17 18 #if defined(HAVE_STD_UNORDERED_MAP) 19 #include <unordered_map> 20 #include <unordered_set> 21 #define GU_UNORDERED_MAP_NAMESPACE std 22 #elif defined(HAVE_TR1_UNORDERED_MAP) 23 #include <tr1/unordered_map> 24 #include <tr1/unordered_set> 25 #define GU_UNORDERED_MAP_NAMESPACE std::tr1 26 #elif defined(HAVE_BOOST_UNORDERED_MAP_HPP) 27 #include <boost/unordered_map.hpp> 28 #include <boost/unordered_set.hpp> 29 #define GU_UNORDERED_MAP_NAMESPACE boost 30 #else 31 #error "no unordered map available" 32 #endif 33 34 #include "gu_throw.hpp" 35 36 namespace gu 37 { 38 template <typename K> 39 class UnorderedHash 40 { 41 public: 42 typedef GU_UNORDERED_MAP_NAMESPACE::hash<K> Type; 43 operator ()(const K & k) const44 size_t operator()(const K& k) const 45 { 46 return Type()(k); 47 } 48 }; 49 50 51 template <typename K> HashValue(const K & key)52 size_t HashValue(const K& key) 53 { 54 return UnorderedHash<K>()(key); 55 } 56 57 template <typename K, typename H = UnorderedHash<K>, 58 class P = std::equal_to<K>, 59 class A = std::allocator<K> > 60 class UnorderedSet 61 { 62 typedef GU_UNORDERED_MAP_NAMESPACE::unordered_set<K, H, P, A> type; 63 type impl_; 64 public: 65 typedef typename type::value_type value_type; 66 typedef typename type::iterator iterator; 67 typedef typename type::const_iterator const_iterator; 68 UnorderedSet()69 UnorderedSet() : impl_() { } UnorderedSet(A a)70 explicit UnorderedSet(A a) : impl_(a) { } 71 begin()72 iterator begin() { return impl_.begin(); } begin() const73 const_iterator begin() const { return impl_.begin(); } end()74 iterator end() { return impl_.end(); } end() const75 const_iterator end() const { return impl_.end(); } insert(const value_type & k)76 std::pair<iterator, bool> insert(const value_type& k) 77 { return impl_.insert(k); } insert_unique(const value_type & k)78 iterator insert_unique(const value_type& k) 79 { 80 std::pair<iterator, bool> ret(insert(k)); 81 if (ret.second == false) gu_throw_fatal << "insert unique failed"; 82 return ret.first; 83 } find(const K & key)84 iterator find(const K& key) { return impl_.find(key); } find(const K & key) const85 const_iterator find(const K& key) const { return impl_.find(key); } erase(iterator i)86 iterator erase(iterator i) { return impl_.erase(i); } size() const87 size_t size() const { return impl_.size(); } empty() const88 bool empty() const { return impl_.empty(); } clear()89 void clear() { impl_.clear(); } rehash(size_t n)90 void rehash(size_t n) { impl_.rehash(n); } 91 }; 92 93 template <typename K, typename H = UnorderedHash<K>, 94 class P = std::equal_to<K>, 95 class A = std::allocator<K> > 96 class UnorderedMultiset 97 { 98 typedef GU_UNORDERED_MAP_NAMESPACE::unordered_multiset<K, H, P, A> type; 99 type impl_; 100 public: 101 typedef typename type::value_type value_type; 102 typedef typename type::iterator iterator; 103 typedef typename type::const_iterator const_iterator; 104 UnorderedMultiset()105 UnorderedMultiset() : impl_() { } 106 begin()107 iterator begin() { return impl_.begin(); } begin() const108 const_iterator begin() const { return impl_.begin(); } end()109 iterator end() { return impl_.end(); } end() const110 const_iterator end() const { return impl_.end(); } insert(const value_type & k)111 iterator insert(const value_type& k) 112 { return impl_.insert(k); } find(const K & key)113 iterator find(const K& key) { return impl_.find(key); } find(const K & key) const114 const_iterator find(const K& key) const { return impl_.find(key); } 115 std::pair<iterator, iterator> equal_range(const K & key)116 equal_range(const K& key) { return impl_.equal_range(key); } 117 std::pair<iterator, iterator> equal_range(const K & key) const118 equal_range(const K& key) const 119 { return impl_.equal_range(key); } erase(iterator i)120 iterator erase(iterator i) { return impl_.erase(i); } size() const121 size_t size() const { return impl_.size(); } empty() const122 bool empty() const { return impl_.empty(); } clear()123 void clear() { impl_.clear(); } rehash(size_t n)124 void rehash(size_t n) { impl_.rehash(n); } 125 }; 126 127 128 template <typename K, typename V, typename H = UnorderedHash<K>, 129 class P = std::equal_to<K>, 130 class A = std::allocator<std::pair<const K, V> > > 131 class UnorderedMap 132 { 133 typedef GU_UNORDERED_MAP_NAMESPACE::unordered_map<K, V, H, P, A> type; 134 type impl_; 135 public: 136 typedef typename type::value_type value_type; 137 typedef typename type::iterator iterator; 138 typedef typename type::const_iterator const_iterator; 139 UnorderedMap()140 UnorderedMap() : impl_() { } 141 begin()142 iterator begin() { return impl_.begin(); } begin() const143 const_iterator begin() const { return impl_.begin(); } end()144 iterator end() { return impl_.end(); } end() const145 const_iterator end() const { return impl_.end(); } insert(const std::pair<K,V> & kv)146 std::pair<iterator, bool> insert(const std::pair<K, V>& kv) 147 { return impl_.insert(kv); } insert_unique(const std::pair<K,V> & kv)148 iterator insert_unique(const std::pair<K, V>& kv) 149 { 150 std::pair<iterator, bool> ret(insert(kv)); 151 if (ret.second == false) gu_throw_fatal << "insert unique failed"; 152 return ret.first; 153 } find(const K & key)154 iterator find(const K& key) { return impl_.find(key); } find(const K & key) const155 const_iterator find(const K& key) const { return impl_.find(key); } erase(iterator i)156 iterator erase(iterator i) { return impl_.erase(i); } size() const157 size_t size() const { return impl_.size(); } empty() const158 bool empty() const { return impl_.empty(); } clear()159 void clear() { impl_.clear(); } rehash(size_t n)160 void rehash(size_t n) { impl_.rehash(n); } 161 }; 162 163 template <typename K, typename V, typename H = UnorderedHash<K> > 164 class UnorderedMultimap 165 { 166 typedef GU_UNORDERED_MAP_NAMESPACE::unordered_multimap<K, V> type; 167 type impl_; 168 public: 169 typedef typename type::value_type value_type; 170 typedef typename type::iterator iterator; 171 typedef typename type::const_iterator const_iterator; 172 UnorderedMultimap()173 UnorderedMultimap() : impl_() { } clear()174 void clear() { impl_.clear(); } 175 begin()176 iterator begin() { return impl_.begin(); } begin() const177 const_iterator begin() const { return impl_.begin(); } end()178 iterator end() { return impl_.end(); } end() const179 const_iterator end() const { return impl_.end(); } insert(const std::pair<K,V> & kv)180 iterator insert(const std::pair<K, V>& kv) 181 { return impl_.insert(kv); } find(const K & key)182 iterator find(const K& key) { return impl_.find(key); } find(const K & key) const183 const_iterator find(const K& key) const { return impl_.find(key); } 184 std::pair<iterator, iterator> equal_range(const K & key)185 equal_range(const K& key) { return impl_.equal_range(key); } 186 std::pair<const_iterator, const_iterator> equal_range(const K & key) const187 equal_range(const K& key) const 188 { return impl_.equal_range(key); } erase(iterator i)189 void erase(iterator i) { impl_.erase(i); } size() const190 size_t size() const { return impl_.size(); } empty() const191 bool empty() const { return impl_.empty(); } 192 }; 193 } 194 195 #undef GU_UNORDERED_MAP_NAMESPACE 196 197 #endif // GU_UNORDERED_HPP 198