libstdc++
profile/multimap.h
Go to the documentation of this file.
1 // Profiling multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-2014 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 <utility>
33 
34 namespace std _GLIBCXX_VISIBILITY(default)
35 {
36 namespace __profile
37 {
38  /// Class std::multimap wrapper with performance instrumentation.
39  template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
40  typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
41  class multimap
42  : public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>
43  {
44  typedef _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> _Base;
45 
46 #if __cplusplus >= 201103L
47  typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits;
48 #endif
49 
50  public:
51  // types:
52  typedef _Key key_type;
53  typedef _Tp mapped_type;
54  typedef std::pair<const _Key, _Tp> value_type;
55  typedef _Compare key_compare;
56  typedef _Allocator allocator_type;
57  typedef typename _Base::reference reference;
58  typedef typename _Base::const_reference const_reference;
59 
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;
64 
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;
69 
70  // 23.3.1.1 construct/copy/destroy:
71 
72  multimap()
73  : _Base() { }
74 
75  explicit multimap(const _Compare& __comp,
76  const _Allocator& __a = _Allocator())
77  : _Base(__comp, __a) { }
78 
79 #if __cplusplus >= 201103L
80  template<typename _InputIterator,
81  typename = std::_RequireInputIter<_InputIterator>>
82 #else
83  template<typename _InputIterator>
84 #endif
85  multimap(_InputIterator __first, _InputIterator __last,
86  const _Compare& __comp = _Compare(),
87  const _Allocator& __a = _Allocator())
88  : _Base(__first, __last, __comp, __a) { }
89 
90 #if __cplusplus < 201103L
91  multimap(const multimap& __x)
92  : _Base(__x) { }
93 #else
94  multimap(const multimap&) = default;
95  multimap(multimap&&) = default;
96 
97  multimap(initializer_list<value_type> __l,
98  const _Compare& __c = _Compare(),
99  const allocator_type& __a = allocator_type())
100  : _Base(__l, __c, __a) { }
101 
102  explicit
103  multimap(const allocator_type& __a)
104  : _Base(__a) { }
105 
106  multimap(const multimap& __x, const allocator_type& __a)
107  : _Base(__x, __a) { }
108 
109  multimap(multimap&& __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) { }
113 
114  multimap(initializer_list<value_type> __l, const allocator_type& __a)
115  : _Base(__l, __a) { }
116 
117  template<typename _InputIterator>
118  multimap(_InputIterator __first, _InputIterator __last,
119  const allocator_type& __a)
120  : _Base(__first, __last, __a) { }
121 #endif
122 
123  multimap(const _Base& __x)
124  : _Base(__x) { }
125 
126  ~multimap() _GLIBCXX_NOEXCEPT { }
127 
128 #if __cplusplus < 201103L
129  multimap&
130  operator=(const multimap& __x)
131  {
132  _M_base() = __x;
133  return *this;
134  }
135 #else
136  multimap&
137  operator=(const multimap&) = default;
138 
139  multimap&
140  operator=(multimap&&) = default;
141 
142  multimap&
143  operator=(initializer_list<value_type> __l)
144  {
145  _M_base() = __l;
146  return *this;
147  }
148 #endif
149 
150  using _Base::get_allocator;
151 
152  // iterators:
153  iterator
154  begin() _GLIBCXX_NOEXCEPT
155  { return iterator(_Base::begin()); }
156 
157  const_iterator
158  begin() const _GLIBCXX_NOEXCEPT
159  { return const_iterator(_Base::begin()); }
160 
161  iterator
162  end() _GLIBCXX_NOEXCEPT
163  { return iterator(_Base::end()); }
164 
165  const_iterator
166  end() const _GLIBCXX_NOEXCEPT
167  { return const_iterator(_Base::end()); }
168 
169  reverse_iterator
170  rbegin() _GLIBCXX_NOEXCEPT
171  { return reverse_iterator(end()); }
172 
173  const_reverse_iterator
174  rbegin() const _GLIBCXX_NOEXCEPT
175  { return const_reverse_iterator(end()); }
176 
177  reverse_iterator
178  rend() _GLIBCXX_NOEXCEPT
179  { return reverse_iterator(begin()); }
180 
181  const_reverse_iterator
182  rend() const _GLIBCXX_NOEXCEPT
183  { return const_reverse_iterator(begin()); }
184 
185 #if __cplusplus >= 201103L
186  const_iterator
187  cbegin() const noexcept
188  { return const_iterator(_Base::begin()); }
189 
190  const_iterator
191  cend() const noexcept
192  { return const_iterator(_Base::end()); }
193 
194  const_reverse_iterator
195  crbegin() const noexcept
196  { return const_reverse_iterator(end()); }
197 
198  const_reverse_iterator
199  crend() const noexcept
200  { return const_reverse_iterator(begin()); }
201 #endif
202 
203  // capacity:
204  using _Base::empty;
205  using _Base::size;
206  using _Base::max_size;
207 
208  // modifiers:
209 #if __cplusplus >= 201103L
210  template<typename... _Args>
211  iterator
212  emplace(_Args&&... __args)
213  {
214  return iterator(_Base::emplace(std::forward<_Args>(__args)...));
215  }
216 
217  template<typename... _Args>
218  iterator
219  emplace_hint(const_iterator __pos, _Args&&... __args)
220  {
221  return iterator(_Base::emplace_hint(__pos,
222  std::forward<_Args>(__args)...));
223  }
224 #endif
225 
226  iterator
227  insert(const value_type& __x)
228  { return iterator(_Base::insert(__x)); }
229 
230 #if __cplusplus >= 201103L
231  template<typename _Pair, typename = typename
232  std::enable_if<std::is_constructible<value_type,
233  _Pair&&>::value>::type>
234  iterator
235  insert(_Pair&& __x)
236  { return iterator(_Base::insert(std::forward<_Pair>(__x))); }
237 #endif
238 
239 #if __cplusplus >= 201103L
240  void
241  insert(std::initializer_list<value_type> __list)
242  { _Base::insert(__list); }
243 #endif
244 
245  iterator
246 #if __cplusplus >= 201103L
247  insert(const_iterator __position, const value_type& __x)
248 #else
249  insert(iterator __position, const value_type& __x)
250 #endif
251  { return iterator(_Base::insert(__position, __x)); }
252 
253 #if __cplusplus >= 201103L
254  template<typename _Pair, typename = typename
255  std::enable_if<std::is_constructible<value_type,
256  _Pair&&>::value>::type>
257  iterator
258  insert(const_iterator __position, _Pair&& __x)
259  { return iterator(_Base::insert(__position,
260  std::forward<_Pair>(__x))); }
261 #endif
262 
263 #if __cplusplus >= 201103L
264  template<typename _InputIterator,
265  typename = std::_RequireInputIter<_InputIterator>>
266 #else
267  template<typename _InputIterator>
268 #endif
269  void
270  insert(_InputIterator __first, _InputIterator __last)
271  { _Base::insert(__first, __last); }
272 
273 #if __cplusplus >= 201103L
274  iterator
275  erase(const_iterator __position)
276  { return iterator(_Base::erase(__position)); }
277 
278  iterator
279  erase(iterator __position)
280  { return iterator(_Base::erase(__position)); }
281 #else
282  void
283  erase(iterator __position)
284  { _Base::erase(__position); }
285 #endif
286 
287  size_type
288  erase(const key_type& __x)
289  {
290  std::pair<iterator, iterator> __victims = this->equal_range(__x);
291  size_type __count = 0;
292  while (__victims.first != __victims.second)
293  {
294  iterator __victim = __victims.first++;
295  _Base::erase(__victim);
296  ++__count;
297  }
298  return __count;
299  }
300 
301 #if __cplusplus >= 201103L
302  iterator
303  erase(const_iterator __first, const_iterator __last)
304  { return iterator(_Base::erase(__first, __last)); }
305 #else
306  void
307  erase(iterator __first, iterator __last)
308  { _Base::erase(__first, __last); }
309 #endif
310 
311  void
312  swap(multimap& __x)
313 #if __cplusplus >= 201103L
314  noexcept(_Alloc_traits::_S_nothrow_swap())
315 #endif
316  { _Base::swap(__x); }
317 
318  void
319  clear() _GLIBCXX_NOEXCEPT
320  { this->erase(begin(), end()); }
321 
322  // observers:
323  using _Base::key_comp;
324  using _Base::value_comp;
325 
326  // 23.3.1.3 multimap operations:
327  iterator
328  find(const key_type& __x)
329  { return iterator(_Base::find(__x)); }
330 
331  const_iterator
332  find(const key_type& __x) const
333  { return const_iterator(_Base::find(__x)); }
334 
335  using _Base::count;
336 
337  iterator
338  lower_bound(const key_type& __x)
339  { return iterator(_Base::lower_bound(__x)); }
340 
341  const_iterator
342  lower_bound(const key_type& __x) const
343  { return const_iterator(_Base::lower_bound(__x)); }
344 
345  iterator
346  upper_bound(const key_type& __x)
347  { return iterator(_Base::upper_bound(__x)); }
348 
349  const_iterator
350  upper_bound(const key_type& __x) const
351  { return const_iterator(_Base::upper_bound(__x)); }
352 
353  std::pair<iterator,iterator>
354  equal_range(const key_type& __x)
355  {
356  typedef typename _Base::iterator _Base_iterator;
357  std::pair<_Base_iterator, _Base_iterator> __res =
358  _Base::equal_range(__x);
359  return std::make_pair(iterator(__res.first),
360  iterator(__res.second));
361  }
362 
363  std::pair<const_iterator,const_iterator>
364  equal_range(const key_type& __x) const
365  {
366  typedef typename _Base::const_iterator _Base_const_iterator;
367  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
368  _Base::equal_range(__x);
369  return std::make_pair(const_iterator(__res.first),
370  const_iterator(__res.second));
371  }
372 
373  _Base&
374  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
375 
376  const _Base&
377  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
378  };
379 
380  template<typename _Key, typename _Tp,
381  typename _Compare, typename _Allocator>
382  inline bool
383  operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
384  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
385  { return __lhs._M_base() == __rhs._M_base(); }
386 
387  template<typename _Key, typename _Tp,
388  typename _Compare, typename _Allocator>
389  inline bool
390  operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
391  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
392  { return __lhs._M_base() != __rhs._M_base(); }
393 
394  template<typename _Key, typename _Tp,
395  typename _Compare, typename _Allocator>
396  inline bool
397  operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
398  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
399  { return __lhs._M_base() < __rhs._M_base(); }
400 
401  template<typename _Key, typename _Tp,
402  typename _Compare, typename _Allocator>
403  inline bool
404  operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
405  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
406  { return __lhs._M_base() <= __rhs._M_base(); }
407 
408  template<typename _Key, typename _Tp,
409  typename _Compare, typename _Allocator>
410  inline bool
411  operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
412  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
413  { return __lhs._M_base() >= __rhs._M_base(); }
414 
415  template<typename _Key, typename _Tp,
416  typename _Compare, typename _Allocator>
417  inline bool
418  operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
419  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
420  { return __lhs._M_base() > __rhs._M_base(); }
421 
422  template<typename _Key, typename _Tp,
423  typename _Compare, typename _Allocator>
424  inline void
425  swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
426  multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
427  { __lhs.swap(__rhs); }
428 
429 } // namespace __profile
430 } // namespace std
431 
432 #endif
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
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
__gnu_cxx::__alloc_traits
Uniform interface to C++98 and C++0x allocators.
Definition: ext/alloc_traits.h:95
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:101
std
ISO C++ entities toplevel namespace is std.
std::__profile::multimap
Class std::multimap wrapper with performance instrumentation.
Definition: profile/multimap.h:41
std::operator>=
bool operator>=(const basic_string< _CharT, _Traits, _Alloc > &__lhs, const basic_string< _CharT, _Traits, _Alloc > &__rhs)
Test if string doesn't precede string.
Definition: basic_string.h:2699
std::multimap
A standard container made up of (key,value) pairs, which can be retrieved based on a key...
Definition: stl_multimap.h:95
std::operator>
bool operator>(const basic_string< _CharT, _Traits, _Alloc > &__lhs, const basic_string< _CharT, _Traits, _Alloc > &__rhs)
Test if string follows string.
Definition: basic_string.h:2625
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
std::swap
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
Definition: move.h:166
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:102