libstdc++
map.h
Go to the documentation of this file.
00001 // Debugging map implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2019 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file debug/map.h
00026  *  This file is a GNU debug extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _GLIBCXX_DEBUG_MAP_H
00030 #define _GLIBCXX_DEBUG_MAP_H 1
00031 
00032 #include <debug/safe_sequence.h>
00033 #include <debug/safe_container.h>
00034 #include <debug/safe_iterator.h>
00035 #include <utility>
00036 
00037 namespace std _GLIBCXX_VISIBILITY(default)
00038 {
00039 namespace __debug
00040 {
00041   /// Class std::map with safety/checking/debug instrumentation.
00042   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
00043            typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
00044     class map
00045     : public __gnu_debug::_Safe_container<
00046         map<_Key, _Tp, _Compare, _Allocator>, _Allocator,
00047         __gnu_debug::_Safe_node_sequence>,
00048       public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>
00049     {
00050       typedef _GLIBCXX_STD_C::map<
00051         _Key, _Tp, _Compare, _Allocator>                        _Base;
00052       typedef __gnu_debug::_Safe_container<
00053         map, _Allocator, __gnu_debug::_Safe_node_sequence>      _Safe;
00054 
00055       typedef typename _Base::const_iterator    _Base_const_iterator;
00056       typedef typename _Base::iterator          _Base_iterator;
00057       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00058 
00059       template<typename _ItT, typename _SeqT, typename _CatT>
00060         friend class ::__gnu_debug::_Safe_iterator;
00061 
00062     public:
00063       // types:
00064       typedef _Key                                      key_type;
00065       typedef _Tp                                       mapped_type;
00066       typedef std::pair<const _Key, _Tp>                value_type;
00067       typedef _Compare                                  key_compare;
00068       typedef _Allocator                                allocator_type;
00069       typedef typename _Base::reference                 reference;
00070       typedef typename _Base::const_reference           const_reference;
00071 
00072       typedef __gnu_debug::_Safe_iterator<_Base_iterator, map>
00073                                                         iterator;
00074       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, map>
00075                                                         const_iterator;
00076 
00077       typedef typename _Base::size_type                 size_type;
00078       typedef typename _Base::difference_type           difference_type;
00079       typedef typename _Base::pointer                   pointer;
00080       typedef typename _Base::const_pointer             const_pointer;
00081       typedef std::reverse_iterator<iterator>           reverse_iterator;
00082       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
00083 
00084       // 23.3.1.1 construct/copy/destroy:
00085 
00086 #if __cplusplus < 201103L
00087       map() : _Base() { }
00088 
00089       map(const map& __x)
00090       : _Base(__x) { }
00091 
00092       ~map() { }
00093 #else
00094       map() = default;
00095       map(const map&) = default;
00096       map(map&&) = default;
00097 
00098       map(initializer_list<value_type> __l,
00099           const _Compare& __c = _Compare(),
00100           const allocator_type& __a = allocator_type())
00101       : _Base(__l, __c, __a) { }
00102 
00103       explicit
00104       map(const allocator_type& __a)
00105       : _Base(__a) { }
00106 
00107       map(const map& __m, const allocator_type& __a)
00108       : _Base(__m, __a) { }
00109 
00110       map(map&& __m, const allocator_type& __a)
00111       noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
00112       : _Safe(std::move(__m._M_safe()), __a),
00113         _Base(std::move(__m._M_base()), __a) { }
00114 
00115       map(initializer_list<value_type> __l, const allocator_type& __a)
00116       : _Base(__l, __a) { }
00117 
00118       template<typename _InputIterator>
00119         map(_InputIterator __first, _InputIterator __last,
00120             const allocator_type& __a)
00121         : _Base(__gnu_debug::__base(
00122                   __glibcxx_check_valid_constructor_range(__first, __last)),
00123                 __gnu_debug::__base(__last), __a)
00124         { }
00125 
00126       ~map() = default;
00127 #endif
00128 
00129       map(const _Base& __x)
00130       : _Base(__x) { }
00131 
00132       explicit map(const _Compare& __comp,
00133                    const _Allocator& __a = _Allocator())
00134       : _Base(__comp, __a) { }
00135 
00136       template<typename _InputIterator>
00137         map(_InputIterator __first, _InputIterator __last,
00138             const _Compare& __comp = _Compare(),
00139             const _Allocator& __a = _Allocator())
00140         : _Base(__gnu_debug::__base(
00141                   __glibcxx_check_valid_constructor_range(__first, __last)),
00142                 __gnu_debug::__base(__last),
00143                 __comp, __a) { }
00144 
00145 #if __cplusplus < 201103L
00146       map&
00147       operator=(const map& __x)
00148       {
00149         this->_M_safe() = __x;
00150         _M_base() = __x;
00151         return *this;
00152       }
00153 #else
00154       map&
00155       operator=(const map&) = default;
00156 
00157       map&
00158       operator=(map&&) = default;
00159 
00160       map&
00161       operator=(initializer_list<value_type> __l)
00162       {
00163         _M_base() = __l;
00164         this->_M_invalidate_all();
00165         return *this;
00166       }
00167 #endif
00168 
00169       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00170       // 133. map missing get_allocator()
00171       using _Base::get_allocator;
00172 
00173       // iterators:
00174       iterator
00175       begin() _GLIBCXX_NOEXCEPT
00176       { return iterator(_Base::begin(), this); }
00177 
00178       const_iterator
00179       begin() const _GLIBCXX_NOEXCEPT
00180       { return const_iterator(_Base::begin(), this); }
00181 
00182       iterator
00183       end() _GLIBCXX_NOEXCEPT
00184       { return iterator(_Base::end(), this); }
00185 
00186       const_iterator
00187       end() const _GLIBCXX_NOEXCEPT
00188       { return const_iterator(_Base::end(), this); }
00189 
00190       reverse_iterator
00191       rbegin() _GLIBCXX_NOEXCEPT
00192       { return reverse_iterator(end()); }
00193 
00194       const_reverse_iterator
00195       rbegin() const _GLIBCXX_NOEXCEPT
00196       { return const_reverse_iterator(end()); }
00197 
00198       reverse_iterator
00199       rend() _GLIBCXX_NOEXCEPT
00200       { return reverse_iterator(begin()); }
00201 
00202       const_reverse_iterator
00203       rend() const _GLIBCXX_NOEXCEPT
00204       { return const_reverse_iterator(begin()); }
00205 
00206 #if __cplusplus >= 201103L
00207       const_iterator
00208       cbegin() const noexcept
00209       { return const_iterator(_Base::begin(), this); }
00210 
00211       const_iterator
00212       cend() const noexcept
00213       { return const_iterator(_Base::end(), this); }
00214 
00215       const_reverse_iterator
00216       crbegin() const noexcept
00217       { return const_reverse_iterator(end()); }
00218 
00219       const_reverse_iterator
00220       crend() const noexcept
00221       { return const_reverse_iterator(begin()); }
00222 #endif
00223 
00224       // capacity:
00225       using _Base::empty;
00226       using _Base::size;
00227       using _Base::max_size;
00228 
00229       // 23.3.1.2 element access:
00230       using _Base::operator[];
00231 
00232       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00233       // DR 464. Suggestion for new member functions in standard containers.
00234       using _Base::at;
00235 
00236       // modifiers:
00237 #if __cplusplus >= 201103L
00238       template<typename... _Args>
00239         std::pair<iterator, bool>
00240         emplace(_Args&&... __args)
00241         {
00242           auto __res = _Base::emplace(std::forward<_Args>(__args)...);
00243           return { { __res.first, this }, __res.second };
00244         }
00245 
00246       template<typename... _Args>
00247         iterator
00248         emplace_hint(const_iterator __pos, _Args&&... __args)
00249         {
00250           __glibcxx_check_insert(__pos);
00251           return
00252             {
00253               _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
00254               this
00255             };
00256         }
00257 #endif
00258 
00259       std::pair<iterator, bool>
00260       insert(const value_type& __x)
00261       {
00262         std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
00263         return std::pair<iterator, bool>(iterator(__res.first, this),
00264                                          __res.second);
00265       }
00266 
00267 #if __cplusplus >= 201103L
00268       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00269       // 2354. Unnecessary copying when inserting into maps with braced-init
00270       std::pair<iterator, bool>
00271       insert(value_type&& __x)
00272       {
00273         auto __res = _Base::insert(std::move(__x));
00274         return { { __res.first, this }, __res.second };
00275       }
00276 
00277       template<typename _Pair, typename = typename
00278                std::enable_if<std::is_constructible<value_type,
00279                                                     _Pair&&>::value>::type>
00280         std::pair<iterator, bool>
00281         insert(_Pair&& __x)
00282         {
00283           auto __res = _Base::insert(std::forward<_Pair>(__x));
00284           return { { __res.first, this }, __res.second };
00285         }
00286 #endif
00287 
00288 #if __cplusplus >= 201103L
00289       void
00290       insert(std::initializer_list<value_type> __list)
00291       { _Base::insert(__list); }
00292 #endif
00293 
00294       iterator
00295 #if __cplusplus >= 201103L
00296       insert(const_iterator __position, const value_type& __x)
00297 #else
00298       insert(iterator __position, const value_type& __x)
00299 #endif
00300       {
00301         __glibcxx_check_insert(__position);
00302         return iterator(_Base::insert(__position.base(), __x), this);
00303       }
00304 
00305 #if __cplusplus >= 201103L
00306       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00307       // 2354. Unnecessary copying when inserting into maps with braced-init
00308       iterator
00309       insert(const_iterator __position, value_type&& __x)
00310       {
00311         __glibcxx_check_insert(__position);
00312         return { _Base::insert(__position.base(), std::move(__x)), this };
00313       }
00314 
00315       template<typename _Pair, typename = typename
00316                std::enable_if<std::is_constructible<value_type,
00317                                                     _Pair&&>::value>::type>
00318         iterator
00319         insert(const_iterator __position, _Pair&& __x)
00320         {
00321           __glibcxx_check_insert(__position);
00322           return
00323             {
00324               _Base::insert(__position.base(), std::forward<_Pair>(__x)),
00325               this
00326             };
00327         }
00328 #endif
00329 
00330       template<typename _InputIterator>
00331         void
00332         insert(_InputIterator __first, _InputIterator __last)
00333         {
00334           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00335           __glibcxx_check_valid_range2(__first, __last, __dist);
00336 
00337           if (__dist.second >= __gnu_debug::__dp_sign)
00338             _Base::insert(__gnu_debug::__unsafe(__first),
00339                           __gnu_debug::__unsafe(__last));
00340           else
00341             _Base::insert(__first, __last);
00342         }
00343 
00344 
00345 #if __cplusplus > 201402L
00346       template <typename... _Args>
00347         pair<iterator, bool>
00348         try_emplace(const key_type& __k, _Args&&... __args)
00349         {
00350           auto __res = _Base::try_emplace(__k,
00351                                           std::forward<_Args>(__args)...);
00352           return { { __res.first, this }, __res.second };
00353         }
00354 
00355       template <typename... _Args>
00356         pair<iterator, bool>
00357         try_emplace(key_type&& __k, _Args&&... __args)
00358         {
00359           auto __res = _Base::try_emplace(std::move(__k),
00360                                           std::forward<_Args>(__args)...);
00361           return { { __res.first, this }, __res.second };
00362         }
00363 
00364       template <typename... _Args>
00365         iterator
00366         try_emplace(const_iterator __hint, const key_type& __k,
00367                     _Args&&... __args)
00368         {
00369           __glibcxx_check_insert(__hint);
00370           return
00371             {
00372               _Base::try_emplace(__hint.base(), __k,
00373                                  std::forward<_Args>(__args)...),
00374               this
00375             };
00376         }
00377 
00378       template <typename... _Args>
00379         iterator
00380         try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
00381         {
00382           __glibcxx_check_insert(__hint);
00383           return
00384             {
00385               _Base::try_emplace(__hint.base(), std::move(__k),
00386                                  std::forward<_Args>(__args)...),
00387               this
00388             };
00389         }
00390 
00391       template <typename _Obj>
00392         std::pair<iterator, bool>
00393         insert_or_assign(const key_type& __k, _Obj&& __obj)
00394         {
00395           auto __res = _Base::insert_or_assign(__k,
00396                                                std::forward<_Obj>(__obj));
00397           return { { __res.first, this }, __res.second };
00398         }
00399 
00400       template <typename _Obj>
00401         std::pair<iterator, bool>
00402         insert_or_assign(key_type&& __k, _Obj&& __obj)
00403         {
00404           auto __res = _Base::insert_or_assign(std::move(__k),
00405                                                std::forward<_Obj>(__obj));
00406           return { { __res.first, this }, __res.second };
00407         }
00408 
00409       template <typename _Obj>
00410         iterator
00411         insert_or_assign(const_iterator __hint,
00412                          const key_type& __k, _Obj&& __obj)
00413         {
00414           __glibcxx_check_insert(__hint);
00415           return
00416             {
00417               _Base::insert_or_assign(__hint.base(), __k,
00418                                       std::forward<_Obj>(__obj)),
00419               this
00420             };
00421         }
00422 
00423       template <typename _Obj>
00424         iterator
00425         insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
00426         {
00427           __glibcxx_check_insert(__hint);
00428           return
00429             {
00430               _Base::insert_or_assign(__hint.base(), std::move(__k),
00431                                       std::forward<_Obj>(__obj)),
00432               this
00433             };
00434         }
00435 #endif // C++17
00436 
00437 #if __cplusplus > 201402L
00438       using node_type = typename _Base::node_type;
00439       using insert_return_type = _Node_insert_return<iterator, node_type>;
00440 
00441       node_type
00442       extract(const_iterator __position)
00443       {
00444         __glibcxx_check_erase(__position);
00445         this->_M_invalidate_if(_Equal(__position.base()));
00446         return _Base::extract(__position.base());
00447       }
00448 
00449       node_type
00450       extract(const key_type& __key)
00451       {
00452         const auto __position = find(__key);
00453         if (__position != end())
00454           return extract(__position);
00455         return {};
00456       }
00457 
00458       insert_return_type
00459       insert(node_type&& __nh)
00460       {
00461         auto __ret = _Base::insert(std::move(__nh));
00462         return
00463           { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
00464       }
00465 
00466       iterator
00467       insert(const_iterator __hint, node_type&& __nh)
00468       {
00469         __glibcxx_check_insert(__hint);
00470         return { _Base::insert(__hint.base(), std::move(__nh)), this };
00471       }
00472 
00473       using _Base::merge;
00474 #endif // C++17
00475 
00476 #if __cplusplus >= 201103L
00477       iterator
00478       erase(const_iterator __position)
00479       {
00480         __glibcxx_check_erase(__position);
00481         this->_M_invalidate_if(_Equal(__position.base()));
00482         return { _Base::erase(__position.base()), this };
00483       }
00484 
00485       _GLIBCXX_ABI_TAG_CXX11
00486       iterator
00487       erase(iterator __position)
00488       { return erase(const_iterator(__position)); }
00489 #else
00490       void
00491       erase(iterator __position)
00492       {
00493         __glibcxx_check_erase(__position);
00494         this->_M_invalidate_if(_Equal(__position.base()));
00495         _Base::erase(__position.base());
00496       }
00497 #endif
00498 
00499       size_type
00500       erase(const key_type& __x)
00501       {
00502         _Base_iterator __victim = _Base::find(__x);
00503         if (__victim == _Base::end())
00504           return 0;
00505         else
00506           {
00507             this->_M_invalidate_if(_Equal(__victim));
00508             _Base::erase(__victim);
00509             return 1;
00510           }
00511       }
00512 
00513 #if __cplusplus >= 201103L
00514       iterator
00515       erase(const_iterator __first, const_iterator __last)
00516       {
00517         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00518         // 151. can't currently clear() empty container
00519         __glibcxx_check_erase_range(__first, __last);
00520         for (_Base_const_iterator __victim = __first.base();
00521              __victim != __last.base(); ++__victim)
00522           {
00523             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
00524                                   _M_message(__gnu_debug::__msg_valid_range)
00525                                   ._M_iterator(__first, "first")
00526                                   ._M_iterator(__last, "last"));
00527             this->_M_invalidate_if(_Equal(__victim));
00528           }
00529 
00530         return { _Base::erase(__first.base(), __last.base()), this };
00531       }
00532 #else
00533       void
00534       erase(iterator __first, iterator __last)
00535       {
00536         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00537         // 151. can't currently clear() empty container
00538         __glibcxx_check_erase_range(__first, __last);
00539         for (_Base_iterator __victim = __first.base();
00540              __victim != __last.base(); ++__victim)
00541           {
00542             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
00543                                   _M_message(__gnu_debug::__msg_valid_range)
00544                                   ._M_iterator(__first, "first")
00545                                   ._M_iterator(__last, "last"));
00546             this->_M_invalidate_if(_Equal(__victim));
00547           }
00548         _Base::erase(__first.base(), __last.base());
00549       }
00550 #endif
00551 
00552       void
00553       swap(map& __x)
00554       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
00555       {
00556         _Safe::_M_swap(__x);
00557         _Base::swap(__x);
00558       }
00559 
00560       void
00561       clear() _GLIBCXX_NOEXCEPT
00562       {
00563         this->_M_invalidate_all();
00564         _Base::clear();
00565       }
00566 
00567       // observers:
00568       using _Base::key_comp;
00569       using _Base::value_comp;
00570 
00571       // 23.3.1.3 map operations:
00572       iterator
00573       find(const key_type& __x)
00574       { return iterator(_Base::find(__x), this); }
00575 
00576 #if __cplusplus > 201103L
00577       template<typename _Kt,
00578                typename _Req =
00579                  typename __has_is_transparent<_Compare, _Kt>::type>
00580         iterator
00581         find(const _Kt& __x)
00582         { return { _Base::find(__x), this }; }
00583 #endif
00584 
00585       const_iterator
00586       find(const key_type& __x) const
00587       { return const_iterator(_Base::find(__x), this); }
00588 
00589 #if __cplusplus > 201103L
00590       template<typename _Kt,
00591                typename _Req =
00592                  typename __has_is_transparent<_Compare, _Kt>::type>
00593         const_iterator
00594         find(const _Kt& __x) const
00595         { return { _Base::find(__x), this }; }
00596 #endif
00597 
00598       using _Base::count;
00599 
00600       iterator
00601       lower_bound(const key_type& __x)
00602       { return iterator(_Base::lower_bound(__x), this); }
00603 
00604 #if __cplusplus > 201103L
00605       template<typename _Kt,
00606                typename _Req =
00607                  typename __has_is_transparent<_Compare, _Kt>::type>
00608         iterator
00609         lower_bound(const _Kt& __x)
00610         { return { _Base::lower_bound(__x), this }; }
00611 #endif
00612 
00613       const_iterator
00614       lower_bound(const key_type& __x) const
00615       { return const_iterator(_Base::lower_bound(__x), this); }
00616 
00617 #if __cplusplus > 201103L
00618       template<typename _Kt,
00619                typename _Req =
00620                  typename __has_is_transparent<_Compare, _Kt>::type>
00621         const_iterator
00622         lower_bound(const _Kt& __x) const
00623         { return { _Base::lower_bound(__x), this }; }
00624 #endif
00625 
00626       iterator
00627       upper_bound(const key_type& __x)
00628       { return iterator(_Base::upper_bound(__x), this); }
00629 
00630 #if __cplusplus > 201103L
00631       template<typename _Kt,
00632                typename _Req =
00633                  typename __has_is_transparent<_Compare, _Kt>::type>
00634         iterator
00635         upper_bound(const _Kt& __x)
00636         { return { _Base::upper_bound(__x), this }; }
00637 #endif
00638 
00639       const_iterator
00640       upper_bound(const key_type& __x) const
00641       { return const_iterator(_Base::upper_bound(__x), this); }
00642 
00643 #if __cplusplus > 201103L
00644       template<typename _Kt,
00645                typename _Req =
00646                  typename __has_is_transparent<_Compare, _Kt>::type>
00647         const_iterator
00648         upper_bound(const _Kt& __x) const
00649         { return { _Base::upper_bound(__x), this }; }
00650 #endif
00651 
00652       std::pair<iterator,iterator>
00653       equal_range(const key_type& __x)
00654       {
00655         std::pair<_Base_iterator, _Base_iterator> __res =
00656         _Base::equal_range(__x);
00657         return std::make_pair(iterator(__res.first, this),
00658                               iterator(__res.second, this));
00659       }
00660 
00661 #if __cplusplus > 201103L
00662       template<typename _Kt,
00663                typename _Req =
00664                  typename __has_is_transparent<_Compare, _Kt>::type>
00665         std::pair<iterator, iterator>
00666         equal_range(const _Kt& __x)
00667         {
00668           auto __res = _Base::equal_range(__x);
00669           return { { __res.first, this }, { __res.second, this } };
00670         }
00671 #endif
00672 
00673       std::pair<const_iterator,const_iterator>
00674       equal_range(const key_type& __x) const
00675       {
00676         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00677         _Base::equal_range(__x);
00678         return std::make_pair(const_iterator(__res.first, this),
00679                               const_iterator(__res.second, this));
00680       }
00681 
00682 #if __cplusplus > 201103L
00683       template<typename _Kt,
00684                typename _Req =
00685                  typename __has_is_transparent<_Compare, _Kt>::type>
00686         std::pair<const_iterator, const_iterator>
00687         equal_range(const _Kt& __x) const
00688         {
00689           auto __res = _Base::equal_range(__x);
00690           return { { __res.first, this }, { __res.second, this } };
00691         }
00692 #endif
00693 
00694       _Base&
00695       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00696 
00697       const _Base&
00698       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00699     };
00700 
00701 #if __cpp_deduction_guides >= 201606
00702 
00703   template<typename _InputIterator,
00704            typename _Compare = less<__iter_key_t<_InputIterator>>,
00705            typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
00706            typename = _RequireInputIter<_InputIterator>,
00707            typename = _RequireNotAllocator<_Compare>,
00708            typename = _RequireAllocator<_Allocator>>
00709     map(_InputIterator, _InputIterator,
00710         _Compare = _Compare(), _Allocator = _Allocator())
00711     -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
00712            _Compare, _Allocator>;
00713 
00714   template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
00715            typename _Allocator = allocator<pair<const _Key, _Tp>>,
00716            typename = _RequireNotAllocator<_Compare>,
00717            typename = _RequireAllocator<_Allocator>>
00718     map(initializer_list<pair<_Key, _Tp>>,
00719         _Compare = _Compare(), _Allocator = _Allocator())
00720     -> map<_Key, _Tp, _Compare, _Allocator>;
00721 
00722   template <typename _InputIterator, typename _Allocator,
00723             typename = _RequireInputIter<_InputIterator>,
00724             typename = _RequireAllocator<_Allocator>>
00725     map(_InputIterator, _InputIterator, _Allocator)
00726     -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
00727            less<__iter_key_t<_InputIterator>>, _Allocator>;
00728 
00729   template<typename _Key, typename _Tp, typename _Allocator,
00730            typename = _RequireAllocator<_Allocator>>
00731     map(initializer_list<pair<_Key, _Tp>>, _Allocator)
00732     -> map<_Key, _Tp, less<_Key>, _Allocator>;
00733 
00734 #endif
00735 
00736   template<typename _Key, typename _Tp,
00737            typename _Compare, typename _Allocator>
00738     inline bool
00739     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00740                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00741     { return __lhs._M_base() == __rhs._M_base(); }
00742 
00743   template<typename _Key, typename _Tp,
00744            typename _Compare, typename _Allocator>
00745     inline bool
00746     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00747                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00748     { return __lhs._M_base() != __rhs._M_base(); }
00749 
00750   template<typename _Key, typename _Tp,
00751            typename _Compare, typename _Allocator>
00752     inline bool
00753     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00754               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00755     { return __lhs._M_base() < __rhs._M_base(); }
00756 
00757   template<typename _Key, typename _Tp,
00758            typename _Compare, typename _Allocator>
00759     inline bool
00760     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00761                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00762     { return __lhs._M_base() <= __rhs._M_base(); }
00763 
00764   template<typename _Key, typename _Tp,
00765            typename _Compare, typename _Allocator>
00766     inline bool
00767     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00768                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00769     { return __lhs._M_base() >= __rhs._M_base(); }
00770 
00771   template<typename _Key, typename _Tp,
00772            typename _Compare, typename _Allocator>
00773     inline bool
00774     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00775               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00776     { return __lhs._M_base() > __rhs._M_base(); }
00777 
00778   template<typename _Key, typename _Tp,
00779            typename _Compare, typename _Allocator>
00780     inline void
00781     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
00782          map<_Key, _Tp, _Compare, _Allocator>& __rhs)
00783     _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
00784     { __lhs.swap(__rhs); }
00785 
00786 } // namespace __debug
00787 } // namespace std
00788 
00789 #endif