libstdc++-v3/include/debug/unordered_set

   1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /** @file debug/unordered_set
  27  *  This file is a GNU debug extension to the Standard C++ Library.
  28  */
  29
  30 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
  31 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
  32
  33 #ifndef __GXX_EXPERIMENTAL_CXX0X__
  34 # include <bits/c++0x_warning.h>
  35 #else
  36 # include <unordered_set>
  37
  38 #include <debug/safe_sequence.h>
  39 #include <debug/safe_iterator.h>
  40
  41 namespace std
  42 {
  43 namespace __debug
  44 {
  45   /// Class std::unordered_set with safety/checking/debug instrumentation.
  46   template<typename _Value,
  47            typename _Hash = std::hash<_Value>,
  48            typename _Pred = std::equal_to<_Value>,
  49            typename _Alloc = std::allocator<_Value> >
  50     class unordered_set
  51     : public _GLIBCXX_STD_D::unordered_set<_Value, _Hash, _Pred, _Alloc>,
  52       public __gnu_debug::_Safe_sequence<unordered_set<_Value, _Hash,
  53                                                        _Pred, _Alloc> >
  54     {
  55       typedef _GLIBCXX_STD_D::unordered_set<_Value, _Hash,
  56                                             _Pred, _Alloc> _Base;
  57       typedef __gnu_debug::_Safe_sequence<unordered_set> _Safe_base;
  58       typedef typename _Base::const_iterator _Base_const_iterator;
  59       typedef typename _Base::iterator _Base_iterator;
  60       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
  61
  62     public:
  63       typedef typename _Base::size_type       size_type;
  64       typedef typename _Base::hasher          hasher;
  65       typedef typename _Base::key_equal       key_equal;
  66       typedef typename _Base::allocator_type  allocator_type;
  67
  68       typedef typename _Base::key_type        key_type;
  69       typedef typename _Base::value_type      value_type;
  70
  71       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
  72                                           unordered_set> iterator;
  73       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
  74                                           unordered_set> const_iterator;
  75
  76       explicit
  77       unordered_set(size_type __n = 10,
  78                     const hasher& __hf = hasher(),
  79                     const key_equal& __eql = key_equal(),
  80                     const allocator_type& __a = allocator_type())
  81       : _Base(__n, __hf, __eql, __a) { }
  82
  83       template<typename _InputIterator>
  84         unordered_set(_InputIterator __first, _InputIterator __last,
  85                       size_type __n = 0,
  86                       const hasher& __hf = hasher(),
  87                       const key_equal& __eql = key_equal(),
  88                       const allocator_type& __a = allocator_type())
  89         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
  90                                                                      __last)),
  91                 __gnu_debug::__base(__last), __n,
  92                 __hf, __eql, __a), _Safe_base() { }
  93
  94       unordered_set(const unordered_set& __x)
  95       : _Base(__x), _Safe_base() { }
  96
  97       unordered_set(const _Base& __x)
  98       : _Base(__x), _Safe_base() { }
  99
 100       unordered_set(unordered_set&& __x)
 101       : _Base(std::move(__x)), _Safe_base() { }
 102
 103       unordered_set(initializer_list<value_type> __l,
 104                     size_type __n = 0,
 105                     const hasher& __hf = hasher(),
 106                     const key_equal& __eql = key_equal(),
 107                     const allocator_type& __a = allocator_type())
 108       : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
 109
 110       unordered_set&
 111       operator=(const unordered_set& __x)
 112       {
 113         *static_cast<_Base*>(this) = __x;
 114         this->_M_invalidate_all();
 115         return *this;
 116       }
 117
 118       unordered_set&
 119       operator=(unordered_set&& __x)
 120       {
 121         // NB: DR 1204.
 122         // NB: DR 675.
 123         clear();
 124         swap(__x);
 125         return *this;
 126       }
 127
 128       unordered_set&
 129       operator=(initializer_list<value_type> __l)
 130       {
 131         this->clear();
 132         this->insert(__l);
 133         return *this;
 134       }
 135
 136       void
 137       swap(unordered_set& __x)
 138       {
 139         _Base::swap(__x);
 140         _Safe_base::_M_swap(__x);
 141       }
 142
 143       void
 144       clear()
 145       {
 146         _Base::clear();
 147         this->_M_invalidate_all();
 148       }
 149
 150       iterator
 151       begin()
 152       { return iterator(_Base::begin(), this); }
 153
 154       const_iterator
 155       begin() const
 156       { return const_iterator(_Base::begin(), this); }
 157
 158       iterator
 159       end()
 160       { return iterator(_Base::end(), this); }
 161
 162       const_iterator
 163       end() const
 164       { return const_iterator(_Base::end(), this); }
 165
 166       const_iterator
 167       cbegin() const
 168       { return const_iterator(_Base::begin(), this); }
 169
 170       const_iterator
 171       cend() const
 172       { return const_iterator(_Base::end(), this); }
 173
 174       // local versions
 175       using _Base::begin;
 176       using _Base::end;
 177       using _Base::cbegin;
 178       using _Base::cend;
 179
 180       std::pair<iterator, bool>
 181       insert(const value_type& __obj)
 182       {
 183         typedef std::pair<_Base_iterator, bool> __pair_type;
 184         __pair_type __res = _Base::insert(__obj);
 185         return std::make_pair(iterator(__res.first, this), __res.second);
 186       }
 187
 188       iterator
 189       insert(const_iterator __hint, const value_type& __obj)
 190       {
 191         __glibcxx_check_insert(__hint);
 192         return iterator(_Base::insert(__hint.base(), __obj), this);
 193       }
 194
 195       std::pair<iterator, bool>
 196       insert(value_type&& __obj)
 197       {
 198         typedef std::pair<typename _Base::iterator, bool> __pair_type;
 199         __pair_type __res = _Base::insert(std::move(__obj));
 200         return std::make_pair(iterator(__res.first, this), __res.second);
 201       }
 202
 203       iterator
 204       insert(const_iterator __hint, value_type&& __obj)
 205       {
 206         __glibcxx_check_insert(__hint);
 207         return iterator(_Base::insert(__hint.base(), std::move(__obj)), this);
 208       }
 209
 210       void
 211       insert(std::initializer_list<value_type> __l)
 212       { _Base::insert(__l); }
 213
 214       template<typename _InputIterator>
 215         void
 216         insert(_InputIterator __first, _InputIterator __last)
 217         {
 218           __glibcxx_check_valid_range(__first, __last);
 219           _Base::insert(__gnu_debug::__base(__first),
 220                         __gnu_debug::__base(__last));
 221         }
 222
 223       iterator
 224       find(const key_type& __key)
 225       { return iterator(_Base::find(__key), this); }
 226
 227       const_iterator
 228       find(const key_type& __key) const
 229       { return const_iterator(_Base::find(__key), this); }
 230
 231       std::pair<iterator, iterator>
 232       equal_range(const key_type& __key)
 233       {
 234         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 235         __pair_type __res = _Base::equal_range(__key);
 236         return std::make_pair(iterator(__res.first, this),
 237                               iterator(__res.second, this));
 238       }
 239
 240       std::pair<const_iterator, const_iterator>
 241       equal_range(const key_type& __key) const
 242       {
 243         std::pair<_Base_const_iterator, _Base_const_iterator>
 244           __res = _Base::equal_range(__key);
 245         return std::make_pair(const_iterator(__res.first, this),
 246                               const_iterator(__res.second, this));
 247       }
 248
 249       size_type
 250       erase(const key_type& __key)
 251       {
 252         size_type __ret(0);
 253         _Base_iterator __victim(_Base::find(__key));
 254         if (__victim != _Base::end())
 255           {
 256             this->_M_invalidate_if(_Equal(__victim));
 257             _Base::erase(__victim);
 258             __ret = 1;
 259           }
 260         return __ret;
 261       }
 262
 263       iterator
 264       erase(const_iterator __it)
 265       {
 266         __glibcxx_check_erase(__it);
 267         this->_M_invalidate_if(_Equal(__it.base()));
 268         return iterator(_Base::erase(__it.base()), this);
 269       }
 270
 271       iterator
 272       erase(const_iterator __first, const_iterator __last)
 273       {
 274         __glibcxx_check_erase_range(__first, __last);
 275         for (_Base_const_iterator __tmp = __first.base();
 276              __tmp != __last.base(); ++__tmp)
 277           {
 278             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 279                                   _M_message(__gnu_debug::__msg_valid_range)
 280                                   ._M_iterator(__first, "first")
 281                                   ._M_iterator(__last, "last"));
 282             this->_M_invalidate_if(_Equal(__tmp));
 283           }
 284         return iterator(_Base::erase(__first.base(),
 285                                      __last.base()), this);
 286       }
 287
 288       _Base&
 289       _M_base() { return *this; }
 290
 291       const _Base&
 292       _M_base() const { return *this; }
 293
 294     private:
 295       void
 296       _M_invalidate_all()
 297       {
 298         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 299         this->_M_invalidate_if(_Not_equal(_Base::end()));
 300       }
 301     };
 302
 303   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 304     inline void
 305     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 306          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 307     { __x.swap(__y); }
 308
 309   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 310     inline bool
 311     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 312                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 313     { return __x._M_equal(__y); }
 314
 315   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 316     inline bool
 317     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 318                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 319     { return !(__x == __y); }
 320
 321
 322   /// Class std::unordered_multiset with safety/checking/debug instrumentation.
 323   template<typename _Value,
 324            typename _Hash = std::hash<_Value>,
 325            typename _Pred = std::equal_to<_Value>,
 326            typename _Alloc = std::allocator<_Value> >
 327     class unordered_multiset
 328     : public _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
 329       public __gnu_debug::_Safe_sequence<unordered_multiset<_Value, _Hash,
 330                                                             _Pred, _Alloc> >
 331     {
 332       typedef _GLIBCXX_STD_D::unordered_multiset<_Value, _Hash,
 333                                                  _Pred, _Alloc> _Base;
 334       typedef __gnu_debug::_Safe_sequence<unordered_multiset> _Safe_base;
 335       typedef typename _Base::const_iterator _Base_const_iterator;
 336       typedef typename _Base::iterator _Base_iterator;
 337       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
 338
 339     public:
 340       typedef typename _Base::size_type       size_type;
 341       typedef typename _Base::hasher          hasher;
 342       typedef typename _Base::key_equal       key_equal;
 343       typedef typename _Base::allocator_type  allocator_type;
 344
 345       typedef typename _Base::key_type        key_type;
 346       typedef typename _Base::value_type      value_type;
 347
 348       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
 349                                           unordered_multiset> iterator;
 350       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
 351                                           unordered_multiset> const_iterator;
 352
 353       explicit
 354       unordered_multiset(size_type __n = 10,
 355                          const hasher& __hf = hasher(),
 356                          const key_equal& __eql = key_equal(),
 357                          const allocator_type& __a = allocator_type())
 358       : _Base(__n, __hf, __eql, __a) { }
 359
 360       template<typename _InputIterator>
 361         unordered_multiset(_InputIterator __first, _InputIterator __last,
 362                            size_type __n = 0,
 363                            const hasher& __hf = hasher(),
 364                            const key_equal& __eql = key_equal(),
 365                            const allocator_type& __a = allocator_type())
 366         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 367                                                                      __last)),
 368                 __gnu_debug::__base(__last), __n,
 369                 __hf, __eql, __a), _Safe_base() { }
 370
 371       unordered_multiset(const unordered_multiset& __x)
 372       : _Base(__x), _Safe_base() { }
 373
 374       unordered_multiset(const _Base& __x)
 375       : _Base(__x), _Safe_base() { }
 376
 377       unordered_multiset(unordered_multiset&& __x)
 378       : _Base(std::move(__x)), _Safe_base() { }
 379
 380       unordered_multiset(initializer_list<value_type> __l,
 381                          size_type __n = 0,
 382                          const hasher& __hf = hasher(),
 383                          const key_equal& __eql = key_equal(),
 384                          const allocator_type& __a = allocator_type())
 385       : _Base(__l, __n, __hf, __eql, __a), _Safe_base() { }
 386
 387       unordered_multiset&
 388       operator=(const unordered_multiset& __x)
 389       {
 390         *static_cast<_Base*>(this) = __x;
 391         this->_M_invalidate_all();
 392         return *this;
 393       }
 394
 395       unordered_multiset&
 396       operator=(unordered_multiset&& __x)
 397       {
 398         // NB: DR 1204.
 399         // NB: DR 675.
 400         clear();
 401         swap(__x);
 402         return *this;
 403       }
 404
 405       unordered_multiset&
 406       operator=(initializer_list<value_type> __l)
 407       {
 408         this->clear();
 409         this->insert(__l);
 410         return *this;
 411       }
 412
 413       void
 414       swap(unordered_multiset& __x)
 415       {
 416         _Base::swap(__x);
 417         _Safe_base::_M_swap(__x);
 418       }
 419
 420       void
 421       clear()
 422       {
 423         _Base::clear();
 424         this->_M_invalidate_all();
 425       }
 426
 427       iterator
 428       begin()
 429       { return iterator(_Base::begin(), this); }
 430
 431       const_iterator
 432       begin() const
 433       { return const_iterator(_Base::begin(), this); }
 434
 435       iterator
 436       end()
 437       { return iterator(_Base::end(), this); }
 438
 439       const_iterator
 440       end() const
 441       { return const_iterator(_Base::end(), this); }
 442
 443       const_iterator
 444       cbegin() const
 445       { return const_iterator(_Base::begin(), this); }
 446
 447       const_iterator
 448       cend() const
 449       { return const_iterator(_Base::end(), this); }
 450
 451       // local versions
 452       using _Base::begin;
 453       using _Base::end;
 454       using _Base::cbegin;
 455       using _Base::cend;
 456
 457       iterator
 458       insert(const value_type& __obj)
 459       { return iterator(_Base::insert(__obj), this); }
 460
 461       iterator
 462       insert(const_iterator __hint, const value_type& __obj)
 463       {
 464         __glibcxx_check_insert(__hint);
 465         return iterator(_Base::insert(__hint.base(), __obj), this);
 466       }
 467
 468       iterator
 469       insert(value_type&& __obj)
 470       { return iterator(_Base::insert(std::move(__obj)), this); }
 471
 472       iterator
 473       insert(const_iterator __hint, value_type&& __obj)
 474       {
 475         __glibcxx_check_insert(__hint);
 476         return iterator(_Base::insert(__hint.base(), std::move(__obj)), this);
 477       }
 478
 479       void
 480       insert(std::initializer_list<value_type> __l)
 481       { _Base::insert(__l); }
 482
 483       template<typename _InputIterator>
 484         void
 485         insert(_InputIterator __first, _InputIterator __last)
 486         {
 487           __glibcxx_check_valid_range(__first, __last);
 488           _Base::insert(__gnu_debug::__base(__first),
 489                         __gnu_debug::__base(__last));
 490         }
 491
 492       iterator
 493       find(const key_type& __key)
 494       { return iterator(_Base::find(__key), this); }
 495
 496       const_iterator
 497       find(const key_type& __key) const
 498       { return const_iterator(_Base::find(__key), this); }
 499
 500       std::pair<iterator, iterator>
 501       equal_range(const key_type& __key)
 502       {
 503         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
 504         __pair_type __res = _Base::equal_range(__key);
 505         return std::make_pair(iterator(__res.first, this),
 506                               iterator(__res.second, this));
 507       }
 508
 509       std::pair<const_iterator, const_iterator>
 510       equal_range(const key_type& __key) const
 511       {
 512         std::pair<_Base_const_iterator, _Base_const_iterator>
 513           __res = _Base::equal_range(__key);
 514         return std::make_pair(const_iterator(__res.first, this),
 515                               const_iterator(__res.second, this));
 516       }
 517
 518       size_type
 519       erase(const key_type& __key)
 520       {
 521         size_type __ret(0);
 522         std::pair<_Base_iterator, _Base_iterator> __pair =
 523           _Base::equal_range(__key);
 524         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
 525           {
 526             this->_M_invalidate_if(_Equal(__victim));
 527             _Base::erase(__victim++);
 528             ++__ret;
 529           }
 530         return __ret;
 531       }
 532
 533       iterator
 534       erase(const_iterator __it)
 535       {
 536         __glibcxx_check_erase(__it);
 537         this->_M_invalidate_if(_Equal(__it.base()));
 538         return iterator(_Base::erase(__it.base()), this);
 539       }
 540
 541       iterator
 542       erase(const_iterator __first, const_iterator __last)
 543       {
 544         __glibcxx_check_erase_range(__first, __last);
 545         for (_Base_const_iterator __tmp = __first.base();
 546              __tmp != __last.base(); ++__tmp)
 547           {
 548             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
 549                                   _M_message(__gnu_debug::__msg_valid_range)
 550                                   ._M_iterator(__first, "first")
 551                                   ._M_iterator(__last, "last"));
 552             this->_M_invalidate_if(_Equal(__tmp));
 553           }
 554         return iterator(_Base::erase(__first.base(),
 555                                      __last.base()), this);
 556       }
 557
 558       _Base&
 559       _M_base() { return *this; }
 560
 561       const _Base&
 562       _M_base() const { return *this; }
 563
 564     private:
 565       void
 566       _M_invalidate_all()
 567       {
 568         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 569         this->_M_invalidate_if(_Not_equal(_Base::end()));
 570       }
 571     };
 572
 573   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 574     inline void
 575     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 576          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 577     { __x.swap(__y); }
 578
 579   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 580     inline bool
 581     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 582                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 583     { return __x._M_equal(__y); }
 584
 585   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 586     inline bool
 587     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 588                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 589     { return !(__x == __y); }
 590
 591 } // namespace __debug
 592 } // namespace std
 593
 594 #endif // __GXX_EXPERIMENTAL_CXX0X__
 595
 596 #endif