include/c++/stl/stl/_unordered_set.h

   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 template <class _Value, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Value>),
  33           _STLP_DFL_TMPL_PARAM(_EqualKey,equal_to<_Value>),
  34           _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) >
  35 class unordered_set
  36 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
  37                : public __stlport_class<unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> >
  38 #endif
  39 {
  40   typedef unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> _Self;
  41   //Specific iterator traits creation
  42   typedef _STLP_PRIV _UnorderedSetTraitsT<_Value> _UnorderedSetTraits;
  43 public:
  44   typedef hashtable<_Value, _Value, _HashFcn,
  45                     _UnorderedSetTraits, _STLP_PRIV _Identity<_Value>, _EqualKey, _Alloc> _Ht;
  46 public:
  47   typedef typename _Ht::key_type key_type;
  48   typedef typename _Ht::value_type value_type;
  49   typedef typename _Ht::hasher hasher;
  50   typedef typename _Ht::key_equal key_equal;
  51
  52   typedef typename _Ht::size_type size_type;
  53   typedef typename _Ht::difference_type difference_type;
  54   typedef typename _Ht::pointer         pointer;
  55   typedef typename _Ht::const_pointer   const_pointer;
  56   typedef typename _Ht::reference       reference;
  57   typedef typename _Ht::const_reference const_reference;
  58
  59   typedef typename _Ht::iterator iterator;
  60   typedef typename _Ht::const_iterator const_iterator;
  61   typedef typename _Ht::local_iterator local_iterator;
  62   typedef typename _Ht::const_local_iterator const_local_iterator;
  63
  64   typedef typename _Ht::allocator_type allocator_type;
  65
  66   hasher hash_function() const { return _M_ht.hash_funct(); }
  67   key_equal key_eq() const { return _M_ht.key_eq(); }
  68   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
  69
  70 private:
  71   _Ht _M_ht;
  72   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
  73
  74 public:
  75   explicit unordered_set(size_type __n = 100, const hasher& __hf = hasher(),
  76                          const key_equal& __eql = key_equal(),
  77                          const allocator_type& __a = allocator_type())
  78     : _M_ht(__n, __hf, __eql, __a) {}
  79
  80   unordered_set(__move_source<_Self> src)
  81     : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {}
  82
  83 #if defined (_STLP_MEMBER_TEMPLATES)
  84   template <class _InputIterator>
  85   unordered_set(_InputIterator __f, _InputIterator __l,
  86                 size_type __n = 100, const hasher& __hf = hasher(),
  87                 const key_equal& __eql = key_equal(),
  88                 const allocator_type& __a = allocator_type())
  89     : _M_ht(__n, __hf, __eql, __a)
  90   { _M_ht.insert_unique(__f, __l); }
  91 #else
  92   unordered_set(const value_type* __f, const value_type* __l,
  93                 size_type __n = 100, const hasher& __hf = hasher(),
  94                 const key_equal& __eql = key_equal(),
  95                 const allocator_type& __a = allocator_type())
  96     : _M_ht(__n, __hf, __eql, __a)
  97   { _M_ht.insert_unique(__f, __l); }
  98
  99   unordered_set(const_iterator __f, const_iterator __l,
 100                 size_type __n = 100, const hasher& __hf = hasher(),
 101                 const key_equal& __eql = key_equal(),
 102                 const allocator_type& __a = allocator_type())
 103     : _M_ht(__n, __hf, __eql, __a)
 104   { _M_ht.insert_unique(__f, __l); }
 105 #endif /*_STLP_MEMBER_TEMPLATES */
 106
 107   _Self& operator = (const _Self& __other)
 108   { _M_ht = __other._M_ht; return *this; }
 109
 110   size_type size() const { return _M_ht.size(); }
 111   size_type max_size() const { return _M_ht.max_size(); }
 112   bool empty() const { return _M_ht.empty(); }
 113   void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
 114
 115   iterator begin() { return _M_ht.begin(); }
 116   iterator end() { return _M_ht.end(); }
 117   const_iterator begin() const { return _M_ht.begin(); }
 118   const_iterator end() const { return _M_ht.end(); }
 119
 120   pair<iterator, bool> insert(const value_type& __obj)
 121   { return _M_ht.insert_unique(__obj); }
 122   iterator insert(const_iterator /*__hint*/, const value_type& __obj)
 123   { return _M_ht.insert_unique(__obj); }
 124 #if defined (_STLP_MEMBER_TEMPLATES)
 125   template <class _InputIterator>
 126   void insert(_InputIterator __f, _InputIterator __l)
 127 #else
 128   void insert(const_iterator __f, const_iterator __l)
 129   {_M_ht.insert_unique(__f, __l); }
 130   void insert(const value_type* __f, const value_type* __l)
 131 #endif
 132   { _M_ht.insert_unique(__f,__l); }
 133
 134   _STLP_TEMPLATE_FOR_CONT_EXT
 135   iterator find(const _KT& __key) { return _M_ht.find(__key); }
 136   _STLP_TEMPLATE_FOR_CONT_EXT
 137   const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
 138
 139   _STLP_TEMPLATE_FOR_CONT_EXT
 140   size_type count(const _KT& __key) const { return _M_ht.count(__key); }
 141
 142   _STLP_TEMPLATE_FOR_CONT_EXT
 143   pair<iterator, iterator> equal_range(const _KT& __key)
 144   { return _M_ht.equal_range(__key); }
 145   _STLP_TEMPLATE_FOR_CONT_EXT
 146   pair<const_iterator, const_iterator> equal_range(const _KT& __key) const
 147   { return _M_ht.equal_range(__key); }
 148
 149   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
 150   void erase(const_iterator __it) { _M_ht.erase(__it); }
 151   void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); }
 152   void clear() { _M_ht.clear(); }
 153
 154   size_type bucket_count() const { return _M_ht.bucket_count(); }
 155   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 156   size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); }
 157   _STLP_TEMPLATE_FOR_CONT_EXT
 158   size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); }
 159   local_iterator begin(size_type __n) { return _M_ht.begin(__n); }
 160   local_iterator end(size_type __n) { return _M_ht.end(__n); }
 161   const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); }
 162   const_local_iterator end(size_type __n) const { return _M_ht.end(__n); }
 163
 164   float load_factor() const { return _M_ht.load_factor(); }
 165   float max_load_factor() const { return _M_ht.max_load_factor(); }
 166   void max_load_factor(float __val) { _M_ht.max_load_factor(__val); }
 167   void rehash(size_type __hint) { _M_ht.rehash(__hint); }
 168 };
 169
 170 //Specific iterator traits creation
 171 _STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMultisetTraitsT, Const_traits)
 172
 173 template <class _Value, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Value>),
 174           _STLP_DFL_TMPL_PARAM(_EqualKey,equal_to<_Value>),
 175           _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) >
 176 class unordered_multiset
 177 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
 178                : public __stlport_class<unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> >
 179 #endif
 180 {
 181   typedef unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Self;
 182   //Specific iterator traits creation
 183   typedef _STLP_PRIV _UnorderedMultisetTraitsT<_Value> _UnorderedMultisetTraits;
 184 public:
 185   typedef hashtable<_Value, _Value, _HashFcn,
 186                     _UnorderedMultisetTraits, _STLP_PRIV _Identity<_Value>, _EqualKey, _Alloc> _Ht;
 187
 188   typedef typename _Ht::key_type key_type;
 189   typedef typename _Ht::value_type value_type;
 190   typedef typename _Ht::hasher hasher;
 191   typedef typename _Ht::key_equal key_equal;
 192
 193   typedef typename _Ht::size_type size_type;
 194   typedef typename _Ht::difference_type difference_type;
 195   typedef typename _Ht::pointer       pointer;
 196   typedef typename _Ht::const_pointer const_pointer;
 197   typedef typename _Ht::reference reference;
 198   typedef typename _Ht::const_reference const_reference;
 199
 200   typedef typename _Ht::iterator iterator;
 201   typedef typename _Ht::const_iterator const_iterator;
 202   typedef typename _Ht::local_iterator local_iterator;
 203   typedef typename _Ht::const_local_iterator const_local_iterator;
 204
 205   typedef typename _Ht::allocator_type allocator_type;
 206
 207   hasher hash_function() const { return _M_ht.hash_funct(); }
 208   key_equal key_eq() const { return _M_ht.key_eq(); }
 209   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
 210
 211 private:
 212   _Ht _M_ht;
 213   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
 214
 215 public:
 216   explicit unordered_multiset(size_type __n = 100, const hasher& __hf = hasher(),
 217                               const key_equal& __eql = key_equal(),
 218                               const allocator_type& __a = allocator_type())
 219     : _M_ht(__n, __hf, __eql, __a) {}
 220
 221   unordered_multiset(__move_source<_Self> src)
 222     : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {}
 223
 224 #if defined (_STLP_MEMBER_TEMPLATES)
 225   template <class _InputIterator>
 226   unordered_multiset(_InputIterator __f, _InputIterator __l,
 227                      size_type __n = 100, 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   { _M_ht.insert_equal(__f, __l); }
 232 #else
 233   unordered_multiset(const value_type* __f, const value_type* __l,
 234                      size_type __n = 100, const hasher& __hf = hasher(),
 235                      const key_equal& __eql = key_equal(),
 236                      const allocator_type& __a = allocator_type())
 237     : _M_ht(__n, __hf, __eql, __a)
 238   { _M_ht.insert_equal(__f, __l); }
 239
 240   unordered_multiset(const_iterator __f, const_iterator __l,
 241                      size_type __n = 100, const hasher& __hf = hasher(),
 242                      const key_equal& __eql = key_equal(),
 243                      const allocator_type& __a = allocator_type())
 244     : _M_ht(__n, __hf, __eql, __a)
 245   { _M_ht.insert_equal(__f, __l); }
 246 #endif /*_STLP_MEMBER_TEMPLATES */
 247
 248   _Self& operator = (const _Self& __other)
 249   { _M_ht = __other._M_ht; return *this; }
 250
 251   size_type size() const { return _M_ht.size(); }
 252   size_type max_size() const { return _M_ht.max_size(); }
 253   bool empty() const { return _M_ht.empty(); }
 254   void swap(_Self& hs) { _M_ht.swap(hs._M_ht); }
 255
 256   iterator begin() { return _M_ht.begin(); }
 257   iterator end() { return _M_ht.end(); }
 258   const_iterator begin() const { return _M_ht.begin(); }
 259   const_iterator end() const { return _M_ht.end(); }
 260
 261   iterator insert(const value_type& __obj)
 262   { return _M_ht.insert_equal(__obj); }
 263   iterator insert(const_iterator /*__hint*/, const value_type& __obj)
 264   { return _M_ht.insert_equal(__obj); }
 265 #if defined (_STLP_MEMBER_TEMPLATES)
 266   template <class _InputIterator>
 267   void insert(_InputIterator __f, _InputIterator __l)
 268 #else
 269   void insert(const value_type* __f, const value_type* __l)
 270   { _M_ht.insert_equal(__f,__l); }
 271   void insert(const_iterator __f, const_iterator __l)
 272 #endif /*_STLP_MEMBER_TEMPLATES */
 273   { _M_ht.insert_equal(__f, __l); }
 274
 275   _STLP_TEMPLATE_FOR_CONT_EXT
 276   iterator find(const _KT& __key) { return _M_ht.find(__key); }
 277   _STLP_TEMPLATE_FOR_CONT_EXT
 278   const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
 279
 280   _STLP_TEMPLATE_FOR_CONT_EXT
 281   size_type count(const _KT& __key) const { return _M_ht.count(__key); }
 282
 283   _STLP_TEMPLATE_FOR_CONT_EXT
 284   pair<iterator, iterator> equal_range(const _KT& __key)
 285   { return _M_ht.equal_range(__key); }
 286   _STLP_TEMPLATE_FOR_CONT_EXT
 287   pair<const_iterator, const_iterator> equal_range(const _KT& __key) const
 288   { return _M_ht.equal_range(__key); }
 289
 290   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
 291   void erase(const_iterator __it) { _M_ht.erase(__it); }
 292   void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); }
 293   void clear() { _M_ht.clear(); }
 294
 295   size_type bucket_count() const { return _M_ht.bucket_count(); }
 296   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 297   size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); }
 298   _STLP_TEMPLATE_FOR_CONT_EXT
 299   size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); }
 300   local_iterator begin(size_type __n) { return _M_ht.begin(__n); }
 301   local_iterator end(size_type __n) { return _M_ht.end(__n); }
 302   const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); }
 303   const_local_iterator end(size_type __n) const { return _M_ht.end(__n); }
 304
 305   float load_factor() const { return _M_ht.load_factor(); }
 306   float max_load_factor() const { return _M_ht.max_load_factor(); }
 307   void max_load_factor(float __val) { _M_ht.max_load_factor(__val); }
 308   void rehash(size_type __hint) { _M_ht.rehash(__hint); }
 309 };
 310
 311 #define _STLP_TEMPLATE_HEADER template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 312 #define _STLP_TEMPLATE_CONTAINER unordered_set<_Value,_HashFcn,_EqualKey,_Alloc>
 313
 314 #include <stl/_relops_hash_cont.h>
 315
 316 #undef _STLP_TEMPLATE_CONTAINER
 317 #define _STLP_TEMPLATE_CONTAINER unordered_multiset<_Value,_HashFcn,_EqualKey,_Alloc>
 318 #include <stl/_relops_hash_cont.h>
 319
 320 #undef _STLP_TEMPLATE_CONTAINER
 321 #undef _STLP_TEMPLATE_HEADER
 322
 323 // Specialization of insert_iterator so that it will work for unordered_set
 324 // and unordered_multiset.
 325
 326 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
 327 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 328 struct __move_traits<unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> > :
 329   _STLP_PRIV __move_traits_aux<typename unordered_set<_Value, _HashFcn, _EqualKey, _Alloc>::_Ht>
 330 {};
 331
 332 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 333 struct __move_traits<unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > :
 334   _STLP_PRIV __move_traits_aux<typename unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc>::_Ht>
 335 {};
 336
 337 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 338 class insert_iterator<unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
 339 protected:
 340   typedef unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
 341   _Container* container;
 342 public:
 343   typedef _Container          container_type;
 344   typedef output_iterator_tag iterator_category;
 345   typedef void                value_type;
 346   typedef void                difference_type;
 347   typedef void                pointer;
 348   typedef void                reference;
 349
 350   insert_iterator(_Container& __x) : container(&__x) {}
 351   insert_iterator(_Container& __x, typename _Container::iterator)
 352     : container(&__x) {}
 353   insert_iterator<_Container>&
 354   operator=(const typename _Container::value_type& __val) {
 355     container->insert(__val);
 356     return *this;
 357   }
 358   insert_iterator<_Container>& operator*() { return *this; }
 359   insert_iterator<_Container>& operator++() { return *this; }
 360   insert_iterator<_Container>& operator++(int) { return *this; }
 361 };
 362
 363 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 364 class insert_iterator<unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
 365 protected:
 366   typedef unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
 367   _Container* container;
 368   typename _Container::iterator iter;
 369 public:
 370   typedef _Container          container_type;
 371   typedef output_iterator_tag iterator_category;
 372   typedef void                value_type;
 373   typedef void                difference_type;
 374   typedef void                pointer;
 375   typedef void                reference;
 376
 377   insert_iterator(_Container& __x) : container(&__x) {}
 378   insert_iterator(_Container& __x, typename _Container::iterator)
 379     : container(&__x) {}
 380   insert_iterator<_Container>&
 381   operator=(const typename _Container::value_type& __val) {
 382     container->insert(__val);
 383     return *this;
 384   }
 385   insert_iterator<_Container>& operator*() { return *this; }
 386   insert_iterator<_Container>& operator++() { return *this; }
 387   insert_iterator<_Container>& operator++(int) { return *this; }
 388 };
 389 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
 390
 391 _STLP_END_NAMESPACE
 392
 393 #endif /* _STLP_INTERNAL_UNORDERED_SET_H */
 394
 395 // Local Variables:
 396 // mode:C++
 397 // End:
 398