lib/3rdparty/stlport/stlport/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 _STLP_BEGIN_TR1_NAMESPACE
  33
  34 template <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>) >
  37 class 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;
  45 public:
  46   typedef hashtable<_Value, _Value, _HashFcn,
  47                     _UnorderedSetTraits, _STLP_PRIV _Identity<_Value>, _EqualKey, _Alloc> _Ht;
  48 public:
  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
  72 private:
  73   _Ht _M_ht;
  74   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
  75
  76 public:
  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
 184 template <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>) >
 187 class 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;
 195 public:
 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
 222 private:
 223   _Ht _M_ht;
 224   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
 225
 226 public:
 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)
 346 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 347 struct __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
 351 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 352 struct __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
 357 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 358 class insert_iterator<_STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
 359 protected:
 360   typedef _STLP_TR1 unordered_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
 361   _Container* container;
 362 public:
 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
 383 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 384 class insert_iterator<_STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
 385 protected:
 386   typedef _STLP_TR1 unordered_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
 387   _Container* container;
 388   typename _Container::iterator iter;
 389 public:
 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