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