1// Debugging multimap implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011
4// Free Software Foundation, Inc.
5//
6// This file is part of the GNU ISO C++ Library.  This library is free
7// software; you can redistribute it and/or modify it under the
8// terms of the GNU General Public License as published by the
9// Free Software Foundation; either version 3, or (at your option)
10// any later version.
11
12// This library is distributed in the hope that it will be useful,
13// but WITHOUT ANY WARRANTY; without even the implied warranty of
14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15// GNU General Public License for more details.
16
17// Under Section 7 of GPL version 3, you are granted additional
18// permissions described in the GCC Runtime Library Exception, version
19// 3.1, as published by the Free Software Foundation.
20
21// You should have received a copy of the GNU General Public License and
22// a copy of the GCC Runtime Library Exception along with this program;
23// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24// <http://www.gnu.org/licenses/>.
25
26/** @file debug/multimap.h
27 *  This file is a GNU debug extension to the Standard C++ Library.
28 */
29
30#ifndef _GLIBCXX_DEBUG_MULTIMAP_H
31#define _GLIBCXX_DEBUG_MULTIMAP_H 1
32
33#include <debug/safe_sequence.h>
34#include <debug/safe_iterator.h>
35#include <utility>
36
37namespace std _GLIBCXX_VISIBILITY(default)
38{
39namespace __debug
40{
41  /// Class std::multimap with safety/checking/debug instrumentation.
42  template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
43	   typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > >
44    class multimap
45    : public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>,
46      public __gnu_debug::_Safe_sequence<multimap<_Key, _Tp,
47						  _Compare, _Allocator> >
48    {
49      typedef _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> _Base;
50      typedef __gnu_debug::_Safe_sequence<multimap> _Safe_base;
51
52      typedef typename _Base::const_iterator _Base_const_iterator;
53      typedef typename _Base::iterator _Base_iterator;
54      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
55    public:
56      // types:
57      typedef _Key				     key_type;
58      typedef _Tp				     mapped_type;
59      typedef std::pair<const _Key, _Tp>             value_type;
60      typedef _Compare                               key_compare;
61      typedef _Allocator                             allocator_type;
62      typedef typename _Base::reference              reference;
63      typedef typename _Base::const_reference        const_reference;
64
65      typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap>
66                                                     iterator;
67      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
68                                           multimap> const_iterator;
69
70      typedef typename _Base::size_type              size_type;
71      typedef typename _Base::difference_type        difference_type;
72      typedef typename _Base::pointer                pointer;
73      typedef typename _Base::const_pointer          const_pointer;
74      typedef std::reverse_iterator<iterator>        reverse_iterator;
75      typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
76
77      // 23.3.1.1 construct/copy/destroy:
78      explicit multimap(const _Compare& __comp = _Compare(),
79			const _Allocator& __a = _Allocator())
80      : _Base(__comp, __a) { }
81
82      template<typename _InputIterator>
83      multimap(_InputIterator __first, _InputIterator __last,
84	       const _Compare& __comp = _Compare(),
85	       const _Allocator& __a = _Allocator())
86	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
87								     __last)),
88		__gnu_debug::__base(__last),
89	      __comp, __a) { }
90
91      multimap(const multimap& __x)
92      : _Base(__x), _Safe_base() { }
93
94      multimap(const _Base& __x)
95      : _Base(__x), _Safe_base() { }
96
97#ifdef __GXX_EXPERIMENTAL_CXX0X__
98      multimap(multimap&& __x)
99      : _Base(std::move(__x)), _Safe_base()
100      { this->_M_swap(__x); }
101
102      multimap(initializer_list<value_type> __l,
103	       const _Compare& __c = _Compare(),
104	       const allocator_type& __a = allocator_type())
105      : _Base(__l, __c, __a), _Safe_base() { }
106#endif
107
108      ~multimap() { }
109
110      multimap&
111      operator=(const multimap& __x)
112      {
113	*static_cast<_Base*>(this) = __x;
114	this->_M_invalidate_all();
115	return *this;
116      }
117
118#ifdef __GXX_EXPERIMENTAL_CXX0X__
119      multimap&
120      operator=(multimap&& __x)
121      {
122	// NB: DR 1204.
123	// NB: DR 675.
124	clear();
125	swap(__x);
126	return *this;
127      }
128
129      multimap&
130      operator=(initializer_list<value_type> __l)
131      {
132	this->clear();
133	this->insert(__l);
134	return *this;
135      }
136#endif
137
138      using _Base::get_allocator;
139
140      // iterators:
141      iterator
142      begin()
143      { return iterator(_Base::begin(), this); }
144
145      const_iterator
146      begin() const
147      { return const_iterator(_Base::begin(), this); }
148
149      iterator
150      end()
151      { return iterator(_Base::end(), this); }
152
153      const_iterator
154      end() const
155      { return const_iterator(_Base::end(), this); }
156
157      reverse_iterator
158      rbegin()
159      { return reverse_iterator(end()); }
160
161      const_reverse_iterator
162      rbegin() const
163      { return const_reverse_iterator(end()); }
164
165      reverse_iterator
166      rend()
167      { return reverse_iterator(begin()); }
168
169      const_reverse_iterator
170      rend() const
171      { return const_reverse_iterator(begin()); }
172
173#ifdef __GXX_EXPERIMENTAL_CXX0X__
174      const_iterator
175      cbegin() const
176      { return const_iterator(_Base::begin(), this); }
177
178      const_iterator
179      cend() const
180      { return const_iterator(_Base::end(), this); }
181
182      const_reverse_iterator
183      crbegin() const
184      { return const_reverse_iterator(end()); }
185
186      const_reverse_iterator
187      crend() const
188      { return const_reverse_iterator(begin()); }
189#endif
190
191      // capacity:
192      using _Base::empty;
193      using _Base::size;
194      using _Base::max_size;
195
196      // modifiers:
197      iterator
198      insert(const value_type& __x)
199      { return iterator(_Base::insert(__x), this); }
200
201#ifdef __GXX_EXPERIMENTAL_CXX0X__
202      template<typename _Pair, typename = typename
203	       std::enable_if<std::is_convertible<_Pair,
204						  value_type>::value>::type>
205        iterator
206        insert(_Pair&& __x)
207        { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); }
208#endif
209
210#ifdef __GXX_EXPERIMENTAL_CXX0X__
211      void
212      insert(std::initializer_list<value_type> __list)
213      { _Base::insert(__list); }
214#endif
215
216      iterator
217#ifdef __GXX_EXPERIMENTAL_CXX0X__
218      insert(const_iterator __position, const value_type& __x)
219#else
220      insert(iterator __position, const value_type& __x)
221#endif
222      {
223	__glibcxx_check_insert(__position);
224	return iterator(_Base::insert(__position.base(), __x), this);
225      }
226
227#ifdef __GXX_EXPERIMENTAL_CXX0X__
228      template<typename _Pair, typename = typename
229	       std::enable_if<std::is_convertible<_Pair,
230						  value_type>::value>::type>
231        iterator
232        insert(const_iterator __position, _Pair&& __x)
233        {
234	  __glibcxx_check_insert(__position);
235	  return iterator(_Base::insert(__position.base(),
236					std::forward<_Pair>(__x)), this);
237	}
238#endif
239
240      template<typename _InputIterator>
241        void
242        insert(_InputIterator __first, _InputIterator __last)
243        {
244	  __glibcxx_check_valid_range(__first, __last);
245	  _Base::insert(__gnu_debug::__base(__first),
246			__gnu_debug::__base(__last));
247	}
248
249#ifdef __GXX_EXPERIMENTAL_CXX0X__
250      iterator
251      erase(const_iterator __position)
252      {
253	__glibcxx_check_erase(__position);
254	this->_M_invalidate_if(_Equal(__position.base()));
255	return iterator(_Base::erase(__position.base()), this);
256      }
257
258      iterator
259      erase(iterator __position)
260      { return erase(const_iterator(__position)); }
261#else
262      void
263      erase(iterator __position)
264      {
265	__glibcxx_check_erase(__position);
266	this->_M_invalidate_if(_Equal(__position.base()));
267	_Base::erase(__position.base());
268      }
269#endif
270
271      size_type
272      erase(const key_type& __x)
273      {
274	std::pair<_Base_iterator, _Base_iterator> __victims =
275	  _Base::equal_range(__x);
276	size_type __count = 0;
277	_Base_iterator __victim = __victims.first;
278	while (__victim !=  __victims.second)
279	  {
280	    this->_M_invalidate_if(_Equal(__victim));
281	    _Base::erase(__victim++);
282	    ++__count;
283	  }
284	return __count;
285      }
286
287#ifdef __GXX_EXPERIMENTAL_CXX0X__
288      iterator
289      erase(const_iterator __first, const_iterator __last)
290      {
291	// _GLIBCXX_RESOLVE_LIB_DEFECTS
292	// 151. can't currently clear() empty container
293	__glibcxx_check_erase_range(__first, __last);
294	for (_Base_const_iterator __victim = __first.base();
295	     __victim != __last.base(); ++__victim)
296	  {
297	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
298				  _M_message(__gnu_debug::__msg_valid_range)
299				  ._M_iterator(__first, "first")
300				  ._M_iterator(__last, "last"));
301	    this->_M_invalidate_if(_Equal(__victim));
302	  }
303	return iterator(_Base::erase(__first.base(), __last.base()), this);
304      }
305#else
306      void
307      erase(iterator __first, iterator __last)
308      {
309	// _GLIBCXX_RESOLVE_LIB_DEFECTS
310	// 151. can't currently clear() empty container
311	__glibcxx_check_erase_range(__first, __last);
312	for (_Base_iterator __victim = __first.base();
313	     __victim != __last.base(); ++__victim)
314	  {
315	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
316				  _M_message(__gnu_debug::__msg_valid_range)
317				  ._M_iterator(__first, "first")
318				  ._M_iterator(__last, "last"));
319	    this->_M_invalidate_if(_Equal(__victim));
320	  }
321	_Base::erase(__first.base(), __last.base());
322      }
323#endif
324
325      void
326      swap(multimap& __x)
327      {
328	_Base::swap(__x);
329	this->_M_swap(__x);
330      }
331
332      void
333      clear()
334      {
335	this->_M_invalidate_all();
336	_Base::clear();
337      }
338
339      // observers:
340      using _Base::key_comp;
341      using _Base::value_comp;
342
343      // 23.3.1.3 multimap operations:
344      iterator
345      find(const key_type& __x)
346      { return iterator(_Base::find(__x), this); }
347
348      const_iterator
349      find(const key_type& __x) const
350      { return const_iterator(_Base::find(__x), this); }
351
352      using _Base::count;
353
354      iterator
355      lower_bound(const key_type& __x)
356      { return iterator(_Base::lower_bound(__x), this); }
357
358      const_iterator
359      lower_bound(const key_type& __x) const
360      { return const_iterator(_Base::lower_bound(__x), this); }
361
362      iterator
363      upper_bound(const key_type& __x)
364      { return iterator(_Base::upper_bound(__x), this); }
365
366      const_iterator
367      upper_bound(const key_type& __x) const
368      { return const_iterator(_Base::upper_bound(__x), this); }
369
370      std::pair<iterator,iterator>
371      equal_range(const key_type& __x)
372      {
373	std::pair<_Base_iterator, _Base_iterator> __res =
374	_Base::equal_range(__x);
375	return std::make_pair(iterator(__res.first, this),
376			      iterator(__res.second, this));
377      }
378
379      std::pair<const_iterator,const_iterator>
380      equal_range(const key_type& __x) const
381      {
382	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
383	  _Base::equal_range(__x);
384	return std::make_pair(const_iterator(__res.first, this),
385			      const_iterator(__res.second, this));
386      }
387
388      _Base&
389      _M_base() { return *this; }
390
391      const _Base&
392      _M_base() const { return *this; }
393
394    private:
395      void
396      _M_invalidate_all()
397      {
398	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
399	this->_M_invalidate_if(_Not_equal(_Base::end()));
400      }
401    };
402
403  template<typename _Key, typename _Tp,
404	   typename _Compare, typename _Allocator>
405    inline bool
406    operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
407	       const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
408    { return __lhs._M_base() == __rhs._M_base(); }
409
410  template<typename _Key, typename _Tp,
411	   typename _Compare, typename _Allocator>
412    inline bool
413    operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
414	       const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
415    { return __lhs._M_base() != __rhs._M_base(); }
416
417  template<typename _Key, typename _Tp,
418	   typename _Compare, typename _Allocator>
419    inline bool
420    operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
421	      const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
422    { return __lhs._M_base() < __rhs._M_base(); }
423
424  template<typename _Key, typename _Tp,
425	   typename _Compare, typename _Allocator>
426    inline bool
427    operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
428	       const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
429    { return __lhs._M_base() <= __rhs._M_base(); }
430
431  template<typename _Key, typename _Tp,
432	   typename _Compare, typename _Allocator>
433    inline bool
434    operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
435	       const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
436    { return __lhs._M_base() >= __rhs._M_base(); }
437
438  template<typename _Key, typename _Tp,
439	   typename _Compare, typename _Allocator>
440    inline bool
441    operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
442	      const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
443    { return __lhs._M_base() > __rhs._M_base(); }
444
445  template<typename _Key, typename _Tp,
446	   typename _Compare, typename _Allocator>
447    inline void
448    swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
449	 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
450    { __lhs.swap(__rhs); }
451
452} // namespace __debug
453} // namespace std
454
455#endif
456