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