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