libstdc++
profile/unordered_set
Go to the documentation of this file.
1// Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
2
3// Copyright (C) 2009-2019 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 along
21// with this library; see the file COPYING3. If not see
22// <http://www.gnu.org/licenses/>.
23
24/** @file profile/unordered_set
25 * This file is a GNU profile extension to the Standard C++ Library.
26 */
27
28#ifndef _GLIBCXX_PROFILE_UNORDERED_SET
29#define _GLIBCXX_PROFILE_UNORDERED_SET 1
30
31#if __cplusplus < 201103L
32# include <bits/c++0x_warning.h>
33#else
34# include <unordered_set>
35
36#include <profile/base.h>
37#include <profile/unordered_base.h>
38
39#define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>
40#define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
41
42namespace std _GLIBCXX_VISIBILITY(default)
43{
44namespace __profile
45{
46 /** @brief Unordered_set wrapper with performance instrumentation. */
47 template<typename _Key,
48 typename _Hash = std::hash<_Key>,
49 typename _Pred = std::equal_to<_Key>,
50 typename _Alloc = std::allocator<_Key> >
51 class unordered_set
52 : public _GLIBCXX_STD_BASE,
53 public _Unordered_profile<unordered_set<_Key, _Hash, _Pred, _Alloc>,
54 true>
55 {
56 typedef _GLIBCXX_STD_BASE _Base;
57
58 _Base&
59 _M_base() noexcept { return *this; }
60
61 const _Base&
62 _M_base() const noexcept { return *this; }
63
64 public:
65 typedef typename _Base::size_type size_type;
66 typedef typename _Base::hasher hasher;
67 typedef typename _Base::key_equal key_equal;
68 typedef typename _Base::allocator_type allocator_type;
69 typedef typename _Base::key_type key_type;
70 typedef typename _Base::value_type value_type;
71 typedef typename _Base::difference_type difference_type;
72 typedef typename _Base::reference reference;
73 typedef typename _Base::const_reference const_reference;
74
75 typedef typename _Base::iterator iterator;
76 typedef typename _Base::const_iterator const_iterator;
77
78 unordered_set() = default;
79
80 explicit
81 unordered_set(size_type __n,
82 const hasher& __hf = hasher(),
83 const key_equal& __eql = key_equal(),
84 const allocator_type& __a = allocator_type())
85 : _Base(__n, __hf, __eql, __a)
86 { }
87
88 template<typename _InputIterator>
89 unordered_set(_InputIterator __f, _InputIterator __l,
90 size_type __n = 0,
91 const hasher& __hf = hasher(),
92 const key_equal& __eql = key_equal(),
93 const allocator_type& __a = allocator_type())
94 : _Base(__f, __l, __n, __hf, __eql, __a)
95 { }
96
97 unordered_set(const unordered_set&) = default;
98
99 unordered_set(const _Base& __x)
100 : _Base(__x)
101 { }
102
103 unordered_set(unordered_set&&) = default;
104
105 explicit
106 unordered_set(const allocator_type& __a)
107 : _Base(__a)
108 { }
109
110 unordered_set(const unordered_set& __uset,
111 const allocator_type& __a)
112 : _Base(__uset._M_base(), __a)
113 { }
114
115 unordered_set(unordered_set&& __uset,
116 const allocator_type& __a)
117 : _Base(std::move(__uset._M_base()), __a)
118 { }
119
120 unordered_set(initializer_list<value_type> __l,
121 size_type __n = 0,
122 const hasher& __hf = hasher(),
123 const key_equal& __eql = key_equal(),
124 const allocator_type& __a = allocator_type())
125 : _Base(__l, __n, __hf, __eql, __a)
126 { }
127
128 unordered_set(size_type __n, const allocator_type& __a)
129 : unordered_set(__n, hasher(), key_equal(), __a)
130 { }
131
132 unordered_set(size_type __n, const hasher& __hf,
133 const allocator_type& __a)
134 : unordered_set(__n, __hf, key_equal(), __a)
135 { }
136
137 template<typename _InputIterator>
138 unordered_set(_InputIterator __first, _InputIterator __last,
139 size_type __n,
140 const allocator_type& __a)
141 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
142 { }
143
144 template<typename _InputIterator>
145 unordered_set(_InputIterator __first, _InputIterator __last,
146 size_type __n, const hasher& __hf,
147 const allocator_type& __a)
148 : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
149 { }
150
151 unordered_set(initializer_list<value_type> __l,
152 size_type __n,
153 const allocator_type& __a)
154 : unordered_set(__l, __n, hasher(), key_equal(), __a)
155 { }
156
157 unordered_set(initializer_list<value_type> __l,
158 size_type __n, const hasher& __hf,
159 const allocator_type& __a)
160 : unordered_set(__l, __n, __hf, key_equal(), __a)
161 { }
162
163 unordered_set&
164 operator=(const unordered_set&) = default;
165
166 unordered_set&
167 operator=(unordered_set&&) = default;
168
169 unordered_set&
170 operator=(initializer_list<value_type> __l)
171 {
172 this->_M_profile_destruct();
173 _M_base() = __l;
174 this->_M_profile_construct();
175 return *this;
176 }
177
178 void
179 swap(unordered_set& __x)
180 noexcept( noexcept(__x._M_base().swap(__x)) )
181 {
182 _Base::swap(__x);
183 this->_M_swap(__x);
184 }
185
186 void
187 clear() noexcept
188 {
189 this->_M_profile_destruct();
190 _Base::clear();
191 this->_M_profile_construct();
192 }
193
194 template<typename... _Args>
195 std::pair<iterator, bool>
196 emplace(_Args&&... __args)
197 {
198 size_type __old_size = _Base::bucket_count();
199 std::pair<iterator, bool> __res
200 = _Base::emplace(std::forward<_Args>(__args)...);
201 this->_M_profile_resize(__old_size);
202 return __res;
203 }
204
205 template<typename... _Args>
206 iterator
207 emplace_hint(const_iterator __it, _Args&&... __args)
208 {
209 size_type __old_size = _Base::bucket_count();
210 iterator __res
211 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
212 this->_M_profile_resize(__old_size);
213 return __res;
214 }
215
216 void
217 insert(std::initializer_list<value_type> __l)
218 {
219 size_type __old_size = _Base::bucket_count();
220 _Base::insert(__l);
221 this->_M_profile_resize(__old_size);
222 }
223
224 std::pair<iterator, bool>
225 insert(const value_type& __obj)
226 {
227 size_type __old_size = _Base::bucket_count();
228 std::pair<iterator, bool> __res = _Base::insert(__obj);
229 this->_M_profile_resize(__old_size);
230 return __res;
231 }
232
233 iterator
234 insert(const_iterator __iter, const value_type& __v)
235 {
236 size_type __old_size = _Base::bucket_count();
237 iterator __res = _Base::insert(__iter, __v);
238 this->_M_profile_resize(__old_size);
239 return __res;
240 }
241
242 std::pair<iterator, bool>
243 insert(value_type&& __obj)
244 {
245 size_type __old_size = _Base::bucket_count();
246 std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
247 this->_M_profile_resize(__old_size);
248 return __res;
249 }
250
251 iterator
252 insert(const_iterator __iter, value_type&& __v)
253 {
254 size_type __old_size = _Base::bucket_count();
255 iterator __res = _Base::insert(__iter, std::move(__v));
256 this->_M_profile_resize(__old_size);
257 return __res;
258 }
259
260 template<typename _InputIter>
261 void
262 insert(_InputIter __first, _InputIter __last)
263 {
264 size_type __old_size = _Base::bucket_count();
265 _Base::insert(__first, __last);
266 this->_M_profile_resize(__old_size);
267 }
268
269 void
270 rehash(size_type __n)
271 {
272 size_type __old_size = _Base::bucket_count();
273 _Base::rehash(__n);
274 this->_M_profile_resize(__old_size);
275 }
276 };
277
278 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
279 inline void
280 swap(unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
281 unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
282 noexcept(noexcept(__x.swap(__y)))
283 { __x.swap(__y); }
284
285 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
286 inline bool
287 operator==(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
288 const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
289 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
290
291 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
292 inline bool
293 operator!=(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
294 const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
295 { return !(__x == __y); }
296
297#undef _GLIBCXX_BASE
298#undef _GLIBCXX_STD_BASE
299#define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
300#define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
301
302 /** @brief Unordered_multiset wrapper with performance instrumentation. */
303 template<typename _Value,
304 typename _Hash = std::hash<_Value>,
305 typename _Pred = std::equal_to<_Value>,
306 typename _Alloc = std::allocator<_Value> >
307 class unordered_multiset
308 : public _GLIBCXX_STD_BASE,
309 public _Unordered_profile<unordered_multiset<_Value,
310 _Hash, _Pred, _Alloc>,
311 false>
312 {
313 typedef _GLIBCXX_STD_BASE _Base;
314
315 _Base&
316 _M_base() noexcept { return *this; }
317
318 const _Base&
319 _M_base() const noexcept { return *this; }
320
321 public:
322 typedef typename _Base::size_type size_type;
323 typedef typename _Base::hasher hasher;
324 typedef typename _Base::key_equal key_equal;
325 typedef typename _Base::allocator_type allocator_type;
326 typedef typename _Base::key_type key_type;
327 typedef typename _Base::value_type value_type;
328 typedef typename _Base::difference_type difference_type;
329 typedef typename _Base::reference reference;
330 typedef typename _Base::const_reference const_reference;
331
332 typedef typename _Base::iterator iterator;
333 typedef typename _Base::const_iterator const_iterator;
334
335 unordered_multiset() = default;
336
337 explicit
338 unordered_multiset(size_type __n,
339 const hasher& __hf = hasher(),
340 const key_equal& __eql = key_equal(),
341 const allocator_type& __a = allocator_type())
342 : _Base(__n, __hf, __eql, __a)
343 { }
344
345 template<typename _InputIterator>
346 unordered_multiset(_InputIterator __f, _InputIterator __l,
347 size_type __n = 0,
348 const hasher& __hf = hasher(),
349 const key_equal& __eql = key_equal(),
350 const allocator_type& __a = allocator_type())
351 : _Base(__f, __l, __n, __hf, __eql, __a)
352 { }
353
354 unordered_multiset(const unordered_multiset&) = default;
355
356 unordered_multiset(const _Base& __x)
357 : _Base(__x)
358 { }
359
360 unordered_multiset(unordered_multiset&&) = default;
361
362 explicit
363 unordered_multiset(const allocator_type& __a)
364 : _Base(__a)
365 { }
366
367 unordered_multiset(const unordered_multiset& __umset,
368 const allocator_type& __a)
369 : _Base(__umset._M_base(), __a)
370 { }
371
372 unordered_multiset(unordered_multiset&& __umset,
373 const allocator_type& __a)
374 : _Base(std::move(__umset._M_base()), __a)
375 { }
376
377 unordered_multiset(initializer_list<value_type> __l,
378 size_type __n = 0,
379 const hasher& __hf = hasher(),
380 const key_equal& __eql = key_equal(),
381 const allocator_type& __a = allocator_type())
382 : _Base(__l, __n, __hf, __eql, __a)
383 { }
384
385 unordered_multiset(size_type __n, const allocator_type& __a)
386 : unordered_multiset(__n, hasher(), key_equal(), __a)
387 { }
388
389 unordered_multiset(size_type __n, const hasher& __hf,
390 const allocator_type& __a)
391 : unordered_multiset(__n, __hf, key_equal(), __a)
392 { }
393
394 template<typename _InputIterator>
395 unordered_multiset(_InputIterator __first, _InputIterator __last,
396 size_type __n,
397 const allocator_type& __a)
398 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
399 { }
400
401 template<typename _InputIterator>
402 unordered_multiset(_InputIterator __first, _InputIterator __last,
403 size_type __n, const hasher& __hf,
404 const allocator_type& __a)
405 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
406 { }
407
408 unordered_multiset(initializer_list<value_type> __l,
409 size_type __n,
410 const allocator_type& __a)
411 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
412 { }
413
414 unordered_multiset(initializer_list<value_type> __l,
415 size_type __n, const hasher& __hf,
416 const allocator_type& __a)
417 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
418 { }
419
420 unordered_multiset&
421 operator=(const unordered_multiset&) = default;
422
423 unordered_multiset&
424 operator=(unordered_multiset&&) = default;
425
426 unordered_multiset&
427 operator=(initializer_list<value_type> __l)
428 {
429 this->_M_profile_destruct();
430 _M_base() = __l;
431 this->_M_profile_construct();
432 return *this;
433 }
434
435 void
436 swap(unordered_multiset& __x)
437 noexcept( noexcept(__x._M_base().swap(__x)) )
438 {
439 _Base::swap(__x);
440 this->_M_swap(__x);
441 }
442
443 void
444 clear() noexcept
445 {
446 this->_M_profile_destruct();
447 _Base::clear();
448 this->_M_profile_construct();
449 }
450
451 template<typename... _Args>
452 iterator
453 emplace(_Args&&... __args)
454 {
455 size_type __old_size = _Base::bucket_count();
456 iterator __res = _Base::emplace(std::forward<_Args>(__args)...);
457 this->_M_profile_resize(__old_size);
458 return __res;
459 }
460
461 template<typename... _Args>
462 iterator
463 emplace_hint(const_iterator __it, _Args&&... __args)
464 {
465 size_type __old_size = _Base::bucket_count();
466 iterator __res
467 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
468 this->_M_profile_resize(__old_size);
469 return __res;
470 }
471
472 void
473 insert(std::initializer_list<value_type> __l)
474 {
475 size_type __old_size = _Base::bucket_count();
476 _Base::insert(__l);
477 this->_M_profile_resize(__old_size);
478 }
479
480 iterator
481 insert(const value_type& __obj)
482 {
483 size_type __old_size = _Base::bucket_count();
484 iterator __res = _Base::insert(__obj);
485 this->_M_profile_resize(__old_size);
486 return __res;
487 }
488
489 iterator
490 insert(const_iterator __iter, const value_type& __v)
491 {
492 size_type __old_size = _Base::bucket_count();
493 iterator __res = _Base::insert(__iter, __v);
494 this->_M_profile_resize(__old_size);
495 return __res;
496 }
497
498 iterator
499 insert(value_type&& __obj)
500 {
501 size_type __old_size = _Base::bucket_count();
502 iterator __res = _Base::insert(std::move(__obj));
503 this->_M_profile_resize(__old_size);
504 return __res;
505 }
506
507 iterator
508 insert(const_iterator __iter, value_type&& __v)
509 {
510 size_type __old_size = _Base::bucket_count();
511 iterator __res = _Base::insert(__iter, std::move(__v));
512 this->_M_profile_resize(__old_size);
513 return __res;
514 }
515
516 template<typename _InputIter>
517 void
518 insert(_InputIter __first, _InputIter __last)
519 {
520 size_type __old_size = _Base::bucket_count();
521 _Base::insert(__first, __last);
522 this->_M_profile_resize(__old_size);
523 }
524
525 void
526 rehash(size_type __n)
527 {
528 size_type __old_size = _Base::bucket_count();
529 _Base::rehash(__n);
530 this->_M_profile_resize(__old_size);
531 }
532 };
533
534 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
535 inline void
536 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
537 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
538 noexcept(noexcept(__x.swap(__y)))
539 { __x.swap(__y); }
540
541 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
542 inline bool
543 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
544 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
545 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
546
547 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
548 inline bool
549 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
550 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
551 { return !(__x == __y); }
552
553} // namespace __profile
554} // namespace std
555
556#undef _GLIBCXX_BASE
557#undef _GLIBCXX_STD_BASE
558
559#endif // C++11
560
561#endif