libstdc++
map.h
Go to the documentation of this file.
1 // Debugging map implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2022 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), __a)) )
122  : _Safe(std::move(__m), __a),
123  _Base(std::move(__m), __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&) = default;
158 
159  map&
160  operator=(map&&) = default;
161 
162  map&
163  operator=(initializer_list<value_type> __l)
164  {
165  _Base::operator=(__l);
166  this->_M_invalidate_all();
167  return *this;
168  }
169 #endif
170 
171  // _GLIBCXX_RESOLVE_LIB_DEFECTS
172  // 133. map missing get_allocator()
173  using _Base::get_allocator;
174 
175  // iterators:
176  iterator
177  begin() _GLIBCXX_NOEXCEPT
178  { return iterator(_Base::begin(), this); }
179 
180  const_iterator
181  begin() const _GLIBCXX_NOEXCEPT
182  { return const_iterator(_Base::begin(), this); }
183 
184  iterator
185  end() _GLIBCXX_NOEXCEPT
186  { return iterator(_Base::end(), this); }
187 
188  const_iterator
189  end() const _GLIBCXX_NOEXCEPT
190  { return const_iterator(_Base::end(), this); }
191 
192  reverse_iterator
193  rbegin() _GLIBCXX_NOEXCEPT
194  { return reverse_iterator(end()); }
195 
196  const_reverse_iterator
197  rbegin() const _GLIBCXX_NOEXCEPT
198  { return const_reverse_iterator(end()); }
199 
200  reverse_iterator
201  rend() _GLIBCXX_NOEXCEPT
202  { return reverse_iterator(begin()); }
203 
204  const_reverse_iterator
205  rend() const _GLIBCXX_NOEXCEPT
206  { return const_reverse_iterator(begin()); }
207 
208 #if __cplusplus >= 201103L
209  const_iterator
210  cbegin() const noexcept
211  { return const_iterator(_Base::begin(), this); }
212 
213  const_iterator
214  cend() const noexcept
215  { return const_iterator(_Base::end(), this); }
216 
217  const_reverse_iterator
218  crbegin() const noexcept
219  { return const_reverse_iterator(end()); }
220 
221  const_reverse_iterator
222  crend() const noexcept
223  { return const_reverse_iterator(begin()); }
224 #endif
225 
226  // capacity:
227  using _Base::empty;
228  using _Base::size;
229  using _Base::max_size;
230 
231  // 23.3.1.2 element access:
232  using _Base::operator[];
233 
234  // _GLIBCXX_RESOLVE_LIB_DEFECTS
235  // DR 464. Suggestion for new member functions in standard containers.
236  using _Base::at;
237 
238  // modifiers:
239 #if __cplusplus >= 201103L
240  template<typename... _Args>
241  std::pair<iterator, bool>
242  emplace(_Args&&... __args)
243  {
244  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
245  return { { __res.first, this }, __res.second };
246  }
247 
248  template<typename... _Args>
249  iterator
250  emplace_hint(const_iterator __pos, _Args&&... __args)
251  {
252  __glibcxx_check_insert(__pos);
253  return
254  {
255  _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
256  this
257  };
258  }
259 #endif
260 
261  std::pair<iterator, bool>
262  insert(const value_type& __x)
263  {
264  std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
265  return std::pair<iterator, bool>(iterator(__res.first, this),
266  __res.second);
267  }
268 
269 #if __cplusplus >= 201103L
270  // _GLIBCXX_RESOLVE_LIB_DEFECTS
271  // 2354. Unnecessary copying when inserting into maps with braced-init
272  std::pair<iterator, bool>
273  insert(value_type&& __x)
274  {
275  auto __res = _Base::insert(std::move(__x));
276  return { { __res.first, this }, __res.second };
277  }
278 
279  template<typename _Pair, typename = typename
280  std::enable_if<std::is_constructible<value_type,
281  _Pair&&>::value>::type>
282  std::pair<iterator, bool>
283  insert(_Pair&& __x)
284  {
285  auto __res = _Base::insert(std::forward<_Pair>(__x));
286  return { { __res.first, this }, __res.second };
287  }
288 #endif
289 
290 #if __cplusplus >= 201103L
291  void
292  insert(std::initializer_list<value_type> __list)
293  { _Base::insert(__list); }
294 #endif
295 
296  iterator
297 #if __cplusplus >= 201103L
298  insert(const_iterator __position, const value_type& __x)
299 #else
300  insert(iterator __position, const value_type& __x)
301 #endif
302  {
303  __glibcxx_check_insert(__position);
304  return iterator(_Base::insert(__position.base(), __x), this);
305  }
306 
307 #if __cplusplus >= 201103L
308  // _GLIBCXX_RESOLVE_LIB_DEFECTS
309  // 2354. Unnecessary copying when inserting into maps with braced-init
310  iterator
311  insert(const_iterator __position, value_type&& __x)
312  {
313  __glibcxx_check_insert(__position);
314  return { _Base::insert(__position.base(), std::move(__x)), this };
315  }
316 
317  template<typename _Pair, typename = typename
318  std::enable_if<std::is_constructible<value_type,
319  _Pair&&>::value>::type>
320  iterator
321  insert(const_iterator __position, _Pair&& __x)
322  {
323  __glibcxx_check_insert(__position);
324  return
325  {
326  _Base::insert(__position.base(), std::forward<_Pair>(__x)),
327  this
328  };
329  }
330 #endif
331 
332  template<typename _InputIterator>
333  void
334  insert(_InputIterator __first, _InputIterator __last)
335  {
336  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
337  __glibcxx_check_valid_range2(__first, __last, __dist);
338 
339  if (__dist.second >= __gnu_debug::__dp_sign)
340  _Base::insert(__gnu_debug::__unsafe(__first),
341  __gnu_debug::__unsafe(__last));
342  else
343  _Base::insert(__first, __last);
344  }
345 
346 
347 #if __cplusplus > 201402L
348  template <typename... _Args>
349  pair<iterator, bool>
350  try_emplace(const key_type& __k, _Args&&... __args)
351  {
352  auto __res = _Base::try_emplace(__k,
353  std::forward<_Args>(__args)...);
354  return { { __res.first, this }, __res.second };
355  }
356 
357  template <typename... _Args>
358  pair<iterator, bool>
359  try_emplace(key_type&& __k, _Args&&... __args)
360  {
361  auto __res = _Base::try_emplace(std::move(__k),
362  std::forward<_Args>(__args)...);
363  return { { __res.first, this }, __res.second };
364  }
365 
366  template <typename... _Args>
367  iterator
368  try_emplace(const_iterator __hint, const key_type& __k,
369  _Args&&... __args)
370  {
371  __glibcxx_check_insert(__hint);
372  return
373  {
374  _Base::try_emplace(__hint.base(), __k,
375  std::forward<_Args>(__args)...),
376  this
377  };
378  }
379 
380  template <typename... _Args>
381  iterator
382  try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
383  {
384  __glibcxx_check_insert(__hint);
385  return
386  {
387  _Base::try_emplace(__hint.base(), std::move(__k),
388  std::forward<_Args>(__args)...),
389  this
390  };
391  }
392 
393  template <typename _Obj>
394  std::pair<iterator, bool>
395  insert_or_assign(const key_type& __k, _Obj&& __obj)
396  {
397  auto __res = _Base::insert_or_assign(__k,
398  std::forward<_Obj>(__obj));
399  return { { __res.first, this }, __res.second };
400  }
401 
402  template <typename _Obj>
403  std::pair<iterator, bool>
404  insert_or_assign(key_type&& __k, _Obj&& __obj)
405  {
406  auto __res = _Base::insert_or_assign(std::move(__k),
407  std::forward<_Obj>(__obj));
408  return { { __res.first, this }, __res.second };
409  }
410 
411  template <typename _Obj>
412  iterator
413  insert_or_assign(const_iterator __hint,
414  const key_type& __k, _Obj&& __obj)
415  {
416  __glibcxx_check_insert(__hint);
417  return
418  {
419  _Base::insert_or_assign(__hint.base(), __k,
420  std::forward<_Obj>(__obj)),
421  this
422  };
423  }
424 
425  template <typename _Obj>
426  iterator
427  insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
428  {
429  __glibcxx_check_insert(__hint);
430  return
431  {
432  _Base::insert_or_assign(__hint.base(), std::move(__k),
433  std::forward<_Obj>(__obj)),
434  this
435  };
436  }
437 #endif // C++17
438 
439 #if __cplusplus > 201402L
440  using node_type = typename _Base::node_type;
441  using insert_return_type = _Node_insert_return<iterator, node_type>;
442 
443  node_type
444  extract(const_iterator __position)
445  {
446  __glibcxx_check_erase(__position);
447  this->_M_invalidate_if(_Equal(__position.base()));
448  return _Base::extract(__position.base());
449  }
450 
451  node_type
452  extract(const key_type& __key)
453  {
454  const auto __position = find(__key);
455  if (__position != end())
456  return extract(__position);
457  return {};
458  }
459 
460  insert_return_type
461  insert(node_type&& __nh)
462  {
463  auto __ret = _Base::insert(std::move(__nh));
464  return
465  { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
466  }
467 
468  iterator
469  insert(const_iterator __hint, node_type&& __nh)
470  {
471  __glibcxx_check_insert(__hint);
472  return { _Base::insert(__hint.base(), std::move(__nh)), this };
473  }
474 
475  using _Base::merge;
476 #endif // C++17
477 
478 #if __cplusplus >= 201103L
479  iterator
480  erase(const_iterator __position)
481  {
482  __glibcxx_check_erase(__position);
483  return { erase(__position.base()), this };
484  }
485 
486  _Base_iterator
487  erase(_Base_const_iterator __position)
488  {
489  __glibcxx_check_erase2(__position);
490  this->_M_invalidate_if(_Equal(__position));
491  return _Base::erase(__position);
492  }
493 
494  _GLIBCXX_ABI_TAG_CXX11
495  iterator
496  erase(iterator __position)
497  { return erase(const_iterator(__position)); }
498 #else
499  void
500  erase(iterator __position)
501  {
502  __glibcxx_check_erase(__position);
503  this->_M_invalidate_if(_Equal(__position.base()));
504  _Base::erase(__position.base());
505  }
506 #endif
507 
508  size_type
509  erase(const key_type& __x)
510  {
511  _Base_iterator __victim = _Base::find(__x);
512  if (__victim == _Base::end())
513  return 0;
514  else
515  {
516  this->_M_invalidate_if(_Equal(__victim));
517  _Base::erase(__victim);
518  return 1;
519  }
520  }
521 
522 #if __cplusplus >= 201103L
523  iterator
524  erase(const_iterator __first, const_iterator __last)
525  {
526  // _GLIBCXX_RESOLVE_LIB_DEFECTS
527  // 151. can't currently clear() empty container
528  __glibcxx_check_erase_range(__first, __last);
529  for (_Base_const_iterator __victim = __first.base();
530  __victim != __last.base(); ++__victim)
531  {
532  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
533  _M_message(__gnu_debug::__msg_valid_range)
534  ._M_iterator(__first, "first")
535  ._M_iterator(__last, "last"));
536  this->_M_invalidate_if(_Equal(__victim));
537  }
538 
539  return { _Base::erase(__first.base(), __last.base()), this };
540  }
541 #else
542  void
543  erase(iterator __first, iterator __last)
544  {
545  // _GLIBCXX_RESOLVE_LIB_DEFECTS
546  // 151. can't currently clear() empty container
547  __glibcxx_check_erase_range(__first, __last);
548  for (_Base_iterator __victim = __first.base();
549  __victim != __last.base(); ++__victim)
550  {
551  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
552  _M_message(__gnu_debug::__msg_valid_range)
553  ._M_iterator(__first, "first")
554  ._M_iterator(__last, "last"));
555  this->_M_invalidate_if(_Equal(__victim));
556  }
557  _Base::erase(__first.base(), __last.base());
558  }
559 #endif
560 
561  void
562  swap(map& __x)
563  _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
564  {
565  _Safe::_M_swap(__x);
566  _Base::swap(__x);
567  }
568 
569  void
570  clear() _GLIBCXX_NOEXCEPT
571  {
572  this->_M_invalidate_all();
573  _Base::clear();
574  }
575 
576  // observers:
577  using _Base::key_comp;
578  using _Base::value_comp;
579 
580  // 23.3.1.3 map operations:
581  iterator
582  find(const key_type& __x)
583  { return iterator(_Base::find(__x), this); }
584 
585 #if __cplusplus > 201103L
586  template<typename _Kt,
587  typename _Req =
588  typename __has_is_transparent<_Compare, _Kt>::type>
589  iterator
590  find(const _Kt& __x)
591  { return { _Base::find(__x), this }; }
592 #endif
593 
594  const_iterator
595  find(const key_type& __x) const
596  { return const_iterator(_Base::find(__x), this); }
597 
598 #if __cplusplus > 201103L
599  template<typename _Kt,
600  typename _Req =
601  typename __has_is_transparent<_Compare, _Kt>::type>
602  const_iterator
603  find(const _Kt& __x) const
604  { return { _Base::find(__x), this }; }
605 #endif
606 
607  using _Base::count;
608 
609  iterator
610  lower_bound(const key_type& __x)
611  { return iterator(_Base::lower_bound(__x), this); }
612 
613 #if __cplusplus > 201103L
614  template<typename _Kt,
615  typename _Req =
616  typename __has_is_transparent<_Compare, _Kt>::type>
617  iterator
618  lower_bound(const _Kt& __x)
619  { return { _Base::lower_bound(__x), this }; }
620 #endif
621 
622  const_iterator
623  lower_bound(const key_type& __x) const
624  { return const_iterator(_Base::lower_bound(__x), this); }
625 
626 #if __cplusplus > 201103L
627  template<typename _Kt,
628  typename _Req =
629  typename __has_is_transparent<_Compare, _Kt>::type>
630  const_iterator
631  lower_bound(const _Kt& __x) const
632  { return { _Base::lower_bound(__x), this }; }
633 #endif
634 
635  iterator
636  upper_bound(const key_type& __x)
637  { return iterator(_Base::upper_bound(__x), this); }
638 
639 #if __cplusplus > 201103L
640  template<typename _Kt,
641  typename _Req =
642  typename __has_is_transparent<_Compare, _Kt>::type>
643  iterator
644  upper_bound(const _Kt& __x)
645  { return { _Base::upper_bound(__x), this }; }
646 #endif
647 
648  const_iterator
649  upper_bound(const key_type& __x) const
650  { return const_iterator(_Base::upper_bound(__x), this); }
651 
652 #if __cplusplus > 201103L
653  template<typename _Kt,
654  typename _Req =
655  typename __has_is_transparent<_Compare, _Kt>::type>
656  const_iterator
657  upper_bound(const _Kt& __x) const
658  { return { _Base::upper_bound(__x), this }; }
659 #endif
660 
661  std::pair<iterator,iterator>
662  equal_range(const key_type& __x)
663  {
664  std::pair<_Base_iterator, _Base_iterator> __res =
665  _Base::equal_range(__x);
666  return std::make_pair(iterator(__res.first, this),
667  iterator(__res.second, this));
668  }
669 
670 #if __cplusplus > 201103L
671  template<typename _Kt,
672  typename _Req =
673  typename __has_is_transparent<_Compare, _Kt>::type>
674  std::pair<iterator, iterator>
675  equal_range(const _Kt& __x)
676  {
677  auto __res = _Base::equal_range(__x);
678  return { { __res.first, this }, { __res.second, this } };
679  }
680 #endif
681 
682  std::pair<const_iterator,const_iterator>
683  equal_range(const key_type& __x) const
684  {
685  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
686  _Base::equal_range(__x);
687  return std::make_pair(const_iterator(__res.first, this),
688  const_iterator(__res.second, this));
689  }
690 
691 #if __cplusplus > 201103L
692  template<typename _Kt,
693  typename _Req =
694  typename __has_is_transparent<_Compare, _Kt>::type>
695  std::pair<const_iterator, const_iterator>
696  equal_range(const _Kt& __x) const
697  {
698  auto __res = _Base::equal_range(__x);
699  return { { __res.first, this }, { __res.second, this } };
700  }
701 #endif
702 
703  _Base&
704  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
705 
706  const _Base&
707  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
708  };
709 
710 #if __cpp_deduction_guides >= 201606
711 
712  template<typename _InputIterator,
713  typename _Compare = less<__iter_key_t<_InputIterator>>,
714  typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
715  typename = _RequireInputIter<_InputIterator>,
716  typename = _RequireNotAllocator<_Compare>,
717  typename = _RequireAllocator<_Allocator>>
718  map(_InputIterator, _InputIterator,
719  _Compare = _Compare(), _Allocator = _Allocator())
720  -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
721  _Compare, _Allocator>;
722 
723  template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
724  typename _Allocator = allocator<pair<const _Key, _Tp>>,
725  typename = _RequireNotAllocator<_Compare>,
726  typename = _RequireAllocator<_Allocator>>
727  map(initializer_list<pair<_Key, _Tp>>,
728  _Compare = _Compare(), _Allocator = _Allocator())
729  -> map<_Key, _Tp, _Compare, _Allocator>;
730 
731  template <typename _InputIterator, typename _Allocator,
732  typename = _RequireInputIter<_InputIterator>,
733  typename = _RequireAllocator<_Allocator>>
734  map(_InputIterator, _InputIterator, _Allocator)
735  -> map<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
736  less<__iter_key_t<_InputIterator>>, _Allocator>;
737 
738  template<typename _Key, typename _Tp, typename _Allocator,
739  typename = _RequireAllocator<_Allocator>>
740  map(initializer_list<pair<_Key, _Tp>>, _Allocator)
741  -> map<_Key, _Tp, less<_Key>, _Allocator>;
742 
743 #endif // deduction guides
744 
745  template<typename _Key, typename _Tp,
746  typename _Compare, typename _Allocator>
747  inline bool
748  operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
749  const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
750  { return __lhs._M_base() == __rhs._M_base(); }
751 
752 #if __cpp_lib_three_way_comparison
753  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
754  inline __detail::__synth3way_t<pair<const _Key, _Tp>>
755  operator<=>(const map<_Key, _Tp, _Compare, _Alloc>& __lhs,
756  const map<_Key, _Tp, _Compare, _Alloc>& __rhs)
757  { return __lhs._M_base() <=> __rhs._M_base(); }
758 #else
759  template<typename _Key, typename _Tp,
760  typename _Compare, typename _Allocator>
761  inline bool
762  operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
763  const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
764  { return __lhs._M_base() != __rhs._M_base(); }
765 
766  template<typename _Key, typename _Tp,
767  typename _Compare, typename _Allocator>
768  inline bool
769  operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
770  const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
771  { return __lhs._M_base() < __rhs._M_base(); }
772 
773  template<typename _Key, typename _Tp,
774  typename _Compare, typename _Allocator>
775  inline bool
776  operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
777  const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
778  { return __lhs._M_base() <= __rhs._M_base(); }
779 
780  template<typename _Key, typename _Tp,
781  typename _Compare, typename _Allocator>
782  inline bool
783  operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
784  const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
785  { return __lhs._M_base() >= __rhs._M_base(); }
786 
787  template<typename _Key, typename _Tp,
788  typename _Compare, typename _Allocator>
789  inline bool
790  operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
791  const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
792  { return __lhs._M_base() > __rhs._M_base(); }
793 #endif // three-way comparison
794 
795  template<typename _Key, typename _Tp,
796  typename _Compare, typename _Allocator>
797  inline void
798  swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
799  map<_Key, _Tp, _Compare, _Allocator>& __rhs)
800  _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
801  { __lhs.swap(__rhs); }
802 
803 } // namespace __debug
804 } // namespace std
805 
806 #endif
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition: macros.h:146
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:248
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition: macros.h:212
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
std
ISO C++ entities toplevel namespace is std.
__gnu_debug::__base
constexpr _Iterator __base(_Iterator __it)
Definition: helper_functions.h:306
std::initializer_list
initializer_list
Definition: initializer_list:48
std::is_constructible
is_constructible
Definition: type_traits:979
std::enable_if
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:2229
std::allocator
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:125
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: safe_iterator.h:117
__gnu_debug::_Safe_iterator::base
_Iterator & base() noexcept
Return the underlying iterator.
Definition: safe_iterator.h:365
std::_Node_insert_return
Return type of insert(node_handle&&) on unique maps/sets.
Definition: node_handle.h:382
std::less
One of the comparison functors.
Definition: stl_function.h:404
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:187
std::pair::first
_T1 first
The first member.
Definition: stl_pair.h:191
std::pair::second
_T2 second
The second member.
Definition: stl_pair.h:192
std::map
A standard container made up of (key,value) pairs, which can be retrieved based on a key,...
Definition: stl_map.h:101
__gnu_debug::_Safe_sequence::_M_invalidate_if
void _M_invalidate_if(_Predicate __pred)
Definition: safe_sequence.tcc:38
std::__debug::map
Class std::map with safety/checking/debug instrumentation.
Definition: map.h:49
__gnu_debug::_Safe_container
Safe class dealing with some allocator dependent operations.
Definition: safe_container.h:43
__gnu_debug::_Safe_node_sequence
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
Definition: safe_sequence.h:133