1 // Profiling map implementation -*- C++ -*-
3 // Copyright (C) 2009-2014 Free Software Foundation, Inc.
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)
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.
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.
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/>.
24 /** @file profile/map.h
25 * This file is a GNU profile extension to the Standard C++ Library.
28 #ifndef _GLIBCXX_PROFILE_MAP_H
29 #define _GLIBCXX_PROFILE_MAP_H 1
31 #include <profile/base.h>
32 #include <profile/ordered_base.h>
34 namespace std
_GLIBCXX_VISIBILITY(default)
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
> > >
42 : public _GLIBCXX_STD_C::map
<_Key
, _Tp
, _Compare
, _Allocator
>,
43 public _Ordered_profile
<map
<_Key
, _Tp
, _Compare
, _Allocator
> >
45 typedef _GLIBCXX_STD_C::map
<_Key
, _Tp
, _Compare
, _Allocator
> _Base
;
49 typedef _Key key_type
;
50 typedef _Tp mapped_type
;
51 typedef typename
_Base::value_type value_type
;
52 typedef _Compare key_compare
;
53 typedef typename
_Base::reference reference
;
54 typedef typename
_Base::const_reference const_reference
;
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::reverse_iterator reverse_iterator
;
61 typedef typename
_Base::const_reverse_iterator const_reverse_iterator
;
63 // 23.3.1.1 construct/copy/destroy:
65 #if __cplusplus < 201103L
74 map(const map
&) = default;
80 map(const _Compare
& __comp
,
81 const _Allocator
& __a
= _Allocator())
82 : _Base(__comp
, __a
) { }
84 #if __cplusplus >= 201103L
85 template<typename _InputIterator
,
86 typename
= std::_RequireInputIter
<_InputIterator
>>
88 template<typename _InputIterator
>
90 map(_InputIterator __first
, _InputIterator __last
,
91 const _Compare
& __comp
= _Compare(),
92 const _Allocator
& __a
= _Allocator())
93 : _Base(__first
, __last
, __comp
, __a
) { }
98 #if __cplusplus >= 201103L
99 map(initializer_list
<value_type
> __l
,
100 const _Compare
& __c
= _Compare(),
101 const _Allocator
& __a
= _Allocator())
102 : _Base(__l
, __c
, __a
) { }
105 map(const _Allocator
& __a
)
108 map(const map
& __x
, const _Allocator
& __a
)
109 : _Base(__x
, __a
) { }
111 map(map
&& __x
, const _Allocator
& __a
)
112 noexcept( noexcept(_Base(std::move(__x
), __a
)) )
113 : _Base(std::move(__x
), __a
) { }
115 map(initializer_list
<value_type
> __l
, const _Allocator
& __a
)
116 : _Base(__l
, __a
) { }
118 template<typename _InputIterator
>
119 map(_InputIterator __first
, _InputIterator __last
,
120 const _Allocator
& __a
)
121 : _Base(__first
, __last
, __a
) { }
124 #if __cplusplus < 201103L
126 operator=(const map
& __x
)
133 operator=(const map
&) = default;
136 operator=(map
&&) = default;
139 operator=(initializer_list
<value_type
> __l
)
147 rbegin() _GLIBCXX_NOEXCEPT
149 __profcxx_map_to_unordered_map_invalidate(this);
150 return _Base::rbegin();
153 const_reverse_iterator
154 rbegin() const _GLIBCXX_NOEXCEPT
156 __profcxx_map_to_unordered_map_invalidate(this);
157 return _Base::rbegin();
161 rend() _GLIBCXX_NOEXCEPT
163 __profcxx_map_to_unordered_map_invalidate(this);
164 return _Base::rend();
167 const_reverse_iterator
168 rend() const _GLIBCXX_NOEXCEPT
170 __profcxx_map_to_unordered_map_invalidate(this);
171 return _Base::rend();
174 #if __cplusplus >= 201103L
175 const_reverse_iterator
176 crbegin() const noexcept
178 __profcxx_map_to_unordered_map_invalidate(this);
179 return _Base::crbegin();
182 const_reverse_iterator
183 crend() const noexcept
185 __profcxx_map_to_unordered_map_invalidate(this);
186 return _Base::crend();
190 // 23.3.1.2 element access:
192 operator[](const key_type
& __k
)
194 __profcxx_map_to_unordered_map_find(this, this->size());
195 return _Base::operator[](__k
);
198 #if __cplusplus >= 201103L
200 operator[](key_type
&& __k
)
202 __profcxx_map_to_unordered_map_find(this, this->size());
203 return _Base::operator[](std::move(__k
));
208 at(const key_type
& __k
)
210 __profcxx_map_to_unordered_map_find(this, this->size());
211 return _Base::at(__k
);
215 at(const key_type
& __k
) const
217 __profcxx_map_to_unordered_map_find(this, this->size());
218 return _Base::at(__k
);
222 #if __cplusplus >= 201103L
223 template<typename
... _Args
>
224 std::pair
<iterator
, bool>
225 emplace(_Args
&&... __args
)
227 // The cost is the same whether or not the element is inserted so we
228 // always report insertion of 1 element.
229 __profcxx_map_to_unordered_map_insert(this, this->size(), 1);
230 return _Base::emplace(std::forward
<_Args
>(__args
)...);
233 template<typename
... _Args
>
235 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
237 auto size_before
= this->size();
238 auto __res
= _Base::emplace_hint(__pos
, std::forward
<_Args
>(__args
)...);
239 __profcxx_map_to_unordered_map_insert(this, size_before
,
240 _M_hint_used(__pos
, __res
) ? 0 : 1);
245 std::pair
<iterator
, bool>
246 insert(const value_type
& __x
)
248 __profcxx_map_to_unordered_map_insert(this, this->size(), 1);
249 return _Base::insert(__x
);
252 #if __cplusplus >= 201103L
253 template<typename _Pair
, typename
= typename
254 std::enable_if
<std::is_constructible
<value_type
,
255 _Pair
&&>::value
>::type
>
256 std::pair
<iterator
, bool>
259 __profcxx_map_to_unordered_map_insert(this, this->size(), 1);
260 return _Base::insert(std::forward
<_Pair
>(__x
));
264 #if __cplusplus >= 201103L
266 insert(std::initializer_list
<value_type
> __list
)
267 { insert(__list
.begin(), __list
.end()); }
271 #if __cplusplus >= 201103L
272 insert(const_iterator __pos
, const value_type
& __x
)
274 insert(iterator __pos
, const value_type
& __x
)
277 size_type size_before
= this->size();
278 iterator __res
= _Base::insert(__pos
, __x
);
280 __profcxx_map_to_unordered_map_insert(this, size_before
,
281 _M_hint_used(__pos
, __res
) ? 0 : 1);
285 #if __cplusplus >= 201103L
286 template<typename _Pair
, typename
= typename
287 std::enable_if
<std::is_constructible
<value_type
,
288 _Pair
&&>::value
>::type
>
290 insert(const_iterator __pos
, _Pair
&& __x
)
292 size_type size_before
= this->size();
293 auto __res
= _Base::insert(__pos
, std::forward
<_Pair
>(__x
));
295 __profcxx_map_to_unordered_map_insert(this, size_before
,
296 _M_hint_used(__pos
, __res
) ? 0 : 1);
301 #if __cplusplus >= 201103L
302 template<typename _InputIterator
,
303 typename
= std::_RequireInputIter
<_InputIterator
>>
305 template<typename _InputIterator
>
308 insert(_InputIterator __first
, _InputIterator __last
)
310 for (; __first
!= __last
; ++__first
)
314 #if __cplusplus >= 201103L
316 erase(const_iterator __position
)
318 __profcxx_map_to_unordered_map_erase(this, this->size(), 1);
319 return _Base::erase(__position
);
323 erase(iterator __position
)
325 __profcxx_map_to_unordered_map_erase(this, this->size(), 1);
326 return _Base::erase(__position
);
330 erase(iterator __position
)
332 __profcxx_map_to_unordered_map_erase(this, this->size(), 1);
333 _Base::erase(__position
);
338 erase(const key_type
& __x
)
340 __profcxx_map_to_unordered_map_find(this, this->size());
341 __profcxx_map_to_unordered_map_erase(this, this->size(), 1);
342 return _Base::erase(__x
);
345 #if __cplusplus >= 201103L
347 erase(const_iterator __first
, const_iterator __last
)
349 if (__first
!= __last
)
352 for (; __first
!= __last
;)
353 __ret
= erase(__first
++);
357 return _Base::erase(__first
, __last
);
361 erase(iterator __first
, iterator __last
)
363 for (; __first
!= __last
;)
370 #if __cplusplus >= 201103L
371 noexcept( noexcept(declval
<_Base
>().swap(__x
)) )
373 { _Base::swap(__x
); }
375 // 23.3.1.3 map operations:
377 find(const key_type
& __x
)
379 __profcxx_map_to_unordered_map_find(this, this->size());
380 return _Base::find(__x
);
384 find(const key_type
& __x
) const
386 __profcxx_map_to_unordered_map_find(this, this->size());
387 return _Base::find(__x
);
391 count(const key_type
& __x
) const
393 __profcxx_map_to_unordered_map_find(this, this->size());
394 return _Base::count(__x
);
398 lower_bound(const key_type
& __x
)
400 __profcxx_map_to_unordered_map_find(this, this->size());
401 __profcxx_map_to_unordered_map_invalidate(this);
402 return _Base::lower_bound(__x
);
406 lower_bound(const key_type
& __x
) const
408 __profcxx_map_to_unordered_map_find(this, this->size());
409 __profcxx_map_to_unordered_map_invalidate(this);
410 return _Base::lower_bound(__x
);
414 upper_bound(const key_type
& __x
)
416 __profcxx_map_to_unordered_map_find(this, this->size());
417 __profcxx_map_to_unordered_map_invalidate(this);
418 return _Base::upper_bound(__x
);
422 upper_bound(const key_type
& __x
) const
424 __profcxx_map_to_unordered_map_find(this, this->size());
425 __profcxx_map_to_unordered_map_invalidate(this);
426 return _Base::upper_bound(__x
);
429 std::pair
<iterator
,iterator
>
430 equal_range(const key_type
& __x
)
432 __profcxx_map_to_unordered_map_find(this, this->size());
433 return _Base::equal_range(__x
);
436 std::pair
<const_iterator
,const_iterator
>
437 equal_range(const key_type
& __x
) const
439 __profcxx_map_to_unordered_map_find(this, this->size());
440 return _Base::equal_range(__x
);
444 _M_base() _GLIBCXX_NOEXCEPT
{ return *this; }
447 _M_base() const _GLIBCXX_NOEXCEPT
{ return *this; }
450 /** If hint is used we consider that the map and unordered_map
451 * operations have equivalent insertion cost so we do not update metrics
453 * Note that to find out if hint has been used is libstdc++
454 * implementation dependent.
457 _M_hint_used(const_iterator __hint
, iterator __res
)
459 return (__hint
== __res
460 || (__hint
== this->end() && ++__res
== this->end())
461 || (__hint
!= this->end() && (++__hint
== __res
462 || ++__res
== --__hint
)));
466 template<typename _Key
, typename _Tp
,
467 typename _Compare
, typename _Allocator
>
469 operator==(const map
<_Key
, _Tp
, _Compare
, _Allocator
>& __lhs
,
470 const map
<_Key
, _Tp
, _Compare
, _Allocator
>& __rhs
)
472 __profcxx_map_to_unordered_map_invalidate(&__lhs
);
473 __profcxx_map_to_unordered_map_invalidate(&__rhs
);
474 return __lhs
._M_base() == __rhs
._M_base();
477 template<typename _Key
, typename _Tp
,
478 typename _Compare
, typename _Allocator
>
480 operator!=(const map
<_Key
, _Tp
, _Compare
, _Allocator
>& __lhs
,
481 const map
<_Key
, _Tp
, _Compare
, _Allocator
>& __rhs
)
483 __profcxx_map_to_unordered_map_invalidate(&__lhs
);
484 __profcxx_map_to_unordered_map_invalidate(&__rhs
);
485 return __lhs
._M_base() != __rhs
._M_base();
488 template<typename _Key
, typename _Tp
,
489 typename _Compare
, typename _Allocator
>
491 operator<(const map
<_Key
, _Tp
, _Compare
, _Allocator
>& __lhs
,
492 const map
<_Key
, _Tp
, _Compare
, _Allocator
>& __rhs
)
494 __profcxx_map_to_unordered_map_invalidate(&__lhs
);
495 __profcxx_map_to_unordered_map_invalidate(&__rhs
);
496 return __lhs
._M_base() < __rhs
._M_base();
499 template<typename _Key
, typename _Tp
,
500 typename _Compare
, typename _Allocator
>
502 operator<=(const map
<_Key
, _Tp
, _Compare
, _Allocator
>& __lhs
,
503 const map
<_Key
, _Tp
, _Compare
, _Allocator
>& __rhs
)
505 __profcxx_map_to_unordered_map_invalidate(&__lhs
);
506 __profcxx_map_to_unordered_map_invalidate(&__rhs
);
507 return __lhs
._M_base() <= __rhs
._M_base();
510 template<typename _Key
, typename _Tp
,
511 typename _Compare
, typename _Allocator
>
513 operator>=(const map
<_Key
, _Tp
, _Compare
, _Allocator
>& __lhs
,
514 const map
<_Key
, _Tp
, _Compare
, _Allocator
>& __rhs
)
516 __profcxx_map_to_unordered_map_invalidate(&__lhs
);
517 __profcxx_map_to_unordered_map_invalidate(&__rhs
);
518 return __lhs
._M_base() >= __rhs
._M_base();
521 template<typename _Key
, typename _Tp
,
522 typename _Compare
, typename _Allocator
>
524 operator>(const map
<_Key
, _Tp
, _Compare
, _Allocator
>& __lhs
,
525 const map
<_Key
, _Tp
, _Compare
, _Allocator
>& __rhs
)
527 __profcxx_map_to_unordered_map_invalidate(&__lhs
);
528 __profcxx_map_to_unordered_map_invalidate(&__rhs
);
529 return __lhs
._M_base() > __rhs
._M_base();
532 template<typename _Key
, typename _Tp
,
533 typename _Compare
, typename _Allocator
>
535 swap(map
<_Key
, _Tp
, _Compare
, _Allocator
>& __lhs
,
536 map
<_Key
, _Tp
, _Compare
, _Allocator
>& __rhs
)
537 { __lhs
.swap(__rhs
); }
539 } // namespace __profile