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

   1 // Debugging map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2020 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 { { __res.first, this }, __res.second };
 244         }
 245
 246       template<typename... _Args>
 247         iterator
 248         emplace_hint(const_iterator __pos, _Args&&... __args)
 249         {
 250           __glibcxx_check_insert(__pos);
 251           return
 252             {
 253               _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
 254               this
 255             };
 256         }
 257 #endif
 258
 259       std::pair<iterator, bool>
 260       insert(const value_type& __x)
 261       {
 262         std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
 263         return std::pair<iterator, bool>(iterator(__res.first, this),
 264                                          __res.second);
 265       }
 266
 267 #if __cplusplus >= 201103L
 268       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 269       // 2354. Unnecessary copying when inserting into maps with braced-init
 270       std::pair<iterator, bool>
 271       insert(value_type&& __x)
 272       {
 273         auto __res = _Base::insert(std::move(__x));
 274         return { { __res.first, this }, __res.second };
 275       }
 276
 277       template<typename _Pair, typename = typename
 278                std::enable_if<std::is_constructible<value_type,
 279                                                     _Pair&&>::value>::type>
 280         std::pair<iterator, bool>
 281         insert(_Pair&& __x)
 282         {
 283           auto __res = _Base::insert(std::forward<_Pair>(__x));
 284           return { { __res.first, this }, __res.second };
 285         }
 286 #endif
 287
 288 #if __cplusplus >= 201103L
 289       void
 290       insert(std::initializer_list<value_type> __list)
 291       { _Base::insert(__list); }
 292 #endif
 293
 294       iterator
 295 #if __cplusplus >= 201103L
 296       insert(const_iterator __position, const value_type& __x)
 297 #else
 298       insert(iterator __position, const value_type& __x)
 299 #endif
 300       {
 301         __glibcxx_check_insert(__position);
 302         return iterator(_Base::insert(__position.base(), __x), this);
 303       }
 304
 305 #if __cplusplus >= 201103L
 306       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 307       // 2354. Unnecessary copying when inserting into maps with braced-init
 308       iterator
 309       insert(const_iterator __position, value_type&& __x)
 310       {
 311         __glibcxx_check_insert(__position);
 312         return { _Base::insert(__position.base(), std::move(__x)), this };
 313       }
 314
 315       template<typename _Pair, typename = typename
 316                std::enable_if<std::is_constructible<value_type,
 317                                                     _Pair&&>::value>::type>
 318         iterator
 319         insert(const_iterator __position, _Pair&& __x)
 320         {
 321           __glibcxx_check_insert(__position);
 322           return
 323             {
 324               _Base::insert(__position.base(), std::forward<_Pair>(__x)),
 325               this
 326             };
 327         }
 328 #endif
 329
 330       template<typename _InputIterator>
 331         void
 332         insert(_InputIterator __first, _InputIterator __last)
 333         {
 334           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
 335           __glibcxx_check_valid_range2(__first, __last, __dist);
 336
 337           if (__dist.second >= __gnu_debug::__dp_sign)
 338             _Base::insert(__gnu_debug::__unsafe(__first),
 339                           __gnu_debug::__unsafe(__last));
 340           else
 341             _Base::insert(__first, __last);
 342         }
 343
 344
 345 #if __cplusplus > 201402L
 346       template <typename... _Args>
 347         pair<iterator, bool>
 348         try_emplace(const key_type& __k, _Args&&... __args)
 349         {
 350           auto __res = _Base::try_emplace(__k,
 351                                           std::forward<_Args>(__args)...);
 352           return { { __res.first, this }, __res.second };
 353         }
 354
 355       template <typename... _Args>
 356         pair<iterator, bool>
 357         try_emplace(key_type&& __k, _Args&&... __args)
 358         {
 359           auto __res = _Base::try_emplace(std::move(__k),
 360                                           std::forward<_Args>(__args)...);
 361           return { { __res.first, this }, __res.second };
 362         }
 363
 364       template <typename... _Args>
 365         iterator
 366         try_emplace(const_iterator __hint, const key_type& __k,
 367                     _Args&&... __args)
 368         {
 369           __glibcxx_check_insert(__hint);
 370           return
 371             {
 372               _Base::try_emplace(__hint.base(), __k,
 373                                  std::forward<_Args>(__args)...),
 374               this
 375             };
 376         }
 377
 378       template <typename... _Args>
 379         iterator
 380         try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
 381         {
 382           __glibcxx_check_insert(__hint);
 383           return
 384             {
 385               _Base::try_emplace(__hint.base(), std::move(__k),
 386                                  std::forward<_Args>(__args)...),
 387               this
 388             };
 389         }
 390
 391       template <typename _Obj>
 392         std::pair<iterator, bool>
 393         insert_or_assign(const key_type& __k, _Obj&& __obj)
 394         {
 395           auto __res = _Base::insert_or_assign(__k,
 396                                                std::forward<_Obj>(__obj));
 397           return { { __res.first, this }, __res.second };
 398         }
 399
 400       template <typename _Obj>
 401         std::pair<iterator, bool>
 402         insert_or_assign(key_type&& __k, _Obj&& __obj)
 403         {
 404           auto __res = _Base::insert_or_assign(std::move(__k),
 405                                                std::forward<_Obj>(__obj));
 406           return { { __res.first, this }, __res.second };
 407         }
 408
 409       template <typename _Obj>
 410         iterator
 411         insert_or_assign(const_iterator __hint,
 412                          const key_type& __k, _Obj&& __obj)
 413         {
 414           __glibcxx_check_insert(__hint);
 415           return
 416             {
 417               _Base::insert_or_assign(__hint.base(), __k,
 418                                       std::forward<_Obj>(__obj)),
 419               this
 420             };
 421         }
 422
 423       template <typename _Obj>
 424         iterator
 425         insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
 426         {
 427           __glibcxx_check_insert(__hint);
 428           return
 429             {
 430               _Base::insert_or_assign(__hint.base(), std::move(__k),
 431                                       std::forward<_Obj>(__obj)),
 432               this
 433             };
 434         }
 435 #endif // C++17
 436
 437 #if __cplusplus > 201402L
 438       using node_type = typename _Base::node_type;
 439       using insert_return_type = _Node_insert_return<iterator, node_type>;
 440
 441       node_type
 442       extract(const_iterator __position)
 443       {
 444         __glibcxx_check_erase(__position);
 445         this->_M_invalidate_if(_Equal(__position.base()));
 446         return _Base::extract(__position.base());
 447       }
 448
 449       node_type
 450       extract(const key_type& __key)
 451       {
 452         const auto __position = find(__key);
 453         if (__position != end())
 454           return extract(__position);
 455         return {};
 456       }
 457
 458       insert_return_type
 459       insert(node_type&& __nh)
 460       {
 461         auto __ret = _Base::insert(std::move(__nh));
 462         return
 463           { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
 464       }
 465
 466       iterator
 467       insert(const_iterator __hint, node_type&& __nh)
 468       {
 469         __glibcxx_check_insert(__hint);
 470         return { _Base::insert(__hint.base(), std::move(__nh)), this };
 471       }
 472
 473       using _Base::merge;
 474 #endif // C++17
 475
 476 #if __cplusplus >= 201103L
 477       iterator
 478       erase(const_iterator __position)
 479       {
 480         __glibcxx_check_erase(__position);
 481         this->_M_invalidate_if(_Equal(__position.base()));
 482         return { _Base::erase(__position.base()), this };
 483       }
 484
 485       _GLIBCXX_ABI_TAG_CXX11
 486       iterator
 487       erase(iterator __position)
 488       { return erase(const_iterator(__position)); }
 489 #else
 490       void
 491       erase(iterator __position)
 492       {
 493         __glibcxx_check_erase(__position);
 494         this->_M_invalidate_if(_Equal(__position.base()));
 495         _Base::erase(__position.base());
 496       }
 497 #endif
 498
 499       size_type
 500       erase(const key_type& __x)
 501       {
 502         _Base_iterator __victim = _Base::find(__x);
 503         if (__victim == _Base::end())
 504           return 0;
 505         else
 506           {
 507             this->_M_invalidate_if(_Equal(__victim));
 508             _Base::erase(__victim);
 509             return 1;
 510           }
 511       }
 512
 513 #if __cplusplus >= 201103L
 514       iterator
 515       erase(const_iterator __first, const_iterator __last)
 516       {
 517         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 518         // 151. can't currently clear() empty container
 519         __glibcxx_check_erase_range(__first, __last);
 520         for (_Base_const_iterator __victim = __first.base();
 521              __victim != __last.base(); ++__victim)
 522           {
 523             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
 524                                   _M_message(__gnu_debug::__msg_valid_range)
 525                                   ._M_iterator(__first, "first")
 526                                   ._M_iterator(__last, "last"));
 527             this->_M_invalidate_if(_Equal(__victim));
 528           }
 529
 530         return { _Base::erase(__first.base(), __last.base()), this };
 531       }
 532 #else
 533       void
 534       erase(iterator __first, iterator __last)
 535       {
 536         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 537         // 151. can't currently clear() empty container
 538         __glibcxx_check_erase_range(__first, __last);
 539         for (_Base_iterator __victim = __first.base();
 540              __victim != __last.base(); ++__victim)
 541           {
 542             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 543                                   _M_message(__gnu_debug::__msg_valid_range)
 544                                   ._M_iterator(__first, "first")
 545                                   ._M_iterator(__last, "last"));
 546             this->_M_invalidate_if(_Equal(__victim));
 547           }
 548         _Base::erase(__first.base(), __last.base());
 549       }
 550 #endif
 551
 552       void
 553       swap(map& __x)
 554       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
 555       {
 556         _Safe::_M_swap(__x);
 557         _Base::swap(__x);
 558       }
 559
 560       void
 561       clear() _GLIBCXX_NOEXCEPT
 562       {
 563         this->_M_invalidate_all();
 564         _Base::clear();
 565       }
 566
 567       // observers:
 568       using _Base::key_comp;
 569       using _Base::value_comp;
 570
 571       // 23.3.1.3 map operations:
 572       iterator
 573       find(const key_type& __x)
 574       { return iterator(_Base::find(__x), this); }
 575
 576 #if __cplusplus > 201103L
 577       template<typename _Kt,
 578                typename _Req =
 579                  typename __has_is_transparent<_Compare, _Kt>::type>
 580         iterator
 581         find(const _Kt& __x)
 582         { return { _Base::find(__x), this }; }
 583 #endif
 584
 585       const_iterator
 586       find(const key_type& __x) const
 587       { return const_iterator(_Base::find(__x), this); }
 588
 589 #if __cplusplus > 201103L
 590       template<typename _Kt,
 591                typename _Req =
 592                  typename __has_is_transparent<_Compare, _Kt>::type>
 593         const_iterator
 594         find(const _Kt& __x) const
 595         { return { _Base::find(__x), this }; }
 596 #endif
 597
 598       using _Base::count;
 599
 600       iterator
 601       lower_bound(const key_type& __x)
 602       { return iterator(_Base::lower_bound(__x), this); }
 603
 604 #if __cplusplus > 201103L
 605       template<typename _Kt,
 606                typename _Req =
 607                  typename __has_is_transparent<_Compare, _Kt>::type>
 608         iterator
 609         lower_bound(const _Kt& __x)
 610         { return { _Base::lower_bound(__x), this }; }
 611 #endif
 612
 613       const_iterator
 614       lower_bound(const key_type& __x) const
 615       { return const_iterator(_Base::lower_bound(__x), this); }
 616
 617 #if __cplusplus > 201103L
 618       template<typename _Kt,
 619                typename _Req =
 620                  typename __has_is_transparent<_Compare, _Kt>::type>
 621         const_iterator
 622         lower_bound(const _Kt& __x) const
 623         { return { _Base::lower_bound(__x), this }; }
 624 #endif
 625
 626       iterator
 627       upper_bound(const key_type& __x)
 628       { return iterator(_Base::upper_bound(__x), this); }
 629
 630 #if __cplusplus > 201103L
 631       template<typename _Kt,
 632                typename _Req =
 633                  typename __has_is_transparent<_Compare, _Kt>::type>
 634         iterator
 635         upper_bound(const _Kt& __x)
 636         { return { _Base::upper_bound(__x), this }; }
 637 #endif
 638
 639       const_iterator
 640       upper_bound(const key_type& __x) const
 641       { return const_iterator(_Base::upper_bound(__x), this); }
 642
 643 #if __cplusplus > 201103L
 644       template<typename _Kt,
 645                typename _Req =
 646                  typename __has_is_transparent<_Compare, _Kt>::type>
 647         const_iterator
 648         upper_bound(const _Kt& __x) const
 649         { return { _Base::upper_bound(__x), this }; }
 650 #endif
 651
 652       std::pair<iterator,iterator>
 653       equal_range(const key_type& __x)
 654       {
 655         std::pair<_Base_iterator, _Base_iterator> __res =
 656         _Base::equal_range(__x);
 657         return std::make_pair(iterator(__res.first, this),
 658                               iterator(__res.second, this));
 659       }
 660
 661 #if __cplusplus > 201103L
 662       template<typename _Kt,
 663                typename _Req =
 664                  typename __has_is_transparent<_Compare, _Kt>::type>
 665         std::pair<iterator, iterator>
 666         equal_range(const _Kt& __x)
 667         {
 668           auto __res = _Base::equal_range(__x);
 669           return { { __res.first, this }, { __res.second, this } };
 670         }
 671 #endif
 672
 673       std::pair<const_iterator,const_iterator>
 674       equal_range(const key_type& __x) const
 675       {
 676         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 677         _Base::equal_range(__x);
 678         return std::make_pair(const_iterator(__res.first, this),
 679                               const_iterator(__res.second, this));
 680       }
 681
 682 #if __cplusplus > 201103L
 683       template<typename _Kt,
 684                typename _Req =
 685                  typename __has_is_transparent<_Compare, _Kt>::type>
 686         std::pair<const_iterator, const_iterator>
 687         equal_range(const _Kt& __x) const
 688         {
 689           auto __res = _Base::equal_range(__x);
 690           return { { __res.first, this }, { __res.second, this } };
 691         }
 692 #endif
 693
 694       _Base&
 695       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
 696
 697       const _Base&
 698       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 699     };
 700
 701 #if __cpp_deduction_guides >= 201606
 702
 703   template<typename _InputIterator,
 704            typename _Compare = less<__iter_key_t<_InputIterator>>,
 705            typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
 706            typename = _RequireInputIter<_InputIterator>,
 707            typename = _RequireNotAllocator<_Compare>,
 708            typename = _RequireAllocator<_Allocator>>
 709     map(_InputIterator, _InputIterator,
 710         _Compare = _Compare(), _Allocator = _Allocator())
 711     -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
 712            _Compare, _Allocator>;
 713
 714   template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
 715            typename _Allocator = allocator<pair<const _Key, _Tp>>,
 716            typename = _RequireNotAllocator<_Compare>,
 717            typename = _RequireAllocator<_Allocator>>
 718     map(initializer_list<pair<_Key, _Tp>>,
 719         _Compare = _Compare(), _Allocator = _Allocator())
 720     -> map<_Key, _Tp, _Compare, _Allocator>;
 721
 722   template <typename _InputIterator, typename _Allocator,
 723             typename = _RequireInputIter<_InputIterator>,
 724             typename = _RequireAllocator<_Allocator>>
 725     map(_InputIterator, _InputIterator, _Allocator)
 726     -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
 727            less<__iter_key_t<_InputIterator>>, _Allocator>;
 728
 729   template<typename _Key, typename _Tp, typename _Allocator,
 730            typename = _RequireAllocator<_Allocator>>
 731     map(initializer_list<pair<_Key, _Tp>>, _Allocator)
 732     -> map<_Key, _Tp, less<_Key>, _Allocator>;
 733
 734 #endif
 735
 736   template<typename _Key, typename _Tp,
 737            typename _Compare, typename _Allocator>
 738     inline bool
 739     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 740                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 741     { return __lhs._M_base() == __rhs._M_base(); }
 742
 743   template<typename _Key, typename _Tp,
 744            typename _Compare, typename _Allocator>
 745     inline bool
 746     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 747                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 748     { return __lhs._M_base() != __rhs._M_base(); }
 749
 750   template<typename _Key, typename _Tp,
 751            typename _Compare, typename _Allocator>
 752     inline bool
 753     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 754               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 755     { return __lhs._M_base() < __rhs._M_base(); }
 756
 757   template<typename _Key, typename _Tp,
 758            typename _Compare, typename _Allocator>
 759     inline bool
 760     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 761                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 762     { return __lhs._M_base() <= __rhs._M_base(); }
 763
 764   template<typename _Key, typename _Tp,
 765            typename _Compare, typename _Allocator>
 766     inline bool
 767     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 768                const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 769     { return __lhs._M_base() >= __rhs._M_base(); }
 770
 771   template<typename _Key, typename _Tp,
 772            typename _Compare, typename _Allocator>
 773     inline bool
 774     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 775               const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 776     { return __lhs._M_base() > __rhs._M_base(); }
 777
 778   template<typename _Key, typename _Tp,
 779            typename _Compare, typename _Allocator>
 780     inline void
 781     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
 782          map<_Key, _Tp, _Compare, _Allocator>& __rhs)
 783     _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
 784     { __lhs.swap(__rhs); }
 785
 786 } // namespace __debug
 787 } // namespace std
 788
 789 #endif