libstdc++
multiset.h
Go to the documentation of this file.
1 // Debugging multiset 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/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 <utility>
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, const allocator_type& __a)
117  : _Base(__m, __a) { }
118 
119  multiset(multiset&& __m, const allocator_type& __a)
120  noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
121  : _Safe(std::move(__m._M_safe()), __a),
122  _Base(std::move(__m._M_base()), __a) { }
123 
124  multiset(initializer_list<value_type> __l, const allocator_type& __a)
125  : _Base(__l, __a)
126  { }
127 
128  template<typename _InputIterator>
129  multiset(_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  ~multiset() = default;
136 #endif
137 
138  explicit multiset(const _Compare& __comp,
139  const _Allocator& __a = _Allocator())
140  : _Base(__comp, __a) { }
141 
142  template<typename _InputIterator>
143  multiset(_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  multiset(_Base_ref __x)
152  : _Base(__x._M_ref) { }
153 
154 #if __cplusplus < 201103L
155  multiset&
156  operator=(const multiset& __x)
157  {
158  this->_M_safe() = __x;
159  _M_base() = __x;
160  return *this;
161  }
162 #else
163  multiset&
164  operator=(const multiset&) = default;
165 
166  multiset&
167  operator=(multiset&&) = default;
168 
169  multiset&
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  iterator
262  insert(value_type&& __x)
263  { return { _Base::insert(std::move(__x)), this }; }
264 #endif
265 
266  iterator
267  insert(const_iterator __position, const value_type& __x)
268  {
269  __glibcxx_check_insert(__position);
270  return iterator(_Base::insert(__position.base(), __x), this);
271  }
272 
273 #if __cplusplus >= 201103L
274  iterator
275  insert(const_iterator __position, value_type&& __x)
276  {
277  __glibcxx_check_insert(__position);
278  return { _Base::insert(__position.base(), std::move(__x)), this };
279  }
280 #endif
281 
282  template<typename _InputIterator>
283  void
284  insert(_InputIterator __first, _InputIterator __last)
285  {
287  __glibcxx_check_valid_range2(__first, __last, __dist);
288 
289  if (__dist.second >= __gnu_debug::__dp_sign)
290  _Base::insert(__gnu_debug::__unsafe(__first),
291  __gnu_debug::__unsafe(__last));
292  else
293  _Base::insert(__first, __last);
294  }
295 
296 #if __cplusplus >= 201103L
297  void
298  insert(initializer_list<value_type> __l)
299  { _Base::insert(__l); }
300 #endif
301 
302 #if __cplusplus > 201402L
303  using node_type = typename _Base::node_type;
304 
305  node_type
306  extract(const_iterator __position)
307  {
308  __glibcxx_check_erase(__position);
309  this->_M_invalidate_if(_Equal(__position.base()));
310  return _Base::extract(__position.base());
311  }
312 
313  node_type
314  extract(const key_type& __key)
315  {
316  const auto __position = find(__key);
317  if (__position != end())
318  return extract(__position);
319  return {};
320  }
321 
322  iterator
323  insert(node_type&& __nh)
324  { return { _Base::insert(std::move(__nh)), this }; }
325 
326  iterator
327  insert(const_iterator __hint, node_type&& __nh)
328  {
329  __glibcxx_check_insert(__hint);
330  return { _Base::insert(__hint.base(), std::move(__nh)), this };
331  }
332 
333  using _Base::merge;
334 #endif // C++17
335 
336 #if __cplusplus >= 201103L
337  _GLIBCXX_ABI_TAG_CXX11
338  iterator
339  erase(const_iterator __position)
340  {
341  __glibcxx_check_erase(__position);
342  this->_M_invalidate_if(_Equal(__position.base()));
343  return { _Base::erase(__position.base()), this };
344  }
345 #else
346  void
347  erase(iterator __position)
348  {
349  __glibcxx_check_erase(__position);
350  this->_M_invalidate_if(_Equal(__position.base()));
351  _Base::erase(__position.base());
352  }
353 #endif
354 
355  size_type
356  erase(const key_type& __x)
357  {
359  _Base::equal_range(__x);
360  size_type __count = 0;
361  _Base_iterator __victim = __victims.first;
362  while (__victim != __victims.second)
363  {
364  this->_M_invalidate_if(_Equal(__victim));
365  _Base::erase(__victim++);
366  ++__count;
367  }
368  return __count;
369  }
370 
371 #if __cplusplus >= 201103L
372  _GLIBCXX_ABI_TAG_CXX11
373  iterator
374  erase(const_iterator __first, const_iterator __last)
375  {
376  // _GLIBCXX_RESOLVE_LIB_DEFECTS
377  // 151. can't currently clear() empty container
378  __glibcxx_check_erase_range(__first, __last);
379  for (_Base_const_iterator __victim = __first.base();
380  __victim != __last.base(); ++__victim)
381  {
382  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
383  _M_message(__gnu_debug::__msg_valid_range)
384  ._M_iterator(__first, "first")
385  ._M_iterator(__last, "last"));
386  this->_M_invalidate_if(_Equal(__victim));
387  }
388 
389  return { _Base::erase(__first.base(), __last.base()), this };
390  }
391 #else
392  void
393  erase(iterator __first, 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_iterator __victim = __first.base();
399  __victim != __last.base(); ++__victim)
400  {
401  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
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  _Base::erase(__first.base(), __last.base());
408  }
409 #endif
410 
411  void
412  swap(multiset& __x)
413  _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
414  {
415  _Safe::_M_swap(__x);
416  _Base::swap(__x);
417  }
418 
419  void
420  clear() _GLIBCXX_NOEXCEPT
421  {
422  this->_M_invalidate_all();
423  _Base::clear();
424  }
425 
426  // observers:
427  using _Base::key_comp;
428  using _Base::value_comp;
429 
430  // multiset operations:
431  iterator
432  find(const key_type& __x)
433  { return iterator(_Base::find(__x), this); }
434 
435  // _GLIBCXX_RESOLVE_LIB_DEFECTS
436  // 214. set::find() missing const overload
438  find(const key_type& __x) const
439  { return const_iterator(_Base::find(__x), this); }
440 
441 #if __cplusplus > 201103L
442  template<typename _Kt,
443  typename _Req =
444  typename __has_is_transparent<_Compare, _Kt>::type>
445  iterator
446  find(const _Kt& __x)
447  { return { _Base::find(__x), this }; }
448 
449  template<typename _Kt,
450  typename _Req =
451  typename __has_is_transparent<_Compare, _Kt>::type>
453  find(const _Kt& __x) const
454  { return { _Base::find(__x), this }; }
455 #endif
456 
457  using _Base::count;
458 
459  iterator
460  lower_bound(const key_type& __x)
461  { return iterator(_Base::lower_bound(__x), this); }
462 
463  // _GLIBCXX_RESOLVE_LIB_DEFECTS
464  // 214. set::find() missing const overload
466  lower_bound(const key_type& __x) const
467  { return const_iterator(_Base::lower_bound(__x), this); }
468 
469 #if __cplusplus > 201103L
470  template<typename _Kt,
471  typename _Req =
472  typename __has_is_transparent<_Compare, _Kt>::type>
473  iterator
474  lower_bound(const _Kt& __x)
475  { return { _Base::lower_bound(__x), this }; }
476 
477  template<typename _Kt,
478  typename _Req =
479  typename __has_is_transparent<_Compare, _Kt>::type>
481  lower_bound(const _Kt& __x) const
482  { return { _Base::lower_bound(__x), this }; }
483 #endif
484 
485  iterator
486  upper_bound(const key_type& __x)
487  { return iterator(_Base::upper_bound(__x), this); }
488 
489  // _GLIBCXX_RESOLVE_LIB_DEFECTS
490  // 214. set::find() missing const overload
492  upper_bound(const key_type& __x) const
493  { return const_iterator(_Base::upper_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  upper_bound(const _Kt& __x)
501  { return { _Base::upper_bound(__x), this }; }
502 
503  template<typename _Kt,
504  typename _Req =
505  typename __has_is_transparent<_Compare, _Kt>::type>
507  upper_bound(const _Kt& __x) const
508  { return { _Base::upper_bound(__x), this }; }
509 #endif
510 
512  equal_range(const key_type& __x)
513  {
515  _Base::equal_range(__x);
516  return std::make_pair(iterator(__res.first, this),
517  iterator(__res.second, this));
518  }
519 
520  // _GLIBCXX_RESOLVE_LIB_DEFECTS
521  // 214. set::find() missing const overload
523  equal_range(const key_type& __x) const
524  {
526  _Base::equal_range(__x);
527  return std::make_pair(const_iterator(__res.first, this),
528  const_iterator(__res.second, this));
529  }
530 
531 #if __cplusplus > 201103L
532  template<typename _Kt,
533  typename _Req =
534  typename __has_is_transparent<_Compare, _Kt>::type>
536  equal_range(const _Kt& __x)
537  {
538  auto __res = _Base::equal_range(__x);
539  return { { __res.first, this }, { __res.second, this } };
540  }
541 
542  template<typename _Kt,
543  typename _Req =
544  typename __has_is_transparent<_Compare, _Kt>::type>
546  equal_range(const _Kt& __x) const
547  {
548  auto __res = _Base::equal_range(__x);
549  return { { __res.first, this }, { __res.second, this } };
550  }
551 #endif
552 
553  _Base&
554  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
555 
556  const _Base&
557  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
558  };
559 
560 #if __cpp_deduction_guides >= 201606
561 
562  template<typename _InputIterator,
563  typename _Compare =
565  typename _Allocator =
567  typename = _RequireInputIter<_InputIterator>,
568  typename = _RequireNotAllocator<_Compare>,
569  typename = _RequireAllocator<_Allocator>>
570  multiset(_InputIterator, _InputIterator,
571  _Compare = _Compare(), _Allocator = _Allocator())
573  _Compare, _Allocator>;
574 
575  template<typename _Key,
576  typename _Compare = less<_Key>,
577  typename _Allocator = allocator<_Key>,
578  typename = _RequireNotAllocator<_Compare>,
579  typename = _RequireAllocator<_Allocator>>
581  _Compare = _Compare(), _Allocator = _Allocator())
583 
584  template<typename _InputIterator, typename _Allocator,
585  typename = _RequireInputIter<_InputIterator>,
586  typename = _RequireAllocator<_Allocator>>
587  multiset(_InputIterator, _InputIterator, _Allocator)
590  _Allocator>;
591 
592  template<typename _Key, typename _Allocator,
593  typename = _RequireAllocator<_Allocator>>
594  multiset(initializer_list<_Key>, _Allocator)
595  -> multiset<_Key, less<_Key>, _Allocator>;
596 
597 #endif // deduction guides
598 
599  template<typename _Key, typename _Compare, typename _Allocator>
600  inline bool
601  operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
603  { return __lhs._M_base() == __rhs._M_base(); }
604 
605 #if __cpp_lib_three_way_comparison
606  template<typename _Key, typename _Compare, typename _Alloc>
607  inline __detail::__synth3way_t<_Key>
608  operator<=>(const multiset<_Key, _Compare, _Alloc>& __lhs,
610  { return __lhs._M_base() <=> __rhs._M_base(); }
611 #else
612  template<typename _Key, typename _Compare, typename _Allocator>
613  inline bool
614  operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
615  const multiset<_Key, _Compare, _Allocator>& __rhs)
616  { return __lhs._M_base() != __rhs._M_base(); }
617 
618  template<typename _Key, typename _Compare, typename _Allocator>
619  inline bool
620  operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
621  const multiset<_Key, _Compare, _Allocator>& __rhs)
622  { return __lhs._M_base() < __rhs._M_base(); }
623 
624  template<typename _Key, typename _Compare, typename _Allocator>
625  inline bool
626  operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
627  const multiset<_Key, _Compare, _Allocator>& __rhs)
628  { return __lhs._M_base() <= __rhs._M_base(); }
629 
630  template<typename _Key, typename _Compare, typename _Allocator>
631  inline bool
632  operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
633  const multiset<_Key, _Compare, _Allocator>& __rhs)
634  { return __lhs._M_base() >= __rhs._M_base(); }
635 
636  template<typename _Key, typename _Compare, typename _Allocator>
637  inline bool
638  operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
639  const multiset<_Key, _Compare, _Allocator>& __rhs)
640  { return __lhs._M_base() > __rhs._M_base(); }
641 #endif // three-way comparison
642 
643  template<typename _Key, typename _Compare, typename _Allocator>
644  void
645  swap(multiset<_Key, _Compare, _Allocator>& __x,
646  multiset<_Key, _Compare, _Allocator>& __y)
647  _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
648  { return __x.swap(__y); }
649 
650 } // namespace __debug
651 } // namespace std
652 
653 #endif
#define __glibcxx_check_insert(_Position)
Definition: macros.h:146
Safe class dealing with some allocator dependent operations.
initializer_list
_Iterator & base() noexcept
Return the underlying iterator.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:245
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:138
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:211
A standard container made up of elements, which can be retrieved in logarithmic time.
Definition: stl_multiset.h:96
Safe iterator wrapper.
Definition: debug.h:61
Class std::multiset with safety/checking/debug instrumentation.
Definition: multiset.h:44
_T2 second
The second member.
Definition: stl_pair.h:218
constexpr _Iterator __base(_Iterator __it)
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:263
_T1 first
The first member.
Definition: stl_pair.h:217
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
ISO C++ entities toplevel namespace is std.
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:240
One of the comparison functors.
Definition: stl_function.h:340
#define __glibcxx_check_erase(_Position)
Definition: macros.h:212