libstdc++
profile/multimap.h
Go to the documentation of this file.
1 // Profiling multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2009, 2010, 2011, 2012 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  public:
47  // types:
48  typedef _Key key_type;
49  typedef _Tp mapped_type;
50  typedef std::pair<const _Key, _Tp> value_type;
51  typedef _Compare key_compare;
52  typedef _Allocator allocator_type;
53  typedef typename _Base::reference reference;
54  typedef typename _Base::const_reference const_reference;
55 
56  typedef typename _Base::iterator iterator;
57  typedef typename _Base::const_iterator const_iterator;
58  typedef typename _Base::reverse_iterator reverse_iterator;
59  typedef typename _Base::const_reverse_iterator const_reverse_iterator;
60 
61  typedef typename _Base::size_type size_type;
62  typedef typename _Base::difference_type difference_type;
63  typedef typename _Base::pointer pointer;
64  typedef typename _Base::const_pointer const_pointer;
65 
66  // 23.3.1.1 construct/copy/destroy:
67  explicit multimap(const _Compare& __comp = _Compare(),
68  const _Allocator& __a = _Allocator())
69  : _Base(__comp, __a) { }
70 
71  template<typename _InputIterator>
72  multimap(_InputIterator __first, _InputIterator __last,
73  const _Compare& __comp = _Compare(),
74  const _Allocator& __a = _Allocator())
75  : _Base(__first, __last, __comp, __a) { }
76 
77  multimap(const multimap& __x)
78  : _Base(__x) { }
79 
80  multimap(const _Base& __x)
81  : _Base(__x) { }
82 
83 #ifdef __GXX_EXPERIMENTAL_CXX0X__
84  multimap(multimap&& __x)
85  noexcept(is_nothrow_copy_constructible<_Compare>::value)
86  : _Base(std::move(__x))
87  { }
88 
89  multimap(initializer_list<value_type> __l,
90  const _Compare& __c = _Compare(),
91  const allocator_type& __a = allocator_type())
92  : _Base(__l, __c, __a) { }
93 #endif
94 
95  ~multimap() _GLIBCXX_NOEXCEPT { }
96 
97  multimap&
98  operator=(const multimap& __x)
99  {
100  *static_cast<_Base*>(this) = __x;
101  return *this;
102  }
103 
104 #ifdef __GXX_EXPERIMENTAL_CXX0X__
105  multimap&
106  operator=(multimap&& __x)
107  {
108  // NB: DR 1204.
109  // NB: DR 675.
110  this->clear();
111  this->swap(__x);
112  return *this;
113  }
114 
115  multimap&
116  operator=(initializer_list<value_type> __l)
117  {
118  this->clear();
119  this->insert(__l);
120  return *this;
121  }
122 #endif
123 
124  using _Base::get_allocator;
125 
126  // iterators:
127  iterator
128  begin() _GLIBCXX_NOEXCEPT
129  { return iterator(_Base::begin()); }
130 
131  const_iterator
132  begin() const _GLIBCXX_NOEXCEPT
133  { return const_iterator(_Base::begin()); }
134 
135  iterator
136  end() _GLIBCXX_NOEXCEPT
137  { return iterator(_Base::end()); }
138 
139  const_iterator
140  end() const _GLIBCXX_NOEXCEPT
141  { return const_iterator(_Base::end()); }
142 
143  reverse_iterator
144  rbegin() _GLIBCXX_NOEXCEPT
145  { return reverse_iterator(end()); }
146 
147  const_reverse_iterator
148  rbegin() const _GLIBCXX_NOEXCEPT
149  { return const_reverse_iterator(end()); }
150 
151  reverse_iterator
152  rend() _GLIBCXX_NOEXCEPT
153  { return reverse_iterator(begin()); }
154 
155  const_reverse_iterator
156  rend() const _GLIBCXX_NOEXCEPT
157  { return const_reverse_iterator(begin()); }
158 
159 #ifdef __GXX_EXPERIMENTAL_CXX0X__
160  const_iterator
161  cbegin() const noexcept
162  { return const_iterator(_Base::begin()); }
163 
164  const_iterator
165  cend() const noexcept
166  { return const_iterator(_Base::end()); }
167 
168  const_reverse_iterator
169  crbegin() const noexcept
170  { return const_reverse_iterator(end()); }
171 
172  const_reverse_iterator
173  crend() const noexcept
174  { return const_reverse_iterator(begin()); }
175 #endif
176 
177  // capacity:
178  using _Base::empty;
179  using _Base::size;
180  using _Base::max_size;
181 
182  // modifiers:
183  iterator
184  insert(const value_type& __x)
185  { return iterator(_Base::insert(__x)); }
186 
187 #ifdef __GXX_EXPERIMENTAL_CXX0X__
188  template<typename _Pair, typename = typename
189  std::enable_if<std::is_constructible<value_type,
190  _Pair&&>::value>::type>
191  iterator
192  insert(_Pair&& __x)
193  { return iterator(_Base::insert(std::forward<_Pair>(__x))); }
194 #endif
195 
196 #ifdef __GXX_EXPERIMENTAL_CXX0X__
197  void
198  insert(std::initializer_list<value_type> __list)
199  { _Base::insert(__list); }
200 #endif
201 
202  iterator
203 #ifdef __GXX_EXPERIMENTAL_CXX0X__
204  insert(const_iterator __position, const value_type& __x)
205 #else
206  insert(iterator __position, const value_type& __x)
207 #endif
208  { return iterator(_Base::insert(__position, __x)); }
209 
210 #ifdef __GXX_EXPERIMENTAL_CXX0X__
211  template<typename _Pair, typename = typename
212  std::enable_if<std::is_constructible<value_type,
213  _Pair&&>::value>::type>
214  iterator
215  insert(const_iterator __position, _Pair&& __x)
216  { return iterator(_Base::insert(__position,
217  std::forward<_Pair>(__x))); }
218 #endif
219 
220  template<typename _InputIterator>
221  void
222  insert(_InputIterator __first, _InputIterator __last)
223  { _Base::insert(__first, __last); }
224 
225 #ifdef __GXX_EXPERIMENTAL_CXX0X__
226  iterator
227  erase(const_iterator __position)
228  { return iterator(_Base::erase(__position)); }
229 
230  iterator
231  erase(iterator __position)
232  { return iterator(_Base::erase(__position)); }
233 #else
234  void
235  erase(iterator __position)
236  { _Base::erase(__position); }
237 #endif
238 
239  size_type
240  erase(const key_type& __x)
241  {
242  std::pair<iterator, iterator> __victims = this->equal_range(__x);
243  size_type __count = 0;
244  while (__victims.first != __victims.second)
245  {
246  iterator __victim = __victims.first++;
247  _Base::erase(__victim);
248  ++__count;
249  }
250  return __count;
251  }
252 
253 #ifdef __GXX_EXPERIMENTAL_CXX0X__
254  iterator
255  erase(const_iterator __first, const_iterator __last)
256  { return iterator(_Base::erase(__first, __last)); }
257 #else
258  void
259  erase(iterator __first, iterator __last)
260  { _Base::erase(__first, __last); }
261 #endif
262 
263  void
264  swap(multimap& __x)
265  { _Base::swap(__x); }
266 
267  void
268  clear() _GLIBCXX_NOEXCEPT
269  { this->erase(begin(), end()); }
270 
271  // observers:
272  using _Base::key_comp;
273  using _Base::value_comp;
274 
275  // 23.3.1.3 multimap operations:
276  iterator
277  find(const key_type& __x)
278  { return iterator(_Base::find(__x)); }
279 
280  const_iterator
281  find(const key_type& __x) const
282  { return const_iterator(_Base::find(__x)); }
283 
284  using _Base::count;
285 
286  iterator
287  lower_bound(const key_type& __x)
288  { return iterator(_Base::lower_bound(__x)); }
289 
290  const_iterator
291  lower_bound(const key_type& __x) const
292  { return const_iterator(_Base::lower_bound(__x)); }
293 
294  iterator
295  upper_bound(const key_type& __x)
296  { return iterator(_Base::upper_bound(__x)); }
297 
298  const_iterator
299  upper_bound(const key_type& __x) const
300  { return const_iterator(_Base::upper_bound(__x)); }
301 
302  std::pair<iterator,iterator>
303  equal_range(const key_type& __x)
304  {
305  typedef typename _Base::iterator _Base_iterator;
306  std::pair<_Base_iterator, _Base_iterator> __res =
307  _Base::equal_range(__x);
308  return std::make_pair(iterator(__res.first),
309  iterator(__res.second));
310  }
311 
312  std::pair<const_iterator,const_iterator>
313  equal_range(const key_type& __x) const
314  {
315  typedef typename _Base::const_iterator _Base_const_iterator;
316  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
317  _Base::equal_range(__x);
318  return std::make_pair(const_iterator(__res.first),
319  const_iterator(__res.second));
320  }
321 
322  _Base&
323  _M_base() _GLIBCXX_NOEXCEPT { return *this; }
324 
325  const _Base&
326  _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
327  };
328 
329  template<typename _Key, typename _Tp,
330  typename _Compare, typename _Allocator>
331  inline bool
332  operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
333  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
334  { return __lhs._M_base() == __rhs._M_base(); }
335 
336  template<typename _Key, typename _Tp,
337  typename _Compare, typename _Allocator>
338  inline bool
339  operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
340  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
341  { return __lhs._M_base() != __rhs._M_base(); }
342 
343  template<typename _Key, typename _Tp,
344  typename _Compare, typename _Allocator>
345  inline bool
346  operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
347  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
348  { return __lhs._M_base() < __rhs._M_base(); }
349 
350  template<typename _Key, typename _Tp,
351  typename _Compare, typename _Allocator>
352  inline bool
353  operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
354  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
355  { return __lhs._M_base() <= __rhs._M_base(); }
356 
357  template<typename _Key, typename _Tp,
358  typename _Compare, typename _Allocator>
359  inline bool
360  operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
361  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
362  { return __lhs._M_base() >= __rhs._M_base(); }
363 
364  template<typename _Key, typename _Tp,
365  typename _Compare, typename _Allocator>
366  inline bool
367  operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
368  const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
369  { return __lhs._M_base() > __rhs._M_base(); }
370 
371  template<typename _Key, typename _Tp,
372  typename _Compare, typename _Allocator>
373  inline void
374  swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
375  multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
376  { __lhs.swap(__rhs); }
377 
378 } // namespace __profile
379 } // namespace std
380 
381 #endif
std::initializer_list
initializer_list
Definition: initializer_list:47
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:93
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:94
std::is_constructible
is_constructible
Definition: type_traits:916
std::enable_if
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:1718
std::count
size_t count() const _GLIBCXX_NOEXCEPT
Returns the number of bits which are set.
Definition: bitset:1279
std::multimap
A standard container made up of (key,value) pairs, which can be retrieved based on a key...
Definition: stl_multimap.h:90
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:88
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:268
std::is_nothrow_copy_constructible
is_nothrow_copy_constructible
Definition: type_traits:1021
std::__profile::multimap
Class std::multimap wrapper with performance instrumentation.
Definition: profile/multimap.h:41
std::size
constexpr size_t size() const _GLIBCXX_NOEXCEPT
Returns the total number of bits.
Definition: bitset:1284