libstdc++
multiset.h
Go to the documentation of this file.
1 // Debugging multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2025 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/multiset.h
26  * This file is a GNU debug extension to the Standard C++ Library.
27  */
28 
29 #ifndef _GLIBCXX_DEBUG_MULTISET_H
30 #define _GLIBCXX_DEBUG_MULTISET_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::multiset with safety/checking/debug instrumentation.
42  template<typename _Key, typename _Compare = std::less<_Key>,
43  typename _Allocator = std::allocator<_Key> >
44  class multiset
46  multiset<_Key, _Compare, _Allocator>, _Allocator,
47  __gnu_debug::_Safe_node_sequence>,
48  public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>
49  {
50  typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
53 
55  typedef typename _Base::iterator _Base_iterator;
57 
58  template<typename _ItT, typename _SeqT, typename _CatT>
59  friend class ::__gnu_debug::_Safe_iterator;
60 
61  // Reference wrapper for base class. Disambiguates multiset(const _Base&)
62  // from copy constructor by requiring a user-defined conversion.
63  // See PR libstdc++/90102.
64  struct _Base_ref
65  {
66  _Base_ref(const _Base& __r) : _M_ref(__r) { }
67 
68  const _Base& _M_ref;
69  };
70 
71  public:
72  // types:
73  typedef _Key key_type;
74  typedef _Key value_type;
75  typedef _Compare key_compare;
76  typedef _Compare value_compare;
77  typedef _Allocator allocator_type;
78  typedef typename _Base::reference reference;
79  typedef typename _Base::const_reference const_reference;
80 
82  iterator;
85 
86  typedef typename _Base::size_type size_type;
87  typedef typename _Base::difference_type difference_type;
88  typedef typename _Base::pointer pointer;
89  typedef typename _Base::const_pointer const_pointer;
92 
93  // 23.3.3.1 construct/copy/destroy:
94 
95 #if __cplusplus < 201103L
96  multiset() : _Base() { }
97 
98  multiset(const multiset& __x)
99  : _Base(__x) { }
100 
101  ~multiset() { }
102 #else
103  multiset() = default;
104  multiset(const multiset&) = default;
105  multiset(multiset&&) = default;
106 
108  const _Compare& __comp = _Compare(),
109  const allocator_type& __a = allocator_type())
110  : _Base(__l, __comp, __a) { }
111 
112  explicit
113  multiset(const allocator_type& __a)
114  : _Base(__a) { }
115 
116  multiset(const multiset& __m,
117  const __type_identity_t<allocator_type>& __a)
118  : _Base(__m, __a) { }
119 
120  multiset(multiset&& __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  multiset(initializer_list<value_type> __l, const allocator_type& __a)
126  : _Base(__l, __a)
127  { }
128 
129  template<typename _InputIterator>
130  multiset(_InputIterator __first, _InputIterator __last,
131  const allocator_type& __a)
133  __glibcxx_check_valid_constructor_range(__first, __last)),
134  __gnu_debug::__base(__last), __a) { }
135 
136 #if __glibcxx_containers_ranges // C++ >= 23
137  /**
138  * @brief Construct a multiset from a range.
139  * @since C++23
140  */
141  template<std::__detail::__container_compatible_range<value_type> _Rg>
142  multiset(std::from_range_t __t, _Rg&& __rg,
143  const _Compare& __c,
144  const allocator_type& __a = allocator_type())
145  : _Base(__t, std::forward<_Rg>(__rg), __c, __a)
146  { }
147 
148  template<std::__detail::__container_compatible_range<value_type> _Rg>
149  multiset(std::from_range_t __t, _Rg&& __rg,
150  const allocator_type& __a = allocator_type())
151  : _Base(__t, std::forward<_Rg>(__rg), __a)
152  { }
153 #endif
154 
155  ~multiset() = default;
156 #endif
157 
158  explicit multiset(const _Compare& __comp,
159  const _Allocator& __a = _Allocator())
160  : _Base(__comp, __a) { }
161 
162  template<typename _InputIterator>
163  multiset(_InputIterator __first, _InputIterator __last,
164  const _Compare& __comp = _Compare(),
165  const _Allocator& __a = _Allocator())
167  __glibcxx_check_valid_constructor_range(__first, __last)),
168  __gnu_debug::__base(__last),
169  __comp, __a) { }
170 
171  multiset(_Base_ref __x)
172  : _Base(__x._M_ref) { }
173 
174 #if __cplusplus >= 201103L
175  multiset&
176  operator=(const multiset&) = default;
177 
178  multiset&
179  operator=(multiset&&) = default;
180 
181  multiset&
182  operator=(initializer_list<value_type> __l)
183  {
184  _Base::operator=(__l);
185  this->_M_invalidate_all();
186  return *this;
187  }
188 #endif
189 
190  using _Base::get_allocator;
191 
192  // iterators:
193  iterator
194  begin() _GLIBCXX_NOEXCEPT
195  { return iterator(_Base::begin(), this); }
196 
198  begin() const _GLIBCXX_NOEXCEPT
199  { return const_iterator(_Base::begin(), this); }
200 
201  iterator
202  end() _GLIBCXX_NOEXCEPT
203  { return iterator(_Base::end(), this); }
204 
206  end() const _GLIBCXX_NOEXCEPT
207  { return const_iterator(_Base::end(), this); }
208 
210  rbegin() _GLIBCXX_NOEXCEPT
211  { return reverse_iterator(end()); }
212 
214  rbegin() const _GLIBCXX_NOEXCEPT
215  { return const_reverse_iterator(end()); }
216 
218  rend() _GLIBCXX_NOEXCEPT
219  { return reverse_iterator(begin()); }
220 
222  rend() const _GLIBCXX_NOEXCEPT
223  { return const_reverse_iterator(begin()); }
224 
225 #if __cplusplus >= 201103L
227  cbegin() const noexcept
228  { return const_iterator(_Base::begin(), this); }
229 
231  cend() const noexcept
232  { return const_iterator(_Base::end(), this); }
233 
235  crbegin() const noexcept
236  { return const_reverse_iterator(end()); }
237 
239  crend() const noexcept
240  { return const_reverse_iterator(begin()); }
241 #endif
242 
243  // capacity:
244  using _Base::empty;
245  using _Base::size;
246  using _Base::max_size;
247 
248  // modifiers:
249 #if __cplusplus >= 201103L
250  template<typename... _Args>
251  iterator
252  emplace(_Args&&... __args)
253  { return { _Base::emplace(std::forward<_Args>(__args)...), this }; }
254 
255  template<typename... _Args>
256  iterator
257  emplace_hint(const_iterator __pos, _Args&&... __args)
258  {
259  __glibcxx_check_insert(__pos);
260  return
261  {
262  _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
263  this
264  };
265  }
266 #endif
267 
268  iterator
269  insert(const value_type& __x)
270  { return iterator(_Base::insert(__x), this); }
271 
272 #if __cplusplus >= 201103L
273  iterator
274  insert(value_type&& __x)
275  { return { _Base::insert(std::move(__x)), this }; }
276 #endif
277 
278  iterator
279  insert(const_iterator __position, const value_type& __x)
280  {
281  __glibcxx_check_insert(__position);
282  return iterator(_Base::insert(__position.base(), __x), this);
283  }
284 
285 #if __cplusplus >= 201103L
286  iterator
287  insert(const_iterator __position, value_type&& __x)
288  {
289  __glibcxx_check_insert(__position);
290  return { _Base::insert(__position.base(), std::move(__x)), this };
291  }
292 #endif
293 
294  template<typename _InputIterator>
295  void
296  insert(_InputIterator __first, _InputIterator __last)
297  {
299  __glibcxx_check_valid_range2(__first, __last, __dist);
300 
301  if (__dist.second >= __gnu_debug::__dp_sign)
302  _Base::insert(__gnu_debug::__unsafe(__first),
303  __gnu_debug::__unsafe(__last));
304  else
305  _Base::insert(__first, __last);
306  }
307 
308 #if __cplusplus >= 201103L
309  void
310  insert(initializer_list<value_type> __l)
311  { _Base::insert(__l); }
312 #endif
313 
314 #if __cplusplus > 201402L
315  using node_type = typename _Base::node_type;
316 
317  node_type
318  extract(const_iterator __position)
319  {
320  __glibcxx_check_erase(__position);
321  this->_M_invalidate_if(_Equal(__position.base()));
322  return _Base::extract(__position.base());
323  }
324 
325  node_type
326  extract(const key_type& __key)
327  {
328  const auto __position = find(__key);
329  if (__position != end())
330  return extract(__position);
331  return {};
332  }
333 
334  iterator
335  insert(node_type&& __nh)
336  { return { _Base::insert(std::move(__nh)), this }; }
337 
338  iterator
339  insert(const_iterator __hint, node_type&& __nh)
340  {
341  __glibcxx_check_insert(__hint);
342  return { _Base::insert(__hint.base(), std::move(__nh)), this };
343  }
344 
345  using _Base::merge;
346 #endif // C++17
347 
348 #if __cplusplus >= 201103L
349  _GLIBCXX_ABI_TAG_CXX11
350  iterator
351  erase(const_iterator __position)
352  {
353  __glibcxx_check_erase(__position);
354  return { erase(__position.base()), this };
355  }
356 
358  erase(_Base_const_iterator __position)
359  {
360  __glibcxx_check_erase2(__position);
361  this->_M_invalidate_if(_Equal(__position));
362  return _Base::erase(__position);
363  }
364 #else
365  void
366  erase(iterator __position)
367  {
368  __glibcxx_check_erase(__position);
369  this->_M_invalidate_if(_Equal(__position.base()));
370  _Base::erase(__position.base());
371  }
372 #endif
373 
374  size_type
375  erase(const key_type& __x)
376  {
378  _Base::equal_range(__x);
379  size_type __count = 0;
380  _Base_iterator __victim = __victims.first;
381  while (__victim != __victims.second)
382  {
383  this->_M_invalidate_if(_Equal(__victim));
384  _Base::erase(__victim++);
385  ++__count;
386  }
387  return __count;
388  }
389 
390 #if __cplusplus >= 201103L
391  _GLIBCXX_ABI_TAG_CXX11
392  iterator
393  erase(const_iterator __first, const_iterator __last)
394  {
395  // _GLIBCXX_RESOLVE_LIB_DEFECTS
396  // 151. can't currently clear() empty container
397  __glibcxx_check_erase_range(__first, __last);
398  for (_Base_const_iterator __victim = __first.base();
399  __victim != __last.base(); ++__victim)
400  {
401  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
402  _M_message(__gnu_debug::__msg_valid_range)
403  ._M_iterator(__first, "first")
404  ._M_iterator(__last, "last"));
405  this->_M_invalidate_if(_Equal(__victim));
406  }
407 
408  return { _Base::erase(__first.base(), __last.base()), this };
409  }
410 #else
411  void
412  erase(iterator __first, iterator __last)
413  {
414  // _GLIBCXX_RESOLVE_LIB_DEFECTS
415  // 151. can't currently clear() empty container
416  __glibcxx_check_erase_range(__first, __last);
417  for (_Base_iterator __victim = __first.base();
418  __victim != __last.base(); ++__victim)
419  {
420  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
421  _M_message(__gnu_debug::__msg_valid_range)
422  ._M_iterator(__first, "first")
423  ._M_iterator(__last, "last"));
424  this->_M_invalidate_if(_Equal(__victim));
425  }
426  _Base::erase(__first.base(), __last.base());
427  }
428 #endif
429 
430  void
431  swap(multiset& __x)
432  _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
433  {
434  _Safe::_M_swap(__x);
435  _Base::swap(__x);
436  }
437 
438  void
439  clear() _GLIBCXX_NOEXCEPT
440  {
441  this->_M_invalidate_all();
442  _Base::clear();
443  }
444 
445  // observers:
446  using _Base::key_comp;
447  using _Base::value_comp;
448 
449  // multiset operations:
450  iterator
451  find(const key_type& __x)
452  { return iterator(_Base::find(__x), this); }
453 
454  // _GLIBCXX_RESOLVE_LIB_DEFECTS
455  // 214. set::find() missing const overload
457  find(const key_type& __x) const
458  { return const_iterator(_Base::find(__x), this); }
459 
460 #if __cplusplus > 201103L
461  template<typename _Kt,
462  typename _Req =
463  typename __has_is_transparent<_Compare, _Kt>::type>
464  iterator
465  find(const _Kt& __x)
466  { return { _Base::find(__x), this }; }
467 
468  template<typename _Kt,
469  typename _Req =
470  typename __has_is_transparent<_Compare, _Kt>::type>
472  find(const _Kt& __x) const
473  { return { _Base::find(__x), this }; }
474 #endif
475 
476  using _Base::count;
477 
478  iterator
479  lower_bound(const key_type& __x)
480  { return iterator(_Base::lower_bound(__x), this); }
481 
482  // _GLIBCXX_RESOLVE_LIB_DEFECTS
483  // 214. set::find() missing const overload
485  lower_bound(const key_type& __x) const
486  { return const_iterator(_Base::lower_bound(__x), this); }
487 
488 #if __cplusplus > 201103L
489  template<typename _Kt,
490  typename _Req =
491  typename __has_is_transparent<_Compare, _Kt>::type>
492  iterator
493  lower_bound(const _Kt& __x)
494  { return { _Base::lower_bound(__x), this }; }
495 
496  template<typename _Kt,
497  typename _Req =
498  typename __has_is_transparent<_Compare, _Kt>::type>
500  lower_bound(const _Kt& __x) const
501  { return { _Base::lower_bound(__x), this }; }
502 #endif
503 
504  iterator
505  upper_bound(const key_type& __x)
506  { return iterator(_Base::upper_bound(__x), this); }
507 
508  // _GLIBCXX_RESOLVE_LIB_DEFECTS
509  // 214. set::find() missing const overload
511  upper_bound(const key_type& __x) const
512  { return const_iterator(_Base::upper_bound(__x), this); }
513 
514 #if __cplusplus > 201103L
515  template<typename _Kt,
516  typename _Req =
517  typename __has_is_transparent<_Compare, _Kt>::type>
518  iterator
519  upper_bound(const _Kt& __x)
520  { return { _Base::upper_bound(__x), this }; }
521 
522  template<typename _Kt,
523  typename _Req =
524  typename __has_is_transparent<_Compare, _Kt>::type>
526  upper_bound(const _Kt& __x) const
527  { return { _Base::upper_bound(__x), this }; }
528 #endif
529 
531  equal_range(const key_type& __x)
532  {
534  _Base::equal_range(__x);
535  return std::make_pair(iterator(__res.first, this),
536  iterator(__res.second, this));
537  }
538 
539  // _GLIBCXX_RESOLVE_LIB_DEFECTS
540  // 214. set::find() missing const overload
542  equal_range(const key_type& __x) const
543  {
545  _Base::equal_range(__x);
546  return std::make_pair(const_iterator(__res.first, this),
547  const_iterator(__res.second, this));
548  }
549 
550 #if __cplusplus > 201103L
551  template<typename _Kt,
552  typename _Req =
553  typename __has_is_transparent<_Compare, _Kt>::type>
555  equal_range(const _Kt& __x)
556  {
557  auto __res = _Base::equal_range(__x);
558  return { { __res.first, this }, { __res.second, this } };
559  }
560 
561  template<typename _Kt,
562  typename _Req =
563  typename __has_is_transparent<_Compare, _Kt>::type>
565  equal_range(const _Kt& __x) const
566  {
567  auto __res = _Base::equal_range(__x);
568  return { { __res.first, this }, { __res.second, this } };
569  }
570 #endif
571 
572  _Base&
573  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
574 
575  const _Base&
576  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
577  };
578 
579 #if __cpp_deduction_guides >= 201606
580 
581  template<typename _InputIterator,
582  typename _Compare =
584  typename _Allocator =
586  typename = _RequireInputIter<_InputIterator>,
587  typename = _RequireNotAllocator<_Compare>,
588  typename = _RequireAllocator<_Allocator>>
589  multiset(_InputIterator, _InputIterator,
590  _Compare = _Compare(), _Allocator = _Allocator())
592  _Compare, _Allocator>;
593 
594  template<typename _Key,
595  typename _Compare = less<_Key>,
596  typename _Allocator = allocator<_Key>,
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  multiset(_InputIterator, _InputIterator, _Allocator)
609  _Allocator>;
610 
611  template<typename _Key, typename _Allocator,
612  typename = _RequireAllocator<_Allocator>>
613  multiset(initializer_list<_Key>, _Allocator)
614  -> multiset<_Key, less<_Key>, _Allocator>;
615 
616 #if __glibcxx_containers_ranges // C++ >= 23
617  template<ranges::input_range _Rg,
618  __not_allocator_like _Compare = less<ranges::range_value_t<_Rg>>,
619  __allocator_like _Alloc = std::allocator<ranges::range_value_t<_Rg>>>
620  multiset(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
621  -> multiset<ranges::range_value_t<_Rg>, _Compare, _Alloc>;
622 
623  template<ranges::input_range _Rg, __allocator_like _Alloc>
624  multiset(from_range_t, _Rg&&, _Alloc)
626 #endif
627 #endif // deduction guides
628 
629  template<typename _Key, typename _Compare, typename _Allocator>
630  inline bool
631  operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
633  { return __lhs._M_base() == __rhs._M_base(); }
634 
635 #if __cpp_lib_three_way_comparison
636  template<typename _Key, typename _Compare, typename _Alloc>
637  inline __detail::__synth3way_t<_Key>
638  operator<=>(const multiset<_Key, _Compare, _Alloc>& __lhs,
640  { return __lhs._M_base() <=> __rhs._M_base(); }
641 #else
642  template<typename _Key, typename _Compare, typename _Allocator>
643  inline bool
644  operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
645  const multiset<_Key, _Compare, _Allocator>& __rhs)
646  { return __lhs._M_base() != __rhs._M_base(); }
647 
648  template<typename _Key, typename _Compare, typename _Allocator>
649  inline bool
650  operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
651  const multiset<_Key, _Compare, _Allocator>& __rhs)
652  { return __lhs._M_base() < __rhs._M_base(); }
653 
654  template<typename _Key, typename _Compare, typename _Allocator>
655  inline bool
656  operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
657  const multiset<_Key, _Compare, _Allocator>& __rhs)
658  { return __lhs._M_base() <= __rhs._M_base(); }
659 
660  template<typename _Key, typename _Compare, typename _Allocator>
661  inline bool
662  operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
663  const multiset<_Key, _Compare, _Allocator>& __rhs)
664  { return __lhs._M_base() >= __rhs._M_base(); }
665 
666  template<typename _Key, typename _Compare, typename _Allocator>
667  inline bool
668  operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
669  const multiset<_Key, _Compare, _Allocator>& __rhs)
670  { return __lhs._M_base() > __rhs._M_base(); }
671 #endif // three-way comparison
672 
673  template<typename _Key, typename _Compare, typename _Allocator>
674  void
675  swap(multiset<_Key, _Compare, _Allocator>& __x,
676  multiset<_Key, _Compare, _Allocator>& __y)
677  _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
678  { return __x.swap(__y); }
679 
680 } // namespace __debug
681 } // namespace std
682 
683 #endif
#define __glibcxx_check_insert(_Position)
Definition: macros.h:143
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:245
#define __glibcxx_check_erase(_Position)
Definition: macros.h:209
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:859
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:873
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:826
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:866
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:138
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:294
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:274
constexpr _Iterator __base(_Iterator __it)
initializer_list
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:134
Safe iterator wrapper.
constexpr _Iterator & base() noexcept
Return the underlying iterator.
One of the comparison functors.
Definition: stl_function.h:401
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:304
_T1 first
The first member.
Definition: stl_pair.h:308
_T2 second
The second member.
Definition: stl_pair.h:309
A standard container made up of elements, which can be retrieved in logarithmic time.
Definition: stl_multiset.h:101
void _M_invalidate_if(_Predicate __pred)
Class std::multiset with safety/checking/debug instrumentation.
Definition: multiset.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...