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