libstdc++
profile/map.h
Go to the documentation of this file.
1 // Profiling map 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 along
21 // with this library; see the file COPYING3. If not see
22 // <http://www.gnu.org/licenses/>.
23 
24 /** @file profile/map.h
25  * This file is a GNU profile extension to the Standard C++ Library.
26  */
27 
28 #ifndef _GLIBCXX_PROFILE_MAP_H
29 #define _GLIBCXX_PROFILE_MAP_H 1
30 
31 #include <utility>
32 #include <profile/base.h>
33 
34 namespace std _GLIBCXX_VISIBILITY(default)
35 {
36 namespace __profile
37 {
38  /// Class std::map 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 map
42  : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>
43  {
44  typedef _GLIBCXX_STD_C::map<_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::size_type size_type;
59  typedef typename _Base::difference_type difference_type;
60  typedef typename _Base::pointer pointer;
61  typedef typename _Base::const_pointer const_pointer;
62  typedef std::reverse_iterator<iterator> reverse_iterator;
63  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
64 
65  // 23.3.1.1 construct/copy/destroy:
66  explicit
67  map(const _Compare& __comp = _Compare(),
68  const _Allocator& __a = _Allocator())
69  : _Base(__comp, __a)
70  { __profcxx_map_to_unordered_map_construct(this); }
71 
72  template<typename _InputIterator>
73  map(_InputIterator __first, _InputIterator __last,
74  const _Compare& __comp = _Compare(),
75  const _Allocator& __a = _Allocator())
76  : _Base(__first, __last, __comp, __a)
77  { __profcxx_map_to_unordered_map_construct(this); }
78 
79  map(const map& __x)
80  : _Base(__x)
81  { __profcxx_map_to_unordered_map_construct(this); }
82 
83  map(const _Base& __x)
84  : _Base(__x)
85  { __profcxx_map_to_unordered_map_construct(this); }
86 
87 #ifdef __GXX_EXPERIMENTAL_CXX0X__
88  map(map&& __x)
89  : _Base(std::move(__x))
90  { }
91 
92  map(initializer_list<value_type> __l,
93  const _Compare& __c = _Compare(),
94  const allocator_type& __a = allocator_type())
95  : _Base(__l, __c, __a) { }
96 #endif
97 
98  ~map()
99  { __profcxx_map_to_unordered_map_destruct(this); }
100 
101  map&
102  operator=(const map& __x)
103  {
104  *static_cast<_Base*>(this) = __x;
105  return *this;
106  }
107 
108 #ifdef __GXX_EXPERIMENTAL_CXX0X__
109  map&
110  operator=(map&& __x)
111  {
112  // NB: DR 1204.
113  // NB: DR 675.
114  this->clear();
115  this->swap(__x);
116  return *this;
117  }
118 
119  map&
120  operator=(initializer_list<value_type> __l)
121  {
122  this->clear();
123  this->insert(__l);
124  return *this;
125  }
126 #endif
127 
128  // _GLIBCXX_RESOLVE_LIB_DEFECTS
129  // 133. map missing get_allocator()
130  using _Base::get_allocator;
131 
132  // iterators:
133  iterator
134  begin()
135  { return _Base::begin(); }
136 
137  const_iterator
138  begin() const
139  { return _Base::begin(); }
140 
141  iterator
142  end()
143  { return _Base::end(); }
144 
145  const_iterator
146  end() const
147  { return _Base::end(); }
148 
149  reverse_iterator
150  rbegin()
151  {
152  __profcxx_map_to_unordered_map_invalidate(this);
153  return reverse_iterator(end());
154  }
155 
156  const_reverse_iterator
157  rbegin() const
158  {
159  __profcxx_map_to_unordered_map_invalidate(this);
160  return const_reverse_iterator(end());
161  }
162 
163  reverse_iterator
164  rend()
165  {
166  __profcxx_map_to_unordered_map_invalidate(this);
167  return reverse_iterator(begin());
168  }
169 
170  const_reverse_iterator
171  rend() const
172  {
173  __profcxx_map_to_unordered_map_invalidate(this);
174  return const_reverse_iterator(begin());
175  }
176 
177 #ifdef __GXX_EXPERIMENTAL_CXX0X__
178  const_iterator
179  cbegin() const
180  { return const_iterator(_Base::begin()); }
181 
182  const_iterator
183  cend() const
184  { return const_iterator(_Base::end()); }
185 
186  const_reverse_iterator
187  crbegin() const
188  {
189  __profcxx_map_to_unordered_map_invalidate(this);
190  return const_reverse_iterator(end());
191  }
192 
193  const_reverse_iterator
194  crend() const
195  {
196  __profcxx_map_to_unordered_map_invalidate(this);
197  return const_reverse_iterator(begin());
198  }
199 #endif
200 
201  // capacity:
202  using _Base::empty;
203  using _Base::size;
204  using _Base::max_size;
205 
206  // 23.3.1.2 element access:
207  mapped_type&
208  operator[](const key_type& __k)
209  {
210  __profcxx_map_to_unordered_map_find(this, size());
211  return _Base::operator[](__k);
212  }
213 
214 #ifdef __GXX_EXPERIMENTAL_CXX0X__
215  mapped_type&
216  operator[](key_type&& __k)
217  {
218  __profcxx_map_to_unordered_map_find(this, size());
219  return _Base::operator[](std::move(__k));
220  }
221 #endif
222 
223  mapped_type&
224  at(const key_type& __k)
225  {
226  __profcxx_map_to_unordered_map_find(this, size());
227  return _Base::at(__k);
228  }
229 
230  const mapped_type&
231  at(const key_type& __k) const
232  {
233  __profcxx_map_to_unordered_map_find(this, size());
234  return _Base::at(__k);
235  }
236 
237  // modifiers:
238  std::pair<iterator, bool>
239  insert(const value_type& __x)
240  {
241  __profcxx_map_to_unordered_map_insert(this, size(), 1);
242  typedef typename _Base::iterator _Base_iterator;
243  std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
244  return std::pair<iterator, bool>(iterator(__res.first),
245  __res.second);
246  }
247 
248 #ifdef __GXX_EXPERIMENTAL_CXX0X__
249  template<typename _Pair, typename = typename
250  std::enable_if<std::is_convertible<_Pair,
251  value_type>::value>::type>
252  std::pair<iterator, bool>
253  insert(_Pair&& __x)
254  {
255  __profcxx_map_to_unordered_map_insert(this, size(), 1);
256  typedef typename _Base::iterator _Base_iterator;
257  std::pair<_Base_iterator, bool> __res
258  = _Base::insert(std::forward<_Pair>(__x));
259  return std::pair<iterator, bool>(iterator(__res.first),
260  __res.second);
261  }
262 #endif
263 
264 #ifdef __GXX_EXPERIMENTAL_CXX0X__
265  void
266  insert(std::initializer_list<value_type> __list)
267  {
268  size_type size_before = size();
269  _Base::insert(__list);
270  __profcxx_map_to_unordered_map_insert(this, size_before,
271  size() - size_before);
272  }
273 #endif
274 
275  iterator
276 #ifdef __GXX_EXPERIMENTAL_CXX0X__
277  insert(const_iterator __position, const value_type& __x)
278 #else
279  insert(iterator __position, const value_type& __x)
280 #endif
281  {
282  size_type size_before = size();
283  iterator __i = iterator(_Base::insert(__position, __x));
284  __profcxx_map_to_unordered_map_insert(this, size_before,
285  size() - size_before);
286  return __i;
287  }
288 
289 #ifdef __GXX_EXPERIMENTAL_CXX0X__
290  template<typename _Pair, typename = typename
291  std::enable_if<std::is_convertible<_Pair,
292  value_type>::value>::type>
293  iterator
294  insert(const_iterator __position, _Pair&& __x)
295  {
296  size_type size_before = size();
297  iterator __i
298  = iterator(_Base::insert(__position, std::forward<_Pair>(__x)));
299  __profcxx_map_to_unordered_map_insert(this, size_before,
300  size() - size_before);
301  return __i;
302  }
303 #endif
304 
305  template<typename _InputIterator>
306  void
307  insert(_InputIterator __first, _InputIterator __last)
308  {
309  size_type size_before = size();
310  _Base::insert(__first, __last);
311  __profcxx_map_to_unordered_map_insert(this, size_before,
312  size() - size_before);
313  }
314 
315 #ifdef __GXX_EXPERIMENTAL_CXX0X__
316  iterator
317  erase(const_iterator __position)
318  {
319  iterator __i = _Base::erase(__position);
320  __profcxx_map_to_unordered_map_erase(this, size(), 1);
321  return __i;
322  }
323 
324  iterator
325  erase(iterator __position)
326  { return erase(const_iterator(__position)); }
327 #else
328  void
329  erase(iterator __position)
330  {
331  _Base::erase(__position);
332  __profcxx_map_to_unordered_map_erase(this, size(), 1);
333  }
334 #endif
335 
336  size_type
337  erase(const key_type& __x)
338  {
339  iterator __victim = find(__x);
340  if (__victim == end())
341  return 0;
342  else
343  {
344  _Base::erase(__victim);
345  return 1;
346  }
347  }
348 
349 #ifdef __GXX_EXPERIMENTAL_CXX0X__
350  iterator
351  erase(const_iterator __first, const_iterator __last)
352  { return iterator(_Base::erase(__first, __last)); }
353 #else
354  void
355  erase(iterator __first, iterator __last)
356  { _Base::erase(__first, __last); }
357 #endif
358 
359  void
360 
361  swap(map& __x)
362  { _Base::swap(__x); }
363 
364  void
365  clear()
366  { this->erase(begin(), end()); }
367 
368  // observers:
369  using _Base::key_comp;
370  using _Base::value_comp;
371 
372  // 23.3.1.3 map operations:
373  iterator
374  find(const key_type& __x)
375  {
376  __profcxx_map_to_unordered_map_find(this, size());
377  return iterator(_Base::find(__x));
378  }
379 
380  const_iterator
381  find(const key_type& __x) const
382  {
383  __profcxx_map_to_unordered_map_find(this, size());
384  return const_iterator(_Base::find(__x));
385  }
386 
387  size_type
388  count(const key_type& __x) const
389  {
390  __profcxx_map_to_unordered_map_find(this, size());
391  return _Base::count(__x);
392  }
393 
394  iterator
395  lower_bound(const key_type& __x)
396  {
397  __profcxx_map_to_unordered_map_invalidate(this);
398  return iterator(_Base::lower_bound(__x));
399  }
400 
401  const_iterator
402  lower_bound(const key_type& __x) const
403  {
404  __profcxx_map_to_unordered_map_invalidate(this);
405  return const_iterator(_Base::lower_bound(__x));
406  }
407 
408  iterator
409  upper_bound(const key_type& __x)
410  {
411  __profcxx_map_to_unordered_map_invalidate(this);
412  return iterator(_Base::upper_bound(__x));
413  }
414 
415  const_iterator
416  upper_bound(const key_type& __x) const
417  {
418  __profcxx_map_to_unordered_map_invalidate(this);
419  return const_iterator(_Base::upper_bound(__x));
420  }
421 
422  std::pair<iterator,iterator>
423  equal_range(const key_type& __x)
424  {
425  typedef typename _Base::iterator _Base_iterator;
426  std::pair<_Base_iterator, _Base_iterator> __res =
427  _Base::equal_range(__x);
428  return std::make_pair(iterator(__res.first),
429  iterator(__res.second));
430  }
431 
432  std::pair<const_iterator,const_iterator>
433  equal_range(const key_type& __x) const
434  {
435  __profcxx_map_to_unordered_map_find(this, size());
436  typedef typename _Base::const_iterator _Base_const_iterator;
437  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
438  _Base::equal_range(__x);
439  return std::make_pair(const_iterator(__res.first),
440  const_iterator(__res.second));
441  }
442 
443  _Base&
444  _M_base() { return *this; }
445 
446  const _Base&
447  _M_base() const { return *this; }
448 
449  };
450 
451  template<typename _Key, typename _Tp,
452  typename _Compare, typename _Allocator>
453  inline bool
454  operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
455  const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
456  {
457  __profcxx_map_to_unordered_map_invalidate(&__lhs);
458  __profcxx_map_to_unordered_map_invalidate(&__rhs);
459  return __lhs._M_base() == __rhs._M_base();
460  }
461 
462  template<typename _Key, typename _Tp,
463  typename _Compare, typename _Allocator>
464  inline bool
465  operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
466  const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
467  {
468  __profcxx_map_to_unordered_map_invalidate(&__lhs);
469  __profcxx_map_to_unordered_map_invalidate(&__rhs);
470  return __lhs._M_base() != __rhs._M_base();
471  }
472 
473  template<typename _Key, typename _Tp,
474  typename _Compare, typename _Allocator>
475  inline bool
476  operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
477  const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
478  {
479  __profcxx_map_to_unordered_map_invalidate(&__lhs);
480  __profcxx_map_to_unordered_map_invalidate(&__rhs);
481  return __lhs._M_base() < __rhs._M_base();
482  }
483 
484  template<typename _Key, typename _Tp,
485  typename _Compare, typename _Allocator>
486  inline bool
487  operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
488  const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
489  {
490  __profcxx_map_to_unordered_map_invalidate(&__lhs);
491  __profcxx_map_to_unordered_map_invalidate(&__rhs);
492  return __lhs._M_base() <= __rhs._M_base();
493  }
494 
495  template<typename _Key, typename _Tp,
496  typename _Compare, typename _Allocator>
497  inline bool
498  operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
499  const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
500  {
501  __profcxx_map_to_unordered_map_invalidate(&__lhs);
502  __profcxx_map_to_unordered_map_invalidate(&__rhs);
503  return __lhs._M_base() >= __rhs._M_base();
504  }
505 
506  template<typename _Key, typename _Tp,
507  typename _Compare, typename _Allocator>
508  inline bool
509  operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
510  const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
511  {
512  __profcxx_map_to_unordered_map_invalidate(&__lhs);
513  __profcxx_map_to_unordered_map_invalidate(&__rhs);
514  return __lhs._M_base() > __rhs._M_base();
515  }
516 
517  template<typename _Key, typename _Tp,
518  typename _Compare, typename _Allocator>
519  inline void
520  swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
521  map<_Key, _Tp, _Compare, _Allocator>& __rhs)
522  { __lhs.swap(__rhs); }
523 
524 } // namespace __profile
525 } // namespace std
526 
527 #endif