Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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