libstdc++
profile/set.h
Go to the documentation of this file.
1 // Profiling set implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-2013 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 <utility>
33 
34 namespace std _GLIBCXX_VISIBILITY(default)
35 {
36 namespace __profile
37 {
38  /// Class std::set wrapper with performance instrumentation.
39  template<typename _Key, typename _Compare = std::less<_Key>,
40  typename _Allocator = std::allocator<_Key> >
41  class set
42  : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>
43  {
44  typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
45 
46  public:
47  // types:
48  typedef _Key key_type;
49  typedef _Key value_type;
50  typedef _Compare key_compare;
51  typedef _Compare value_compare;
52  typedef _Allocator allocator_type;
53  typedef typename _Base::reference reference;
54  typedef typename _Base::const_reference const_reference;
55 
56  typedef typename _Base::iterator iterator;
57  typedef typename _Base::const_iterator const_iterator;
58  typedef typename _Base::reverse_iterator reverse_iterator;
59  typedef typename _Base::const_reverse_iterator const_reverse_iterator;
60 
61  typedef typename _Base::size_type size_type;
62  typedef typename _Base::difference_type difference_type;
63  typedef typename _Base::pointer pointer;
64  typedef typename _Base::const_pointer const_pointer;
65 
66  // 23.3.3.1 construct/copy/destroy:
67  explicit set(const _Compare& __comp = _Compare(),
68  const _Allocator& __a = _Allocator())
69  : _Base(__comp, __a) { }
70 
71 #if __cplusplus >= 201103L
72  template<typename _InputIterator,
73  typename = std::_RequireInputIter<_InputIterator>>
74 #else
75  template<typename _InputIterator>
76 #endif
77  set(_InputIterator __first, _InputIterator __last,
78  const _Compare& __comp = _Compare(),
79  const _Allocator& __a = _Allocator())
80  : _Base(__first, __last, __comp, __a) { }
81 
82  set(const set& __x)
83  : _Base(__x) { }
84 
85  set(const _Base& __x)
86  : _Base(__x) { }
87 
88 #if __cplusplus >= 201103L
89  set(set&& __x)
90  noexcept(is_nothrow_copy_constructible<_Compare>::value)
91  : _Base(std::move(__x))
92  { }
93 
94  set(initializer_list<value_type> __l,
95  const _Compare& __comp = _Compare(),
96  const allocator_type& __a = allocator_type())
97  : _Base(__l, __comp, __a) { }
98 #endif
99 
100  ~set() _GLIBCXX_NOEXCEPT { }
101 
102  set&
103  operator=(const set& __x)
104  {
105  *static_cast<_Base*>(this) = __x;
106  return *this;
107  }
108 
109 #if __cplusplus >= 201103L
110  set&
111  operator=(set&& __x)
112  {
113  // NB: DR 1204.
114  // NB: DR 675.
115  this->clear();
116  this->swap(__x);
117  return *this;
118  }
119 
120  set&
121  operator=(initializer_list<value_type> __l)
122  {
123  this->clear();
124  this->insert(__l);
125  return *this;
126  }
127 #endif
128 
129  using _Base::get_allocator;
130 
131  // iterators:
132  iterator
133  begin() _GLIBCXX_NOEXCEPT
134  { return iterator(_Base::begin()); }
135 
136  const_iterator
137  begin() const _GLIBCXX_NOEXCEPT
138  { return const_iterator(_Base::begin()); }
139 
140  iterator
141  end() _GLIBCXX_NOEXCEPT
142  { return iterator(_Base::end()); }
143 
144  const_iterator
145  end() const _GLIBCXX_NOEXCEPT
146  { return const_iterator(_Base::end()); }
147 
148  reverse_iterator
149  rbegin() _GLIBCXX_NOEXCEPT
150  { return reverse_iterator(end()); }
151 
152  const_reverse_iterator
153  rbegin() const _GLIBCXX_NOEXCEPT
154  { return const_reverse_iterator(end()); }
155 
156  reverse_iterator
157  rend() _GLIBCXX_NOEXCEPT
158  { return reverse_iterator(begin()); }
159 
160  const_reverse_iterator
161  rend() const _GLIBCXX_NOEXCEPT
162  { return const_reverse_iterator(begin()); }
163 
164 #if __cplusplus >= 201103L
165  const_iterator
166  cbegin() const noexcept
167  { return const_iterator(_Base::begin()); }
168 
169  const_iterator
170  cend() const noexcept
171  { return const_iterator(_Base::end()); }
172 
173  const_reverse_iterator
174  crbegin() const noexcept
175  { return const_reverse_iterator(end()); }
176 
177  const_reverse_iterator
178  crend() const noexcept
179  { return const_reverse_iterator(begin()); }
180 #endif
181 
182  // capacity:
183  using _Base::empty;
184  using _Base::size;
185  using _Base::max_size;
186 
187  // modifiers:
188 #if __cplusplus >= 201103L
189  template<typename... _Args>
190  std::pair<iterator, bool>
191  emplace(_Args&&... __args)
192  {
193  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
194  return std::pair<iterator, bool>(iterator(__res.first),
195  __res.second);
196  }
197 
198  template<typename... _Args>
199  iterator
200  emplace_hint(const_iterator __pos, _Args&&... __args)
201  {
202  return iterator(_Base::emplace_hint(__pos,
203  std::forward<_Args>(__args)...));
204  }
205 #endif
206 
207  std::pair<iterator, bool>
208  insert(const value_type& __x)
209  {
210  typedef typename _Base::iterator _Base_iterator;
211  std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
212  return std::pair<iterator, bool>(iterator(__res.first),
213  __res.second);
214  }
215 
216 #if __cplusplus >= 201103L
217  std::pair<iterator, bool>
218  insert(value_type&& __x)
219  {
220  typedef typename _Base::iterator _Base_iterator;
221  std::pair<_Base_iterator, bool> __res
222  = _Base::insert(std::move(__x));
223  return std::pair<iterator, bool>(iterator(__res.first),
224  __res.second);
225  }
226 #endif
227 
228  iterator
229  insert(const_iterator __position, const value_type& __x)
230  { return iterator(_Base::insert(__position, __x)); }
231 
232 #if __cplusplus >= 201103L
233  iterator
234  insert(const_iterator __position, value_type&& __x)
235  { return iterator(_Base::insert(__position, std::move(__x))); }
236 #endif
237 
238 #if __cplusplus >= 201103L
239  template<typename _InputIterator,
240  typename = std::_RequireInputIter<_InputIterator>>
241 #else
242  template<typename _InputIterator>
243 #endif
244  void
245  insert(_InputIterator __first, _InputIterator __last)
246  { _Base::insert(__first, __last); }
247 
248 #if __cplusplus >= 201103L
249  void
250  insert(initializer_list<value_type> __l)
251  { _Base::insert(__l); }
252 #endif
253 
254 #if __cplusplus >= 201103L
255  iterator
256  erase(const_iterator __position)
257  { return iterator(_Base::erase(__position)); }
258 #else
259  void
260  erase(iterator __position)
261  { _Base::erase(__position); }
262 #endif
263 
264  size_type
265  erase(const key_type& __x)
266  {
267  iterator __victim = find(__x);
268  if (__victim == end())
269  return 0;
270  else
271  {
272  _Base::erase(__victim);
273  return 1;
274  }
275  }
276 
277 #if __cplusplus >= 201103L
278  iterator
279  erase(const_iterator __first, const_iterator __last)
280  { return iterator(_Base::erase(__first, __last)); }
281 #else
282  void
283  erase(iterator __first, iterator __last)
284  { _Base::erase(__first, __last); }
285 #endif
286 
287  void
288  swap(set& __x)
289  { _Base::swap(__x); }
290 
291  void
292  clear() _GLIBCXX_NOEXCEPT
293  { this->erase(begin(), end()); }
294 
295  // observers:
296  using _Base::key_comp;
297  using _Base::value_comp;
298 
299  // set operations:
300  iterator
301  find(const key_type& __x)
302  { return iterator(_Base::find(__x)); }
303 
304  // _GLIBCXX_RESOLVE_LIB_DEFECTS
305  // 214. set::find() missing const overload
306  const_iterator
307  find(const key_type& __x) const
308  { return const_iterator(_Base::find(__x)); }
309 
310  using _Base::count;
311 
312  iterator
313  lower_bound(const key_type& __x)
314  { return iterator(_Base::lower_bound(__x)); }
315 
316  // _GLIBCXX_RESOLVE_LIB_DEFECTS
317  // 214. set::find() missing const overload
318  const_iterator
319  lower_bound(const key_type& __x) const
320  { return const_iterator(_Base::lower_bound(__x)); }
321 
322  iterator
323  upper_bound(const key_type& __x)
324  { return iterator(_Base::upper_bound(__x)); }
325 
326  // _GLIBCXX_RESOLVE_LIB_DEFECTS
327  // 214. set::find() missing const overload
328  const_iterator
329  upper_bound(const key_type& __x) const
330  { return const_iterator(_Base::upper_bound(__x)); }
331 
332  std::pair<iterator,iterator>
333  equal_range(const key_type& __x)
334  {
335  typedef typename _Base::iterator _Base_iterator;
336  std::pair<_Base_iterator, _Base_iterator> __res =
337  _Base::equal_range(__x);
338  return std::make_pair(iterator(__res.first),
339  iterator(__res.second));
340  }
341 
342  // _GLIBCXX_RESOLVE_LIB_DEFECTS
343  // 214. set::find() missing const overload
344  std::pair<const_iterator,const_iterator>
345  equal_range(const key_type& __x) const
346  {
347  typedef typename _Base::const_iterator _Base_iterator;
348  std::pair<_Base_iterator, _Base_iterator> __res =
349  _Base::equal_range(__x);
350  return std::make_pair(const_iterator(__res.first),
351  const_iterator(__res.second));
352  }
353 
354  _Base&
355  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
356 
357  const _Base&
358  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
359 
360  };
361 
362  template<typename _Key, typename _Compare, typename _Allocator>
363  inline bool
364  operator==(const set<_Key, _Compare, _Allocator>& __lhs,
365  const set<_Key, _Compare, _Allocator>& __rhs)
366  { return __lhs._M_base() == __rhs._M_base(); }
367 
368  template<typename _Key, typename _Compare, typename _Allocator>
369  inline bool
370  operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
371  const set<_Key, _Compare, _Allocator>& __rhs)
372  { return __lhs._M_base() != __rhs._M_base(); }
373 
374  template<typename _Key, typename _Compare, typename _Allocator>
375  inline bool
376  operator<(const set<_Key, _Compare, _Allocator>& __lhs,
377  const set<_Key, _Compare, _Allocator>& __rhs)
378  { return __lhs._M_base() < __rhs._M_base(); }
379 
380  template<typename _Key, typename _Compare, typename _Allocator>
381  inline bool
382  operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
383  const set<_Key, _Compare, _Allocator>& __rhs)
384  { return __lhs._M_base() <= __rhs._M_base(); }
385 
386  template<typename _Key, typename _Compare, typename _Allocator>
387  inline bool
388  operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
389  const set<_Key, _Compare, _Allocator>& __rhs)
390  { return __lhs._M_base() >= __rhs._M_base(); }
391 
392  template<typename _Key, typename _Compare, typename _Allocator>
393  inline bool
394  operator>(const set<_Key, _Compare, _Allocator>& __lhs,
395  const set<_Key, _Compare, _Allocator>& __rhs)
396  { return __lhs._M_base() > __rhs._M_base(); }
397 
398  template<typename _Key, typename _Compare, typename _Allocator>
399  void
400  swap(set<_Key, _Compare, _Allocator>& __x,
401  set<_Key, _Compare, _Allocator>& __y)
402  { return __x.swap(__y); }
403 
404 } // namespace __profile
405 } // namespace std
406 
407 #endif
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
std::operator>=
bool operator>=(const basic_string< _CharT, _Traits, _Alloc > &__lhs, const basic_string< _CharT, _Traits, _Alloc > &__rhs)
Test if string doesn't precede string.
Definition: basic_string.h:2680
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
ISO C++ entities toplevel namespace is std.
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:101
std::swap
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
Definition: move.h:166
std::set
A standard container made up of unique keys, which can be retrieved in logarithmic time...
Definition: stl_set.h:90
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
std::__profile::set
Class std::set wrapper with performance instrumentation.
Definition: profile/set.h:41
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:102
std::operator>
bool operator>(const basic_string< _CharT, _Traits, _Alloc > &__lhs, const basic_string< _CharT, _Traits, _Alloc > &__rhs)
Test if string follows string.
Definition: basic_string.h:2606