libstdc++
profile/multiset.h
Go to the documentation of this file.
1 // Profiling multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2009, 2010, 2011 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 <utility>
33 
34 namespace std _GLIBCXX_VISIBILITY(default)
35 {
36 namespace __profile
37 {
38  /// Class std::multiset wrapper with performance instrumentation.
39  template<typename _Key, typename _Compare = std::less<_Key>,
40  typename _Allocator = std::allocator<_Key> >
41  class multiset
42  : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>
43  {
44  typedef _GLIBCXX_STD_C::multiset<_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 multiset(const _Compare& __comp = _Compare(),
68  const _Allocator& __a = _Allocator())
69  : _Base(__comp, __a) { }
70 
71  template<typename _InputIterator>
72  multiset(_InputIterator __first, _InputIterator __last,
73  const _Compare& __comp = _Compare(),
74  const _Allocator& __a = _Allocator())
75  : _Base(__first, __last, __comp, __a) { }
76 
77  multiset(const multiset& __x)
78  : _Base(__x) { }
79 
80  multiset(const _Base& __x)
81  : _Base(__x) { }
82 
83 #ifdef __GXX_EXPERIMENTAL_CXX0X__
84  multiset(multiset&& __x)
85  noexcept(is_nothrow_copy_constructible<_Compare>::value)
86  : _Base(std::move(__x))
87  { }
88 
89  multiset(initializer_list<value_type> __l,
90  const _Compare& __comp = _Compare(),
91  const allocator_type& __a = allocator_type())
92  : _Base(__l, __comp, __a) { }
93 #endif
94 
95  ~multiset() _GLIBCXX_NOEXCEPT { }
96 
97  multiset&
98  operator=(const multiset& __x)
99  {
100  *static_cast<_Base*>(this) = __x;
101  return *this;
102  }
103 
104 #ifdef __GXX_EXPERIMENTAL_CXX0X__
105  multiset&
106  operator=(multiset&& __x)
107  {
108  // NB: DR 1204.
109  // NB: DR 675.
110  this->clear();
111  this->swap(__x);
112  return *this;
113  }
114 
115  multiset&
116  operator=(initializer_list<value_type> __l)
117  {
118  this->clear();
119  this->insert(__l);
120  return *this;
121  }
122 #endif
123 
124  using _Base::get_allocator;
125 
126  // iterators:
127  iterator
128  begin() _GLIBCXX_NOEXCEPT
129  { return iterator(_Base::begin()); }
130 
131  const_iterator
132  begin() const _GLIBCXX_NOEXCEPT
133  { return const_iterator(_Base::begin()); }
134 
135  iterator
136  end() _GLIBCXX_NOEXCEPT
137  { return iterator(_Base::end()); }
138 
139  const_iterator
140  end() const _GLIBCXX_NOEXCEPT
141  { return const_iterator(_Base::end()); }
142 
143  reverse_iterator
144  rbegin() _GLIBCXX_NOEXCEPT
145  { return reverse_iterator(end()); }
146 
147  const_reverse_iterator
148  rbegin() const _GLIBCXX_NOEXCEPT
149  { return const_reverse_iterator(end()); }
150 
151  reverse_iterator
152  rend() _GLIBCXX_NOEXCEPT
153  { return reverse_iterator(begin()); }
154 
155  const_reverse_iterator
156  rend() const _GLIBCXX_NOEXCEPT
157  { return const_reverse_iterator(begin()); }
158 
159 #ifdef __GXX_EXPERIMENTAL_CXX0X__
160  const_iterator
161  cbegin() const noexcept
162  { return const_iterator(_Base::begin()); }
163 
164  const_iterator
165  cend() const noexcept
166  { return const_iterator(_Base::end()); }
167 
168  const_reverse_iterator
169  crbegin() const noexcept
170  { return const_reverse_iterator(end()); }
171 
172  const_reverse_iterator
173  crend() const noexcept
174  { return const_reverse_iterator(begin()); }
175 #endif
176 
177  // capacity:
178  using _Base::empty;
179  using _Base::size;
180  using _Base::max_size;
181 
182  // modifiers:
183  iterator
184  insert(const value_type& __x)
185  { return iterator(_Base::insert(__x)); }
186 
187 #ifdef __GXX_EXPERIMENTAL_CXX0X__
188  iterator
189  insert(value_type&& __x)
190  { return iterator(_Base::insert(std::move(__x))); }
191 #endif
192 
193  iterator
194  insert(const_iterator __position, const value_type& __x)
195  { return iterator(_Base::insert(__position, __x)); }
196 
197 #ifdef __GXX_EXPERIMENTAL_CXX0X__
198  iterator
199  insert(const_iterator __position, value_type&& __x)
200  { return iterator(_Base::insert(__position, std::move(__x))); }
201 #endif
202 
203  template<typename _InputIterator>
204  void
205  insert(_InputIterator __first, _InputIterator __last)
206  { _Base::insert(__first, __last); }
207 
208 #ifdef __GXX_EXPERIMENTAL_CXX0X__
209  void
210  insert(initializer_list<value_type> __l)
211  { _Base::insert(__l); }
212 #endif
213 
214 #ifdef __GXX_EXPERIMENTAL_CXX0X__
215  iterator
216  erase(const_iterator __position)
217  { return iterator(_Base::erase(__position)); }
218 #else
219  void
220  erase(iterator __position)
221  { _Base::erase(__position); }
222 #endif
223 
224  size_type
225  erase(const key_type& __x)
226  {
227  std::pair<iterator, iterator> __victims = this->equal_range(__x);
228  size_type __count = 0;
229  while (__victims.first != __victims.second)
230  {
231  iterator __victim = __victims.first++;
232  _Base::erase(__victim);
233  ++__count;
234  }
235  return __count;
236  }
237 
238 #ifdef __GXX_EXPERIMENTAL_CXX0X__
239  iterator
240  erase(const_iterator __first, const_iterator __last)
241  { return iterator(_Base::erase(__first, __last)); }
242 #else
243  void
244  erase(iterator __first, iterator __last)
245  { _Base::erase(__first, __last); }
246 #endif
247 
248  void
249  swap(multiset& __x)
250  { _Base::swap(__x); }
251 
252  void
253  clear() _GLIBCXX_NOEXCEPT
254  { this->erase(begin(), end()); }
255 
256  // observers:
257  using _Base::key_comp;
258  using _Base::value_comp;
259 
260  // multiset operations:
261  iterator
262  find(const key_type& __x)
263  { return iterator(_Base::find(__x)); }
264 
265  // _GLIBCXX_RESOLVE_LIB_DEFECTS
266  // 214. set::find() missing const overload
267  const_iterator
268  find(const key_type& __x) const
269  { return const_iterator(_Base::find(__x)); }
270 
271  using _Base::count;
272 
273  iterator
274  lower_bound(const key_type& __x)
275  { return iterator(_Base::lower_bound(__x)); }
276 
277  // _GLIBCXX_RESOLVE_LIB_DEFECTS
278  // 214. set::find() missing const overload
279  const_iterator
280  lower_bound(const key_type& __x) const
281  { return const_iterator(_Base::lower_bound(__x)); }
282 
283  iterator
284  upper_bound(const key_type& __x)
285  { return iterator(_Base::upper_bound(__x)); }
286 
287  // _GLIBCXX_RESOLVE_LIB_DEFECTS
288  // 214. set::find() missing const overload
289  const_iterator
290  upper_bound(const key_type& __x) const
291  { return const_iterator(_Base::upper_bound(__x)); }
292 
293  std::pair<iterator,iterator>
294  equal_range(const key_type& __x)
295  {
296  typedef typename _Base::iterator _Base_iterator;
297  std::pair<_Base_iterator, _Base_iterator> __res =
298  _Base::equal_range(__x);
299  return std::make_pair(iterator(__res.first),
300  iterator(__res.second));
301  }
302 
303  // _GLIBCXX_RESOLVE_LIB_DEFECTS
304  // 214. set::find() missing const overload
305  std::pair<const_iterator,const_iterator>
306  equal_range(const key_type& __x) const
307  {
308  typedef typename _Base::const_iterator _Base_iterator;
309  std::pair<_Base_iterator, _Base_iterator> __res =
310  _Base::equal_range(__x);
311  return std::make_pair(const_iterator(__res.first),
312  const_iterator(__res.second));
313  }
314 
315  _Base&
316  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
317 
318  const _Base&
319  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
320 
321  };
322 
323  template<typename _Key, typename _Compare, typename _Allocator>
324  inline bool
325  operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
326  const multiset<_Key, _Compare, _Allocator>& __rhs)
327  { return __lhs._M_base() == __rhs._M_base(); }
328 
329  template<typename _Key, typename _Compare, typename _Allocator>
330  inline bool
331  operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
332  const multiset<_Key, _Compare, _Allocator>& __rhs)
333  { return __lhs._M_base() != __rhs._M_base(); }
334 
335  template<typename _Key, typename _Compare, typename _Allocator>
336  inline bool
337  operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
338  const multiset<_Key, _Compare, _Allocator>& __rhs)
339  { return __lhs._M_base() < __rhs._M_base(); }
340 
341  template<typename _Key, typename _Compare, typename _Allocator>
342  inline bool
343  operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
344  const multiset<_Key, _Compare, _Allocator>& __rhs)
345  { return __lhs._M_base() <= __rhs._M_base(); }
346 
347  template<typename _Key, typename _Compare, typename _Allocator>
348  inline bool
349  operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
350  const multiset<_Key, _Compare, _Allocator>& __rhs)
351  { return __lhs._M_base() >= __rhs._M_base(); }
352 
353  template<typename _Key, typename _Compare, typename _Allocator>
354  inline bool
355  operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
356  const multiset<_Key, _Compare, _Allocator>& __rhs)
357  { return __lhs._M_base() > __rhs._M_base(); }
358 
359  template<typename _Key, typename _Compare, typename _Allocator>
360  void
361  swap(multiset<_Key, _Compare, _Allocator>& __x,
362  multiset<_Key, _Compare, _Allocator>& __y)
363  { return __x.swap(__y); }
364 
365 } // namespace __profile
366 } // namespace std
367 
368 #endif
std::initializer_list
initializer_list
Definition: initializer_list:47
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:93
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:94
std::__profile::multiset
Class std::multiset wrapper with performance instrumentation.
Definition: profile/multiset.h:41
std::count
size_t count() const _GLIBCXX_NOEXCEPT
Returns the number of bits which are set.
Definition: bitset:1279
std::multiset
A standard container made up of elements, which can be retrieved in logarithmic time.
Definition: stl_multiset.h:88
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:88
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:268
std::is_nothrow_copy_constructible
is_nothrow_copy_constructible
Definition: type_traits:1021
std::size
constexpr size_t size() const _GLIBCXX_NOEXCEPT
Returns the total number of bits.
Definition: bitset:1284