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
34namespace std _GLIBCXX_VISIBILITY(default)
35{
36namespace __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
408