1 // Profiling multimap implementation -*- C++ -*-
2
3 // Copyright (C) 2009-2014 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
_GLIBCXX_VISIBILITY(default)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 #if __cplusplus >= 201103L
47 typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits;
48 #endif
49
50 public:
51 // types:
52 typedef _Key key_type;
53 typedef _Tp mapped_type;
54 typedef std::pair<const _Key, _Tp> value_type;
55 typedef _Compare key_compare;
56 typedef _Allocator allocator_type;
57 typedef typename _Base::reference reference;
58 typedef typename _Base::const_reference const_reference;
59
60 typedef typename _Base::iterator iterator;
61 typedef typename _Base::const_iterator const_iterator;
62 typedef typename _Base::reverse_iterator reverse_iterator;
63 typedef typename _Base::const_reverse_iterator const_reverse_iterator;
64
65 typedef typename _Base::size_type size_type;
66 typedef typename _Base::difference_type difference_type;
67 typedef typename _Base::pointer pointer;
68 typedef typename _Base::const_pointer const_pointer;
69
70 // 23.3.1.1 construct/copy/destroy:
71
72 multimap()
73 : _Base() { }
74
75 explicit multimap(const _Compare& __comp,
76 const _Allocator& __a = _Allocator())
77 : _Base(__comp, __a) { }
78
79 #if __cplusplus >= 201103L
80 template<typename _InputIterator,
81 typename = std::_RequireInputIter<_InputIterator>>
82 #else
83 template<typename _InputIterator>
84 #endif
85 multimap(_InputIterator __first, _InputIterator __last,
86 const _Compare& __comp = _Compare(),
87 const _Allocator& __a = _Allocator())
88 : _Base(__first, __last, __comp, __a) { }
89
90 #if __cplusplus < 201103L
91 multimap(const multimap& __x)
92 : _Base(__x) { }
93 #else
94 multimap(const multimap&) = default;
95 multimap(multimap&&) = default;
96
97 multimap(initializer_list<value_type> __l,
98 const _Compare& __c = _Compare(),
99 const allocator_type& __a = allocator_type())
100 : _Base(__l, __c, __a) { }
101
102 explicit
103 multimap(const allocator_type& __a)
104 : _Base(__a) { }
105
106 multimap(const multimap& __x, const allocator_type& __a)
107 : _Base(__x, __a) { }
108
109 multimap(multimap&& __x, const allocator_type& __a)
110 noexcept(is_nothrow_copy_constructible<_Compare>::value
111 && _Alloc_traits::_S_always_equal())
112 : _Base(std::move(__x), __a) { }
113
114 multimap(initializer_list<value_type> __l, const allocator_type& __a)
115 : _Base(__l, __a) { }
116
117 template<typename _InputIterator>
118 multimap(_InputIterator __first, _InputIterator __last,
119 const allocator_type& __a)
120 : _Base(__first, __last, __a) { }
121 #endif
122
123 multimap(const _Base& __x)
124 : _Base(__x) { }
125
126 ~multimap() _GLIBCXX_NOEXCEPT { }
127
128 #if __cplusplus < 201103L
129 multimap&
130 operator=(const multimap& __x)
131 {
132 _M_base() = __x;
133 return *this;
134 }
135 #else
136 multimap&
137 operator=(const multimap&) = default;
138
139 multimap&
140 operator=(multimap&&) = default;
141
142 multimap&
143 operator=(initializer_list<value_type> __l)
144 {
145 _M_base() = __l;
146 return *this;
147 }
148 #endif
149
150 using _Base::get_allocator;
151
152 // iterators:
153 iterator
154 begin() _GLIBCXX_NOEXCEPT
155 { return iterator(_Base::begin()); }
156
157 const_iterator
158 begin() const _GLIBCXX_NOEXCEPT
159 { return const_iterator(_Base::begin()); }
160
161 iterator
162 end() _GLIBCXX_NOEXCEPT
163 { return iterator(_Base::end()); }
164
165 const_iterator
166 end() const _GLIBCXX_NOEXCEPT
167 { return const_iterator(_Base::end()); }
168
169 reverse_iterator
170 rbegin() _GLIBCXX_NOEXCEPT
171 { return reverse_iterator(end()); }
172
173 const_reverse_iterator
174 rbegin() const _GLIBCXX_NOEXCEPT
175 { return const_reverse_iterator(end()); }
176
177 reverse_iterator
178 rend() _GLIBCXX_NOEXCEPT
179 { return reverse_iterator(begin()); }
180
181 const_reverse_iterator
182 rend() const _GLIBCXX_NOEXCEPT
183 { return const_reverse_iterator(begin()); }
184
185 #if __cplusplus >= 201103L
186 const_iterator
187 cbegin() const noexcept
188 { return const_iterator(_Base::begin()); }
189
190 const_iterator
191 cend() const noexcept
192 { return const_iterator(_Base::end()); }
193
194 const_reverse_iterator
195 crbegin() const noexcept
196 { return const_reverse_iterator(end()); }
197
198 const_reverse_iterator
199 crend() const noexcept
200 { return const_reverse_iterator(begin()); }
201 #endif
202
203 // capacity:
204 using _Base::empty;
205 using _Base::size;
206 using _Base::max_size;
207
208 // modifiers:
209 #if __cplusplus >= 201103L
210 template<typename... _Args>
211 iterator
212 emplace(_Args&&... __args)
213 {
214 return iterator(_Base::emplace(std::forward<_Args>(__args)...));
215 }
216
217 template<typename... _Args>
218 iterator
219 emplace_hint(const_iterator __pos, _Args&&... __args)
220 {
221 return iterator(_Base::emplace_hint(__pos,
222 std::forward<_Args>(__args)...));
223 }
224 #endif
225
226 iterator
227 insert(const value_type& __x)
228 { return iterator(_Base::insert(__x)); }
229
230 #if __cplusplus >= 201103L
231 template<typename _Pair, typename = typename
232 std::enable_if<std::is_constructible<value_type,
233 _Pair&&>::value>::type>
234 iterator
235 insert(_Pair&& __x)
236 { return iterator(_Base::insert(std::forward<_Pair>(__x))); }
237 #endif
238
239 #if __cplusplus >= 201103L
240 void
241 insert(std::initializer_list<value_type> __list)
242 { _Base::insert(__list); }
243 #endif
244
245 iterator
246 #if __cplusplus >= 201103L
247 insert(const_iterator __position, const value_type& __x)
248 #else
249 insert(iterator __position, const value_type& __x)
250 #endif
251 { return iterator(_Base::insert(__position, __x)); }
252
253 #if __cplusplus >= 201103L
254 template<typename _Pair, typename = typename
255 std::enable_if<std::is_constructible<value_type,
256 _Pair&&>::value>::type>
257 iterator
258 insert(const_iterator __position, _Pair&& __x)
259 { return iterator(_Base::insert(__position,
260 std::forward<_Pair>(__x))); }
261 #endif
262
263 #if __cplusplus >= 201103L
264 template<typename _InputIterator,
265 typename = std::_RequireInputIter<_InputIterator>>
266 #else
267 template<typename _InputIterator>
268 #endif
269 void
270 insert(_InputIterator __first, _InputIterator __last)
271 { _Base::insert(__first, __last); }
272
273 #if __cplusplus >= 201103L
274 iterator
275 erase(const_iterator __position)
276 { return iterator(_Base::erase(__position)); }
277
278 iterator
279 erase(iterator __position)
280 { return iterator(_Base::erase(__position)); }
281 #else
282 void
283 erase(iterator __position)
284 { _Base::erase(__position); }
285 #endif
286
287 size_type
288 erase(const key_type& __x)
289 {
290 std::pair<iterator, iterator> __victims = this->equal_range(__x);
291 size_type __count = 0;
292 while (__victims.first != __victims.second)
293 {
294 iterator __victim = __victims.first++;
295 _Base::erase(__victim);
296 ++__count;
297 }
298 return __count;
299 }
300
301 #if __cplusplus >= 201103L
302 iterator
303 erase(const_iterator __first, const_iterator __last)
304 { return iterator(_Base::erase(__first, __last)); }
305 #else
306 void
307 erase(iterator __first, iterator __last)
308 { _Base::erase(__first, __last); }
309 #endif
310
311 void
312 swap(multimap& __x)
313 #if __cplusplus >= 201103L
314 noexcept(_Alloc_traits::_S_nothrow_swap())
315 #endif
316 { _Base::swap(__x); }
317
318 void
319 clear() _GLIBCXX_NOEXCEPT
320 { this->erase(begin(), end()); }
321
322 // observers:
323 using _Base::key_comp;
324 using _Base::value_comp;
325
326 // 23.3.1.3 multimap operations:
327 iterator
328 find(const key_type& __x)
329 { return iterator(_Base::find(__x)); }
330
331 const_iterator
332 find(const key_type& __x) const
333 { return const_iterator(_Base::find(__x)); }
334
335 using _Base::count;
336
337 iterator
338 lower_bound(const key_type& __x)
339 { return iterator(_Base::lower_bound(__x)); }
340
341 const_iterator
342 lower_bound(const key_type& __x) const
343 { return const_iterator(_Base::lower_bound(__x)); }
344
345 iterator
346 upper_bound(const key_type& __x)
347 { return iterator(_Base::upper_bound(__x)); }
348
349 const_iterator
350 upper_bound(const key_type& __x) const
351 { return const_iterator(_Base::upper_bound(__x)); }
352
353 std::pair<iterator,iterator>
354 equal_range(const key_type& __x)
355 {
356 typedef typename _Base::iterator _Base_iterator;
357 std::pair<_Base_iterator, _Base_iterator> __res =
358 _Base::equal_range(__x);
359 return std::make_pair(iterator(__res.first),
360 iterator(__res.second));
361 }
362
363 std::pair<const_iterator,const_iterator>
364 equal_range(const key_type& __x) const
365 {
366 typedef typename _Base::const_iterator _Base_const_iterator;
367 std::pair<_Base_const_iterator, _Base_const_iterator> __res =
368 _Base::equal_range(__x);
369 return std::make_pair(const_iterator(__res.first),
370 const_iterator(__res.second));
371 }
372
373 _Base&
374 _M_base() _GLIBCXX_NOEXCEPT { return *this; }
375
376 const _Base&
377 _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
378 };
379
380 template<typename _Key, typename _Tp,
381 typename _Compare, typename _Allocator>
382 inline bool
383 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
384 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
385 { return __lhs._M_base() == __rhs._M_base(); }
386
387 template<typename _Key, typename _Tp,
388 typename _Compare, typename _Allocator>
389 inline bool
390 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
391 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
392 { return __lhs._M_base() != __rhs._M_base(); }
393
394 template<typename _Key, typename _Tp,
395 typename _Compare, typename _Allocator>
396 inline bool
397 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
398 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
399 { return __lhs._M_base() < __rhs._M_base(); }
400
401 template<typename _Key, typename _Tp,
402 typename _Compare, typename _Allocator>
403 inline bool
404 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
405 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
406 { return __lhs._M_base() <= __rhs._M_base(); }
407
408 template<typename _Key, typename _Tp,
409 typename _Compare, typename _Allocator>
410 inline bool
411 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
412 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
413 { return __lhs._M_base() >= __rhs._M_base(); }
414
415 template<typename _Key, typename _Tp,
416 typename _Compare, typename _Allocator>
417 inline bool
418 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
419 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
420 { return __lhs._M_base() > __rhs._M_base(); }
421
422 template<typename _Key, typename _Tp,
423 typename _Compare, typename _Allocator>
424 inline void
425 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
426 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
427 { __lhs.swap(__rhs); }
428
429 } // namespace __profile
430 } // namespace std
431
432 #endif
433