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