_unordered_set.h revision e46c9386c4f79aa40185f79a19fc5b2a7ef528b3
1/* 2 * Copyright (c) 2004 3 * Francois Dumont 4 * 5 * This material is provided "as is", with absolutely no warranty expressed 6 * or implied. Any use is at your own risk. 7 * 8 * Permission to use or copy this software for any purpose is hereby granted 9 * without fee, provided the above notices are retained on all copies. 10 * Permission to modify the code and to distribute modified code is granted, 11 * provided the above notices are retained, and a notice that the code was 12 * modified is included with the above copyright notice. 13 * 14 */ 15 16/* NOTE: This is an internal header file, included by other STL headers. 17 * You should not attempt to use it directly. 18 */ 19 20#ifndef _STLP_INTERNAL_UNORDERED_SET_H 21#define _STLP_INTERNAL_UNORDERED_SET_H 22 23#ifndef _STLP_INTERNAL_HASHTABLE_H 24# include <stl/_hashtable.h> 25#endif 26 27_STLP_BEGIN_NAMESPACE 28 29//Specific iterator traits creation 30_STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedSetTraitsT, Const_traits) 31 32_STLP_BEGIN_TR1_NAMESPACE 33 34template <class _Value, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Value>), 35 _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Value>), 36 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Value>) > 37class unordered_set 38#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 39 : public __stlport_class<unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> > 40#endif 41{ 42 typedef unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> _Self; 43 //Specific iterator traits creation 44 typedef _STLP_PRIV _UnorderedSetTraitsT<_Value> _UnorderedSetTraits; 45public: 46 typedef hashtable<_Value, _Value, _HashFcn, 47 _UnorderedSetTraits, _STLP_PRIV _Identity<_Value>, _EqualKey, _Alloc> _Ht; 48public: 49 typedef typename _Ht::key_type key_type; 50 typedef typename _Ht::value_type value_type; 51 typedef typename _Ht::hasher hasher; 52 typedef typename _Ht::key_equal key_equal; 53 54 typedef typename _Ht::size_type size_type; 55 typedef typename _Ht::difference_type difference_type; 56 typedef typename _Ht::pointer pointer; 57 typedef typename _Ht::const_pointer const_pointer; 58 typedef typename _Ht::reference reference; 59 typedef typename _Ht::const_reference const_reference; 60 61 typedef typename _Ht::iterator iterator; 62 typedef typename _Ht::const_iterator const_iterator; 63 typedef typename _Ht::local_iterator local_iterator; 64 typedef typename _Ht::const_local_iterator const_local_iterator; 65 66 typedef typename _Ht::allocator_type allocator_type; 67 68 hasher hash_function() const { return _M_ht.hash_funct(); } 69 key_equal key_eq() const { return _M_ht.key_eq(); } 70 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 71 72private: 73 _Ht _M_ht; 74 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 75 76public: 77 explicit unordered_set(size_type __n = 0, const hasher& __hf = hasher(), 78 const key_equal& __eql = key_equal(), 79 const allocator_type& __a = allocator_type()) 80 : _M_ht(__n, __hf, __eql, __a) {} 81 82#if !defined (_STLP_NO_MOVE_SEMANTIC) 83 unordered_set(__move_source<_Self> src) 84 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {} 85#endif 86 87#if defined (_STLP_MEMBER_TEMPLATES) 88 template <class _InputIterator> 89 unordered_set(_InputIterator __f, _InputIterator __l, 90 size_type __n = 0, const hasher& __hf = hasher(), 91 const key_equal& __eql = key_equal(), 92 const allocator_type& __a = allocator_type()) 93 : _M_ht(__n, __hf, __eql, __a) 94 { _M_ht.insert_unique(__f, __l); } 95#else 96 unordered_set(const value_type* __f, const value_type* __l, 97 size_type __n = 0, const hasher& __hf = hasher(), 98 const key_equal& __eql = key_equal(), 99 const allocator_type& __a = allocator_type()) 100 : _M_ht(__n, __hf, __eql, __a) 101 { _M_ht.insert_unique(__f, __l); } 102 103 unordered_set(const_iterator __f, const_iterator __l, 104 size_type __n = 0, const hasher& __hf = hasher(), 105 const key_equal& __eql = key_equal(), 106 const allocator_type& __a = allocator_type()) 107 : _M_ht(__n, __hf, __eql, __a) 108 { _M_ht.insert_unique(__f, __l); } 109#endif /*_STLP_MEMBER_TEMPLATES */ 110 111 _Self& operator = (const _Self& __other) 112 { _M_ht = __other._M_ht; return *this; } 113 114 size_type size() const { return _M_ht.size(); } 115 size_type max_size() const { return _M_ht.max_size(); } 116 bool empty() const { return _M_ht.empty(); } 117 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); } 118#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 119 void _M_swap_workaround(_Self& __x) { swap(__x); } 120#endif 121 122 iterator begin() { return _M_ht.begin(); } 123 iterator end() { return _M_ht.end(); } 124 const_iterator begin() const { return _M_ht.begin(); } 125 const_iterator end() const { return _M_ht.end(); } 126 127 pair<iterator, bool> insert(const value_type& __obj) 128 { return _M_ht.insert_unique(__obj); } 129 iterator insert(const_iterator /*__hint*/, const value_type& __obj) 130 { return _M_ht.insert_unique(__obj); } 131#if defined (_STLP_MEMBER_TEMPLATES) 132 template <class _InputIterator> 133 void insert(_InputIterator __f, _InputIterator __l) 134#else 135 void insert(const_iterator __f, const_iterator __l) 136 {_M_ht.insert_unique(__f, __l); } 137 void insert(const value_type* __f, const value_type* __l) 138#endif 139 { _M_ht.insert_unique(__f,__l); } 140 141 _STLP_TEMPLATE_FOR_CONT_EXT 142 iterator find(const _KT& __key) { return _M_ht.find(__key); } 143 _STLP_TEMPLATE_FOR_CONT_EXT 144 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); } 145 146 _STLP_TEMPLATE_FOR_CONT_EXT 147 size_type count(const _KT& __key) const { return _M_ht.count(__key); } 148 149 _STLP_TEMPLATE_FOR_CONT_EXT 150 pair<iterator, iterator> equal_range(const _KT& __key) 151 { return _M_ht.equal_range(__key); } 152 _STLP_TEMPLATE_FOR_CONT_EXT 153 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const 154 { return _M_ht.equal_range(__key); } 155 156 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 157 void erase(const_iterator __it) { _M_ht.erase(__it); } 158 void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); } 159 void clear() { _M_ht.clear(); } 160 161 size_type bucket_count() const { return _M_ht.bucket_count(); } 162 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 163 size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); } 164 _STLP_TEMPLATE_FOR_CONT_EXT 165 size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); } 166 local_iterator begin(size_type __n) { return _M_ht.begin(__n); } 167 local_iterator end(size_type __n) { return _M_ht.end(__n); } 168 const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); } 169 const_local_iterator end(size_type __n) const { return _M_ht.end(__n); } 170 171 float load_factor() const { return _M_ht.load_factor(); } 172 float max_load_factor() const { return _M_ht.max_load_factor(); } 173 void max_load_factor(float __val) { _M_ht.max_load_factor(__val); } 174 void rehash(size_type __hint) { _M_ht.rehash(__hint); } 175}; 176 177_STLP_END_NAMESPACE 178 179//Specific iterator traits creation 180_STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMultisetTraitsT, Const_traits) 181 182_STLP_BEGIN_TR1_NAMESPACE 183 184template <class _Value, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Value>), 185 _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Value>), 186 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Value>) > 187class unordered_multiset 188#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 189 : public __stlport_class<unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > 190#endif 191{ 192 typedef unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Self; 193 //Specific iterator traits creation 194 typedef _STLP_PRIV _UnorderedMultisetTraitsT<_Value> _UnorderedMultisetTraits; 195public: 196 typedef hashtable<_Value, _Value, _HashFcn, 197 _UnorderedMultisetTraits, _STLP_PRIV _Identity<_Value>, _EqualKey, _Alloc> _Ht; 198 199 typedef typename _Ht::key_type key_type; 200 typedef typename _Ht::value_type value_type; 201 typedef typename _Ht::hasher hasher; 202 typedef typename _Ht::key_equal key_equal; 203 204 typedef typename _Ht::size_type size_type; 205 typedef typename _Ht::difference_type difference_type; 206 typedef typename _Ht::pointer pointer; 207 typedef typename _Ht::const_pointer const_pointer; 208 typedef typename _Ht::reference reference; 209 typedef typename _Ht::const_reference const_reference; 210 211 typedef typename _Ht::iterator iterator; 212 typedef typename _Ht::const_iterator const_iterator; 213 typedef typename _Ht::local_iterator local_iterator; 214 typedef typename _Ht::const_local_iterator const_local_iterator; 215 216 typedef typename _Ht::allocator_type allocator_type; 217 218 hasher hash_function() const { return _M_ht.hash_funct(); } 219 key_equal key_eq() const { return _M_ht.key_eq(); } 220 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 221 222private: 223 _Ht _M_ht; 224 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 225 226public: 227 explicit unordered_multiset(size_type __n = 0, const hasher& __hf = hasher(), 228 const key_equal& __eql = key_equal(), 229 const allocator_type& __a = allocator_type()) 230 : _M_ht(__n, __hf, __eql, __a) {} 231 232#if !defined (_STLP_NO_MOVE_SEMANTIC) 233 unordered_multiset(__move_source<_Self> src) 234 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {} 235#endif 236 237#if defined (_STLP_MEMBER_TEMPLATES) 238 template <class _InputIterator> 239 unordered_multiset(_InputIterator __f, _InputIterator __l, 240 size_type __n = 0, const hasher& __hf = hasher(), 241 const key_equal& __eql = key_equal(), 242 const allocator_type& __a = allocator_type()) 243 : _M_ht(__n, __hf, __eql, __a) 244 { _M_ht.insert_equal(__f, __l); } 245#else 246 unordered_multiset(const value_type* __f, const value_type* __l, 247 size_type __n = 0, const hasher& __hf = hasher(), 248 const key_equal& __eql = key_equal(), 249 const allocator_type& __a = allocator_type()) 250 : _M_ht(__n, __hf, __eql, __a) 251 { _M_ht.insert_equal(__f, __l); } 252 253 unordered_multiset(const_iterator __f, const_iterator __l, 254 size_type __n = 0, const hasher& __hf = hasher(), 255 const key_equal& __eql = key_equal(), 256 const allocator_type& __a = allocator_type()) 257 : _M_ht(__n, __hf, __eql, __a) 258 { _M_ht.insert_equal(__f, __l); } 259#endif /*_STLP_MEMBER_TEMPLATES */ 260 261 _Self& operator = (const _Self& __other) 262 { _M_ht = __other._M_ht; return *this; } 263 264 size_type size() const { return _M_ht.size(); } 265 size_type max_size() const { return _M_ht.max_size(); } 266 bool empty() const { return _M_ht.empty(); } 267 void swap(_Self& hs) { _M_ht.swap(hs._M_ht); } 268#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 269 void _M_swap_workaround(_Self& __x) { swap(__x); } 270#endif 271 272 iterator begin() { return _M_ht.begin(); } 273 iterator end() { return _M_ht.end(); } 274 const_iterator begin() const { return _M_ht.begin(); } 275 const_iterator end() const { return _M_ht.end(); } 276 277 iterator insert(const value_type& __obj) 278 { return _M_ht.insert_equal(__obj); } 279 iterator insert(const_iterator /*__hint*/, const value_type& __obj) 280 { return _M_ht.insert_equal(__obj); } 281#if defined (_STLP_MEMBER_TEMPLATES) 282 template <class _InputIterator> 283 void insert(_InputIterator __f, _InputIterator __l) 284#else 285 void insert(const value_type* __f, const value_type* __l) 286 { _M_ht.insert_equal(__f,__l); } 287 void insert(const_iterator __f, const_iterator __l) 288#endif /*_STLP_MEMBER_TEMPLATES */ 289 { _M_ht.insert_equal(__f, __l); } 290 291 _STLP_TEMPLATE_FOR_CONT_EXT 292 iterator find(const _KT& __key) { return _M_ht.find(__key); } 293 _STLP_TEMPLATE_FOR_CONT_EXT 294 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); } 295 296 _STLP_TEMPLATE_FOR_CONT_EXT 297 size_type count(const _KT& __key) const { return _M_ht.count(__key); } 298 299 _STLP_TEMPLATE_FOR_CONT_EXT 300 pair<iterator, iterator> equal_range(const _KT& __key) 301 { return _M_ht.equal_range(__key); } 302 _STLP_TEMPLATE_FOR_CONT_EXT 303 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const 304 { return _M_ht.equal_range(__key); } 305 306 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 307 void erase(const_iterator __it) { _M_ht.erase(__it); } 308 void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); } 309 void clear() { _M_ht.clear(); } 310 311 size_type bucket_count() const { return _M_ht.bucket_count(); } 312 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 313 size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); } 314 _STLP_TEMPLATE_FOR_CONT_EXT 315 size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); } 316 local_iterator begin(size_type __n) { return _M_ht.begin(__n); } 317 local_iterator end(size_type __n) { return _M_ht.end(__n); } 318 const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); } 319 const_local_iterator end(size_type __n) const { return _M_ht.end(__n); } 320 321 float load_factor() const { return _M_ht.load_factor(); } 322 float max_load_factor() const { return _M_ht.max_load_factor(); } 323 void max_load_factor(float __val) { _M_ht.max_load_factor(__val); } 324 void rehash(size_type __hint) { _M_ht.rehash(__hint); } 325}; 326 327#define _STLP_TEMPLATE_HEADER template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 328#define _STLP_TEMPLATE_CONTAINER unordered_set<_Value,_HashFcn,_EqualKey,_Alloc> 329 330#include <stl/_relops_hash_cont.h> 331 332#undef _STLP_TEMPLATE_CONTAINER 333#define _STLP_TEMPLATE_CONTAINER unordered_multiset<_Value,_HashFcn,_EqualKey,_Alloc> 334#include <stl/_relops_hash_cont.h> 335 336#undef _STLP_TEMPLATE_CONTAINER 337#undef _STLP_TEMPLATE_HEADER 338 339_STLP_END_NAMESPACE 340 341// Specialization of insert_iterator so that it will work for unordered_set 342// and unordered_multiset. 343 344#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 345# if !defined (_STLP_NO_MOVE_SEMANTIC) 346template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 347struct __move_traits<_STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> > : 348 _STLP_PRIV __move_traits_aux<typename _STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc>::_Ht> 349{}; 350 351template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 352struct __move_traits<_STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > : 353 _STLP_PRIV __move_traits_aux<typename _STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc>::_Ht> 354{}; 355# endif 356 357template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 358class insert_iterator<_STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> > { 359protected: 360 typedef _STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container; 361 _Container* container; 362public: 363 typedef _Container container_type; 364 typedef output_iterator_tag iterator_category; 365 typedef void value_type; 366 typedef void difference_type; 367 typedef void pointer; 368 typedef void reference; 369 370 insert_iterator(_Container& __x) : container(&__x) {} 371 insert_iterator(_Container& __x, typename _Container::iterator) 372 : container(&__x) {} 373 insert_iterator<_Container>& 374 operator=(const typename _Container::value_type& __val) { 375 container->insert(__val); 376 return *this; 377 } 378 insert_iterator<_Container>& operator*() { return *this; } 379 insert_iterator<_Container>& operator++() { return *this; } 380 insert_iterator<_Container>& operator++(int) { return *this; } 381}; 382 383template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 384class insert_iterator<_STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > { 385protected: 386 typedef _STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container; 387 _Container* container; 388 typename _Container::iterator iter; 389public: 390 typedef _Container container_type; 391 typedef output_iterator_tag iterator_category; 392 typedef void value_type; 393 typedef void difference_type; 394 typedef void pointer; 395 typedef void reference; 396 397 insert_iterator(_Container& __x) : container(&__x) {} 398 insert_iterator(_Container& __x, typename _Container::iterator) 399 : container(&__x) {} 400 insert_iterator<_Container>& 401 operator=(const typename _Container::value_type& __val) { 402 container->insert(__val); 403 return *this; 404 } 405 insert_iterator<_Container>& operator*() { return *this; } 406 insert_iterator<_Container>& operator++() { return *this; } 407 insert_iterator<_Container>& operator++(int) { return *this; } 408}; 409#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 410 411_STLP_END_NAMESPACE 412 413#endif /* _STLP_INTERNAL_UNORDERED_SET_H */ 414 415// Local Variables: 416// mode:C++ 417// End: 418 419