libstdc++
profile/multiset.h
Go to the documentation of this file.
1 // Profiling multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-2015 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 #if __cplusplus >= 201103L
230  noexcept( noexcept(declval<_Base>().swap(__x)) )
231 #endif
232  {
233  _Base::swap(__x);
234  this->_M_swap(__x);
235  }
236 
237  // modifiers:
238 #if __cplusplus >= 201103L
239  template<typename... _Args>
240  iterator
241  emplace(_Args&&... __args)
242  {
243  // The cost is the same whether or not the element is inserted so we
244  // always report insertion of 1 element.
245  __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
246  return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
247  }
248 
249  template<typename... _Args>
250  iterator
251  emplace_hint(const_iterator __pos, _Args&&... __args)
252  {
253  auto size_before = this->size();
254  auto __res
255  = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
256  __profcxx_map2umap_insert(this->_M_map2umap_info,
257  size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
258  return iterator(__res, this);
259  }
260 #endif
261 
262  iterator
263  insert(const value_type& __x)
264  {
265  __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
266  return iterator(_Base::insert(__x), this);
267  }
268 
269 #if __cplusplus >= 201103L
270  iterator
271  insert(value_type&& __x)
272  {
273  __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
274  return iterator(_Base::insert(std::move(__x)), this);
275  }
276 #endif
277 
278  iterator
279  insert(const_iterator __pos, const value_type& __x)
280  {
281  size_type size_before = this->size();
282  _Base_iterator __res = _Base::insert(__pos.base(), __x);
283 
284  __profcxx_map2umap_insert(this->_M_map2umap_info,
285  size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
286  return iterator(__res, this);
287  }
288 
289 #if __cplusplus >= 201103L
290  iterator
291  insert(const_iterator __pos, value_type&& __x)
292  {
293  auto size_before = this->size();
294  auto __res = _Base::insert(__pos.base(), std::move(__x));
295  __profcxx_map2umap_insert(this->_M_map2umap_info,
296  size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
297  return iterator(__res, this);
298  }
299 #endif
300 
301 #if __cplusplus >= 201103L
302  template<typename _InputIterator,
303  typename = std::_RequireInputIter<_InputIterator>>
304 #else
305  template<typename _InputIterator>
306 #endif
307  void
308  insert(_InputIterator __first, _InputIterator __last)
309  {
310  for (; __first != __last; ++__first)
311  insert(*__first);
312  }
313 
314 #if __cplusplus >= 201103L
315  void
316  insert(initializer_list<value_type> __l)
317  { insert(__l.begin(), __l.end()); }
318 #endif
319 
320 #if __cplusplus >= 201103L
321  iterator
322  erase(const_iterator __pos)
323  {
324  __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
325  return iterator(_Base::erase(__pos.base()), this);
326  }
327 #else
328  void
329  erase(iterator __pos)
330  {
331  __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
332  _Base::erase(__pos.base());
333  }
334 #endif
335 
336  size_type
337  erase(const key_type& __x)
338  {
339  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
340  __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
341  return _Base::erase(__x);
342  }
343 
344 #if __cplusplus >= 201103L
345  iterator
346  erase(const_iterator __first, const_iterator __last)
347  {
348  if (__first != __last)
349  {
350  iterator __ret;
351  for (; __first != __last;)
352  __ret = erase(__first++);
353  return __ret;
354  }
355  else
356  return iterator(_Base::erase(__first.base(), __last.base()), this);
357  }
358 #else
359  void
360  erase(iterator __first, iterator __last)
361  {
362  for (; __first != __last;)
363  erase(__first++);
364  }
365 #endif
366 
367  void
368  clear() _GLIBCXX_NOEXCEPT
369  {
370  this->_M_profile_destruct();
371  _Base::clear();
372  this->_M_profile_construct();
373  }
374 
375  size_type
376  count(const key_type& __x) const
377  {
378  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
379  return _Base::count(__x);
380  }
381 
382  // multiset operations:
383  iterator
384  find(const key_type& __x)
385  {
386  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
387  return iterator(_Base::find(__x), this);
388  }
389 
390  // _GLIBCXX_RESOLVE_LIB_DEFECTS
391  // 214. set::find() missing const overload
392  const_iterator
393  find(const key_type& __x) const
394  {
395  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
396  return const_iterator(_Base::find(__x), this);
397  }
398 
399  iterator
400  lower_bound(const key_type& __x)
401  {
402  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
403  return iterator(_Base::lower_bound(__x), this);
404  }
405 
406  // _GLIBCXX_RESOLVE_LIB_DEFECTS
407  // 214. set::find() missing const overload
408  const_iterator
409  lower_bound(const key_type& __x) const
410  {
411  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
412  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
413  return const_iterator(_Base::lower_bound(__x), this);
414  }
415 
416  iterator
417  upper_bound(const key_type& __x)
418  {
419  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
420  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
421  return iterator(_Base::upper_bound(__x), this);
422  }
423 
424  // _GLIBCXX_RESOLVE_LIB_DEFECTS
425  // 214. set::find() missing const overload
426  const_iterator
427  upper_bound(const key_type& __x) const
428  {
429  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
430  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
431  return const_iterator(_Base::upper_bound(__x), this);
432  }
433 
434  std::pair<iterator,iterator>
435  equal_range(const key_type& __x)
436  {
437  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
438  std::pair<_Base_iterator, _Base_iterator> __base_ret
439  = _Base::equal_range(__x);
440  return std::make_pair(iterator(__base_ret.first, this),
441  iterator(__base_ret.second, this));
442  }
443 
444  // _GLIBCXX_RESOLVE_LIB_DEFECTS
445  // 214. set::find() missing const overload
446  std::pair<const_iterator,const_iterator>
447  equal_range(const key_type& __x) const
448  {
449  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
450  std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
451  = _Base::equal_range(__x);
452  return std::make_pair(const_iterator(__base_ret.first, this),
453  const_iterator(__base_ret.second, this));
454  }
455 
456  _Base&
457  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
458 
459  const _Base&
460  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
461 
462  private:
463  /** If hint is used we consider that the map and unordered_map
464  * operations have equivalent insertion cost so we do not update metrics
465  * about it.
466  * Note that to find out if hint has been used is libstdc++
467  * implementation dependent.
468  */
469  bool
470  _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
471  {
472  return (__hint == __res
473  || (__hint == _M_base().end() && ++__res == _M_base().end())
474  || (__hint != _M_base().end() && (++__hint == __res
475  || ++__res == --__hint)));
476  }
477 
478  template<typename _K1, typename _C1, typename _A1>
479  friend bool
480  operator==(const multiset<_K1, _C1, _A1>&,
481  const multiset<_K1, _C1, _A1>&);
482 
483  template<typename _K1, typename _C1, typename _A1>
484  friend bool
485  operator< (const multiset<_K1, _C1, _A1>&,
486  const multiset<_K1, _C1, _A1>&);
487  };
488 
489  template<typename _Key, typename _Compare, typename _Allocator>
490  inline bool
491  operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
492  const multiset<_Key, _Compare, _Allocator>& __rhs)
493  {
494  __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
495  __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
496  return __lhs._M_base() == __rhs._M_base();
497  }
498 
499  template<typename _Key, typename _Compare, typename _Allocator>
500  inline bool
501  operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
502  const multiset<_Key, _Compare, _Allocator>& __rhs)
503  {
504  __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
505  __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
506  return __lhs._M_base() < __rhs._M_base();
507  }
508 
509  template<typename _Key, typename _Compare, typename _Allocator>
510  inline bool
511  operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
512  const multiset<_Key, _Compare, _Allocator>& __rhs)
513  { return !(__lhs == __rhs); }
514 
515  template<typename _Key, typename _Compare, typename _Allocator>
516  inline bool
517  operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
518  const multiset<_Key, _Compare, _Allocator>& __rhs)
519  { return !(__rhs < __lhs); }
520 
521  template<typename _Key, typename _Compare, typename _Allocator>
522  inline bool
523  operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
524  const multiset<_Key, _Compare, _Allocator>& __rhs)
525  { return !(__lhs < __rhs); }
526 
527  template<typename _Key, typename _Compare, typename _Allocator>
528  inline bool
529  operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
530  const multiset<_Key, _Compare, _Allocator>& __rhs)
531  { return __rhs < __lhs; }
532 
533  template<typename _Key, typename _Compare, typename _Allocator>
534  void
535  swap(multiset<_Key, _Compare, _Allocator>& __x,
536  multiset<_Key, _Compare, _Allocator>& __y)
537  { return __x.swap(__y); }
538 
539 } // namespace __profile
540 } // namespace std
541 
542 #endif
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:276
std::initializer_list
initializer_list
Definition: initializer_list:47
std::__profile::multiset
Class std::multiset wrapper with performance instrumentation.
Definition: profile/multiset.h:42
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:102
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:101
base.h
Sequential helper functions. This file is a GNU profile extension to the Standard C++ Library...
std
ISO C++ entities toplevel namespace is std.