Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // Debugging unordered_map/unordered_multimap 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_map
  26.  *  This file is a GNU debug extension to the Standard C++ Library.
  27.  */
  28.  
  29. #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
  30. #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
  31.  
  32. #if __cplusplus < 201103L
  33. # include <bits/c++0x_warning.h>
  34. #else
  35. # include <unordered_map>
  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_map with safety/checking/debug instrumentation.
  46.   template<typename _Key, typename _Tp,
  47.            typename _Hash = std::hash<_Key>,
  48.            typename _Pred = std::equal_to<_Key>,
  49.            typename _Alloc = std::allocator<_Key> >
  50.     class unordered_map
  51.     : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
  52.       public __gnu_debug::_Safe_unordered_container<unordered_map<_Key, _Tp,
  53.                                                         _Hash, _Pred, _Alloc> >
  54.     {
  55.       typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
  56.                                             _Pred, _Alloc> _Base;
  57.       typedef __gnu_debug::_Safe_unordered_container<unordered_map> _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_map> iterator;
  74.       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
  75.                                           unordered_map> const_iterator;
  76.       typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator,
  77.                                           unordered_map> local_iterator;
  78.       typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator,
  79.                                           unordered_map> const_local_iterator;
  80.  
  81.       explicit
  82.       unordered_map(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_map(_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_map(const unordered_map& __x) = default;
  100.  
  101.       unordered_map(const _Base& __x)
  102.       : _Base(__x) { }
  103.  
  104.       unordered_map(unordered_map&& __x) = default;
  105.  
  106.       unordered_map(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_map() noexcept { }
  114.  
  115.       unordered_map&
  116.       operator=(const unordered_map& __x)
  117.       {
  118.         *static_cast<_Base*>(this) = __x;
  119.         this->_M_invalidate_all();
  120.         return *this;
  121.       }
  122.  
  123.       unordered_map&
  124.       operator=(unordered_map&& __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_map&
  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_map& __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.         std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
  269.         _M_check_rehashed(__bucket_count);
  270.         return std::make_pair(iterator(__res.first, this), __res.second);
  271.       }
  272.  
  273.       iterator
  274.       insert(const_iterator __hint, const value_type& __obj)
  275.       {
  276.         __glibcxx_check_insert(__hint);
  277.         size_type __bucket_count = this->bucket_count();
  278.         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
  279.         _M_check_rehashed(__bucket_count);
  280.         return iterator(__it, this);
  281.       }
  282.  
  283.       template<typename _Pair, typename = typename
  284.                std::enable_if<std::is_constructible<value_type,
  285.                                                     _Pair&&>::value>::type>
  286.         std::pair<iterator, bool>
  287.         insert(_Pair&& __obj)
  288.         {
  289.           size_type __bucket_count = this->bucket_count();
  290.           std::pair<_Base_iterator, bool> __res =
  291.             _Base::insert(std::forward<_Pair>(__obj));
  292.           _M_check_rehashed(__bucket_count);
  293.           return std::make_pair(iterator(__res.first, this), __res.second);
  294.         }
  295.  
  296.       template<typename _Pair, typename = typename
  297.                std::enable_if<std::is_constructible<value_type,
  298.                                                     _Pair&&>::value>::type>
  299.         iterator
  300.         insert(const_iterator __hint, _Pair&& __obj)
  301.         {
  302.           __glibcxx_check_insert(__hint);
  303.           size_type __bucket_count = this->bucket_count();
  304.           _Base_iterator __it =
  305.             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
  306.           _M_check_rehashed(__bucket_count);
  307.           return iterator(__it, this);
  308.         }
  309.  
  310.       void
  311.       insert(std::initializer_list<value_type> __l)
  312.       {
  313.         size_type __bucket_count = this->bucket_count();
  314.         _Base::insert(__l);
  315.         _M_check_rehashed(__bucket_count);
  316.       }
  317.  
  318.       template<typename _InputIterator>
  319.         void
  320.         insert(_InputIterator __first, _InputIterator __last)
  321.         {
  322.           __glibcxx_check_valid_range(__first, __last);
  323.           size_type __bucket_count = this->bucket_count();
  324.           _Base::insert(__gnu_debug::__base(__first),
  325.                         __gnu_debug::__base(__last));
  326.           _M_check_rehashed(__bucket_count);
  327.         }
  328.  
  329.       iterator
  330.       find(const key_type& __key)
  331.       { return iterator(_Base::find(__key), this); }
  332.  
  333.       const_iterator
  334.       find(const key_type& __key) const
  335.       { return const_iterator(_Base::find(__key), this); }
  336.  
  337.       std::pair<iterator, iterator>
  338.       equal_range(const key_type& __key)
  339.       {
  340.         std::pair<_Base_iterator, _Base_iterator> __res =
  341.           _Base::equal_range(__key);
  342.         return std::make_pair(iterator(__res.first, this),
  343.                               iterator(__res.second, this));
  344.       }
  345.  
  346.       std::pair<const_iterator, const_iterator>
  347.       equal_range(const key_type& __key) const
  348.       {
  349.         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
  350.           _Base::equal_range(__key);
  351.         return std::make_pair(const_iterator(__res.first, this),
  352.                               const_iterator(__res.second, this));
  353.       }
  354.  
  355.       size_type
  356.       erase(const key_type& __key)
  357.       {
  358.         size_type __ret(0);
  359.         _Base_iterator __victim(_Base::find(__key));
  360.         if (__victim != _Base::end())
  361.           {
  362.             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
  363.                             { return __it == __victim; });
  364.             this->_M_invalidate_local_if(
  365.                             [__victim](_Base_const_local_iterator __it)
  366.                             { return __it._M_cur == __victim._M_cur; });
  367.             size_type __bucket_count = this->bucket_count();
  368.             _Base::erase(__victim);
  369.             _M_check_rehashed(__bucket_count);
  370.             __ret = 1;
  371.           }
  372.         return __ret;
  373.       }
  374.  
  375.       iterator
  376.       erase(const_iterator __it)
  377.       {
  378.         __glibcxx_check_erase(__it);
  379.         _Base_const_iterator __victim = __it.base();
  380.         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
  381.                         { return __it == __victim; });
  382.         this->_M_invalidate_local_if(
  383.                         [__victim](_Base_const_local_iterator __it)
  384.                         { return __it._M_cur == __victim._M_cur; });
  385.         size_type __bucket_count = this->bucket_count();
  386.         _Base_iterator __next = _Base::erase(__it.base());
  387.         _M_check_rehashed(__bucket_count);
  388.         return iterator(__next, this);
  389.       }
  390.  
  391.       iterator
  392.       erase(iterator __it)
  393.       { return erase(const_iterator(__it)); }
  394.  
  395.       iterator
  396.       erase(const_iterator __first, const_iterator __last)
  397.       {
  398.         __glibcxx_check_erase_range(__first, __last);
  399.         for (_Base_const_iterator __tmp = __first.base();
  400.              __tmp != __last.base(); ++__tmp)
  401.           {
  402.             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
  403.                                   _M_message(__gnu_debug::__msg_valid_range)
  404.                                   ._M_iterator(__first, "first")
  405.                                   ._M_iterator(__last, "last"));
  406.             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
  407.                             { return __it == __tmp; });
  408.             this->_M_invalidate_local_if(
  409.                             [__tmp](_Base_const_local_iterator __it)
  410.                             { return __it._M_cur == __tmp._M_cur; });
  411.           }
  412.         size_type __bucket_count = this->bucket_count();
  413.         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
  414.         _M_check_rehashed(__bucket_count);
  415.         return iterator(__next, this);
  416.       }
  417.  
  418.       _Base&
  419.       _M_base() noexcept       { return *this; }
  420.  
  421.       const _Base&
  422.       _M_base() const noexcept { return *this; }
  423.  
  424.     private:
  425.       void
  426.       _M_invalidate_locals()
  427.       {
  428.         _Base_local_iterator __local_end = _Base::end(0);
  429.         this->_M_invalidate_local_if(
  430.                         [__local_end](_Base_const_local_iterator __it)
  431.                         { return __it != __local_end; });
  432.       }
  433.  
  434.       void
  435.       _M_invalidate_all()
  436.       {
  437.         _Base_iterator __end = _Base::end();
  438.         this->_M_invalidate_if([__end](_Base_const_iterator __it)
  439.                         { return __it != __end; });
  440.         _M_invalidate_locals();
  441.       }
  442.  
  443.       void
  444.       _M_check_rehashed(size_type __prev_count)
  445.       {
  446.         if (__prev_count != this->bucket_count())
  447.           _M_invalidate_locals();
  448.       }
  449.     };
  450.  
  451.   template<typename _Key, typename _Tp, typename _Hash,
  452.            typename _Pred, typename _Alloc>
  453.     inline void
  454.     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
  455.          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
  456.     { __x.swap(__y); }
  457.  
  458.   template<typename _Key, typename _Tp, typename _Hash,
  459.            typename _Pred, typename _Alloc>
  460.     inline bool
  461.     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
  462.                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
  463.     { return __x._M_base() == __y._M_base(); }
  464.  
  465.   template<typename _Key, typename _Tp, typename _Hash,
  466.            typename _Pred, typename _Alloc>
  467.     inline bool
  468.     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
  469.                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
  470.     { return !(__x == __y); }
  471.  
  472.  
  473.   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
  474.   template<typename _Key, typename _Tp,
  475.            typename _Hash = std::hash<_Key>,
  476.            typename _Pred = std::equal_to<_Key>,
  477.            typename _Alloc = std::allocator<_Key> >
  478.     class unordered_multimap
  479.     : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
  480.                                                 _Pred, _Alloc>,
  481.       public __gnu_debug::_Safe_unordered_container<unordered_multimap<_Key,
  482.                                                 _Tp, _Hash, _Pred, _Alloc> >
  483.     {
  484.       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
  485.                                                  _Pred, _Alloc> _Base;
  486.       typedef __gnu_debug::_Safe_unordered_container<unordered_multimap>
  487.         _Safe_base;
  488.       typedef typename _Base::const_iterator _Base_const_iterator;
  489.       typedef typename _Base::iterator _Base_iterator;
  490.       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
  491.       typedef typename _Base::local_iterator _Base_local_iterator;
  492.  
  493.     public:
  494.       typedef typename _Base::size_type       size_type;
  495.       typedef typename _Base::hasher          hasher;
  496.       typedef typename _Base::key_equal       key_equal;
  497.       typedef typename _Base::allocator_type  allocator_type;
  498.  
  499.       typedef typename _Base::key_type        key_type;
  500.       typedef typename _Base::value_type      value_type;
  501.  
  502.       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
  503.                                           unordered_multimap> iterator;
  504.       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
  505.                                           unordered_multimap> const_iterator;
  506.       typedef __gnu_debug::_Safe_local_iterator<
  507.         _Base_local_iterator, unordered_multimap> local_iterator;
  508.       typedef __gnu_debug::_Safe_local_iterator<
  509.         _Base_const_local_iterator, unordered_multimap> const_local_iterator;
  510.  
  511.       explicit
  512.       unordered_multimap(size_type __n = 10,
  513.                          const hasher& __hf = hasher(),
  514.                          const key_equal& __eql = key_equal(),
  515.                          const allocator_type& __a = allocator_type())
  516.       : _Base(__n, __hf, __eql, __a) { }
  517.  
  518.       template<typename _InputIterator>
  519.         unordered_multimap(_InputIterator __first, _InputIterator __last,
  520.                            size_type __n = 0,
  521.                            const hasher& __hf = hasher(),
  522.                            const key_equal& __eql = key_equal(),
  523.                            const allocator_type& __a = allocator_type())
  524.         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
  525.                                                                      __last)),
  526.                 __gnu_debug::__base(__last), __n,
  527.                 __hf, __eql, __a) { }
  528.  
  529.       unordered_multimap(const unordered_multimap& __x) = default;
  530.  
  531.       unordered_multimap(const _Base& __x)
  532.       : _Base(__x) { }
  533.  
  534.       unordered_multimap(unordered_multimap&& __x) = default;
  535.  
  536.       unordered_multimap(initializer_list<value_type> __l,
  537.                          size_type __n = 0,
  538.                          const hasher& __hf = hasher(),
  539.                          const key_equal& __eql = key_equal(),
  540.                          const allocator_type& __a = allocator_type())
  541.       : _Base(__l, __n, __hf, __eql, __a) { }
  542.  
  543.       ~unordered_multimap() noexcept { }
  544.  
  545.       unordered_multimap&
  546.       operator=(const unordered_multimap& __x)
  547.       {
  548.         *static_cast<_Base*>(this) = __x;
  549.         this->_M_invalidate_all();
  550.         return *this;
  551.       }
  552.  
  553.       unordered_multimap&
  554.       operator=(unordered_multimap&& __x)
  555.       {
  556.         // NB: DR 1204.
  557.         // NB: DR 675.
  558.         __glibcxx_check_self_move_assign(__x);
  559.         clear();
  560.         swap(__x);
  561.         return *this;
  562.       }
  563.  
  564.       unordered_multimap&
  565.       operator=(initializer_list<value_type> __l)
  566.       {
  567.         this->clear();
  568.         this->insert(__l);
  569.         return *this;
  570.       }
  571.  
  572.       void
  573.       swap(unordered_multimap& __x)
  574.       {
  575.         _Base::swap(__x);
  576.         _Safe_base::_M_swap(__x);
  577.       }
  578.  
  579.       void
  580.       clear() noexcept
  581.       {
  582.         _Base::clear();
  583.         this->_M_invalidate_all();
  584.       }
  585.  
  586.       iterator
  587.       begin() noexcept
  588.       { return iterator(_Base::begin(), this); }
  589.  
  590.       const_iterator
  591.       begin() const noexcept
  592.       { return const_iterator(_Base::begin(), this); }
  593.  
  594.       iterator
  595.       end() noexcept
  596.       { return iterator(_Base::end(), this); }
  597.  
  598.       const_iterator
  599.       end() const noexcept
  600.       { return const_iterator(_Base::end(), this); }
  601.  
  602.       const_iterator
  603.       cbegin() const noexcept
  604.       { return const_iterator(_Base::begin(), this); }
  605.  
  606.       const_iterator
  607.       cend() const noexcept
  608.       { return const_iterator(_Base::end(), this); }
  609.  
  610.       // local versions
  611.       local_iterator
  612.       begin(size_type __b)
  613.       {
  614.         __glibcxx_check_bucket_index(__b);
  615.         return local_iterator(_Base::begin(__b), __b, this);
  616.       }
  617.  
  618.       local_iterator
  619.       end(size_type __b)
  620.       {
  621.         __glibcxx_check_bucket_index(__b);
  622.         return local_iterator(_Base::end(__b), __b, this);
  623.       }
  624.  
  625.       const_local_iterator
  626.       begin(size_type __b) const
  627.       {
  628.         __glibcxx_check_bucket_index(__b);
  629.         return const_local_iterator(_Base::begin(__b), __b, this);
  630.       }
  631.  
  632.       const_local_iterator
  633.       end(size_type __b) const
  634.       {
  635.         __glibcxx_check_bucket_index(__b);
  636.         return const_local_iterator(_Base::end(__b), __b, this);
  637.       }
  638.  
  639.       const_local_iterator
  640.       cbegin(size_type __b) const
  641.       {
  642.         __glibcxx_check_bucket_index(__b);
  643.         return const_local_iterator(_Base::cbegin(__b), __b, this);
  644.       }
  645.  
  646.       const_local_iterator
  647.       cend(size_type __b) const
  648.       {
  649.         __glibcxx_check_bucket_index(__b);
  650.         return const_local_iterator(_Base::cend(__b), __b, this);
  651.       }
  652.  
  653.       size_type
  654.       bucket_size(size_type __b) const
  655.       {
  656.         __glibcxx_check_bucket_index(__b);
  657.         return _Base::bucket_size(__b);
  658.       }
  659.  
  660.       float
  661.       max_load_factor() const noexcept
  662.       { return _Base::max_load_factor(); }
  663.  
  664.       void
  665.       max_load_factor(float __f)
  666.       {
  667.         __glibcxx_check_max_load_factor(__f);
  668.         _Base::max_load_factor(__f);
  669.       }
  670.  
  671.       template<typename... _Args>
  672.         iterator
  673.         emplace(_Args&&... __args)
  674.         {
  675.           size_type __bucket_count = this->bucket_count();
  676.           _Base_iterator __it
  677.             = _Base::emplace(std::forward<_Args>(__args)...);
  678.           _M_check_rehashed(__bucket_count);
  679.           return iterator(__it, this);
  680.         }
  681.  
  682.       template<typename... _Args>
  683.         iterator
  684.         emplace_hint(const_iterator __hint, _Args&&... __args)
  685.         {
  686.           __glibcxx_check_insert(__hint);
  687.           size_type __bucket_count = this->bucket_count();
  688.           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
  689.                                         std::forward<_Args>(__args)...);
  690.           _M_check_rehashed(__bucket_count);
  691.           return iterator(__it, this);
  692.         }
  693.  
  694.       iterator
  695.       insert(const value_type& __obj)
  696.       {
  697.         size_type __bucket_count = this->bucket_count();
  698.         _Base_iterator __it = _Base::insert(__obj);
  699.         _M_check_rehashed(__bucket_count);
  700.         return iterator(__it, this);
  701.       }
  702.  
  703.       iterator
  704.       insert(const_iterator __hint, const value_type& __obj)
  705.       {
  706.         __glibcxx_check_insert(__hint);
  707.         size_type __bucket_count = this->bucket_count();
  708.         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
  709.         _M_check_rehashed(__bucket_count);
  710.         return iterator(__it, this);
  711.       }
  712.  
  713.       template<typename _Pair, typename = typename
  714.                std::enable_if<std::is_constructible<value_type,
  715.                                                     _Pair&&>::value>::type>
  716.         iterator
  717.         insert(_Pair&& __obj)
  718.         {
  719.           size_type __bucket_count = this->bucket_count();
  720.           _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
  721.           _M_check_rehashed(__bucket_count);
  722.           return iterator(__it, this);
  723.         }
  724.  
  725.       template<typename _Pair, typename = typename
  726.                std::enable_if<std::is_constructible<value_type,
  727.                                                     _Pair&&>::value>::type>
  728.         iterator
  729.         insert(const_iterator __hint, _Pair&& __obj)
  730.         {
  731.           __glibcxx_check_insert(__hint);
  732.           size_type __bucket_count = this->bucket_count();
  733.           _Base_iterator __it =
  734.             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
  735.           _M_check_rehashed(__bucket_count);
  736.           return iterator(__it, this);
  737.         }
  738.  
  739.       void
  740.       insert(std::initializer_list<value_type> __l)
  741.       { _Base::insert(__l); }
  742.  
  743.       template<typename _InputIterator>
  744.         void
  745.         insert(_InputIterator __first, _InputIterator __last)
  746.         {
  747.           __glibcxx_check_valid_range(__first, __last);
  748.           size_type __bucket_count = this->bucket_count();
  749.           _Base::insert(__gnu_debug::__base(__first),
  750.                         __gnu_debug::__base(__last));
  751.           _M_check_rehashed(__bucket_count);
  752.         }
  753.  
  754.       iterator
  755.       find(const key_type& __key)
  756.       { return iterator(_Base::find(__key), this); }
  757.  
  758.       const_iterator
  759.       find(const key_type& __key) const
  760.       { return const_iterator(_Base::find(__key), this); }
  761.  
  762.       std::pair<iterator, iterator>
  763.       equal_range(const key_type& __key)
  764.       {
  765.         std::pair<_Base_iterator, _Base_iterator> __res =
  766.           _Base::equal_range(__key);
  767.         return std::make_pair(iterator(__res.first, this),
  768.                               iterator(__res.second, this));
  769.       }
  770.  
  771.       std::pair<const_iterator, const_iterator>
  772.       equal_range(const key_type& __key) const
  773.       {
  774.         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
  775.           _Base::equal_range(__key);
  776.         return std::make_pair(const_iterator(__res.first, this),
  777.                               const_iterator(__res.second, this));
  778.       }
  779.  
  780.       size_type
  781.       erase(const key_type& __key)
  782.       {
  783.         size_type __ret(0);
  784.         size_type __bucket_count = this->bucket_count();
  785.         std::pair<_Base_iterator, _Base_iterator> __pair =
  786.           _Base::equal_range(__key);
  787.         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
  788.           {
  789.             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
  790.                             { return __it == __victim; });
  791.             this->_M_invalidate_local_if(
  792.                             [__victim](_Base_const_local_iterator __it)
  793.                             { return __it._M_cur == __victim._M_cur; });
  794.             _Base::erase(__victim++);
  795.             ++__ret;
  796.           }
  797.         _M_check_rehashed(__bucket_count);
  798.         return __ret;
  799.       }
  800.  
  801.       iterator
  802.       erase(const_iterator __it)
  803.       {
  804.         __glibcxx_check_erase(__it);
  805.         _Base_const_iterator __victim = __it.base();
  806.         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
  807.                         { return __it == __victim; });
  808.         this->_M_invalidate_local_if(
  809.                         [__victim](_Base_const_local_iterator __it)
  810.                         { return __it._M_cur == __victim._M_cur; });
  811.         size_type __bucket_count = this->bucket_count();
  812.         _Base_iterator __next = _Base::erase(__it.base());
  813.         _M_check_rehashed(__bucket_count);
  814.         return iterator(__next, this);
  815.       }
  816.  
  817.       iterator
  818.       erase(iterator __it)
  819.       { return erase(const_iterator(__it)); }
  820.  
  821.       iterator
  822.       erase(const_iterator __first, const_iterator __last)
  823.       {
  824.         __glibcxx_check_erase_range(__first, __last);
  825.         for (_Base_const_iterator __tmp = __first.base();
  826.              __tmp != __last.base(); ++__tmp)
  827.           {
  828.             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
  829.                                   _M_message(__gnu_debug::__msg_valid_range)
  830.                                   ._M_iterator(__first, "first")
  831.                                   ._M_iterator(__last, "last"));
  832.             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
  833.                             { return __it == __tmp; });
  834.             this->_M_invalidate_local_if(
  835.                             [__tmp](_Base_const_local_iterator __it)
  836.                             { return __it._M_cur == __tmp._M_cur; });
  837.           }
  838.         size_type __bucket_count = this->bucket_count();
  839.         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
  840.         _M_check_rehashed(__bucket_count);
  841.         return iterator(__next, this);
  842.       }
  843.  
  844.       _Base&
  845.       _M_base() noexcept       { return *this; }
  846.  
  847.       const _Base&
  848.       _M_base() const noexcept { return *this; }
  849.  
  850.     private:
  851.       void
  852.       _M_invalidate_locals()
  853.       {
  854.         _Base_local_iterator __local_end = _Base::end(0);
  855.         this->_M_invalidate_local_if(
  856.                         [__local_end](_Base_const_local_iterator __it)
  857.                         { return __it != __local_end; });
  858.       }
  859.  
  860.       void
  861.       _M_invalidate_all()
  862.       {
  863.         _Base_iterator __end = _Base::end();
  864.         this->_M_invalidate_if([__end](_Base_const_iterator __it)
  865.                         { return __it != __end; });
  866.         _M_invalidate_locals();
  867.       }
  868.  
  869.       void
  870.       _M_check_rehashed(size_type __prev_count)
  871.       {
  872.         if (__prev_count != this->bucket_count())
  873.           _M_invalidate_locals();
  874.       }
  875.     };
  876.  
  877.   template<typename _Key, typename _Tp, typename _Hash,
  878.            typename _Pred, typename _Alloc>
  879.     inline void
  880.     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
  881.          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
  882.     { __x.swap(__y); }
  883.  
  884.   template<typename _Key, typename _Tp, typename _Hash,
  885.            typename _Pred, typename _Alloc>
  886.     inline bool
  887.     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
  888.                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
  889.     { return __x._M_base() == __y._M_base(); }
  890.  
  891.   template<typename _Key, typename _Tp, typename _Hash,
  892.            typename _Pred, typename _Alloc>
  893.     inline bool
  894.     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
  895.                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
  896.     { return !(__x == __y); }
  897.  
  898. } // namespace __debug
  899. } // namespace std
  900.  
  901. #endif // C++11
  902.  
  903. #endif
  904.