Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2003-2013 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the
  7. // terms of the GNU General Public License as published by the
  8. // Free Software Foundation; either version 3, or (at your option)
  9. // any later version.
  10.  
  11. // This library is distributed in the hope that it will be useful,
  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. // GNU General Public License for more details.
  15.  
  16. // Under Section 7 of GPL version 3, you are granted additional
  17. // permissions described in the GCC Runtime Library Exception, version
  18. // 3.1, as published by the Free Software Foundation.
  19.  
  20. // You should have received a copy of the GNU General Public License and
  21. // a copy of the GCC Runtime Library Exception along with this program;
  22. // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23. // <http://www.gnu.org/licenses/>.
  24.  
  25. /** @file debug/unordered_set
  26.  *  This file is a GNU debug extension to the Standard C++ Library.
  27.  */
  28.  
  29. #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
  30. #define _GLIBCXX_DEBUG_UNORDERED_SET 1
  31.  
  32. #if __cplusplus < 201103L
  33. # include <bits/c++0x_warning.h>
  34. #else
  35. # include <unordered_set>
  36.  
  37. #include <debug/safe_unordered_container.h>
  38. #include <debug/safe_iterator.h>
  39. #include <debug/safe_local_iterator.h>
  40.  
  41. namespace std _GLIBCXX_VISIBILITY(default)
  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_C::unordered_set<_Value, _Hash, _Pred, _Alloc>,
  52.       public __gnu_debug::_Safe_unordered_container<unordered_set<_Value, _Hash,
  53.                                                        _Pred, _Alloc> >
  54.     {
  55.       typedef _GLIBCXX_STD_C::unordered_set<_Value, _Hash,
  56.                                             _Pred, _Alloc> _Base;
  57.       typedef __gnu_debug::_Safe_unordered_container<unordered_set> _Safe_base;
  58.       typedef typename _Base::const_iterator _Base_const_iterator;
  59.       typedef typename _Base::iterator _Base_iterator;
  60.       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
  61.       typedef typename _Base::local_iterator _Base_local_iterator;
  62.  
  63.     public:
  64.       typedef typename _Base::size_type       size_type;
  65.       typedef typename _Base::hasher          hasher;
  66.       typedef typename _Base::key_equal       key_equal;
  67.       typedef typename _Base::allocator_type  allocator_type;
  68.  
  69.       typedef typename _Base::key_type        key_type;
  70.       typedef typename _Base::value_type      value_type;
  71.  
  72.       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
  73.                                           unordered_set> iterator;
  74.       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
  75.                                           unordered_set> const_iterator;
  76.       typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator,
  77.                                           unordered_set> local_iterator;
  78.       typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator,
  79.                                           unordered_set> const_local_iterator;
  80.  
  81.       explicit
  82.       unordered_set(size_type __n = 10,
  83.                     const hasher& __hf = hasher(),
  84.                     const key_equal& __eql = key_equal(),
  85.                     const allocator_type& __a = allocator_type())
  86.       : _Base(__n, __hf, __eql, __a) { }
  87.  
  88.       template<typename _InputIterator>
  89.         unordered_set(_InputIterator __first, _InputIterator __last,
  90.                       size_type __n = 0,
  91.                       const hasher& __hf = hasher(),
  92.                       const key_equal& __eql = key_equal(),
  93.                       const allocator_type& __a = allocator_type())
  94.         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
  95.                                                                      __last)),
  96.                 __gnu_debug::__base(__last), __n,
  97.                 __hf, __eql, __a) { }
  98.  
  99.       unordered_set(const unordered_set& __x) = default;
  100.  
  101.       unordered_set(const _Base& __x)
  102.       : _Base(__x) { }
  103.  
  104.       unordered_set(unordered_set&& __x) = default;
  105.  
  106.       unordered_set(initializer_list<value_type> __l,
  107.                     size_type __n = 0,
  108.                     const hasher& __hf = hasher(),
  109.                     const key_equal& __eql = key_equal(),
  110.                     const allocator_type& __a = allocator_type())
  111.       : _Base(__l, __n, __hf, __eql, __a) { }
  112.  
  113.       ~unordered_set() noexcept { }
  114.  
  115.       unordered_set&
  116.       operator=(const unordered_set& __x)
  117.       {
  118.         *static_cast<_Base*>(this) = __x;
  119.         this->_M_invalidate_all();
  120.         return *this;
  121.       }
  122.  
  123.       unordered_set&
  124.       operator=(unordered_set&& __x)
  125.       {
  126.         // NB: DR 1204.
  127.         // NB: DR 675.
  128.         __glibcxx_check_self_move_assign(__x);
  129.         clear();
  130.         swap(__x);
  131.         return *this;
  132.       }
  133.  
  134.       unordered_set&
  135.       operator=(initializer_list<value_type> __l)
  136.       {
  137.         this->clear();
  138.         this->insert(__l);
  139.         return *this;
  140.       }
  141.  
  142.       void
  143.       swap(unordered_set& __x)
  144.       {
  145.         _Base::swap(__x);
  146.         _Safe_base::_M_swap(__x);
  147.       }
  148.  
  149.       void
  150.       clear() noexcept
  151.       {
  152.         _Base::clear();
  153.         this->_M_invalidate_all();
  154.       }
  155.  
  156.       iterator
  157.       begin() noexcept
  158.       { return iterator(_Base::begin(), this); }
  159.  
  160.       const_iterator
  161.       begin() const noexcept
  162.       { return const_iterator(_Base::begin(), this); }
  163.  
  164.       iterator
  165.       end() noexcept
  166.       { return iterator(_Base::end(), this); }
  167.  
  168.       const_iterator
  169.       end() const noexcept
  170.       { return const_iterator(_Base::end(), this); }
  171.  
  172.       const_iterator
  173.       cbegin() const noexcept
  174.       { return const_iterator(_Base::begin(), this); }
  175.  
  176.       const_iterator
  177.       cend() const noexcept
  178.       { return const_iterator(_Base::end(), this); }
  179.  
  180.       // local versions
  181.       local_iterator
  182.       begin(size_type __b)
  183.       {
  184.         __glibcxx_check_bucket_index(__b);
  185.         return local_iterator(_Base::begin(__b), __b, this);
  186.       }
  187.  
  188.       local_iterator
  189.       end(size_type __b)
  190.       {
  191.         __glibcxx_check_bucket_index(__b);
  192.         return local_iterator(_Base::end(__b), __b, this);
  193.       }
  194.  
  195.       const_local_iterator
  196.       begin(size_type __b) const
  197.       {
  198.         __glibcxx_check_bucket_index(__b);
  199.         return const_local_iterator(_Base::begin(__b), __b, this);
  200.       }
  201.  
  202.       const_local_iterator
  203.       end(size_type __b) const
  204.       {
  205.         __glibcxx_check_bucket_index(__b);
  206.         return const_local_iterator(_Base::end(__b), __b, this);
  207.       }
  208.  
  209.       const_local_iterator
  210.       cbegin(size_type __b) const
  211.       {
  212.         __glibcxx_check_bucket_index(__b);
  213.         return const_local_iterator(_Base::cbegin(__b), __b, this);
  214.       }
  215.  
  216.       const_local_iterator
  217.       cend(size_type __b) const
  218.       {
  219.         __glibcxx_check_bucket_index(__b);
  220.         return const_local_iterator(_Base::cend(__b), __b, this);
  221.       }
  222.  
  223.       size_type
  224.       bucket_size(size_type __b) const
  225.       {
  226.         __glibcxx_check_bucket_index(__b);
  227.         return _Base::bucket_size(__b);
  228.       }
  229.  
  230.       float
  231.       max_load_factor() const noexcept
  232.       { return _Base::max_load_factor(); }
  233.  
  234.       void
  235.       max_load_factor(float __f)
  236.       {
  237.         __glibcxx_check_max_load_factor(__f);
  238.         _Base::max_load_factor(__f);
  239.       }
  240.  
  241.       template<typename... _Args>
  242.         std::pair<iterator, bool>
  243.         emplace(_Args&&... __args)
  244.         {
  245.           size_type __bucket_count = this->bucket_count();
  246.           std::pair<_Base_iterator, bool> __res
  247.             = _Base::emplace(std::forward<_Args>(__args)...);
  248.           _M_check_rehashed(__bucket_count);
  249.           return std::make_pair(iterator(__res.first, this), __res.second);
  250.         }
  251.  
  252.       template<typename... _Args>
  253.         iterator
  254.         emplace_hint(const_iterator __hint, _Args&&... __args)
  255.         {
  256.           __glibcxx_check_insert(__hint);
  257.           size_type __bucket_count = this->bucket_count();
  258.           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
  259.                                         std::forward<_Args>(__args)...);
  260.           _M_check_rehashed(__bucket_count);
  261.           return iterator(__it, this);
  262.         }
  263.  
  264.       std::pair<iterator, bool>
  265.       insert(const value_type& __obj)
  266.       {
  267.         size_type __bucket_count = this->bucket_count();
  268.         typedef std::pair<_Base_iterator, bool> __pair_type;
  269.           __pair_type __res = _Base::insert(__obj);
  270.         _M_check_rehashed(__bucket_count);
  271.         return std::make_pair(iterator(__res.first, this), __res.second);
  272.       }
  273.  
  274.       iterator
  275.       insert(const_iterator __hint, const value_type& __obj)
  276.       {
  277.         __glibcxx_check_insert(__hint);
  278.         size_type __bucket_count = this->bucket_count();
  279.         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
  280.         _M_check_rehashed(__bucket_count);
  281.         return iterator(__it, this);
  282.       }
  283.  
  284.       std::pair<iterator, bool>
  285.       insert(value_type&& __obj)
  286.       {
  287.         size_type __bucket_count = this->bucket_count();
  288.         typedef std::pair<typename _Base::iterator, bool> __pair_type;
  289.           __pair_type __res = _Base::insert(std::move(__obj));
  290.         _M_check_rehashed(__bucket_count);
  291.         return std::make_pair(iterator(__res.first, this), __res.second);
  292.       }
  293.  
  294.       iterator
  295.       insert(const_iterator __hint, value_type&& __obj)
  296.       {
  297.         __glibcxx_check_insert(__hint);
  298.         size_type __bucket_count = this->bucket_count();
  299.         _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
  300.         _M_check_rehashed(__bucket_count);
  301.         return iterator(__it, this);
  302.       }
  303.  
  304.       void
  305.       insert(std::initializer_list<value_type> __l)
  306.       {
  307.         size_type __bucket_count = this->bucket_count();
  308.         _Base::insert(__l);
  309.         _M_check_rehashed(__bucket_count);
  310.       }
  311.  
  312.       template<typename _InputIterator>
  313.         void
  314.         insert(_InputIterator __first, _InputIterator __last)
  315.         {
  316.           __glibcxx_check_valid_range(__first, __last);
  317.           size_type __bucket_count = this->bucket_count();
  318.           _Base::insert(__gnu_debug::__base(__first),
  319.                         __gnu_debug::__base(__last));
  320.           _M_check_rehashed(__bucket_count);
  321.         }
  322.  
  323.       iterator
  324.       find(const key_type& __key)
  325.       { return iterator(_Base::find(__key), this); }
  326.  
  327.       const_iterator
  328.       find(const key_type& __key) const
  329.       { return const_iterator(_Base::find(__key), this); }
  330.  
  331.       std::pair<iterator, iterator>
  332.       equal_range(const key_type& __key)
  333.       {
  334.         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
  335.         __pair_type __res = _Base::equal_range(__key);
  336.         return std::make_pair(iterator(__res.first, this),
  337.                               iterator(__res.second, this));
  338.       }
  339.  
  340.       std::pair<const_iterator, const_iterator>
  341.       equal_range(const key_type& __key) const
  342.       {
  343.         std::pair<_Base_const_iterator, _Base_const_iterator>
  344.           __res = _Base::equal_range(__key);
  345.         return std::make_pair(const_iterator(__res.first, this),
  346.                               const_iterator(__res.second, this));
  347.       }
  348.  
  349.       size_type
  350.       erase(const key_type& __key)
  351.       {
  352.         size_type __ret(0);
  353.         _Base_iterator __victim(_Base::find(__key));
  354.         if (__victim != _Base::end())
  355.           {
  356.             this->_M_invalidate_if(
  357.                             [__victim](_Base_const_iterator __it)
  358.                             { return __it == __victim; });
  359.             this->_M_invalidate_local_if(
  360.                             [__victim](_Base_const_local_iterator __it)
  361.                             { return __it._M_cur == __victim._M_cur; });
  362.             size_type __bucket_count = this->bucket_count();
  363.             _Base::erase(__victim);
  364.             _M_check_rehashed(__bucket_count);
  365.             __ret = 1;
  366.           }
  367.         return __ret;
  368.       }
  369.  
  370.       iterator
  371.       erase(const_iterator __it)
  372.       {
  373.         __glibcxx_check_erase(__it);
  374.         _Base_const_iterator __victim = __it.base();
  375.         this->_M_invalidate_if(
  376.                         [__victim](_Base_const_iterator __it)
  377.                         { return __it == __victim; });
  378.         this->_M_invalidate_local_if(
  379.                         [__victim](_Base_const_local_iterator __it)
  380.                         { return __it._M_cur == __victim._M_cur; });
  381.         size_type __bucket_count = this->bucket_count();
  382.         _Base_iterator __next = _Base::erase(__it.base());
  383.         _M_check_rehashed(__bucket_count);
  384.         return iterator(__next, this);
  385.       }
  386.  
  387.       iterator
  388.       erase(iterator __it)
  389.       { return erase(const_iterator(__it)); }
  390.  
  391.       iterator
  392.       erase(const_iterator __first, const_iterator __last)
  393.       {
  394.         __glibcxx_check_erase_range(__first, __last);
  395.         for (_Base_const_iterator __tmp = __first.base();
  396.              __tmp != __last.base(); ++__tmp)
  397.           {
  398.             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
  399.                                   _M_message(__gnu_debug::__msg_valid_range)
  400.                                   ._M_iterator(__first, "first")
  401.                                   ._M_iterator(__last, "last"));
  402.             this->_M_invalidate_if(
  403.                             [__tmp](_Base_const_iterator __it)
  404.                             { return __it == __tmp; });
  405.             this->_M_invalidate_local_if(
  406.                             [__tmp](_Base_const_local_iterator __it)
  407.                             { return __it._M_cur == __tmp._M_cur; });
  408.           }
  409.         size_type __bucket_count = this->bucket_count();
  410.         _Base_iterator __next = _Base::erase(__first.base(),
  411.                                              __last.base());
  412.         _M_check_rehashed(__bucket_count);
  413.         return iterator(__next, this);
  414.       }
  415.  
  416.       _Base&
  417.       _M_base() noexcept       { return *this; }
  418.  
  419.       const _Base&
  420.       _M_base() const noexcept { return *this; }
  421.  
  422.     private:
  423.       void
  424.       _M_invalidate_locals()
  425.       {
  426.         _Base_local_iterator __local_end = _Base::end(0);
  427.         this->_M_invalidate_local_if(
  428.                         [__local_end](_Base_const_local_iterator __it)
  429.                         { return __it != __local_end; });
  430.       }
  431.  
  432.       void
  433.       _M_invalidate_all()
  434.       {
  435.         _Base_iterator __end = _Base::end();
  436.         this->_M_invalidate_if(
  437.                         [__end](_Base_const_iterator __it)
  438.                         { return __it != __end; });
  439.         _M_invalidate_locals();
  440.       }
  441.  
  442.       void
  443.       _M_check_rehashed(size_type __prev_count)
  444.       {
  445.         if (__prev_count != this->bucket_count())
  446.           _M_invalidate_locals();
  447.       }
  448.     };
  449.  
  450.   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
  451.     inline void
  452.     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
  453.          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
  454.     { __x.swap(__y); }
  455.  
  456.   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
  457.     inline bool
  458.     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
  459.                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
  460.     { return __x._M_base() == __y._M_base(); }
  461.  
  462.   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
  463.     inline bool
  464.     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
  465.                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
  466.     { return !(__x == __y); }
  467.  
  468.  
  469.   /// Class std::unordered_multiset with safety/checking/debug instrumentation.
  470.   template<typename _Value,
  471.            typename _Hash = std::hash<_Value>,
  472.            typename _Pred = std::equal_to<_Value>,
  473.            typename _Alloc = std::allocator<_Value> >
  474.     class unordered_multiset
  475.     : public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
  476.       public __gnu_debug::_Safe_unordered_container<
  477.                 unordered_multiset<_Value, _Hash, _Pred, _Alloc> >
  478.     {
  479.       typedef _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash,
  480.                                                  _Pred, _Alloc> _Base;
  481.       typedef __gnu_debug::_Safe_unordered_container<unordered_multiset>
  482.                 _Safe_base;
  483.       typedef typename _Base::const_iterator _Base_const_iterator;
  484.       typedef typename _Base::iterator _Base_iterator;
  485.       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
  486.       typedef typename _Base::local_iterator _Base_local_iterator;
  487.  
  488.     public:
  489.       typedef typename _Base::size_type       size_type;
  490.       typedef typename _Base::hasher          hasher;
  491.       typedef typename _Base::key_equal       key_equal;
  492.       typedef typename _Base::allocator_type  allocator_type;
  493.  
  494.       typedef typename _Base::key_type        key_type;
  495.       typedef typename _Base::value_type      value_type;
  496.  
  497.       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
  498.                                           unordered_multiset> iterator;
  499.       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
  500.                                           unordered_multiset> const_iterator;
  501.       typedef __gnu_debug::_Safe_local_iterator<
  502.         _Base_local_iterator, unordered_multiset> local_iterator;
  503.       typedef __gnu_debug::_Safe_local_iterator<
  504.         _Base_const_local_iterator, unordered_multiset> const_local_iterator;
  505.  
  506.       explicit
  507.       unordered_multiset(size_type __n = 10,
  508.                          const hasher& __hf = hasher(),
  509.                          const key_equal& __eql = key_equal(),
  510.                          const allocator_type& __a = allocator_type())
  511.       : _Base(__n, __hf, __eql, __a) { }
  512.  
  513.       template<typename _InputIterator>
  514.         unordered_multiset(_InputIterator __first, _InputIterator __last,
  515.                            size_type __n = 0,
  516.                            const hasher& __hf = hasher(),
  517.                            const key_equal& __eql = key_equal(),
  518.                            const allocator_type& __a = allocator_type())
  519.         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
  520.                                                                      __last)),
  521.                 __gnu_debug::__base(__last), __n,
  522.                 __hf, __eql, __a) { }
  523.  
  524.       unordered_multiset(const unordered_multiset& __x) = default;
  525.  
  526.       unordered_multiset(const _Base& __x)
  527.       : _Base(__x) { }
  528.  
  529.       unordered_multiset(unordered_multiset&& __x) = default;
  530.  
  531.       unordered_multiset(initializer_list<value_type> __l,
  532.                          size_type __n = 0,
  533.                          const hasher& __hf = hasher(),
  534.                          const key_equal& __eql = key_equal(),
  535.                          const allocator_type& __a = allocator_type())
  536.       : _Base(__l, __n, __hf, __eql, __a) { }
  537.  
  538.       ~unordered_multiset() noexcept { }
  539.  
  540.       unordered_multiset&
  541.       operator=(const unordered_multiset& __x)
  542.       {
  543.         *static_cast<_Base*>(this) = __x;
  544.         this->_M_invalidate_all();
  545.         return *this;
  546.       }
  547.  
  548.       unordered_multiset&
  549.       operator=(unordered_multiset&& __x)
  550.       {
  551.         // NB: DR 1204.
  552.         // NB: DR 675.
  553.         __glibcxx_check_self_move_assign(__x);
  554.         clear();
  555.         swap(__x);
  556.         return *this;
  557.       }
  558.  
  559.       unordered_multiset&
  560.       operator=(initializer_list<value_type> __l)
  561.       {
  562.         this->clear();
  563.         this->insert(__l);
  564.         return *this;
  565.       }
  566.  
  567.       void
  568.       swap(unordered_multiset& __x)
  569.       {
  570.         _Base::swap(__x);
  571.         _Safe_base::_M_swap(__x);
  572.       }
  573.  
  574.       void
  575.       clear() noexcept
  576.       {
  577.         _Base::clear();
  578.         this->_M_invalidate_all();
  579.       }
  580.  
  581.       iterator
  582.       begin() noexcept
  583.       { return iterator(_Base::begin(), this); }
  584.  
  585.       const_iterator
  586.       begin() const noexcept
  587.       { return const_iterator(_Base::begin(), this); }
  588.  
  589.       iterator
  590.       end() noexcept
  591.       { return iterator(_Base::end(), this); }
  592.  
  593.       const_iterator
  594.       end() const noexcept
  595.       { return const_iterator(_Base::end(), this); }
  596.  
  597.       const_iterator
  598.       cbegin() const noexcept
  599.       { return const_iterator(_Base::begin(), this); }
  600.  
  601.       const_iterator
  602.       cend() const noexcept
  603.       { return const_iterator(_Base::end(), this); }
  604.  
  605.       // local versions
  606.       local_iterator
  607.       begin(size_type __b)
  608.       {
  609.         __glibcxx_check_bucket_index(__b);
  610.         return local_iterator(_Base::begin(__b), __b, this);
  611.       }
  612.  
  613.       local_iterator
  614.       end(size_type __b)
  615.       {
  616.         __glibcxx_check_bucket_index(__b);
  617.         return local_iterator(_Base::end(__b), __b, this);
  618.       }
  619.  
  620.       const_local_iterator
  621.       begin(size_type __b) const
  622.       {
  623.         __glibcxx_check_bucket_index(__b);
  624.         return const_local_iterator(_Base::begin(__b), __b, this);
  625.       }
  626.  
  627.       const_local_iterator
  628.       end(size_type __b) const
  629.       {
  630.         __glibcxx_check_bucket_index(__b);
  631.         return const_local_iterator(_Base::end(__b), __b, this);
  632.       }
  633.  
  634.       const_local_iterator
  635.       cbegin(size_type __b) const
  636.       {
  637.         __glibcxx_check_bucket_index(__b);
  638.         return const_local_iterator(_Base::cbegin(__b), __b, this);
  639.       }
  640.  
  641.       const_local_iterator
  642.       cend(size_type __b) const
  643.       {
  644.         __glibcxx_check_bucket_index(__b);
  645.         return const_local_iterator(_Base::cend(__b), __b, this);
  646.       }
  647.  
  648.       size_type
  649.       bucket_size(size_type __b) const
  650.       {
  651.         __glibcxx_check_bucket_index(__b);
  652.         return _Base::bucket_size(__b);
  653.       }
  654.  
  655.       float
  656.       max_load_factor() const noexcept
  657.       { return _Base::max_load_factor(); }
  658.  
  659.       void
  660.       max_load_factor(float __f)
  661.       {
  662.         __glibcxx_check_max_load_factor(__f);
  663.         _Base::max_load_factor(__f);
  664.       }
  665.  
  666.       template<typename... _Args>
  667.         iterator
  668.         emplace(_Args&&... __args)
  669.         {
  670.           size_type __bucket_count = this->bucket_count();
  671.           _Base_iterator __it
  672.             = _Base::emplace(std::forward<_Args>(__args)...);
  673.           _M_check_rehashed(__bucket_count);
  674.           return iterator(__it, this);
  675.         }
  676.  
  677.       template<typename... _Args>
  678.         iterator
  679.         emplace_hint(const_iterator __hint, _Args&&... __args)
  680.         {
  681.           __glibcxx_check_insert(__hint);
  682.           size_type __bucket_count = this->bucket_count();
  683.           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
  684.                                         std::forward<_Args>(__args)...);
  685.           _M_check_rehashed(__bucket_count);
  686.           return iterator(__it, this);
  687.         }
  688.  
  689.       iterator
  690.       insert(const value_type& __obj)
  691.       {
  692.         size_type __bucket_count = this->bucket_count();
  693.         _Base_iterator __it = _Base::insert(__obj);
  694.         _M_check_rehashed(__bucket_count);
  695.         return iterator(__it, this);
  696.       }
  697.  
  698.       iterator
  699.       insert(const_iterator __hint, const value_type& __obj)
  700.       {
  701.         __glibcxx_check_insert(__hint);
  702.         size_type __bucket_count = this->bucket_count();
  703.         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
  704.         _M_check_rehashed(__bucket_count);
  705.         return iterator(__it, this);
  706.       }
  707.  
  708.       iterator
  709.       insert(value_type&& __obj)
  710.       {
  711.         size_type __bucket_count = this->bucket_count();
  712.         _Base_iterator __it = _Base::insert(std::move(__obj));
  713.         _M_check_rehashed(__bucket_count);
  714.         return iterator(__it, this);
  715.       }
  716.  
  717.       iterator
  718.       insert(const_iterator __hint, value_type&& __obj)
  719.       {
  720.         __glibcxx_check_insert(__hint);
  721.         size_type __bucket_count = this->bucket_count();
  722.         _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
  723.         _M_check_rehashed(__bucket_count);
  724.         return iterator(__it, this);
  725.       }
  726.  
  727.       void
  728.       insert(std::initializer_list<value_type> __l)
  729.       {
  730.         size_type __bucket_count = this->bucket_count();
  731.         _Base::insert(__l);
  732.         _M_check_rehashed(__bucket_count);
  733.       }
  734.  
  735.       template<typename _InputIterator>
  736.         void
  737.         insert(_InputIterator __first, _InputIterator __last)
  738.         {
  739.           __glibcxx_check_valid_range(__first, __last);
  740.           size_type __bucket_count = this->bucket_count();
  741.           _Base::insert(__gnu_debug::__base(__first),
  742.                         __gnu_debug::__base(__last));
  743.           _M_check_rehashed(__bucket_count);
  744.         }
  745.  
  746.       iterator
  747.       find(const key_type& __key)
  748.       { return iterator(_Base::find(__key), this); }
  749.  
  750.       const_iterator
  751.       find(const key_type& __key) const
  752.       { return const_iterator(_Base::find(__key), this); }
  753.  
  754.       std::pair<iterator, iterator>
  755.       equal_range(const key_type& __key)
  756.       {
  757.         typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
  758.         __pair_type __res = _Base::equal_range(__key);
  759.         return std::make_pair(iterator(__res.first, this),
  760.                               iterator(__res.second, this));
  761.       }
  762.  
  763.       std::pair<const_iterator, const_iterator>
  764.       equal_range(const key_type& __key) const
  765.       {
  766.         std::pair<_Base_const_iterator, _Base_const_iterator>
  767.           __res = _Base::equal_range(__key);
  768.         return std::make_pair(const_iterator(__res.first, this),
  769.                               const_iterator(__res.second, this));
  770.       }
  771.  
  772.       size_type
  773.       erase(const key_type& __key)
  774.       {
  775.         size_type __ret(0);
  776.         std::pair<_Base_iterator, _Base_iterator> __pair =
  777.           _Base::equal_range(__key);
  778.         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
  779.           {
  780.             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
  781.                             { return __it == __victim; });
  782.             this->_M_invalidate_local_if(
  783.                             [__victim](_Base_const_local_iterator __it)
  784.                             { return __it._M_cur == __victim._M_cur; });
  785.             _Base::erase(__victim++);
  786.             ++__ret;
  787.           }
  788.         return __ret;
  789.       }
  790.  
  791.       iterator
  792.       erase(const_iterator __it)
  793.       {
  794.         __glibcxx_check_erase(__it);
  795.         _Base_const_iterator __victim = __it.base();
  796.         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
  797.                         { return __it == __victim; });
  798.         this->_M_invalidate_local_if(
  799.                         [__victim](_Base_const_local_iterator __it)
  800.                         { return __it._M_cur == __victim._M_cur; });
  801.         return iterator(_Base::erase(__it.base()), this);
  802.       }
  803.  
  804.       iterator
  805.       erase(iterator __it)
  806.       { return erase(const_iterator(__it)); }
  807.  
  808.       iterator
  809.       erase(const_iterator __first, const_iterator __last)
  810.       {
  811.         __glibcxx_check_erase_range(__first, __last);
  812.         for (_Base_const_iterator __tmp = __first.base();
  813.              __tmp != __last.base(); ++__tmp)
  814.           {
  815.             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
  816.                                   _M_message(__gnu_debug::__msg_valid_range)
  817.                                   ._M_iterator(__first, "first")
  818.                                   ._M_iterator(__last, "last"));
  819.             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
  820.                             { return __it == __tmp; });
  821.             this->_M_invalidate_local_if(
  822.                             [__tmp](_Base_const_local_iterator __it)
  823.                             { return __it._M_cur == __tmp._M_cur; });
  824.           }
  825.         return iterator(_Base::erase(__first.base(),
  826.                                      __last.base()), this);
  827.       }
  828.  
  829.       _Base&
  830.       _M_base() noexcept       { return *this; }
  831.  
  832.       const _Base&
  833.       _M_base() const noexcept { return *this; }
  834.  
  835.     private:
  836.       void
  837.       _M_invalidate_locals()
  838.       {
  839.         _Base_local_iterator __local_end = _Base::end(0);
  840.         this->_M_invalidate_local_if(
  841.                         [__local_end](_Base_const_local_iterator __it)
  842.                         { return __it != __local_end; });
  843.       }
  844.  
  845.       void
  846.       _M_invalidate_all()
  847.       {
  848.         _Base_iterator __end = _Base::end();
  849.         this->_M_invalidate_if([__end](_Base_const_iterator __it)
  850.                         { return __it != __end; });
  851.         _M_invalidate_locals();
  852.       }
  853.  
  854.       void
  855.       _M_check_rehashed(size_type __prev_count)
  856.       {
  857.         if (__prev_count != this->bucket_count())
  858.           _M_invalidate_locals();
  859.       }
  860.     };
  861.  
  862.   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
  863.     inline void
  864.     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
  865.          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
  866.     { __x.swap(__y); }
  867.  
  868.   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
  869.     inline bool
  870.     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
  871.                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
  872.     { return __x._M_base() == __y._M_base(); }
  873.  
  874.   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
  875.     inline bool
  876.     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
  877.                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
  878.     { return !(__x == __y); }
  879.  
  880. } // namespace __debug
  881. } // namespace std
  882.  
  883. #endif // C++11
  884.  
  885. #endif
  886.