libstdc++-v3/include/debug/map.h

   1 // Debugging map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2018 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/map.h
  26  *  This file is a GNU debug extension to the Standard C++ Library.
  27  */
  28
  29 #ifndef _GLIBCXX_DEBUG_MAP_H
  30 #define _GLIBCXX_DEBUG_MAP_H 1
  31
  32 #include <debug/safe_sequence.h>
  33 #include <debug/safe_container.h>
  34 #include <debug/safe_iterator.h>
  35 #include <utility>
  36
  37 namespace std _GLIBCXX_VISIBILITY(default)
  38 {
  39 namespace __debug
  40 {
  41   /// Class std::map with safety/checking/debug instrumentation.
  42   template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
  43            typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
  44     class map
  45     : public __gnu_debug::_Safe_container<
  46         map<_Key, _Tp, _Compare, _Allocator>, _Allocator,
  47         __gnu_debug::_Safe_node_sequence>,
  48       public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>
  49     {
  50       typedef _GLIBCXX_STD_C::map<
  51         _Key, _Tp, _Compare, _Allocator>                        _Base;
  52       typedef __gnu_debug::_Safe_container<
  53         map, _Allocator, __gnu_debug::_Safe_node_sequence>      _Safe;
  54
  55       typedef typename _Base::const_iterator    _Base_const_iterator;
  56       typedef typename _Base::iterator          _Base_iterator;
  57       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
  58
  59       template<typename _ItT, typename _SeqT, typename _CatT>
  60         friend class ::__gnu_debug::_Safe_iterator;
  61
  62     public:
  63       // types:
  64       typedef _Key                                      key_type;
  65       typedef _Tp                                       mapped_type;
  66       typedef std::pair<const _Key, _Tp>                value_type;
  67       typedef _Compare                                  key_compare;
  68       typedef _Allocator                                allocator_type;
  69       typedef typename _Base::reference                 reference;
  70       typedef typename _Base::const_reference           const_reference;
  71
  72       typedef __gnu_debug::_Safe_iterator<_Base_iterator, map>
  73                                                         iterator;
  74       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, map>
  75                                                         const_iterator;
  76
  77       typedef typename _Base::size_type                 size_type;
  78       typedef typename _Base::difference_type           difference_type;
  79       typedef typename _Base::pointer                   pointer;
  80       typedef typename _Base::const_pointer             const_pointer;
  81       typedef std::reverse_iterator<iterator>           reverse_iterator;
  82       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
  83
  84       // 23.3.1.1 construct/copy/destroy:
  85
  86 #if __cplusplus < 201103L
  87       map() : _Base() { }
  88
  89       map(const map& __x)
  90       : _Base(__x) { }
  91
  92       ~map() { }
  93 #else
  94       map() = default;
  95       map(const map&) = default;
  96       map(map&&) = default;
  97
  98       map(initializer_list<value_type> __l,
  99           const _Compare& __c = _Compare(),
 100           const allocator_type& __a = allocator_type())
 101       : _Base(__l, __c, __a) { }
 102
 103       explicit
 104       map(const allocator_type& __a)
 105       : _Base(__a) { }
 106
 107       map(const map& __m, const allocator_type& __a)
 108       : _Base(__m, __a) { }
 109
 110       map(map&& __m, const allocator_type& __a)
 111       noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
 112       : _Safe(std::move(__m._M_safe()), __a),
 113         _Base(std::move(__m._M_base()), __a) { }
 114
 115       map(initializer_list<value_type> __l, const allocator_type& __a)
 116       : _Base(__l, __a) { }
 117
 118       template<typename _InputIterator>
 119         map(_InputIterator __first, _InputIterator __last,
 120             const allocator_type& __a)
 121         : _Base(__gnu_debug::__base(
 122                   __glibcxx_check_valid_constructor_range(__first, __last)),
 123                 __gnu_debug::__base(__last), __a)
 124         { }
 125
 126       ~map() = default;
 127 #endif
 128
 129       map(const _Base& __x)
 130       : _Base(__x) { }
 131
 132       explicit map(const _Compare& __comp,
 133                    const _Allocator& __a = _Allocator())
 134       : _Base(__comp, __a) { }
 135
 136       template<typename _InputIterator>
 137         map(_InputIterator __first, _InputIterator __last,
 138             const _Compare& __comp = _Compare(),
 139             const _Allocator& __a = _Allocator())
 140         : _Base(__gnu_debug::__base(
 141                   __glibcxx_check_valid_constructor_range(__first, __last)),
 142                 __gnu_debug::__base(__last),
 143                 __comp, __a) { }
 144
 145 #if __cplusplus < 201103L
 146       map&
 147       operator=(const map& __x)
 148       {
 149         this->_M_safe() = __x;
 150         _M_base() = __x;
 151         return *this;
 152       }
 153 #else
 154       map&
 155       operator=(const map&) = default;
 156
 157       map&
 158       operator=(map&&) = default;
 159
 160       map&
 161       operator=(initializer_list<value_type> __l)
 162       {
 163         _M_base() = __l;
 164         this->_M_invalidate_all();
 165         return *this;
 166       }
 167 #endif
 168
 169       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 170       // 133. map missing get_allocator()
 171       using _Base::get_allocator;
 172
 173       // iterators:
 174       iterator
 175       begin() _GLIBCXX_NOEXCEPT
 176       { return iterator(_Base::begin(), this); }
 177
 178       const_iterator
 179       begin() const _GLIBCXX_NOEXCEPT
 180       { return const_iterator(_Base::begin(), this); }
 181
 182       iterator
 183       end() _GLIBCXX_NOEXCEPT
 184       { return iterator(_Base::end(), this); }
 185
 186       const_iterator
 187       end() const _GLIBCXX_NOEXCEPT
 188       { return const_iterator(_Base::end(), this); }
 189
 190       reverse_iterator
 191       rbegin() _GLIBCXX_NOEXCEPT
 192       { return reverse_iterator(end()); }
 193
 194       const_reverse_iterator
 195       rbegin() const _GLIBCXX_NOEXCEPT
 196       { return const_reverse_iterator(end()); }
 197
 198       reverse_iterator
 199       rend() _GLIBCXX_NOEXCEPT
 200       { return reverse_iterator(begin()); }
 201
 202       const_reverse_iterator
 203       rend() const _GLIBCXX_NOEXCEPT
 204       { return const_reverse_iterator(begin()); }
 205
 206 #if __cplusplus >= 201103L
 207       const_iterator
 208       cbegin() const noexcept
 209       { return const_iterator(_Base::begin(), this); }
 210
 211       const_iterator
 212       cend() const noexcept
 213       { return const_iterator(_Base::end(), this); }
 214
 215       const_reverse_iterator
 216       crbegin() const noexcept
 217       { return const_reverse_iterator(end()); }
 218
 219       const_reverse_iterator
 220       crend() const noexcept
 221       { return const_reverse_iterator(begin()); }
 222 #endif
 223
 224       // capacity:
 225       using _Base::empty;
 226       using _Base::size;
 227       using _Base::max_size;
 228
 229       // 23.3.1.2 element access:
 230       using _Base::operator[];
 231
 232       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 233       // DR 464. Suggestion for new member functions in standard containers.
 234       using _Base::at;
 235
 236       // modifiers:
 237 #if __cplusplus >= 201103L
 238       template<typename... _Args>
 239         std::pair<iterator, bool>
 240         emplace(_Args&&... __args)
 241         {
 242           auto __res = _Base::emplace(std::forward<_Args>(__args)...);
 243           return std::pair<iterator, bool>(iterator(__res.first, this),
 244                                            __res.second);
 245         }
 246
 247       template<typename... _Args>
 248         iterator
 249         emplace_hint(const_iterator __pos, _Args&&... __args)
 250         {
 251           __glibcxx_check_insert(__pos);
 252           return iterator(_Base::emplace_hint(__pos.base(),
 253                                               std::forward<_Args>(__args)...),
 254                           this);
 255         }
 256 #endif
 257
 258       std::pair<iterator, bool>
 259       insert(const value_type& __x)
 260       {
 261         std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
 262         return std::pair<iterator, bool>(iterator(__res.first, this),
 263                                          __res.second);
 264       }
 265
 266 #if __cplusplus >= 201103L
 267       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 268       // 2354. Unnecessary copying when inserting into maps with braced-init
 269       std::pair<iterator, bool>
 270       insert(value_type&& __x)
 271       {
 272         auto __res = _Base::insert(std::move(__x));
 273         return { iterator(__res.first, this), __res.second };
 274       }
 275
 276       template<typename _Pair, typename = typename
 277                std::enable_if<std::is_constructible<value_type,
 278                                                     _Pair&&>::value>::type>
 279         std::pair<iterator, bool>
 280         insert(_Pair&& __x)
 281         {
 282           std::pair<_Base_iterator, bool> __res
 283             = _Base::insert(std::forward<_Pair>(__x));
 284           return std::pair<iterator, bool>(iterator(__res.first, this),
 285                                            __res.second);
 286         }
 287 #endif
 288
 289 #if __cplusplus >= 201103L
 290       void
 291       insert(std::initializer_list<value_type> __list)
 292       { _Base::insert(__list); }
 293 #endif
 294
 295       iterator
 296 #if __cplusplus >= 201103L
 297       insert(const_iterator __position, const value_type& __x)
 298 #else
 299       insert(iterator __position, const value_type& __x)
 300 #endif
 301       {
 302         __glibcxx_check_insert(__position);
 303         return iterator(_Base::insert(__position.base(), __x), this);
 304       }
 305
 306 #if __cplusplus >= 201103L
 307       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 308       // 2354. Unnecessary copying when inserting into maps with braced-init
 309       iterator
 310       insert(const_iterator __position, value_type&& __x)
 311       {
 312         __glibcxx_check_insert(__position);
 313         return { _Base::insert(__position.base(), std::move(__x)), this };
 314       }
 315
 316       template<typename _Pair, typename = typename
 317                std::enable_if<std::is_constructible<value_type,
 318                                                     _Pair&&>::value>::type>
 319         iterator
 320         insert(const_iterator __position, _Pair&& __x)
 321         {
 322           __glibcxx_check_insert(__position);
 323           return iterator(_Base::insert(__position.base(),
 324                                         std::forward<_Pair>(__x)), this);
 325         }
 326 #endif
 327
 328       template<typename _InputIterator>
 329         void
 330         insert(_InputIterator __first, _InputIterator __last)
 331         {
 332           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 333           __glibcxx_check_valid_range2(__first, __last, __dist);
 334
 335           if (__dist.second >= __gnu_debug::__dp_sign)
 336             _Base::insert(__gnu_debug::__unsafe(__first),
 337                           __gnu_debug::__unsafe(__last));
 338           else
 339             _Base::insert(__first, __last);
 340         }
 341
 342
 343 #if __cplusplus > 201402L
 344       template <typename... _Args>
 345         pair<iterator, bool>
 346         try_emplace(const key_type& __k, _Args&&... __args)
 347         {
 348           auto __res = _Base::try_emplace(__k,
 349                                           std::forward<_Args>(__args)...);
 350           return { iterator(__res.first, this), __res.second };
 351         }
 352
 353       template <typename... _Args>
 354         pair<iterator, bool>
 355         try_emplace(key_type&& __k, _Args&&... __args)
 356         {
 357           auto __res = _Base::try_emplace(std::move(__k),
 358                                           std::forward<_Args>(__args)...);
 359           return { iterator(__res.first, this), __res.second };
 360         }
 361
 362       template <typename... _Args>
 363         iterator
 364         try_emplace(const_iterator __hint, const key_type& __k,
 365                     _Args&&... __args)
 366         {
 367           __glibcxx_check_insert(__hint);
 368           return iterator(_Base::try_emplace(__hint.base(), __k,
 369                                              std::forward<_Args>(__args)...),
 370                           this);
 371         }
 372
 373       template <typename... _Args>
 374         iterator
 375         try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
 376         {
 377           __glibcxx_check_insert(__hint);
 378           return iterator(_Base::try_emplace(__hint.base(), std::move(__k),
 379                                              std::forward<_Args>(__args)...),
 380                           this);
 381         }
 382
 383       template <typename _Obj>
 384         std::pair<iterator, bool>
 385         insert_or_assign(const key_type& __k, _Obj&& __obj)
 386         {
 387           auto __res = _Base::insert_or_assign(__k,
 388                                                std::forward<_Obj>(__obj));
 389           return { iterator(__res.first, this), __res.second };
 390         }
 391
 392       template <typename _Obj>
 393         std::pair<iterator, bool>
 394         insert_or_assign(key_type&& __k, _Obj&& __obj)
 395         {
 396           auto __res = _Base::insert_or_assign(std::move(__k),
 397                                                std::forward<_Obj>(__obj));
 398           return { iterator(__res.first, this), __res.second };
 399         }
 400
 401       template <typename _Obj>
 402         iterator
 403         insert_or_assign(const_iterator __hint,
 404                          const key_type& __k, _Obj&& __obj)
 405         {
 406           __glibcxx_check_insert(__hint);
 407           return iterator(_Base::insert_or_assign(__hint.base(), __k,
 408                                                   std::forward<_Obj>(__obj)),
 409                           this);
 410         }
 411
 412       template <typename _Obj>
 413         iterator
 414         insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
 415         {
 416           __glibcxx_check_insert(__hint);
 417           return iterator(_Base::insert_or_assign(__hint.base(),
 418                                                   std::move(__k),
 419                                                   std::forward<_Obj>(__obj)),
 420                           this);
 421         }
 422 #endif // C++17
 423
 424 #if __cplusplus > 201402L
 425       using node_type = typename _Base::node_type;
 426       using insert_return_type = _Node_insert_return<iterator, node_type>;
 427
 428       node_type
 429       extract(const_iterator __position)
 430       {
 431         __glibcxx_check_erase(__position);
 432         this->_M_invalidate_if(_Equal(__position.base()));
 433         return _Base::extract(__position.base());
 434       }
 435
 436       node_type
 437       extract(const key_type& __key)
 438       {
 439         const auto __position = find(__key);
 440         if (__position != end())
 441           return extract(__position);
 442         return {};
 443       }
 444
 445       insert_return_type
 446       insert(node_type&& __nh)
 447       {
 448         auto __ret = _Base::insert(std::move(__nh));
 449         iterator __pos = iterator(__ret.position, this);
 450         return { __pos, __ret.inserted, std::move(__ret.node) };
 451       }
 452
 453       iterator
 454       insert(const_iterator __hint, node_type&& __nh)
 455       {
 456         __glibcxx_check_insert(__hint);
 457         return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
 458       }
 459
 460       using _Base::merge;
 461 #endif // C++17
 462
 463 #if __cplusplus >= 201103L
 464       iterator
 465       erase(const_iterator __position)
 466       {
 467         __glibcxx_check_erase(__position);
 468         this->_M_invalidate_if(_Equal(__position.base()));
 469         return iterator(_Base::erase(__position.base()), this);
 470       }
 471
 472       iterator
 473       erase(iterator __position)
 474       { return erase(const_iterator(__position)); }
 475 #else
 476       void
 477       erase(iterator __position)
 478       {
 479         __glibcxx_check_erase(__position);
 480         this->_M_invalidate_if(_Equal(__position.base()));
 481         _Base::erase(__position.base());
 482       }
 483 #endif
 484
 485       size_type
 486       erase(const key_type& __x)
 487       {
 488         _Base_iterator __victim = _Base::find(__x);
 489         if (__victim == _Base::end())
 490           return 0;
 491         else
 492           {
 493             this->_M_invalidate_if(_Equal(__victim));
 494             _Base::erase(__victim);
 495             return 1;
 496           }
 497       }
 498
 499 #if __cplusplus >= 201103L
 500       iterator
 501       erase(const_iterator __first, const_iterator __last)
 502       {
 503         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 504         // 151. can't currently clear() empty container
 505         __glibcxx_check_erase_range(__first, __last);
 506         for (_Base_const_iterator __victim = __first.base();
 507              __victim != __last.base(); ++__victim)
 508           {
 509             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 510                                   _M_message(__gnu_debug::__msg_valid_range)
 511                                   ._M_iterator(__first, "first")
 512                                   ._M_iterator(__last, "last"));
 513             this->_M_invalidate_if(_Equal(__victim));
 514           }
 515         return iterator(_Base::erase(__first.base(), __last.base()), this);
 516       }
 517 #else
 518       void
 519       erase(iterator __first, iterator __last)
 520       {
 521         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 522         // 151. can't currently clear() empty container
 523         __glibcxx_check_erase_range(__first, __last);
 524         for (_Base_iterator __victim = __first.base();
 525              __victim != __last.base(); ++__victim)
 526           {
 527             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 528                                   _M_message(__gnu_debug::__msg_valid_range)
 529                                   ._M_iterator(__first, "first")
 530                                   ._M_iterator(__last, "last"));
 531             this->_M_invalidate_if(_Equal(__victim));
 532           }
 533         _Base::erase(__first.base(), __last.base());
 534       }
 535 #endif
 536
 537       void
 538       swap(map& __x)
 539       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
 540       {
 541         _Safe::_M_swap(__x);
 542         _Base::swap(__x);
 543       }
 544
 545       void
 546       clear() _GLIBCXX_NOEXCEPT
 547       {
 548         this->_M_invalidate_all();
 549         _Base::clear();
 550       }
 551
 552       // observers:
 553       using _Base::key_comp;
 554       using _Base::value_comp;
 555
 556       // 23.3.1.3 map operations:
 557       iterator
 558       find(const key_type& __x)
 559       { return iterator(_Base::find(__x), this); }
 560
 561 #if __cplusplus > 201103L
 562       template<typename _Kt,
 563                typename _Req =
 564                  typename __has_is_transparent<_Compare, _Kt>::type>
 565         iterator
 566         find(const _Kt& __x)
 567         { return { _Base::find(__x), this }; }
 568 #endif
 569
 570       const_iterator
 571       find(const key_type& __x) const
 572       { return const_iterator(_Base::find(__x), this); }
 573
 574 #if __cplusplus > 201103L
 575       template<typename _Kt,
 576                typename _Req =
 577                  typename __has_is_transparent<_Compare, _Kt>::type>
 578         const_iterator
 579         find(const _Kt& __x) const
 580         { return { _Base::find(__x), this }; }
 581 #endif
 582
 583       using _Base::count;
 584
 585       iterator
 586       lower_bound(const key_type& __x)
 587       { return iterator(_Base::lower_bound(__x), this); }
 588
 589 #if __cplusplus > 201103L
 590       template<typename _Kt,
 591                typename _Req =
 592                  typename __has_is_transparent<_Compare, _Kt>::type>
 593         iterator
 594         lower_bound(const _Kt& __x)
 595         { return { _Base::lower_bound(__x), this }; }
 596 #endif
 597
 598       const_iterator
 599       lower_bound(const key_type& __x) const
 600       { return const_iterator(_Base::lower_bound(__x), this); }
 601
 602 #if __cplusplus > 201103L
 603       template<typename _Kt,
 604                typename _Req =
 605                  typename __has_is_transparent<_Compare, _Kt>::type>
 606         const_iterator
 607         lower_bound(const _Kt& __x) const
 608         { return { _Base::lower_bound(__x), this }; }
 609 #endif
 610
 611       iterator
 612       upper_bound(const key_type& __x)
 613       { return iterator(_Base::upper_bound(__x), this); }
 614
 615 #if __cplusplus > 201103L
 616       template<typename _Kt,
 617                typename _Req =
 618                  typename __has_is_transparent<_Compare, _Kt>::type>
 619         iterator
 620         upper_bound(const _Kt& __x)
 621         { return { _Base::upper_bound(__x), this }; }
 622 #endif
 623
 624       const_iterator
 625       upper_bound(const key_type& __x) const
 626       { return const_iterator(_Base::upper_bound(__x), this); }
 627
 628 #if __cplusplus > 201103L
 629       template<typename _Kt,
 630                typename _Req =
 631                  typename __has_is_transparent<_Compare, _Kt>::type>
 632         const_iterator
 633         upper_bound(const _Kt& __x) const
 634         { return { _Base::upper_bound(__x), this }; }
 635 #endif
 636
 637       std::pair<iterator,iterator>
 638       equal_range(const key_type& __x)
 639       {
 640         std::pair<_Base_iterator, _Base_iterator> __res =
 641         _Base::equal_range(__x);
 642         return std::make_pair(iterator(__res.first, this),
 643                               iterator(__res.second, this));
 644       }
 645
 646 #if __cplusplus > 201103L
 647       template<typename _Kt,
 648                typename _Req =
 649                  typename __has_is_transparent<_Compare, _Kt>::type>
 650         std::pair<iterator, iterator>
 651         equal_range(const _Kt& __x)
 652         {
 653           auto __res = _Base::equal_range(__x);
 654           return { { __res.first, this }, { __res.second, this } };
 655         }
 656 #endif
 657
 658       std::pair<const_iterator,const_iterator>
 659       equal_range(const key_type& __x) const
 660       {
 661         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 662         _Base::equal_range(__x);
 663         return std::make_pair(const_iterator(__res.first, this),
 664                               const_iterator(__res.second, this));
 665       }
 666
 667 #if __cplusplus > 201103L
 668       template<typename _Kt,
 669                typename _Req =
 670                  typename __has_is_transparent<_Compare, _Kt>::type>
 671         std::pair<const_iterator, const_iterator>
 672         equal_range(const _Kt& __x) const
 673         {
 674           auto __res = _Base::equal_range(__x);
 675           return { { __res.first, this }, { __res.second, this } };
 676         }
 677 #endif
 678
 679       _Base&
 680       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
 681
 682       const _Base&
 683       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 684     };
 685
 686 #if __cpp_deduction_guides >= 201606
 687
 688  template<typename _InputIterator,
 689           typename _Compare = less<__iter_key_t<_InputIterator>>,
 690           typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
 691           typename = _RequireInputIter<_InputIterator>,
 692           typename = _RequireAllocator<_Allocator>>
 693   map(_InputIterator, _InputIterator,
 694       _Compare = _Compare(), _Allocator = _Allocator())
 695   -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
 696          _Compare, _Allocator>;
 697
 698  template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
 699           typename _Allocator = allocator<pair<const _Key, _Tp>>,
 700           typename = _RequireAllocator<_Allocator>>
 701    map(initializer_list<pair<_Key, _Tp>>,
 702        _Compare = _Compare(), _Allocator = _Allocator())
 703    -> map<_Key, _Tp, _Compare, _Allocator>;
 704
 705  template <typename _InputIterator, typename _Allocator,
 706            typename = _RequireInputIter<_InputIterator>,
 707            typename = _RequireAllocator<_Allocator>>
 708    map(_InputIterator, _InputIterator, _Allocator)
 709    -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
 710           less<__iter_key_t<_InputIterator>>, _Allocator>;
 711
 712  template<typename _Key, typename _Tp, typename _Allocator,
 713           typename = _RequireAllocator<_Allocator>>
 714    map(initializer_list<pair<_Key, _Tp>>, _Allocator)
 715    -> map<_Key, _Tp, less<_Key>, _Allocator>;
 716
 717 #endif
 718
 719   template<typename _Key, typename _Tp,
 720            typename _Compare, typename _Allocator>
 721     inline bool
 722     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 723                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 724     { return __lhs._M_base() == __rhs._M_base(); }
 725
 726   template<typename _Key, typename _Tp,
 727            typename _Compare, typename _Allocator>
 728     inline bool
 729     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 730                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 731     { return __lhs._M_base() != __rhs._M_base(); }
 732
 733   template<typename _Key, typename _Tp,
 734            typename _Compare, typename _Allocator>
 735     inline bool
 736     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 737               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 738     { return __lhs._M_base() < __rhs._M_base(); }
 739
 740   template<typename _Key, typename _Tp,
 741            typename _Compare, typename _Allocator>
 742     inline bool
 743     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 744                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 745     { return __lhs._M_base() <= __rhs._M_base(); }
 746
 747   template<typename _Key, typename _Tp,
 748            typename _Compare, typename _Allocator>
 749     inline bool
 750     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 751                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 752     { return __lhs._M_base() >= __rhs._M_base(); }
 753
 754   template<typename _Key, typename _Tp,
 755            typename _Compare, typename _Allocator>
 756     inline bool
 757     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 758               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 759     { return __lhs._M_base() > __rhs._M_base(); }
 760
 761   template<typename _Key, typename _Tp,
 762            typename _Compare, typename _Allocator>
 763     inline void
 764     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 765          map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 766     _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
 767     { __lhs.swap(__rhs); }
 768
 769 } // namespace __debug
 770 } // namespace std
 771
 772 #endif