libstdc++
profile/multiset.h
Go to the documentation of this file.
1 // Profiling multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-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 profile/multiset.h
26  * This file is a GNU profile extension to the Standard C++ Library.
27  */
28 
29 #ifndef _GLIBCXX_PROFILE_MULTISET_H
30 #define _GLIBCXX_PROFILE_MULTISET_H 1
31 
32 #include <profile/base.h>
33 #include <profile/ordered_base.h>
34 
35 namespace std _GLIBCXX_VISIBILITY(default)
36 {
37 namespace __profile
38 {
39  /// Class std::multiset wrapper with performance instrumentation.
40  template<typename _Key, typename _Compare = std::less<_Key>,
41  typename _Allocator = std::allocator<_Key> >
42  class multiset
43  : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>,
44  public _Ordered_profile<multiset<_Key, _Compare, _Allocator> >
45  {
46  typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
47 
48  typedef typename _Base::iterator _Base_iterator;
49  typedef typename _Base::const_iterator _Base_const_iterator;
50 
51  public:
52  // types:
53  typedef _Key key_type;
54  typedef _Key value_type;
55  typedef _Compare key_compare;
56  typedef _Compare value_compare;
57  typedef _Allocator allocator_type;
58  typedef typename _Base::reference reference;
59  typedef typename _Base::const_reference const_reference;
60 
61  typedef __iterator_tracker<_Base_iterator,
62  multiset> iterator;
63  typedef __iterator_tracker<_Base_const_iterator,
64  multiset> const_iterator;
65  typedef std::reverse_iterator<iterator> reverse_iterator;
66  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
67 
68  typedef typename _Base::size_type size_type;
69  typedef typename _Base::difference_type difference_type;
70 
71  // 23.3.3.1 construct/copy/destroy:
72 
73 #if __cplusplus < 201103L
74  multiset()
75  : _Base() { }
76  multiset(const multiset& __x)
77  : _Base(__x) { }
78  ~multiset() { }
79 #else
80  multiset() = default;
81  multiset(const multiset&) = default;
82  multiset(multiset&&) = default;
83  ~multiset() = default;
84 #endif
85 
86  explicit multiset(const _Compare& __comp,
87  const _Allocator& __a = _Allocator())
88  : _Base(__comp, __a) { }
89 
90 #if __cplusplus >= 201103L
91  template<typename _InputIterator,
92  typename = std::_RequireInputIter<_InputIterator>>
93 #else
94  template<typename _InputIterator>
95 #endif
96  multiset(_InputIterator __first, _InputIterator __last,
97  const _Compare& __comp = _Compare(),
98  const _Allocator& __a = _Allocator())
99  : _Base(__first, __last, __comp, __a) { }
100 
101 #if __cplusplus >= 201103L
102  multiset(initializer_list<value_type> __l,
103  const _Compare& __comp = _Compare(),
104  const allocator_type& __a = allocator_type())
105  : _Base(__l, __comp, __a) { }
106 
107  explicit
108  multiset(const allocator_type& __a)
109  : _Base(__a) { }
110 
111  multiset(const multiset& __x, const allocator_type& __a)
112  : _Base(__x, __a) { }
113 
114  multiset(multiset&& __x, const allocator_type& __a)
115  noexcept( noexcept(_Base(std::move(__x), __a)) )
116  : _Base(std::move(__x), __a) { }
117 
118  multiset(initializer_list<value_type> __l, const allocator_type& __a)
119  : _Base(__l, __a) { }
120 
121  template<typename _InputIterator>
122  multiset(_InputIterator __first, _InputIterator __last,
123  const allocator_type& __a)
124  : _Base(__first, __last, __a) { }
125 #endif
126 
127  multiset(const _Base& __x)
128  : _Base(__x) { }
129 
130 #if __cplusplus < 201103L
131  multiset&
132  operator=(const multiset& __x)
133  {
134  this->_M_profile_destruct();
135  _M_base() = __x;
136  this->_M_profile_construct();
137  return *this;
138  }
139 #else
140  multiset&
141  operator=(const multiset&) = default;
142 
143  multiset&
144  operator=(multiset&&) = default;
145 
146  multiset&
147  operator=(initializer_list<value_type> __l)
148  {
149  this->_M_profile_destruct();
150  _M_base() = __l;
151  this->_M_profile_construct();
152  return *this;
153  }
154 #endif
155 
156  // iterators
157  iterator
158  begin() _GLIBCXX_NOEXCEPT
159  { return iterator(_Base::begin(), this); }
160 
161  const_iterator
162  begin() const _GLIBCXX_NOEXCEPT
163  { return const_iterator(_Base::begin(), this); }
164 
165  iterator
166  end() _GLIBCXX_NOEXCEPT
167  { return iterator(_Base::end(), this); }
168 
169  const_iterator
170  end() const _GLIBCXX_NOEXCEPT
171  { return const_iterator(_Base::end(), this); }
172 
173 #if __cplusplus >= 201103L
174  const_iterator
175  cbegin() const noexcept
176  { return const_iterator(_Base::cbegin(), this); }
177 
178  const_iterator
179  cend() const noexcept
180  { return const_iterator(_Base::cend(), this); }
181 #endif
182 
183  reverse_iterator
184  rbegin() _GLIBCXX_NOEXCEPT
185  {
186  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
187  return reverse_iterator(end());
188  }
189 
190  const_reverse_iterator
191  rbegin() const _GLIBCXX_NOEXCEPT
192  {
193  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
194  return const_reverse_iterator(end());
195  }
196 
197  reverse_iterator
198  rend() _GLIBCXX_NOEXCEPT
199  {
200  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
201  return reverse_iterator(begin());
202  }
203 
204  const_reverse_iterator
205  rend() const _GLIBCXX_NOEXCEPT
206  {
207  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
208  return const_reverse_iterator(begin());
209  }
210 
211 #if __cplusplus >= 201103L
212  const_reverse_iterator
213  crbegin() const noexcept
214  {
215  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
216  return const_reverse_iterator(cend());
217  }
218 
219  const_reverse_iterator
220  crend() const noexcept
221  {
222  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
223  return const_reverse_iterator(cbegin());
224  }
225 #endif
226 
227  void
228  swap(multiset& __x)
229  _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
230  {
231  _Base::swap(__x);
232  this->_M_swap(__x);
233  }
234 
235  // modifiers:
236 #if __cplusplus >= 201103L
237  template<typename... _Args>
238  iterator
239  emplace(_Args&&... __args)
240  {
241  // The cost is the same whether or not the element is inserted so we
242  // always report insertion of 1 element.
243  __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
244  return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
245  }
246 
247  template<typename... _Args>
248  iterator
249  emplace_hint(const_iterator __pos, _Args&&... __args)
250  {
251  auto size_before = this->size();
252  auto __res
253  = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
254  __profcxx_map2umap_insert(this->_M_map2umap_info,
255  size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
256  return iterator(__res, this);
257  }
258 #endif
259 
260  iterator
261  insert(const value_type& __x)
262  {
263  __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
264  return iterator(_Base::insert(__x), this);
265  }
266 
267 #if __cplusplus >= 201103L
268  iterator
269  insert(value_type&& __x)
270  {
271  __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
272  return iterator(_Base::insert(std::move(__x)), this);
273  }
274 #endif
275 
276  iterator
277  insert(const_iterator __pos, const value_type& __x)
278  {
279  size_type size_before = this->size();
280  _Base_iterator __res = _Base::insert(__pos.base(), __x);
281 
282  __profcxx_map2umap_insert(this->_M_map2umap_info,
283  size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
284  return iterator(__res, this);
285  }
286 
287 #if __cplusplus >= 201103L
288  iterator
289  insert(const_iterator __pos, value_type&& __x)
290  {
291  auto size_before = this->size();
292  auto __res = _Base::insert(__pos.base(), std::move(__x));
293  __profcxx_map2umap_insert(this->_M_map2umap_info,
294  size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
295  return iterator(__res, this);
296  }
297 #endif
298 
299 #if __cplusplus >= 201103L
300  template<typename _InputIterator,
301  typename = std::_RequireInputIter<_InputIterator>>
302 #else
303  template<typename _InputIterator>
304 #endif
305  void
306  insert(_InputIterator __first, _InputIterator __last)
307  {
308  for (; __first != __last; ++__first)
309  insert(*__first);
310  }
311 
312 #if __cplusplus >= 201103L
313  void
314  insert(initializer_list<value_type> __l)
315  { insert(__l.begin(), __l.end()); }
316 #endif
317 
318 #if __cplusplus >= 201103L
319  iterator
320  erase(const_iterator __pos)
321  {
322  __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
323  return iterator(_Base::erase(__pos.base()), this);
324  }
325 #else
326  void
327  erase(iterator __pos)
328  {
329  __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
330  _Base::erase(__pos.base());
331  }
332 #endif
333 
334  size_type
335  erase(const key_type& __x)
336  {
337  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
338  __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
339  return _Base::erase(__x);
340  }
341 
342 #if __cplusplus >= 201103L
343  iterator
344  erase(const_iterator __first, const_iterator __last)
345  {
346  if (__first != __last)
347  {
348  iterator __ret;
349  for (; __first != __last;)
350  __ret = erase(__first++);
351  return __ret;
352  }
353  else
354  return iterator(_Base::erase(__first.base(), __last.base()), this);
355  }
356 #else
357  void
358  erase(iterator __first, iterator __last)
359  {
360  for (; __first != __last;)
361  erase(__first++);
362  }
363 #endif
364 
365  void
366  clear() _GLIBCXX_NOEXCEPT
367  {
368  this->_M_profile_destruct();
369  _Base::clear();
370  this->_M_profile_construct();
371  }
372 
373  size_type
374  count(const key_type& __x) const
375  {
376  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
377  return _Base::count(__x);
378  }
379 
380 #if __cplusplus > 201103L
381  template<typename _Kt,
382  typename _Req =
383  typename __has_is_transparent<_Compare, _Kt>::type>
384  size_type
385  count(const _Kt& __x) const
386  {
387  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
388  return _Base::count(__x);
389  }
390 #endif
391 
392  // multiset operations:
393  iterator
394  find(const key_type& __x)
395  {
396  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
397  return iterator(_Base::find(__x), this);
398  }
399 
400  // _GLIBCXX_RESOLVE_LIB_DEFECTS
401  // 214. set::find() missing const overload
402  const_iterator
403  find(const key_type& __x) const
404  {
405  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
406  return const_iterator(_Base::find(__x), this);
407  }
408 
409 #if __cplusplus > 201103L
410  template<typename _Kt,
411  typename _Req =
412  typename __has_is_transparent<_Compare, _Kt>::type>
413  iterator
414  find(const _Kt& __x)
415  {
416  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
417  return { _Base::find(__x), this };
418  }
419 
420  template<typename _Kt,
421  typename _Req =
422  typename __has_is_transparent<_Compare, _Kt>::type>
423  const_iterator
424  find(const _Kt& __x) const
425  {
426  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
427  return { _Base::find(__x), this };
428  }
429 #endif
430 
431  iterator
432  lower_bound(const key_type& __x)
433  {
434  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
435  return iterator(_Base::lower_bound(__x), this);
436  }
437 
438  // _GLIBCXX_RESOLVE_LIB_DEFECTS
439  // 214. set::find() missing const overload
440  const_iterator
441  lower_bound(const key_type& __x) const
442  {
443  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
444  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
445  return const_iterator(_Base::lower_bound(__x), this);
446  }
447 
448 #if __cplusplus > 201103L
449  template<typename _Kt,
450  typename _Req =
451  typename __has_is_transparent<_Compare, _Kt>::type>
452  iterator
453  lower_bound(const _Kt& __x)
454  {
455  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
456  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
457  return { _Base::lower_bound(__x), this };
458  }
459 
460  template<typename _Kt,
461  typename _Req =
462  typename __has_is_transparent<_Compare, _Kt>::type>
463  const_iterator
464  lower_bound(const _Kt& __x) const
465  {
466  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
467  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
468  return { _Base::lower_bound(__x), this };
469  }
470 #endif
471 
472  iterator
473  upper_bound(const key_type& __x)
474  {
475  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
476  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
477  return iterator(_Base::upper_bound(__x), this);
478  }
479 
480  // _GLIBCXX_RESOLVE_LIB_DEFECTS
481  // 214. set::find() missing const overload
482  const_iterator
483  upper_bound(const key_type& __x) const
484  {
485  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
486  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
487  return const_iterator(_Base::upper_bound(__x), this);
488  }
489 
490 #if __cplusplus > 201103L
491  template<typename _Kt,
492  typename _Req =
493  typename __has_is_transparent<_Compare, _Kt>::type>
494  iterator
495  upper_bound(const _Kt& __x)
496  {
497  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
498  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
499  return { _Base::upper_bound(__x), this };
500  }
501 
502  template<typename _Kt,
503  typename _Req =
504  typename __has_is_transparent<_Compare, _Kt>::type>
505  const_iterator
506  upper_bound(const _Kt& __x) const
507  {
508  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
509  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
510  return { _Base::upper_bound(__x), this };
511  }
512 #endif
513 
514  std::pair<iterator,iterator>
515  equal_range(const key_type& __x)
516  {
517  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
518  std::pair<_Base_iterator, _Base_iterator> __base_ret
519  = _Base::equal_range(__x);
520  return std::make_pair(iterator(__base_ret.first, this),
521  iterator(__base_ret.second, this));
522  }
523 
524  // _GLIBCXX_RESOLVE_LIB_DEFECTS
525  // 214. set::find() missing const overload
526  std::pair<const_iterator,const_iterator>
527  equal_range(const key_type& __x) const
528  {
529  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
530  std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
531  = _Base::equal_range(__x);
532  return std::make_pair(const_iterator(__base_ret.first, this),
533  const_iterator(__base_ret.second, this));
534  }
535 
536 #if __cplusplus > 201103L
537  template<typename _Kt,
538  typename _Req =
539  typename __has_is_transparent<_Compare, _Kt>::type>
540  std::pair<iterator, iterator>
541  equal_range(const _Kt& __x)
542  {
543  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
544  auto __res = _Base::equal_range(__x);
545  return { { __res.first, this }, { __res.second, this } };
546  }
547 
548  template<typename _Kt,
549  typename _Req =
550  typename __has_is_transparent<_Compare, _Kt>::type>
551  std::pair<const_iterator, const_iterator>
552  equal_range(const _Kt& __x) const
553  {
554  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
555  auto __res = _Base::equal_range(__x);
556  return { { __res.first, this }, { __res.second, this } };
557  }
558 #endif
559 
560  _Base&
561  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
562 
563  const _Base&
564  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
565 
566  private:
567  /** If hint is used we consider that the map and unordered_map
568  * operations have equivalent insertion cost so we do not update metrics
569  * about it.
570  * Note that to find out if hint has been used is libstdc++
571  * implementation dependent.
572  */
573  bool
574  _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
575  {
576  return (__hint == __res
577  || (__hint == _M_base().end() && ++__res == _M_base().end())
578  || (__hint != _M_base().end() && (++__hint == __res
579  || ++__res == --__hint)));
580  }
581 
582  template<typename _K1, typename _C1, typename _A1>
583  friend bool
584  operator==(const multiset<_K1, _C1, _A1>&,
585  const multiset<_K1, _C1, _A1>&);
586 
587  template<typename _K1, typename _C1, typename _A1>
588  friend bool
589  operator< (const multiset<_K1, _C1, _A1>&,
590  const multiset<_K1, _C1, _A1>&);
591  };
592 
593  template<typename _Key, typename _Compare, typename _Allocator>
594  inline bool
595  operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
596  const multiset<_Key, _Compare, _Allocator>& __rhs)
597  {
598  __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
599  __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
600  return __lhs._M_base() == __rhs._M_base();
601  }
602 
603  template<typename _Key, typename _Compare, typename _Allocator>
604  inline bool
605  operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
606  const multiset<_Key, _Compare, _Allocator>& __rhs)
607  {
608  __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
609  __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
610  return __lhs._M_base() < __rhs._M_base();
611  }
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 == __rhs); }
618 
619  template<typename _Key, typename _Compare, typename _Allocator>
620  inline bool
621  operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
622  const multiset<_Key, _Compare, _Allocator>& __rhs)
623  { return !(__rhs < __lhs); }
624 
625  template<typename _Key, typename _Compare, typename _Allocator>
626  inline bool
627  operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
628  const multiset<_Key, _Compare, _Allocator>& __rhs)
629  { return !(__lhs < __rhs); }
630 
631  template<typename _Key, typename _Compare, typename _Allocator>
632  inline bool
633  operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
634  const multiset<_Key, _Compare, _Allocator>& __rhs)
635  { return __rhs < __lhs; }
636 
637  template<typename _Key, typename _Compare, typename _Allocator>
638  void
639  swap(multiset<_Key, _Compare, _Allocator>& __x,
640  multiset<_Key, _Compare, _Allocator>& __y)
641  _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
642  { return __x.swap(__y); }
643 
644 } // namespace __profile
645 } // namespace std
646 
647 #endif
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:208
std::__profile::multiset
Class std::multiset wrapper with performance instrumentation.
Definition: profile/multiset.h:42
std::multiset
A standard container made up of elements, which can be retrieved in logarithmic time.
Definition: stl_multiset.h:96
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
std
ISO C++ entities toplevel namespace is std.
base.h
Sequential helper functions. This file is a GNU profile extension to the Standard C++ Library.
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