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