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