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

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