libstdc++
multimap.h
Go to the documentation of this file.
1 // Debugging multimap 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/multimap.h
26  * This file is a GNU debug extension to the Standard C++ Library.
27  */
28 
29 #ifndef _GLIBCXX_DEBUG_MULTIMAP_H
30 #define _GLIBCXX_DEBUG_MULTIMAP_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::multimap 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 multimap
46  multimap<_Key, _Tp, _Compare, _Allocator>, _Allocator,
47  __gnu_debug::_Safe_node_sequence>,
48  public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>
49  {
50  typedef _GLIBCXX_STD_C::multimap<
51  _Key, _Tp, _Compare, _Allocator> _Base;
54 
56  typedef typename _Base::iterator _Base_iterator;
58 
59  template<typename _ItT, typename _SeqT, typename _CatT>
60  friend class ::__gnu_debug::_Safe_iterator;
61 
62  // Reference wrapper for base class. Disambiguates multimap(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;
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 
83  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;
93 
94  // 23.3.1.1 construct/copy/destroy:
95 
96 #if __cplusplus < 201103L
97  multimap() : _Base() { }
98 
99  multimap(const multimap& __x)
100  : _Base(__x) { }
101 
102  ~multimap() { }
103 #else
104  multimap() = default;
105  multimap(const multimap&) = default;
106  multimap(multimap&&) = default;
107 
109  const _Compare& __c = _Compare(),
110  const allocator_type& __a = allocator_type())
111  : _Base(__l, __c, __a) { }
112 
113  explicit
114  multimap(const allocator_type& __a)
115  : _Base(__a) { }
116 
117  multimap(const multimap& __m, const allocator_type& __a)
118  : _Base(__m, __a) { }
119 
120  multimap(multimap&& __m, const 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  multimap(initializer_list<value_type> __l, const allocator_type& __a)
126  : _Base(__l, __a) { }
127 
128  template<typename _InputIterator>
129  multimap(_InputIterator __first, _InputIterator __last,
130  const allocator_type& __a)
132  __glibcxx_check_valid_constructor_range(__first, __last)),
133  __gnu_debug::__base(__last), __a) { }
134 
135  ~multimap() = default;
136 #endif
137 
138  explicit multimap(const _Compare& __comp,
139  const _Allocator& __a = _Allocator())
140  : _Base(__comp, __a) { }
141 
142  template<typename _InputIterator>
143  multimap(_InputIterator __first, _InputIterator __last,
144  const _Compare& __comp = _Compare(),
145  const _Allocator& __a = _Allocator())
147  __glibcxx_check_valid_constructor_range(__first, __last)),
148  __gnu_debug::__base(__last),
149  __comp, __a) { }
150 
151  multimap(_Base_ref __x)
152  : _Base(__x._M_ref) { }
153 
154 #if __cplusplus < 201103L
155  multimap&
156  operator=(const multimap& __x)
157  {
158  this->_M_safe() = __x;
159  _M_base() = __x;
160  return *this;
161  }
162 #else
163  multimap&
164  operator=(const multimap&) = default;
165 
166  multimap&
167  operator=(multimap&&) = default;
168 
169  multimap&
170  operator=(initializer_list<value_type> __l)
171  {
172  _M_base() = __l;
173  this->_M_invalidate_all();
174  return *this;
175  }
176 #endif
177 
178  using _Base::get_allocator;
179 
180  // iterators:
181  iterator
182  begin() _GLIBCXX_NOEXCEPT
183  { return iterator(_Base::begin(), this); }
184 
186  begin() const _GLIBCXX_NOEXCEPT
187  { return const_iterator(_Base::begin(), this); }
188 
189  iterator
190  end() _GLIBCXX_NOEXCEPT
191  { return iterator(_Base::end(), this); }
192 
194  end() const _GLIBCXX_NOEXCEPT
195  { return const_iterator(_Base::end(), this); }
196 
198  rbegin() _GLIBCXX_NOEXCEPT
199  { return reverse_iterator(end()); }
200 
202  rbegin() const _GLIBCXX_NOEXCEPT
203  { return const_reverse_iterator(end()); }
204 
206  rend() _GLIBCXX_NOEXCEPT
207  { return reverse_iterator(begin()); }
208 
210  rend() const _GLIBCXX_NOEXCEPT
211  { return const_reverse_iterator(begin()); }
212 
213 #if __cplusplus >= 201103L
215  cbegin() const noexcept
216  { return const_iterator(_Base::begin(), this); }
217 
219  cend() const noexcept
220  { return const_iterator(_Base::end(), this); }
221 
223  crbegin() const noexcept
224  { return const_reverse_iterator(end()); }
225 
227  crend() const noexcept
228  { return const_reverse_iterator(begin()); }
229 #endif
230 
231  // capacity:
232  using _Base::empty;
233  using _Base::size;
234  using _Base::max_size;
235 
236  // modifiers:
237 #if __cplusplus >= 201103L
238  template<typename... _Args>
239  iterator
240  emplace(_Args&&... __args)
241  { return { _Base::emplace(std::forward<_Args>(__args)...), this }; }
242 
243  template<typename... _Args>
244  iterator
245  emplace_hint(const_iterator __pos, _Args&&... __args)
246  {
247  __glibcxx_check_insert(__pos);
248  return
249  {
250  _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
251  this
252  };
253  }
254 #endif
255 
256  iterator
257  insert(const value_type& __x)
258  { return iterator(_Base::insert(__x), this); }
259 
260 #if __cplusplus >= 201103L
261  // _GLIBCXX_RESOLVE_LIB_DEFECTS
262  // 2354. Unnecessary copying when inserting into maps with braced-init
263  iterator
264  insert(value_type&& __x)
265  { return { _Base::insert(std::move(__x)), this }; }
266 
267  template<typename _Pair, typename = typename
269  _Pair&&>::value>::type>
270  iterator
271  insert(_Pair&& __x)
272  { return { _Base::insert(std::forward<_Pair>(__x)), this }; }
273 #endif
274 
275 #if __cplusplus >= 201103L
276  void
277  insert(std::initializer_list<value_type> __list)
278  { _Base::insert(__list); }
279 #endif
280 
281  iterator
282 #if __cplusplus >= 201103L
283  insert(const_iterator __position, const value_type& __x)
284 #else
285  insert(iterator __position, const value_type& __x)
286 #endif
287  {
288  __glibcxx_check_insert(__position);
289  return iterator(_Base::insert(__position.base(), __x), this);
290  }
291 
292 #if __cplusplus >= 201103L
293  // _GLIBCXX_RESOLVE_LIB_DEFECTS
294  // 2354. Unnecessary copying when inserting into maps with braced-init
295  iterator
296  insert(const_iterator __position, value_type&& __x)
297  {
298  __glibcxx_check_insert(__position);
299  return { _Base::insert(__position.base(), std::move(__x)), this };
300  }
301 
302  template<typename _Pair, typename = typename
304  _Pair&&>::value>::type>
305  iterator
306  insert(const_iterator __position, _Pair&& __x)
307  {
308  __glibcxx_check_insert(__position);
309  return
310  {
311  _Base::insert(__position.base(), std::forward<_Pair>(__x)),
312  this
313  };
314  }
315 #endif
316 
317  template<typename _InputIterator>
318  void
319  insert(_InputIterator __first, _InputIterator __last)
320  {
322  __glibcxx_check_valid_range2(__first, __last, __dist);
323 
324  if (__dist.second >= __gnu_debug::__dp_sign)
325  _Base::insert(__gnu_debug::__unsafe(__first),
326  __gnu_debug::__unsafe(__last));
327  else
328  _Base::insert(__first, __last);
329  }
330 
331 #if __cplusplus > 201402L
332  using node_type = typename _Base::node_type;
333 
334  node_type
335  extract(const_iterator __position)
336  {
337  __glibcxx_check_erase(__position);
338  this->_M_invalidate_if(_Equal(__position.base()));
339  return _Base::extract(__position.base());
340  }
341 
342  node_type
343  extract(const key_type& __key)
344  {
345  const auto __position = find(__key);
346  if (__position != end())
347  return extract(__position);
348  return {};
349  }
350 
351  iterator
352  insert(node_type&& __nh)
353  { return { _Base::insert(std::move(__nh)), this }; }
354 
355  iterator
356  insert(const_iterator __hint, node_type&& __nh)
357  {
358  __glibcxx_check_insert(__hint);
359  return { _Base::insert(__hint.base(), std::move(__nh)), this };
360  }
361 
362  using _Base::merge;
363 #endif // C++17
364 
365 #if __cplusplus >= 201103L
366  iterator
367  erase(const_iterator __position)
368  {
369  __glibcxx_check_erase(__position);
370  this->_M_invalidate_if(_Equal(__position.base()));
371  return { _Base::erase(__position.base()), this };
372  }
373 
374  _GLIBCXX_ABI_TAG_CXX11
375  iterator
376  erase(iterator __position)
377  { return erase(const_iterator(__position)); }
378 #else
379  void
380  erase(iterator __position)
381  {
382  __glibcxx_check_erase(__position);
383  this->_M_invalidate_if(_Equal(__position.base()));
384  _Base::erase(__position.base());
385  }
386 #endif
387 
388  size_type
389  erase(const key_type& __x)
390  {
392  _Base::equal_range(__x);
393  size_type __count = 0;
394  _Base_iterator __victim = __victims.first;
395  while (__victim != __victims.second)
396  {
397  this->_M_invalidate_if(_Equal(__victim));
398  _Base::erase(__victim++);
399  ++__count;
400  }
401  return __count;
402  }
403 
404 #if __cplusplus >= 201103L
405  iterator
406  erase(const_iterator __first, const_iterator __last)
407  {
408  // _GLIBCXX_RESOLVE_LIB_DEFECTS
409  // 151. can't currently clear() empty container
410  __glibcxx_check_erase_range(__first, __last);
411  for (_Base_const_iterator __victim = __first.base();
412  __victim != __last.base(); ++__victim)
413  {
414  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
415  _M_message(__gnu_debug::__msg_valid_range)
416  ._M_iterator(__first, "first")
417  ._M_iterator(__last, "last"));
418  this->_M_invalidate_if(_Equal(__victim));
419  }
420 
421  return { _Base::erase(__first.base(), __last.base()), this };
422  }
423 #else
424  void
425  erase(iterator __first, iterator __last)
426  {
427  // _GLIBCXX_RESOLVE_LIB_DEFECTS
428  // 151. can't currently clear() empty container
429  __glibcxx_check_erase_range(__first, __last);
430  for (_Base_iterator __victim = __first.base();
431  __victim != __last.base(); ++__victim)
432  {
433  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
434  _M_message(__gnu_debug::__msg_valid_range)
435  ._M_iterator(__first, "first")
436  ._M_iterator(__last, "last"));
437  this->_M_invalidate_if(_Equal(__victim));
438  }
439  _Base::erase(__first.base(), __last.base());
440  }
441 #endif
442 
443  void
444  swap(multimap& __x)
445  _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
446  {
447  _Safe::_M_swap(__x);
448  _Base::swap(__x);
449  }
450 
451  void
452  clear() _GLIBCXX_NOEXCEPT
453  {
454  this->_M_invalidate_all();
455  _Base::clear();
456  }
457 
458  // observers:
459  using _Base::key_comp;
460  using _Base::value_comp;
461 
462  // 23.3.1.3 multimap operations:
463  iterator
464  find(const key_type& __x)
465  { return iterator(_Base::find(__x), this); }
466 
467 #if __cplusplus > 201103L
468  template<typename _Kt,
469  typename _Req =
470  typename __has_is_transparent<_Compare, _Kt>::type>
471  iterator
472  find(const _Kt& __x)
473  { return { _Base::find(__x), this }; }
474 #endif
475 
477  find(const key_type& __x) const
478  { return const_iterator(_Base::find(__x), this); }
479 
480 #if __cplusplus > 201103L
481  template<typename _Kt,
482  typename _Req =
483  typename __has_is_transparent<_Compare, _Kt>::type>
485  find(const _Kt& __x) const
486  { return { _Base::find(__x), this }; }
487 #endif
488 
489  using _Base::count;
490 
491  iterator
492  lower_bound(const key_type& __x)
493  { return iterator(_Base::lower_bound(__x), this); }
494 
495 #if __cplusplus > 201103L
496  template<typename _Kt,
497  typename _Req =
498  typename __has_is_transparent<_Compare, _Kt>::type>
499  iterator
500  lower_bound(const _Kt& __x)
501  { return { _Base::lower_bound(__x), this }; }
502 #endif
503 
505  lower_bound(const key_type& __x) const
506  { return const_iterator(_Base::lower_bound(__x), this); }
507 
508 #if __cplusplus > 201103L
509  template<typename _Kt,
510  typename _Req =
511  typename __has_is_transparent<_Compare, _Kt>::type>
513  lower_bound(const _Kt& __x) const
514  { return { _Base::lower_bound(__x), this }; }
515 #endif
516 
517  iterator
518  upper_bound(const key_type& __x)
519  { return iterator(_Base::upper_bound(__x), this); }
520 
521 #if __cplusplus > 201103L
522  template<typename _Kt,
523  typename _Req =
524  typename __has_is_transparent<_Compare, _Kt>::type>
525  iterator
526  upper_bound(const _Kt& __x)
527  { return { _Base::upper_bound(__x), this }; }
528 #endif
529 
531  upper_bound(const key_type& __x) const
532  { return const_iterator(_Base::upper_bound(__x), this); }
533 
534 #if __cplusplus > 201103L
535  template<typename _Kt,
536  typename _Req =
537  typename __has_is_transparent<_Compare, _Kt>::type>
539  upper_bound(const _Kt& __x) const
540  { return { _Base::upper_bound(__x), this }; }
541 #endif
542 
544  equal_range(const key_type& __x)
545  {
547  _Base::equal_range(__x);
548  return std::make_pair(iterator(__res.first, this),
549  iterator(__res.second, this));
550  }
551 
552 #if __cplusplus > 201103L
553  template<typename _Kt,
554  typename _Req =
555  typename __has_is_transparent<_Compare, _Kt>::type>
557  equal_range(const _Kt& __x)
558  {
559  auto __res = _Base::equal_range(__x);
560  return { { __res.first, this }, { __res.second, this } };
561  }
562 #endif
563 
565  equal_range(const key_type& __x) const
566  {
568  _Base::equal_range(__x);
569  return std::make_pair(const_iterator(__res.first, this),
570  const_iterator(__res.second, this));
571  }
572 
573 #if __cplusplus > 201103L
574  template<typename _Kt,
575  typename _Req =
576  typename __has_is_transparent<_Compare, _Kt>::type>
578  equal_range(const _Kt& __x) const
579  {
580  auto __res = _Base::equal_range(__x);
581  return { { __res.first, this }, { __res.second, this } };
582  }
583 #endif
584 
585  _Base&
586  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
587 
588  const _Base&
589  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
590  };
591 
592 #if __cpp_deduction_guides >= 201606
593 
594  template<typename _InputIterator,
595  typename _Compare = less<__iter_key_t<_InputIterator>>,
596  typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
597  typename = _RequireInputIter<_InputIterator>,
598  typename = _RequireNotAllocator<_Compare>,
599  typename = _RequireAllocator<_Allocator>>
600  multimap(_InputIterator, _InputIterator,
601  _Compare = _Compare(), _Allocator = _Allocator())
602  -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
603  _Compare, _Allocator>;
604 
605  template<typename _Key, typename _Tp, typename _Compare = less<_Key>,
606  typename _Allocator = allocator<pair<const _Key, _Tp>>,
607  typename = _RequireNotAllocator<_Compare>,
608  typename = _RequireAllocator<_Allocator>>
610  _Compare = _Compare(), _Allocator = _Allocator())
612 
613  template<typename _InputIterator, typename _Allocator,
614  typename = _RequireInputIter<_InputIterator>,
615  typename = _RequireAllocator<_Allocator>>
616  multimap(_InputIterator, _InputIterator, _Allocator)
617  -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>,
618  less<__iter_key_t<_InputIterator>>, _Allocator>;
619 
620  template<typename _Key, typename _Tp, typename _Allocator,
621  typename = _RequireAllocator<_Allocator>>
623  -> multimap<_Key, _Tp, less<_Key>, _Allocator>;
624 
625 #endif
626 
627  template<typename _Key, typename _Tp,
628  typename _Compare, typename _Allocator>
629  inline bool
630  operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
632  { return __lhs._M_base() == __rhs._M_base(); }
633 
634 #if __cpp_lib_three_way_comparison
635  template<typename _Key, typename _Tp, typename _Compare, typename _Alloc>
636  inline __detail::__synth3way_t<pair<const _Key, _Tp>>
637  operator<=>(const multimap<_Key, _Tp, _Compare, _Alloc>& __lhs,
639  { return __lhs._M_base() <=> __rhs._M_base(); }
640 #else
641  template<typename _Key, typename _Tp,
642  typename _Compare, typename _Allocator>
643  inline bool
644  operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
645  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
646  { return __lhs._M_base() != __rhs._M_base(); }
647 
648  template<typename _Key, typename _Tp,
649  typename _Compare, typename _Allocator>
650  inline bool
651  operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
652  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
653  { return __lhs._M_base() < __rhs._M_base(); }
654 
655  template<typename _Key, typename _Tp,
656  typename _Compare, typename _Allocator>
657  inline bool
658  operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
659  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
660  { return __lhs._M_base() <= __rhs._M_base(); }
661 
662  template<typename _Key, typename _Tp,
663  typename _Compare, typename _Allocator>
664  inline bool
665  operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
666  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
667  { return __lhs._M_base() >= __rhs._M_base(); }
668 
669  template<typename _Key, typename _Tp,
670  typename _Compare, typename _Allocator>
671  inline bool
672  operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
673  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
674  { return __lhs._M_base() > __rhs._M_base(); }
675 #endif // three-way comparison
676 
677  template<typename _Key, typename _Tp,
678  typename _Compare, typename _Allocator>
679  inline void
680  swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
681  multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
682  _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
683  { __lhs.swap(__rhs); }
684 
685 } // namespace __debug
686 } // namespace std
687 
688 #endif
#define __glibcxx_check_insert(_Position)
Definition: macros.h:146
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:240
#define __glibcxx_check_erase(_Position)
Definition: macros.h:212
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
Definition: any:428
ISO C++ entities toplevel namespace is std.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:263
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:245
constexpr _Iterator __base(_Iterator __it)
initializer_list
is_constructible
Definition: type_traits:954
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:2194
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:125
One of the comparison functors.
Definition: stl_function.h:396
A standard container made up of (key,value) pairs, which can be retrieved based on a key,...
Definition: stl_multimap.h:100
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213
_T1 first
The first member.
Definition: stl_pair.h:217
_T2 second
The second member.
Definition: stl_pair.h:218
Safe iterator wrapper.
_Iterator & base() noexcept
Return the underlying iterator.
void _M_invalidate_if(_Predicate __pred)
Class std::multimap with safety/checking/debug instrumentation.
Definition: multimap.h:49
Safe class dealing with some allocator dependent operations.
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...