1 // Profiling set implementation -*- C++ -*-
3 // Copyright (C) 2009-2014 Free Software Foundation, Inc.
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)
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.
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.
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/>.
25 /** @file profile/set.h
26 * This file is a GNU profile extension to the Standard C++ Library.
29 #ifndef _GLIBCXX_PROFILE_SET_H
30 #define _GLIBCXX_PROFILE_SET_H 1
34 namespace std _GLIBCXX_VISIBILITY(default)
38 /// Class std::set wrapper with performance instrumentation.
39 template<typename _Key, typename _Compare = std::less<_Key>,
40 typename _Allocator = std::allocator<_Key> >
42 : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>
44 typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
46 #if __cplusplus >= 201103L
47 typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits;
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;
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;
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;
70 // 23.3.3.1 construct/copy/destroy:
75 explicit set(const _Compare& __comp,
76 const _Allocator& __a = _Allocator())
77 : _Base(__comp, __a) { }
79 #if __cplusplus >= 201103L
80 template<typename _InputIterator,
81 typename = std::_RequireInputIter<_InputIterator>>
83 template<typename _InputIterator>
85 set(_InputIterator __first, _InputIterator __last,
86 const _Compare& __comp = _Compare(),
87 const _Allocator& __a = _Allocator())
88 : _Base(__first, __last, __comp, __a) { }
90 #if __cplusplus < 201103L
94 set(const set&) = default;
97 set(initializer_list<value_type> __l,
98 const _Compare& __comp = _Compare(),
99 const allocator_type& __a = allocator_type())
100 : _Base(__l, __comp, __a) { }
103 set(const allocator_type& __a)
106 set(const set& __x, const allocator_type& __a)
107 : _Base(__x, __a) { }
109 set(set&& __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) { }
114 set(initializer_list<value_type> __l, const allocator_type& __a)
115 : _Base(__l, __a) { }
117 template<typename _InputIterator>
118 set(_InputIterator __first, _InputIterator __last,
119 const allocator_type& __a)
120 : _Base(__first, __last, __a) { }
123 set(const _Base& __x)
126 ~set() _GLIBCXX_NOEXCEPT { }
128 #if __cplusplus < 201103L
130 operator=(const set& __x)
137 operator=(const set&) = default;
140 operator=(set&&) = default;
143 operator=(initializer_list<value_type> __l)
150 using _Base::get_allocator;
154 begin() _GLIBCXX_NOEXCEPT
155 { return iterator(_Base::begin()); }
158 begin() const _GLIBCXX_NOEXCEPT
159 { return const_iterator(_Base::begin()); }
162 end() _GLIBCXX_NOEXCEPT
163 { return iterator(_Base::end()); }
166 end() const _GLIBCXX_NOEXCEPT
167 { return const_iterator(_Base::end()); }
170 rbegin() _GLIBCXX_NOEXCEPT
171 { return reverse_iterator(end()); }
173 const_reverse_iterator
174 rbegin() const _GLIBCXX_NOEXCEPT
175 { return const_reverse_iterator(end()); }
178 rend() _GLIBCXX_NOEXCEPT
179 { return reverse_iterator(begin()); }
181 const_reverse_iterator
182 rend() const _GLIBCXX_NOEXCEPT
183 { return const_reverse_iterator(begin()); }
185 #if __cplusplus >= 201103L
187 cbegin() const noexcept
188 { return const_iterator(_Base::begin()); }
191 cend() const noexcept
192 { return const_iterator(_Base::end()); }
194 const_reverse_iterator
195 crbegin() const noexcept
196 { return const_reverse_iterator(end()); }
198 const_reverse_iterator
199 crend() const noexcept
200 { return const_reverse_iterator(begin()); }
206 using _Base::max_size;
209 #if __cplusplus >= 201103L
210 template<typename... _Args>
211 std::pair<iterator, bool>
212 emplace(_Args&&... __args)
214 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
215 return std::pair<iterator, bool>(iterator(__res.first),
219 template<typename... _Args>
221 emplace_hint(const_iterator __pos, _Args&&... __args)
223 return iterator(_Base::emplace_hint(__pos,
224 std::forward<_Args>(__args)...));
228 std::pair<iterator, bool>
229 insert(const value_type& __x)
231 typedef typename _Base::iterator _Base_iterator;
232 std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
233 return std::pair<iterator, bool>(iterator(__res.first),
237 #if __cplusplus >= 201103L
238 std::pair<iterator, bool>
239 insert(value_type&& __x)
241 typedef typename _Base::iterator _Base_iterator;
242 std::pair<_Base_iterator, bool> __res
243 = _Base::insert(std::move(__x));
244 return std::pair<iterator, bool>(iterator(__res.first),
250 insert(const_iterator __position, const value_type& __x)
251 { return iterator(_Base::insert(__position, __x)); }
253 #if __cplusplus >= 201103L
255 insert(const_iterator __position, value_type&& __x)
256 { return iterator(_Base::insert(__position, std::move(__x))); }
259 #if __cplusplus >= 201103L
260 template<typename _InputIterator,
261 typename = std::_RequireInputIter<_InputIterator>>
263 template<typename _InputIterator>
266 insert(_InputIterator __first, _InputIterator __last)
267 { _Base::insert(__first, __last); }
269 #if __cplusplus >= 201103L
271 insert(initializer_list<value_type> __l)
272 { _Base::insert(__l); }
275 #if __cplusplus >= 201103L
277 erase(const_iterator __position)
278 { return iterator(_Base::erase(__position)); }
281 erase(iterator __position)
282 { _Base::erase(__position); }
286 erase(const key_type& __x)
288 iterator __victim = find(__x);
289 if (__victim == end())
293 _Base::erase(__victim);
298 #if __cplusplus >= 201103L
300 erase(const_iterator __first, const_iterator __last)
301 { return iterator(_Base::erase(__first, __last)); }
304 erase(iterator __first, iterator __last)
305 { _Base::erase(__first, __last); }
310 #if __cplusplus >= 201103L
311 noexcept(_Alloc_traits::_S_nothrow_swap())
313 { _Base::swap(__x); }
316 clear() _GLIBCXX_NOEXCEPT
317 { this->erase(begin(), end()); }
320 using _Base::key_comp;
321 using _Base::value_comp;
325 find(const key_type& __x)
326 { return iterator(_Base::find(__x)); }
328 // _GLIBCXX_RESOLVE_LIB_DEFECTS
329 // 214. set::find() missing const overload
331 find(const key_type& __x) const
332 { return const_iterator(_Base::find(__x)); }
337 lower_bound(const key_type& __x)
338 { return iterator(_Base::lower_bound(__x)); }
340 // _GLIBCXX_RESOLVE_LIB_DEFECTS
341 // 214. set::find() missing const overload
343 lower_bound(const key_type& __x) const
344 { return const_iterator(_Base::lower_bound(__x)); }
347 upper_bound(const key_type& __x)
348 { return iterator(_Base::upper_bound(__x)); }
350 // _GLIBCXX_RESOLVE_LIB_DEFECTS
351 // 214. set::find() missing const overload
353 upper_bound(const key_type& __x) const
354 { return const_iterator(_Base::upper_bound(__x)); }
356 std::pair<iterator,iterator>
357 equal_range(const key_type& __x)
359 typedef typename _Base::iterator _Base_iterator;
360 std::pair<_Base_iterator, _Base_iterator> __res =
361 _Base::equal_range(__x);
362 return std::make_pair(iterator(__res.first),
363 iterator(__res.second));
366 // _GLIBCXX_RESOLVE_LIB_DEFECTS
367 // 214. set::find() missing const overload
368 std::pair<const_iterator,const_iterator>
369 equal_range(const key_type& __x) const
371 typedef typename _Base::const_iterator _Base_iterator;
372 std::pair<_Base_iterator, _Base_iterator> __res =
373 _Base::equal_range(__x);
374 return std::make_pair(const_iterator(__res.first),
375 const_iterator(__res.second));
379 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
382 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
386 template<typename _Key, typename _Compare, typename _Allocator>
388 operator==(const set<_Key, _Compare, _Allocator>& __lhs,
389 const set<_Key, _Compare, _Allocator>& __rhs)
390 { return __lhs._M_base() == __rhs._M_base(); }
392 template<typename _Key, typename _Compare, typename _Allocator>
394 operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
395 const set<_Key, _Compare, _Allocator>& __rhs)
396 { return __lhs._M_base() != __rhs._M_base(); }
398 template<typename _Key, typename _Compare, typename _Allocator>
400 operator<(const set<_Key, _Compare, _Allocator>& __lhs,
401 const set<_Key, _Compare, _Allocator>& __rhs)
402 { return __lhs._M_base() < __rhs._M_base(); }
404 template<typename _Key, typename _Compare, typename _Allocator>
406 operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
407 const set<_Key, _Compare, _Allocator>& __rhs)
408 { return __lhs._M_base() <= __rhs._M_base(); }
410 template<typename _Key, typename _Compare, typename _Allocator>
412 operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
413 const set<_Key, _Compare, _Allocator>& __rhs)
414 { return __lhs._M_base() >= __rhs._M_base(); }
416 template<typename _Key, typename _Compare, typename _Allocator>
418 operator>(const set<_Key, _Compare, _Allocator>& __lhs,
419 const set<_Key, _Compare, _Allocator>& __rhs)
420 { return __lhs._M_base() > __rhs._M_base(); }
422 template<typename _Key, typename _Compare, typename _Allocator>
424 swap(set<_Key, _Compare, _Allocator>& __x,
425 set<_Key, _Compare, _Allocator>& __y)
426 { return __x.swap(__y); }
428 } // namespace __profile