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