libstdc++
profile/multimap.h
Go to the documentation of this file.
1 // Profiling multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-2015 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 #if __cplusplus >= 201103L
368  noexcept( noexcept(declval<_Base>().swap(__x)) )
369 #endif
370  {
371  std::swap(this->_M_map2umap_info, __x._M_map2umap_info);
372  _Base::swap(__x);
373  }
374 
375  void
376  clear() _GLIBCXX_NOEXCEPT
377  {
378  this->_M_profile_destruct();
379  _Base::clear();
380  this->_M_profile_construct();
381  }
382 
383  // 23.3.1.3 multimap operations:
384  iterator
385  find(const key_type& __x)
386  {
387  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
388  return iterator(_Base::find(__x), this);
389  }
390 
391  const_iterator
392  find(const key_type& __x) const
393  {
394  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
395  return const_iterator(_Base::find(__x), this);
396  }
397 
398  size_type
399  count(const key_type& __x) const
400  {
401  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
402  return _Base::count(__x);
403  }
404 
405  iterator
406  lower_bound(const key_type& __x)
407  {
408  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
409  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
410  return iterator(_Base::lower_bound(__x), this);
411  }
412 
413  const_iterator
414  lower_bound(const key_type& __x) const
415  {
416  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
417  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
418  return const_iterator(_Base::lower_bound(__x), this);
419  }
420 
421  iterator
422  upper_bound(const key_type& __x)
423  {
424  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
425  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
426  return iterator(_Base::upper_bound(__x), this);
427  }
428 
429  const_iterator
430  upper_bound(const key_type& __x) const
431  {
432  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
433  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
434  return const_iterator(_Base::upper_bound(__x), this);
435  }
436 
437  std::pair<iterator,iterator>
438  equal_range(const key_type& __x)
439  {
440  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
441  std::pair<_Base_iterator, _Base_iterator> __base_ret
442  = _Base::equal_range(__x);
443  return std::make_pair(iterator(__base_ret.first, this),
444  iterator(__base_ret.second, this));
445  }
446 
447  std::pair<const_iterator,const_iterator>
448  equal_range(const key_type& __x) const
449  {
450  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
451  std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret
452  = _Base::equal_range(__x);
453  return std::make_pair(const_iterator(__base_ret.first, this),
454  const_iterator(__base_ret.second, this));
455  }
456 
457  _Base&
458  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
459 
460  const _Base&
461  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
462 
463  private:
464  /** If hint is used we consider that the map and unordered_map
465  * operations have equivalent insertion cost so we do not update metrics
466  * about it.
467  * Note that to find out if hint has been used is libstdc++
468  * implementation dependent.
469  */
470  bool
471  _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res)
472  {
473  return (__hint == __res
474  || (__hint == _M_base().end() && ++__res == _M_base().end())
475  || (__hint != _M_base().end() && (++__hint == __res
476  || ++__res == --__hint)));
477  }
478 
479  template<typename _K1, typename _T1, typename _C1, typename _A1>
480  friend bool
481  operator==(const multimap<_K1, _T1, _C1, _A1>&,
482  const multimap<_K1, _T1, _C1, _A1>&);
483 
484  template<typename _K1, typename _T1, typename _C1, typename _A1>
485  friend bool
486  operator<(const multimap<_K1, _T1, _C1, _A1>&,
487  const multimap<_K1, _T1, _C1, _A1>&);
488  };
489 
490  template<typename _Key, typename _Tp,
491  typename _Compare, typename _Allocator>
492  inline bool
493  operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
494  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
495  {
496  __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
497  __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
498  return __lhs._M_base() == __rhs._M_base();
499  }
500 
501  template<typename _Key, typename _Tp,
502  typename _Compare, typename _Allocator>
503  inline bool
504  operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
505  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
506  {
507  __profcxx_map2umap_invalidate(__lhs._M_map2umap_info);
508  __profcxx_map2umap_invalidate(__rhs._M_map2umap_info);
509  return __lhs._M_base() < __rhs._M_base();
510  }
511 
512  template<typename _Key, typename _Tp,
513  typename _Compare, typename _Allocator>
514  inline bool
515  operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
516  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
517  { return !(__lhs == __rhs); }
518 
519  template<typename _Key, typename _Tp,
520  typename _Compare, typename _Allocator>
521  inline bool
522  operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
523  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
524  { return !(__rhs < __lhs); }
525 
526  template<typename _Key, typename _Tp,
527  typename _Compare, typename _Allocator>
528  inline bool
529  operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
530  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
531  { return !(__lhs < __rhs); }
532 
533  template<typename _Key, typename _Tp,
534  typename _Compare, typename _Allocator>
535  inline bool
536  operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
537  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
538  { return __rhs < __lhs; }
539 
540  template<typename _Key, typename _Tp,
541  typename _Compare, typename _Allocator>
542  inline void
543  swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
544  multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
545  { __lhs.swap(__rhs); }
546 
547 } // namespace __profile
548 } // namespace std
549 
550 #endif
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:276
std::__profile::multimap
Class std::multimap wrapper with performance instrumentation.
Definition: profile/multimap.h:42
std::initializer_list
initializer_list
Definition: initializer_list:47
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:102
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:101
base.h
Sequential helper functions. This file is a GNU profile extension to the Standard C++ Library...
std
ISO C++ entities toplevel namespace is std.