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