1 // Profiling multiset implementation -*- C++ -*-
2
3 // Copyright (C) 2009-2017 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 <profile/base.h>
33 #include <profile/ordered_base.h>
34
_GLIBCXX_VISIBILITY(default)35 namespace std _GLIBCXX_VISIBILITY(default)
36 {
37 namespace __profile
38 {
39 /// Class std::multiset wrapper with performance instrumentation.
40 template<typename _Key, typename _Compare = std::less<_Key>,
41 typename _Allocator = std::allocator<_Key> >
42 class multiset
43 : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>,
44 public _Ordered_profile<multiset<_Key, _Compare, _Allocator> >
45 {
46 typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
47
48 typedef typename _Base::iterator _Base_iterator;
49 typedef typename _Base::const_iterator _Base_const_iterator;
50
51 public:
52 // types:
53 typedef _Key key_type;
54 typedef _Key value_type;
55 typedef _Compare key_compare;
56 typedef _Compare value_compare;
57 typedef _Allocator allocator_type;
58 typedef typename _Base::reference reference;
59 typedef typename _Base::const_reference const_reference;
60
61 typedef __iterator_tracker<_Base_iterator,
62 multiset> iterator;
63 typedef __iterator_tracker<_Base_const_iterator,
64 multiset> const_iterator;
65 typedef std::reverse_iterator<iterator> reverse_iterator;
66 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
67
68 typedef typename _Base::size_type size_type;
69 typedef typename _Base::difference_type difference_type;
70
71 // 23.3.3.1 construct/copy/destroy:
72
73 #if __cplusplus < 201103L
74 multiset()
75 : _Base() { }
76 multiset(const multiset& __x)
77 : _Base(__x) { }
78 ~multiset() { }
79 #else
80 multiset() = default;
81 multiset(const multiset&) = default;
82 multiset(multiset&&) = default;
83 ~multiset() = default;
84 #endif
85
86 explicit multiset(const _Compare& __comp,
87 const _Allocator& __a = _Allocator())
88 : _Base(__comp, __a) { }
89
90 #if __cplusplus >= 201103L
91 template<typename _InputIterator,
92 typename = std::_RequireInputIter<_InputIterator>>
93 #else
94 template<typename _InputIterator>
95 #endif
96 multiset(_InputIterator __first, _InputIterator __last,
97 const _Compare& __comp = _Compare(),
98 const _Allocator& __a = _Allocator())
99 : _Base(__first, __last, __comp, __a) { }
100
101 #if __cplusplus >= 201103L
102 multiset(initializer_list<value_type> __l,
103 const _Compare& __comp = _Compare(),
104 const allocator_type& __a = allocator_type())
105 : _Base(__l, __comp, __a) { }
106
107 explicit
108 multiset(const allocator_type& __a)
109 : _Base(__a) { }
110
111 multiset(const multiset& __x, const allocator_type& __a)
112 : _Base(__x, __a) { }
113
114 multiset(multiset&& __x, const allocator_type& __a)
115 noexcept( noexcept(_Base(std::move(__x), __a)) )
116 : _Base(std::move(__x), __a) { }
117
118 multiset(initializer_list<value_type> __l, const allocator_type& __a)
119 : _Base(__l, __a) { }
120
121 template<typename _InputIterator>
122 multiset(_InputIterator __first, _InputIterator __last,
123 const allocator_type& __a)
124 : _Base(__first, __last, __a) { }
125 #endif
126
127 multiset(const _Base& __x)
128 : _Base(__x) { }
129
130 #if __cplusplus < 201103L
131 multiset&
132 operator=(const multiset& __x)
133 {
134 this->_M_profile_destruct();
135 _M_base() = __x;
136 this->_M_profile_construct();
137 return *this;
138 }
139 #else
140 multiset&
141 operator=(const multiset&) = default;
142
143 multiset&
144 operator=(multiset&&) = default;
145
146 multiset&
147 operator=(initializer_list<value_type> __l)
148 {
149 this->_M_profile_destruct();
150 _M_base() = __l;
151 this->_M_profile_construct();
152 return *this;
153 }
154 #endif
155
156 // iterators
157 iterator
158 begin() _GLIBCXX_NOEXCEPT
159 { return iterator(_Base::begin(), this); }
160
161 const_iterator
162 begin() const _GLIBCXX_NOEXCEPT
163 { return const_iterator(_Base::begin(), this); }
164
165 iterator
166 end() _GLIBCXX_NOEXCEPT
167 { return iterator(_Base::end(), this); }
168
169 const_iterator
170 end() const _GLIBCXX_NOEXCEPT
171 { return const_iterator(_Base::end(), this); }
172
173 #if __cplusplus >= 201103L
174 const_iterator
175 cbegin() const noexcept
176 { return const_iterator(_Base::cbegin(), this); }
177
178 const_iterator
179 cend() const noexcept
180 { return const_iterator(_Base::cend(), this); }
181 #endif
182
183 reverse_iterator
184 rbegin() _GLIBCXX_NOEXCEPT
185 {
186 __profcxx_map2umap_invalidate(this->_M_map2umap_info);
187 return reverse_iterator(end());
188 }
189
190 const_reverse_iterator
191 rbegin() const _GLIBCXX_NOEXCEPT
192 {
193 __profcxx_map2umap_invalidate(this->_M_map2umap_info);
194 return const_reverse_iterator(end());
195 }
196
197 reverse_iterator
198 rend() _GLIBCXX_NOEXCEPT
199 {
200 __profcxx_map2umap_invalidate(this->_M_map2umap_info);
201 return reverse_iterator(begin());
202 }
203
204 const_reverse_iterator
205 rend() const _GLIBCXX_NOEXCEPT
206 {
207 __profcxx_map2umap_invalidate(this->_M_map2umap_info);
208 return const_reverse_iterator(begin());
209 }
210
211 #if __cplusplus >= 201103L
212 const_reverse_iterator
213 crbegin() const noexcept
214 {
215 __profcxx_map2umap_invalidate(this->_M_map2umap_info);
216 return const_reverse_iterator(cend());
217 }
218
219 const_reverse_iterator
220 crend() const noexcept
221 {
222 __profcxx_map2umap_invalidate(this->_M_map2umap_info);
223 return const_reverse_iterator(cbegin());
224 }
225 #endif
226
227 void
228 swap(multiset& __x)
229 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
230 {
231 _Base::swap(__x);
232 this->_M_swap(__x);
233 }
234
235 // modifiers:
236 #if __cplusplus >= 201103L
237 template<typename... _Args>
238 iterator
239 emplace(_Args&&... __args)
240 {
241 // The cost is the same whether or not the element is inserted so we
242 // always report insertion of 1 element.
243 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
244 return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
245 }
246
247 template<typename... _Args>
248 iterator
249 emplace_hint(const_iterator __pos, _Args&&... __args)
250 {
251 auto size_before = this->size();
252 auto __res
253 = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...);
254 __profcxx_map2umap_insert(this->_M_map2umap_info,
255 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
256 return iterator(__res, this);
257 }
258 #endif
259
260 iterator
261 insert(const value_type& __x)
262 {
263 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
264 return iterator(_Base::insert(__x), this);
265 }
266
267 #if __cplusplus >= 201103L
268 iterator
269 insert(value_type&& __x)
270 {
271 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1);
272 return iterator(_Base::insert(std::move(__x)), this);
273 }
274 #endif
275
276 iterator
277 insert(const_iterator __pos, const value_type& __x)
278 {
279 size_type size_before = this->size();
280 _Base_iterator __res = _Base::insert(__pos.base(), __x);
281
282 __profcxx_map2umap_insert(this->_M_map2umap_info,
283 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
284 return iterator(__res, this);
285 }
286
287 #if __cplusplus >= 201103L
288 iterator
289 insert(const_iterator __pos, value_type&& __x)
290 {
291 auto size_before = this->size();
292 auto __res = _Base::insert(__pos.base(), std::move(__x));
293 __profcxx_map2umap_insert(this->_M_map2umap_info,
294 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1);
295 return iterator(__res, this);
296 }
297 #endif
298
299 #if __cplusplus >= 201103L
300 template<typename _InputIterator,
301 typename = std::_RequireInputIter<_InputIterator>>
302 #else
303 template<typename _InputIterator>
304 #endif
305 void
306 insert(_InputIterator __first, _InputIterator __last)
307 {
308 for (; __first != __last; ++__first)
309 insert(*__first);
310 }
311
312 #if __cplusplus >= 201103L
313 void
314 insert(initializer_list<value_type> __l)
315 { insert(__l.begin(), __l.end()); }
316 #endif
317
318 #if __cplusplus >= 201103L
319 iterator
320 erase(const_iterator __pos)
321 {
322 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
323 return iterator(_Base::erase(__pos.base()), this);
324 }
325 #else
326 void
327 erase(iterator __pos)
328 {
329 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
330 _Base::erase(__pos.base());
331 }
332 #endif
333
334 size_type
335 erase(const key_type& __x)
336 {
337 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
338 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1);
339 return _Base::erase(__x);
340 }
341
342 #if __cplusplus >= 201103L
343 iterator
344 erase(const_iterator __first, const_iterator __last)
345 {
346 if (__first != __last)
347 {
348 iterator __ret;
349 for (; __first != __last;)
350 __ret = erase(__first++);
351 return __ret;
352 }
353 else
354 return iterator(_Base::erase(__first.base(), __last.base()), this);
355 }
356 #else
357 void
358 erase(iterator __first, iterator __last)
359 {
360 for (; __first != __last;)
361 erase(__first++);
362 }
363 #endif
364
365 void
366 clear() _GLIBCXX_NOEXCEPT
367 {
368 this->_M_profile_destruct();
369 _Base::clear();
370 this->_M_profile_construct();
371 }
372
373 size_type
374 count(const key_type& __x) const
375 {
376 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
377 return _Base::count(__x);
378 }
379
380 #if __cplusplus > 201103L
381 template<typename _Kt,
382 typename _Req =
383 typename __has_is_transparent<_Compare, _Kt>::type>
384 size_type
385 count(const _Kt& __x) const
386 {
387 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
388 return _Base::count(__x);
389 }
390 #endif
391
392 // multiset operations:
393 iterator
394 find(const key_type& __x)
395 {
396 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
397 return iterator(_Base::find(__x), this);
398 }
399
400 // _GLIBCXX_RESOLVE_LIB_DEFECTS
401 // 214. set::find() missing const overload
402 const_iterator
403 find(const key_type& __x) const
404 {
405 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
406 return const_iterator(_Base::find(__x), this);
407 }
408
409 #if __cplusplus > 201103L
410 template<typename _Kt,
411 typename _Req =
412 typename __has_is_transparent<_Compare, _Kt>::type>
413 iterator
414 find(const _Kt& __x)
415 {
416 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
417 return { _Base::find(__x), this };
418 }
419
420 template<typename _Kt,
421 typename _Req =
422 typename __has_is_transparent<_Compare, _Kt>::type>
423 const_iterator
424 find(const _Kt& __x) const
425 {
426 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
427 return { _Base::find(__x), this };
428 }
429 #endif
430
431 iterator
432 lower_bound(const key_type& __x)
433 {
434 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
435 return iterator(_Base::lower_bound(__x), this);
436 }
437
438 // _GLIBCXX_RESOLVE_LIB_DEFECTS
439 // 214. set::find() missing const overload
440 const_iterator
441 lower_bound(const key_type& __x) const
442 {
443 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
444 __profcxx_map2umap_invalidate(this->_M_map2umap_info);
445 return const_iterator(_Base::lower_bound(__x), this);
446 }
447
448 #if __cplusplus > 201103L
449 template<typename _Kt,
450 typename _Req =
451 typename __has_is_transparent<_Compare, _Kt>::type>
452 iterator
453 lower_bound(const _Kt& __x)
454 {
455 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
456 __profcxx_map2umap_invalidate(this->_M_map2umap_info);
457 return { _Base::lower_bound(__x), this };
458 }
459
460 template<typename _Kt,
461 typename _Req =
462 typename __has_is_transparent<_Compare, _Kt>::type>
463 const_iterator
464 lower_bound(const _Kt& __x) const
465 {
466 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
467 __profcxx_map2umap_invalidate(this->_M_map2umap_info);
468 return { _Base::lower_bound(__x), this };
469 }
470 #endif
471
472 iterator
473 upper_bound(const key_type& __x)
474 {
475 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
476 __profcxx_map2umap_invalidate(this->_M_map2umap_info);
477 return iterator(_Base::upper_bound(__x), this);
478 }
479
480 // _GLIBCXX_RESOLVE_LIB_DEFECTS
481 // 214. set::find() missing const overload
482 const_iterator
483 upper_bound(const key_type& __x) const
484 {
485 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
486 __profcxx_map2umap_invalidate(this->_M_map2umap_info);
487 return const_iterator(_Base::upper_bound(__x), this);
488 }
489
490 #if __cplusplus > 201103L
491 template<typename _Kt,
492 typename _Req =
493 typename __has_is_transparent<_Compare, _Kt>::type>
494 iterator
495 upper_bound(const _Kt& __x)
496 {
497 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
498 __profcxx_map2umap_invalidate(this->_M_map2umap_info);
499 return { _Base::upper_bound(__x), this };
500 }
501
502 template<typename _Kt,
503 typename _Req =
504 typename __has_is_transparent<_Compare, _Kt>::type>
505 const_iterator
506 upper_bound(const _Kt& __x) const
507 {
508 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
509 __profcxx_map2umap_invalidate(this->_M_map2umap_info);
510 return { _Base::upper_bound(__x), this };
511 }
512 #endif
513
514 std::pair<iterator,iterator>
515 equal_range(const key_type& __x)
516 {
517 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
518 std::pair<_Base_iterator, _Base_iterator> __base_ret
519 = _Base::equal_range(__x);
520 return std::make_pair(iterator(__base_ret.first, this),
521 iterator(__base_ret.second, this));
522 }
523
524 // _GLIBCXX_RESOLVE_LIB_DEFECTS
525 // 214. set::find() missing const overload
526 std::pair<const_iterator,const_iterator>
527 equal_range(const key_type& __x) const
528 {
529 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
530 std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
531 = _Base::equal_range(__x);
532 return std::make_pair(const_iterator(__base_ret.first, this),
533 const_iterator(__base_ret.second, this));
534 }
535
536 #if __cplusplus > 201103L
537 template<typename _Kt,
538 typename _Req =
539 typename __has_is_transparent<_Compare, _Kt>::type>
540 std::pair<iterator, iterator>
541 equal_range(const _Kt& __x)
542 {
543 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
544 auto __res = _Base::equal_range(__x);
545 return { { __res.first, this }, { __res.second, this } };
546 }
547
548 template<typename _Kt,
549 typename _Req =
550 typename __has_is_transparent<_Compare, _Kt>::type>
551 std::pair<const_iterator, const_iterator>
552 equal_range(const _Kt& __x) const
553 {
554 __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
555 auto __res = _Base::equal_range(__x);
556 return { { __res.first, this }, { __res.second, this } };
557 }
558 #endif
559
560 _Base&
561 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
562
563 const _Base&
564 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
565
566 private:
567 /** If hint is used we consider that the map and unordered_map
568 * operations have equivalent insertion cost so we do not update metrics
569 * about it.
570 * Note that to find out if hint has been used is libstdc++
571 * implementation dependent.
572 */
573 bool
574 _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
575 {
576 return (__hint == __res
577 || (__hint == _M_base().end() && ++__res == _M_base().end())
578 || (__hint != _M_base().end() && (++__hint == __res
579 || ++__res == --__hint)));
580 }
581
582 template<typename _K1, typename _C1, typename _A1>
583 friend bool
584 operator==(const multiset<_K1, _C1, _A1>&,
585 const multiset<_K1, _C1, _A1>&);
586
587 template<typename _K1, typename _C1, typename _A1>
588 friend bool
589 operator< (const multiset<_K1, _C1, _A1>&,
590 const multiset<_K1, _C1, _A1>&);
591 };
592
593 template<typename _Key, typename _Compare, typename _Allocator>
594 inline bool
595 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
596 const multiset<_Key, _Compare, _Allocator>& __rhs)
597 {
598 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
599 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
600 return __lhs._M_base() == __rhs._M_base();
601 }
602
603 template<typename _Key, typename _Compare, typename _Allocator>
604 inline bool
605 operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
606 const multiset<_Key, _Compare, _Allocator>& __rhs)
607 {
608 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
609 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
610 return __lhs._M_base() < __rhs._M_base();
611 }
612
613 template<typename _Key, typename _Compare, typename _Allocator>
614 inline bool
615 operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
616 const multiset<_Key, _Compare, _Allocator>& __rhs)
617 { return !(__lhs == __rhs); }
618
619 template<typename _Key, typename _Compare, typename _Allocator>
620 inline bool
621 operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
622 const multiset<_Key, _Compare, _Allocator>& __rhs)
623 { return !(__rhs < __lhs); }
624
625 template<typename _Key, typename _Compare, typename _Allocator>
626 inline bool
627 operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
628 const multiset<_Key, _Compare, _Allocator>& __rhs)
629 { return !(__lhs < __rhs); }
630
631 template<typename _Key, typename _Compare, typename _Allocator>
632 inline bool
633 operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
634 const multiset<_Key, _Compare, _Allocator>& __rhs)
635 { return __rhs < __lhs; }
636
637 template<typename _Key, typename _Compare, typename _Allocator>
638 void
639 swap(multiset<_Key, _Compare, _Allocator>& __x,
640 multiset<_Key, _Compare, _Allocator>& __y)
641 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
642 { return __x.swap(__y); }
643
644 } // namespace __profile
645 } // namespace std
646
647 #endif
648