libstdc++
profile/map.h
Go to the documentation of this file.
1 // Profiling map 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 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;
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;
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)
90  : _Base(std::move(__x))
91  { }
92 
94  const _Compare& __c = _Compare(),
95  const allocator_type& __a = allocator_type())
96  : _Base(__l, __c, __a) { }
97 #endif
98 
99  ~map() _GLIBCXX_NOEXCEPT
100  { __profcxx_map_to_unordered_map_destruct(this); }
101 
102  map&
103  operator=(const map& __x)
104  {
105  *static_cast<_Base*>(this) = __x;
106  return *this;
107  }
108 
109 #ifdef __GXX_EXPERIMENTAL_CXX0X__
110  map&
111  operator=(map&& __x)
112  {
113  // NB: DR 1204.
114  // NB: DR 675.
115  this->clear();
116  this->swap(__x);
117  return *this;
118  }
119 
120  map&
121  operator=(initializer_list<value_type> __l)
122  {
123  this->clear();
124  this->insert(__l);
125  return *this;
126  }
127 #endif
128 
129  // _GLIBCXX_RESOLVE_LIB_DEFECTS
130  // 133. map missing get_allocator()
131  using _Base::get_allocator;
132 
133  // iterators:
134  iterator
135  begin() _GLIBCXX_NOEXCEPT
136  { return _Base::begin(); }
137 
138  const_iterator
139  begin() const _GLIBCXX_NOEXCEPT
140  { return _Base::begin(); }
141 
142  iterator
143  end() _GLIBCXX_NOEXCEPT
144  { return _Base::end(); }
145 
146  const_iterator
147  end() const _GLIBCXX_NOEXCEPT
148  { return _Base::end(); }
149 
151  rbegin() _GLIBCXX_NOEXCEPT
152  {
153  __profcxx_map_to_unordered_map_invalidate(this);
154  return reverse_iterator(end());
155  }
156 
158  rbegin() const _GLIBCXX_NOEXCEPT
159  {
160  __profcxx_map_to_unordered_map_invalidate(this);
161  return const_reverse_iterator(end());
162  }
163 
165  rend() _GLIBCXX_NOEXCEPT
166  {
167  __profcxx_map_to_unordered_map_invalidate(this);
168  return reverse_iterator(begin());
169  }
170 
172  rend() const _GLIBCXX_NOEXCEPT
173  {
174  __profcxx_map_to_unordered_map_invalidate(this);
175  return const_reverse_iterator(begin());
176  }
177 
178 #ifdef __GXX_EXPERIMENTAL_CXX0X__
179  const_iterator
180  cbegin() const noexcept
181  { return const_iterator(_Base::begin()); }
182 
183  const_iterator
184  cend() const noexcept
185  { return const_iterator(_Base::end()); }
186 
188  crbegin() const noexcept
189  {
190  __profcxx_map_to_unordered_map_invalidate(this);
191  return const_reverse_iterator(end());
192  }
193 
195  crend() const noexcept
196  {
197  __profcxx_map_to_unordered_map_invalidate(this);
198  return const_reverse_iterator(begin());
199  }
200 #endif
201 
202  // capacity:
203  using _Base::empty;
204  using _Base::size;
205  using _Base::max_size;
206 
207  // 23.3.1.2 element access:
208  mapped_type&
209  operator[](const key_type& __k)
210  {
211  __profcxx_map_to_unordered_map_find(this, size());
212  return _Base::operator[](__k);
213  }
214 
215 #ifdef __GXX_EXPERIMENTAL_CXX0X__
216  mapped_type&
217  operator[](key_type&& __k)
218  {
219  __profcxx_map_to_unordered_map_find(this, size());
220  return _Base::operator[](std::move(__k));
221  }
222 #endif
223 
224  mapped_type&
225  at(const key_type& __k)
226  {
227  __profcxx_map_to_unordered_map_find(this, size());
228  return _Base::at(__k);
229  }
230 
231  const mapped_type&
232  at(const key_type& __k) const
233  {
234  __profcxx_map_to_unordered_map_find(this, size());
235  return _Base::at(__k);
236  }
237 
238  // modifiers:
240  insert(const value_type& __x)
241  {
242  __profcxx_map_to_unordered_map_insert(this, size(), 1);
243  typedef typename _Base::iterator _Base_iterator;
244  std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
245  return std::pair<iterator, bool>(iterator(__res.first),
246  __res.second);
247  }
248 
249 #ifdef __GXX_EXPERIMENTAL_CXX0X__
250  template<typename _Pair, typename = typename
252  _Pair&&>::value>::type>
254  insert(_Pair&& __x)
255  {
256  __profcxx_map_to_unordered_map_insert(this, size(), 1);
257  typedef typename _Base::iterator _Base_iterator;
259  = _Base::insert(std::forward<_Pair>(__x));
260  return std::pair<iterator, bool>(iterator(__res.first),
261  __res.second);
262  }
263 #endif
264 
265 #ifdef __GXX_EXPERIMENTAL_CXX0X__
266  void
267  insert(std::initializer_list<value_type> __list)
268  {
269  size_type size_before = size();
270  _Base::insert(__list);
271  __profcxx_map_to_unordered_map_insert(this, size_before,
272  size() - size_before);
273  }
274 #endif
275 
276  iterator
277 #ifdef __GXX_EXPERIMENTAL_CXX0X__
278  insert(const_iterator __position, const value_type& __x)
279 #else
280  insert(iterator __position, const value_type& __x)
281 #endif
282  {
283  size_type size_before = size();
284  iterator __i = iterator(_Base::insert(__position, __x));
285  __profcxx_map_to_unordered_map_insert(this, size_before,
286  size() - size_before);
287  return __i;
288  }
289 
290 #ifdef __GXX_EXPERIMENTAL_CXX0X__
291  template<typename _Pair, typename = typename
293  _Pair&&>::value>::type>
294  iterator
295  insert(const_iterator __position, _Pair&& __x)
296  {
297  size_type size_before = size();
298  iterator __i
299  = iterator(_Base::insert(__position, std::forward<_Pair>(__x)));
300  __profcxx_map_to_unordered_map_insert(this, size_before,
301  size() - size_before);
302  return __i;
303  }
304 #endif
305 
306  template<typename _InputIterator>
307  void
308  insert(_InputIterator __first, _InputIterator __last)
309  {
310  size_type size_before = size();
311  _Base::insert(__first, __last);
312  __profcxx_map_to_unordered_map_insert(this, size_before,
313  size() - size_before);
314  }
315 
316 #ifdef __GXX_EXPERIMENTAL_CXX0X__
317  iterator
318  erase(const_iterator __position)
319  {
320  iterator __i = _Base::erase(__position);
321  __profcxx_map_to_unordered_map_erase(this, size(), 1);
322  return __i;
323  }
324 
325  iterator
326  erase(iterator __position)
327  { return erase(const_iterator(__position)); }
328 #else
329  void
330  erase(iterator __position)
331  {
332  _Base::erase(__position);
333  __profcxx_map_to_unordered_map_erase(this, size(), 1);
334  }
335 #endif
336 
337  size_type
338  erase(const key_type& __x)
339  {
340  iterator __victim = find(__x);
341  if (__victim == end())
342  return 0;
343  else
344  {
345  _Base::erase(__victim);
346  return 1;
347  }
348  }
349 
350 #ifdef __GXX_EXPERIMENTAL_CXX0X__
351  iterator
352  erase(const_iterator __first, const_iterator __last)
353  { return iterator(_Base::erase(__first, __last)); }
354 #else
355  void
356  erase(iterator __first, iterator __last)
357  { _Base::erase(__first, __last); }
358 #endif
359 
360  void
361  swap(map& __x)
362  { _Base::swap(__x); }
363 
364  void
365  clear() _GLIBCXX_NOEXCEPT
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 
423  equal_range(const key_type& __x)
424  {
425  typedef typename _Base::iterator _Base_iterator;
427  _Base::equal_range(__x);
428  return std::make_pair(iterator(__res.first),
429  iterator(__res.second));
430  }
431 
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;
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() _GLIBCXX_NOEXCEPT { return *this; }
445 
446  const _Base&
447  _M_base() const _GLIBCXX_NOEXCEPT { 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,
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,
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