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