libstdc++
debug/multiset.h
Go to the documentation of this file.
1 // Debugging multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2018 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
45  : public __gnu_debug::_Safe_container<
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;
51  typedef __gnu_debug::_Safe_container<
52  multiset, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe;
53 
54  typedef typename _Base::const_iterator _Base_const_iterator;
55  typedef typename _Base::iterator _Base_iterator;
56  typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
57 
58  public:
59  // types:
60  typedef _Key key_type;
61  typedef _Key value_type;
62  typedef _Compare key_compare;
63  typedef _Compare value_compare;
64  typedef _Allocator allocator_type;
65  typedef typename _Base::reference reference;
66  typedef typename _Base::const_reference const_reference;
67 
68  typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
69  iterator;
70  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
71  multiset> const_iterator;
72 
73  typedef typename _Base::size_type size_type;
74  typedef typename _Base::difference_type difference_type;
75  typedef typename _Base::pointer pointer;
76  typedef typename _Base::const_pointer const_pointer;
77  typedef std::reverse_iterator<iterator> reverse_iterator;
78  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
79 
80  // 23.3.3.1 construct/copy/destroy:
81 
82 #if __cplusplus < 201103L
83  multiset() : _Base() { }
84 
85  multiset(const multiset& __x)
86  : _Base(__x) { }
87 
88  ~multiset() { }
89 #else
90  multiset() = default;
91  multiset(const multiset&) = default;
92  multiset(multiset&&) = default;
93 
94  multiset(initializer_list<value_type> __l,
95  const _Compare& __comp = _Compare(),
96  const allocator_type& __a = allocator_type())
97  : _Base(__l, __comp, __a) { }
98 
99  explicit
100  multiset(const allocator_type& __a)
101  : _Base(__a) { }
102 
103  multiset(const multiset& __m, const allocator_type& __a)
104  : _Base(__m, __a) { }
105 
106  multiset(multiset&& __m, const allocator_type& __a)
107  noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
108  : _Safe(std::move(__m._M_safe()), __a),
109  _Base(std::move(__m._M_base()), __a) { }
110 
111  multiset(initializer_list<value_type> __l, const allocator_type& __a)
112  : _Base(__l, __a)
113  { }
114 
115  template<typename _InputIterator>
116  multiset(_InputIterator __first, _InputIterator __last,
117  const allocator_type& __a)
118  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
119  __last)),
120  __gnu_debug::__base(__last), __a) { }
121 
122  ~multiset() = default;
123 #endif
124 
125  explicit multiset(const _Compare& __comp,
126  const _Allocator& __a = _Allocator())
127  : _Base(__comp, __a) { }
128 
129  template<typename _InputIterator>
130  multiset(_InputIterator __first, _InputIterator __last,
131  const _Compare& __comp = _Compare(),
132  const _Allocator& __a = _Allocator())
133  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
134  __last)),
135  __gnu_debug::__base(__last),
136  __comp, __a) { }
137 
138  multiset(const _Base& __x)
139  : _Base(__x) { }
140 
141 #if __cplusplus < 201103L
142  multiset&
143  operator=(const multiset& __x)
144  {
145  this->_M_safe() = __x;
146  _M_base() = __x;
147  return *this;
148  }
149 #else
150  multiset&
151  operator=(const multiset&) = default;
152 
153  multiset&
154  operator=(multiset&&) = default;
155 
156  multiset&
157  operator=(initializer_list<value_type> __l)
158  {
159  _M_base() = __l;
160  this->_M_invalidate_all();
161  return *this;
162  }
163 #endif
164 
165  using _Base::get_allocator;
166 
167  // iterators:
168  iterator
169  begin() _GLIBCXX_NOEXCEPT
170  { return iterator(_Base::begin(), this); }
171 
172  const_iterator
173  begin() const _GLIBCXX_NOEXCEPT
174  { return const_iterator(_Base::begin(), this); }
175 
176  iterator
177  end() _GLIBCXX_NOEXCEPT
178  { return iterator(_Base::end(), this); }
179 
180  const_iterator
181  end() const _GLIBCXX_NOEXCEPT
182  { return const_iterator(_Base::end(), this); }
183 
184  reverse_iterator
185  rbegin() _GLIBCXX_NOEXCEPT
186  { return reverse_iterator(end()); }
187 
188  const_reverse_iterator
189  rbegin() const _GLIBCXX_NOEXCEPT
190  { return const_reverse_iterator(end()); }
191 
192  reverse_iterator
193  rend() _GLIBCXX_NOEXCEPT
194  { return reverse_iterator(begin()); }
195 
196  const_reverse_iterator
197  rend() const _GLIBCXX_NOEXCEPT
198  { return const_reverse_iterator(begin()); }
199 
200 #if __cplusplus >= 201103L
201  const_iterator
202  cbegin() const noexcept
203  { return const_iterator(_Base::begin(), this); }
204 
205  const_iterator
206  cend() const noexcept
207  { return const_iterator(_Base::end(), this); }
208 
209  const_reverse_iterator
210  crbegin() const noexcept
211  { return const_reverse_iterator(end()); }
212 
213  const_reverse_iterator
214  crend() const noexcept
215  { return const_reverse_iterator(begin()); }
216 #endif
217 
218  // capacity:
219  using _Base::empty;
220  using _Base::size;
221  using _Base::max_size;
222 
223  // modifiers:
224 #if __cplusplus >= 201103L
225  template<typename... _Args>
226  iterator
227  emplace(_Args&&... __args)
228  {
229  return iterator(_Base::emplace(std::forward<_Args>(__args)...),
230  this);
231  }
232 
233  template<typename... _Args>
234  iterator
235  emplace_hint(const_iterator __pos, _Args&&... __args)
236  {
237  __glibcxx_check_insert(__pos);
238  return iterator(_Base::emplace_hint(__pos.base(),
239  std::forward<_Args>(__args)...),
240  this);
241  }
242 #endif
243 
244  iterator
245  insert(const value_type& __x)
246  { return iterator(_Base::insert(__x), this); }
247 
248 #if __cplusplus >= 201103L
249  iterator
250  insert(value_type&& __x)
251  { return iterator(_Base::insert(std::move(__x)), this); }
252 #endif
253 
254  iterator
255  insert(const_iterator __position, const value_type& __x)
256  {
257  __glibcxx_check_insert(__position);
258  return iterator(_Base::insert(__position.base(), __x), this);
259  }
260 
261 #if __cplusplus >= 201103L
262  iterator
263  insert(const_iterator __position, value_type&& __x)
264  {
265  __glibcxx_check_insert(__position);
266  return iterator(_Base::insert(__position.base(), std::move(__x)),
267  this);
268  }
269 #endif
270 
271  template<typename _InputIterator>
272  void
273  insert(_InputIterator __first, _InputIterator __last)
274  {
275  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
276  __glibcxx_check_valid_range2(__first, __last, __dist);
277 
278  if (__dist.second >= __gnu_debug::__dp_sign)
279  _Base::insert(__gnu_debug::__unsafe(__first),
280  __gnu_debug::__unsafe(__last));
281  else
282  _Base::insert(__first, __last);
283  }
284 
285 #if __cplusplus >= 201103L
286  void
287  insert(initializer_list<value_type> __l)
288  { _Base::insert(__l); }
289 #endif
290 
291 #if __cplusplus > 201402L
292  using node_type = typename _Base::node_type;
293 
294  node_type
295  extract(const_iterator __position)
296  {
297  __glibcxx_check_erase(__position);
298  this->_M_invalidate_if(_Equal(__position.base()));
299  return _Base::extract(__position.base());
300  }
301 
302  node_type
303  extract(const key_type& __key)
304  {
305  const auto __position = find(__key);
306  if (__position != end())
307  return extract(__position);
308  return {};
309  }
310 
311  iterator
312  insert(node_type&& __nh)
313  { return iterator(_Base::insert(std::move(__nh)), this); }
314 
315  iterator
316  insert(const_iterator __hint, node_type&& __nh)
317  {
318  __glibcxx_check_insert(__hint);
319  return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
320  }
321 
322  using _Base::merge;
323 #endif // C++17
324 
325 #if __cplusplus >= 201103L
326  iterator
327  erase(const_iterator __position)
328  {
329  __glibcxx_check_erase(__position);
330  this->_M_invalidate_if(_Equal(__position.base()));
331  return iterator(_Base::erase(__position.base()), this);
332  }
333 #else
334  void
335  erase(iterator __position)
336  {
337  __glibcxx_check_erase(__position);
338  this->_M_invalidate_if(_Equal(__position.base()));
339  _Base::erase(__position.base());
340  }
341 #endif
342 
343  size_type
344  erase(const key_type& __x)
345  {
346  std::pair<_Base_iterator, _Base_iterator> __victims =
347  _Base::equal_range(__x);
348  size_type __count = 0;
349  _Base_iterator __victim = __victims.first;
350  while (__victim != __victims.second)
351  {
352  this->_M_invalidate_if(_Equal(__victim));
353  _Base::erase(__victim++);
354  ++__count;
355  }
356  return __count;
357  }
358 
359 #if __cplusplus >= 201103L
360  iterator
361  erase(const_iterator __first, const_iterator __last)
362  {
363  // _GLIBCXX_RESOLVE_LIB_DEFECTS
364  // 151. can't currently clear() empty container
365  __glibcxx_check_erase_range(__first, __last);
366  for (_Base_const_iterator __victim = __first.base();
367  __victim != __last.base(); ++__victim)
368  {
369  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
370  _M_message(__gnu_debug::__msg_valid_range)
371  ._M_iterator(__first, "first")
372  ._M_iterator(__last, "last"));
373  this->_M_invalidate_if(_Equal(__victim));
374  }
375  return iterator(_Base::erase(__first.base(), __last.base()), this);
376  }
377 #else
378  void
379  erase(iterator __first, iterator __last)
380  {
381  // _GLIBCXX_RESOLVE_LIB_DEFECTS
382  // 151. can't currently clear() empty container
383  __glibcxx_check_erase_range(__first, __last);
384  for (_Base_iterator __victim = __first.base();
385  __victim != __last.base(); ++__victim)
386  {
387  _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
388  _M_message(__gnu_debug::__msg_valid_range)
389  ._M_iterator(__first, "first")
390  ._M_iterator(__last, "last"));
391  this->_M_invalidate_if(_Equal(__victim));
392  }
393  _Base::erase(__first.base(), __last.base());
394  }
395 #endif
396 
397  void
398  swap(multiset& __x)
399  _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
400  {
401  _Safe::_M_swap(__x);
402  _Base::swap(__x);
403  }
404 
405  void
406  clear() _GLIBCXX_NOEXCEPT
407  {
408  this->_M_invalidate_all();
409  _Base::clear();
410  }
411 
412  // observers:
413  using _Base::key_comp;
414  using _Base::value_comp;
415 
416  // multiset operations:
417  iterator
418  find(const key_type& __x)
419  { return iterator(_Base::find(__x), this); }
420 
421  // _GLIBCXX_RESOLVE_LIB_DEFECTS
422  // 214. set::find() missing const overload
423  const_iterator
424  find(const key_type& __x) const
425  { return const_iterator(_Base::find(__x), this); }
426 
427 #if __cplusplus > 201103L
428  template<typename _Kt,
429  typename _Req =
430  typename __has_is_transparent<_Compare, _Kt>::type>
431  iterator
432  find(const _Kt& __x)
433  { return { _Base::find(__x), this }; }
434 
435  template<typename _Kt,
436  typename _Req =
437  typename __has_is_transparent<_Compare, _Kt>::type>
438  const_iterator
439  find(const _Kt& __x) const
440  { return { _Base::find(__x), this }; }
441 #endif
442 
443  using _Base::count;
444 
445  iterator
446  lower_bound(const key_type& __x)
447  { return iterator(_Base::lower_bound(__x), this); }
448 
449  // _GLIBCXX_RESOLVE_LIB_DEFECTS
450  // 214. set::find() missing const overload
451  const_iterator
452  lower_bound(const key_type& __x) const
453  { return const_iterator(_Base::lower_bound(__x), this); }
454 
455 #if __cplusplus > 201103L
456  template<typename _Kt,
457  typename _Req =
458  typename __has_is_transparent<_Compare, _Kt>::type>
459  iterator
460  lower_bound(const _Kt& __x)
461  { return { _Base::lower_bound(__x), this }; }
462 
463  template<typename _Kt,
464  typename _Req =
465  typename __has_is_transparent<_Compare, _Kt>::type>
466  const_iterator
467  lower_bound(const _Kt& __x) const
468  { return { _Base::lower_bound(__x), this }; }
469 #endif
470 
471  iterator
472  upper_bound(const key_type& __x)
473  { return iterator(_Base::upper_bound(__x), this); }
474 
475  // _GLIBCXX_RESOLVE_LIB_DEFECTS
476  // 214. set::find() missing const overload
477  const_iterator
478  upper_bound(const key_type& __x) const
479  { return const_iterator(_Base::upper_bound(__x), this); }
480 
481 #if __cplusplus > 201103L
482  template<typename _Kt,
483  typename _Req =
484  typename __has_is_transparent<_Compare, _Kt>::type>
485  iterator
486  upper_bound(const _Kt& __x)
487  { return { _Base::upper_bound(__x), this }; }
488 
489  template<typename _Kt,
490  typename _Req =
491  typename __has_is_transparent<_Compare, _Kt>::type>
492  const_iterator
493  upper_bound(const _Kt& __x) const
494  { return { _Base::upper_bound(__x), this }; }
495 #endif
496 
497  std::pair<iterator,iterator>
498  equal_range(const key_type& __x)
499  {
500  std::pair<_Base_iterator, _Base_iterator> __res =
501  _Base::equal_range(__x);
502  return std::make_pair(iterator(__res.first, this),
503  iterator(__res.second, this));
504  }
505 
506  // _GLIBCXX_RESOLVE_LIB_DEFECTS
507  // 214. set::find() missing const overload
508  std::pair<const_iterator,const_iterator>
509  equal_range(const key_type& __x) const
510  {
511  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
512  _Base::equal_range(__x);
513  return std::make_pair(const_iterator(__res.first, this),
514  const_iterator(__res.second, this));
515  }
516 
517 #if __cplusplus > 201103L
518  template<typename _Kt,
519  typename _Req =
520  typename __has_is_transparent<_Compare, _Kt>::type>
521  std::pair<iterator, iterator>
522  equal_range(const _Kt& __x)
523  {
524  auto __res = _Base::equal_range(__x);
525  return { { __res.first, this }, { __res.second, this } };
526  }
527 
528  template<typename _Kt,
529  typename _Req =
530  typename __has_is_transparent<_Compare, _Kt>::type>
531  std::pair<const_iterator, const_iterator>
532  equal_range(const _Kt& __x) const
533  {
534  auto __res = _Base::equal_range(__x);
535  return { { __res.first, this }, { __res.second, this } };
536  }
537 #endif
538 
539  _Base&
540  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
541 
542  const _Base&
543  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
544  };
545 
546 #if __cpp_deduction_guides >= 201606
547 
548  template<typename _InputIterator,
549  typename _Compare =
550  less<typename iterator_traits<_InputIterator>::value_type>,
551  typename _Allocator =
552  allocator<typename iterator_traits<_InputIterator>::value_type>,
553  typename = _RequireInputIter<_InputIterator>,
554  typename = _RequireAllocator<_Allocator>>
555  multiset(_InputIterator, _InputIterator,
556  _Compare = _Compare(), _Allocator = _Allocator())
557  -> multiset<typename iterator_traits<_InputIterator>::value_type,
558  _Compare, _Allocator>;
559 
560  template<typename _Key,
561  typename _Compare = less<_Key>,
562  typename _Allocator = allocator<_Key>,
563  typename = _RequireAllocator<_Allocator>>
564  multiset(initializer_list<_Key>,
565  _Compare = _Compare(), _Allocator = _Allocator())
566  -> multiset<_Key, _Compare, _Allocator>;
567 
568  template<typename _InputIterator, typename _Allocator,
569  typename = _RequireInputIter<_InputIterator>,
570  typename = _RequireAllocator<_Allocator>>
571  multiset(_InputIterator, _InputIterator, _Allocator)
572  -> multiset<typename iterator_traits<_InputIterator>::value_type,
573  less<typename iterator_traits<_InputIterator>::value_type>,
574  _Allocator>;
575 
576  template<typename _Key, typename _Allocator,
577  typename = _RequireAllocator<_Allocator>>
578  multiset(initializer_list<_Key>, _Allocator)
579  -> multiset<_Key, less<_Key>, _Allocator>;
580 
581 #endif
582 
583  template<typename _Key, typename _Compare, typename _Allocator>
584  inline bool
585  operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
586  const multiset<_Key, _Compare, _Allocator>& __rhs)
587  { return __lhs._M_base() == __rhs._M_base(); }
588 
589  template<typename _Key, typename _Compare, typename _Allocator>
590  inline bool
591  operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
592  const multiset<_Key, _Compare, _Allocator>& __rhs)
593  { return __lhs._M_base() != __rhs._M_base(); }
594 
595  template<typename _Key, typename _Compare, typename _Allocator>
596  inline bool
597  operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
598  const multiset<_Key, _Compare, _Allocator>& __rhs)
599  { return __lhs._M_base() < __rhs._M_base(); }
600 
601  template<typename _Key, typename _Compare, typename _Allocator>
602  inline bool
603  operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
604  const multiset<_Key, _Compare, _Allocator>& __rhs)
605  { return __lhs._M_base() <= __rhs._M_base(); }
606 
607  template<typename _Key, typename _Compare, typename _Allocator>
608  inline bool
609  operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
610  const multiset<_Key, _Compare, _Allocator>& __rhs)
611  { return __lhs._M_base() >= __rhs._M_base(); }
612 
613  template<typename _Key, typename _Compare, typename _Allocator>
614  inline bool
615  operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
616  const multiset<_Key, _Compare, _Allocator>& __rhs)
617  { return __lhs._M_base() > __rhs._M_base(); }
618 
619  template<typename _Key, typename _Compare, typename _Allocator>
620  void
621  swap(multiset<_Key, _Compare, _Allocator>& __x,
622  multiset<_Key, _Compare, _Allocator>& __y)
623  _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
624  { return __x.swap(__y); }
625 
626 } // namespace __debug
627 } // namespace std
628 
629 #endif
__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:131
std::less
One of the comparison functors.
Definition: stl_function.h:340
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:208
std::__debug::multiset
Class std::multiset with safety/checking/debug instrumentation.
Definition: debug/multiset.h:44
std::multiset
A standard container made up of elements, which can be retrieved in logarithmic time.
Definition: stl_multiset.h:96
std::allocator
The standard allocator, as per [20.4].
Definition: allocator.h:108
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: formatter.h:56
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition: macros.h:145
std::make_pair
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:524
std::initializer_list
initializer_list
Definition: initializer_list:47
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition: macros.h:79
std
ISO C++ entities toplevel namespace is std.
__gnu_debug::_Safe_iterator::base
_Iterator & base() noexcept
Return the underlying iterator.
Definition: safe_iterator.h:403
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:173
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:214
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:215
__gnu_debug::_Safe_container
Safe class dealing with some allocator dependent operations.
Definition: safe_container.h:41