xref: /dflybsd-src/contrib/gcc-4.7/libstdc++-v3/include/debug/map.h (revision 04febcfb30580676d3e95f58a16c5137ee478b32)
1*e4b17023SJohn Marino // Debugging map 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/map.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_MAP_H
31*e4b17023SJohn Marino #define _GLIBCXX_DEBUG_MAP_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::map 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 map
45*e4b17023SJohn Marino     : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>,
46*e4b17023SJohn Marino       public __gnu_debug::_Safe_sequence<map<_Key, _Tp, _Compare, _Allocator> >
47*e4b17023SJohn Marino     {
48*e4b17023SJohn Marino       typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base;
49*e4b17023SJohn Marino 
50*e4b17023SJohn Marino       typedef typename _Base::const_iterator _Base_const_iterator;
51*e4b17023SJohn Marino       typedef typename _Base::iterator _Base_iterator;
52*e4b17023SJohn Marino       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
53*e4b17023SJohn Marino     public:
54*e4b17023SJohn Marino       // types:
55*e4b17023SJohn Marino       typedef _Key                                  key_type;
56*e4b17023SJohn Marino       typedef _Tp                                   mapped_type;
57*e4b17023SJohn Marino       typedef std::pair<const _Key, _Tp>            value_type;
58*e4b17023SJohn Marino       typedef _Compare                              key_compare;
59*e4b17023SJohn Marino       typedef _Allocator                            allocator_type;
60*e4b17023SJohn Marino       typedef typename _Base::reference             reference;
61*e4b17023SJohn Marino       typedef typename _Base::const_reference       const_reference;
62*e4b17023SJohn Marino 
63*e4b17023SJohn Marino       typedef __gnu_debug::_Safe_iterator<_Base_iterator, map>
64*e4b17023SJohn Marino                                                     iterator;
65*e4b17023SJohn Marino       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, map>
66*e4b17023SJohn Marino                                                     const_iterator;
67*e4b17023SJohn Marino 
68*e4b17023SJohn Marino       typedef typename _Base::size_type             size_type;
69*e4b17023SJohn Marino       typedef typename _Base::difference_type       difference_type;
70*e4b17023SJohn Marino       typedef typename _Base::pointer               pointer;
71*e4b17023SJohn Marino       typedef typename _Base::const_pointer         const_pointer;
72*e4b17023SJohn Marino       typedef std::reverse_iterator<iterator>       reverse_iterator;
73*e4b17023SJohn Marino       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
74*e4b17023SJohn Marino 
75*e4b17023SJohn Marino       // 23.3.1.1 construct/copy/destroy:
76*e4b17023SJohn Marino       explicit map(const _Compare& __comp = _Compare(),
77*e4b17023SJohn Marino 		   const _Allocator& __a = _Allocator())
78*e4b17023SJohn Marino       : _Base(__comp, __a) { }
79*e4b17023SJohn Marino 
80*e4b17023SJohn Marino       template<typename _InputIterator>
81*e4b17023SJohn Marino         map(_InputIterator __first, _InputIterator __last,
82*e4b17023SJohn Marino 	    const _Compare& __comp = _Compare(),
83*e4b17023SJohn Marino 	    const _Allocator& __a = _Allocator())
84*e4b17023SJohn Marino 	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
85*e4b17023SJohn Marino 								     __last)),
86*e4b17023SJohn Marino 		__gnu_debug::__base(__last),
87*e4b17023SJohn Marino 		__comp, __a) { }
88*e4b17023SJohn Marino 
89*e4b17023SJohn Marino       map(const map& __x)
90*e4b17023SJohn Marino       : _Base(__x) { }
91*e4b17023SJohn Marino 
92*e4b17023SJohn Marino       map(const _Base& __x)
93*e4b17023SJohn Marino       : _Base(__x) { }
94*e4b17023SJohn Marino 
95*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
96*e4b17023SJohn Marino       map(map&& __x)
97*e4b17023SJohn Marino       noexcept(is_nothrow_copy_constructible<_Compare>::value)
98*e4b17023SJohn Marino       : _Base(std::move(__x))
99*e4b17023SJohn Marino       { this->_M_swap(__x); }
100*e4b17023SJohn Marino 
101*e4b17023SJohn Marino       map(initializer_list<value_type> __l,
102*e4b17023SJohn Marino 	  const _Compare& __c = _Compare(),
103*e4b17023SJohn Marino 	  const allocator_type& __a = allocator_type())
104*e4b17023SJohn Marino       : _Base(__l, __c, __a) { }
105*e4b17023SJohn Marino #endif
106*e4b17023SJohn Marino 
107*e4b17023SJohn Marino       ~map() _GLIBCXX_NOEXCEPT { }
108*e4b17023SJohn Marino 
109*e4b17023SJohn Marino       map&
110*e4b17023SJohn Marino       operator=(const map& __x)
111*e4b17023SJohn Marino       {
112*e4b17023SJohn Marino 	*static_cast<_Base*>(this) = __x;
113*e4b17023SJohn Marino 	this->_M_invalidate_all();
114*e4b17023SJohn Marino 	return *this;
115*e4b17023SJohn Marino       }
116*e4b17023SJohn Marino 
117*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
118*e4b17023SJohn Marino       map&
119*e4b17023SJohn Marino       operator=(map&& __x)
120*e4b17023SJohn Marino       {
121*e4b17023SJohn Marino 	// NB: DR 1204.
122*e4b17023SJohn Marino 	// NB: DR 675.
123*e4b17023SJohn Marino 	clear();
124*e4b17023SJohn Marino 	swap(__x);
125*e4b17023SJohn Marino 	return *this;
126*e4b17023SJohn Marino       }
127*e4b17023SJohn Marino 
128*e4b17023SJohn Marino       map&
129*e4b17023SJohn Marino       operator=(initializer_list<value_type> __l)
130*e4b17023SJohn Marino       {
131*e4b17023SJohn Marino 	this->clear();
132*e4b17023SJohn Marino 	this->insert(__l);
133*e4b17023SJohn Marino 	return *this;
134*e4b17023SJohn Marino       }
135*e4b17023SJohn Marino #endif
136*e4b17023SJohn Marino 
137*e4b17023SJohn Marino       // _GLIBCXX_RESOLVE_LIB_DEFECTS
138*e4b17023SJohn Marino       // 133. map missing get_allocator()
139*e4b17023SJohn Marino       using _Base::get_allocator;
140*e4b17023SJohn Marino 
141*e4b17023SJohn Marino       // iterators:
142*e4b17023SJohn Marino       iterator
143*e4b17023SJohn Marino       begin() _GLIBCXX_NOEXCEPT
144*e4b17023SJohn Marino       { return iterator(_Base::begin(), this); }
145*e4b17023SJohn Marino 
146*e4b17023SJohn Marino       const_iterator
147*e4b17023SJohn Marino       begin() const _GLIBCXX_NOEXCEPT
148*e4b17023SJohn Marino       { return const_iterator(_Base::begin(), this); }
149*e4b17023SJohn Marino 
150*e4b17023SJohn Marino       iterator
151*e4b17023SJohn Marino       end() _GLIBCXX_NOEXCEPT
152*e4b17023SJohn Marino       { return iterator(_Base::end(), this); }
153*e4b17023SJohn Marino 
154*e4b17023SJohn Marino       const_iterator
155*e4b17023SJohn Marino       end() const _GLIBCXX_NOEXCEPT
156*e4b17023SJohn Marino       { return const_iterator(_Base::end(), this); }
157*e4b17023SJohn Marino 
158*e4b17023SJohn Marino       reverse_iterator
159*e4b17023SJohn Marino       rbegin() _GLIBCXX_NOEXCEPT
160*e4b17023SJohn Marino       { return reverse_iterator(end()); }
161*e4b17023SJohn Marino 
162*e4b17023SJohn Marino       const_reverse_iterator
163*e4b17023SJohn Marino       rbegin() const _GLIBCXX_NOEXCEPT
164*e4b17023SJohn Marino       { return const_reverse_iterator(end()); }
165*e4b17023SJohn Marino 
166*e4b17023SJohn Marino       reverse_iterator
167*e4b17023SJohn Marino       rend() _GLIBCXX_NOEXCEPT
168*e4b17023SJohn Marino       { return reverse_iterator(begin()); }
169*e4b17023SJohn Marino 
170*e4b17023SJohn Marino       const_reverse_iterator
171*e4b17023SJohn Marino       rend() const _GLIBCXX_NOEXCEPT
172*e4b17023SJohn Marino       { return const_reverse_iterator(begin()); }
173*e4b17023SJohn Marino 
174*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
175*e4b17023SJohn Marino       const_iterator
176*e4b17023SJohn Marino       cbegin() const noexcept
177*e4b17023SJohn Marino       { return const_iterator(_Base::begin(), this); }
178*e4b17023SJohn Marino 
179*e4b17023SJohn Marino       const_iterator
180*e4b17023SJohn Marino       cend() const noexcept
181*e4b17023SJohn Marino       { return const_iterator(_Base::end(), this); }
182*e4b17023SJohn Marino 
183*e4b17023SJohn Marino       const_reverse_iterator
184*e4b17023SJohn Marino       crbegin() const noexcept
185*e4b17023SJohn Marino       { return const_reverse_iterator(end()); }
186*e4b17023SJohn Marino 
187*e4b17023SJohn Marino       const_reverse_iterator
188*e4b17023SJohn Marino       crend() const noexcept
189*e4b17023SJohn Marino       { return const_reverse_iterator(begin()); }
190*e4b17023SJohn Marino #endif
191*e4b17023SJohn Marino 
192*e4b17023SJohn Marino       // capacity:
193*e4b17023SJohn Marino       using _Base::empty;
194*e4b17023SJohn Marino       using _Base::size;
195*e4b17023SJohn Marino       using _Base::max_size;
196*e4b17023SJohn Marino 
197*e4b17023SJohn Marino       // 23.3.1.2 element access:
198*e4b17023SJohn Marino       using _Base::operator[];
199*e4b17023SJohn Marino 
200*e4b17023SJohn Marino       // _GLIBCXX_RESOLVE_LIB_DEFECTS
201*e4b17023SJohn Marino       // DR 464. Suggestion for new member functions in standard containers.
202*e4b17023SJohn Marino       using _Base::at;
203*e4b17023SJohn Marino 
204*e4b17023SJohn Marino       // modifiers:
205*e4b17023SJohn Marino       std::pair<iterator, bool>
206*e4b17023SJohn Marino       insert(const value_type& __x)
207*e4b17023SJohn Marino       {
208*e4b17023SJohn Marino 	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
209*e4b17023SJohn Marino 	return std::pair<iterator, bool>(iterator(__res.first, this),
210*e4b17023SJohn Marino 					 __res.second);
211*e4b17023SJohn Marino       }
212*e4b17023SJohn Marino 
213*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
214*e4b17023SJohn Marino       template<typename _Pair, typename = typename
215*e4b17023SJohn Marino 	       std::enable_if<std::is_constructible<value_type,
216*e4b17023SJohn Marino 						    _Pair&&>::value>::type>
217*e4b17023SJohn Marino         std::pair<iterator, bool>
218*e4b17023SJohn Marino         insert(_Pair&& __x)
219*e4b17023SJohn Marino         {
220*e4b17023SJohn Marino 	  std::pair<_Base_iterator, bool> __res
221*e4b17023SJohn Marino 	    = _Base::insert(std::forward<_Pair>(__x));
222*e4b17023SJohn Marino 	  return std::pair<iterator, bool>(iterator(__res.first, this),
223*e4b17023SJohn Marino 					   __res.second);
224*e4b17023SJohn Marino 	}
225*e4b17023SJohn Marino #endif
226*e4b17023SJohn Marino 
227*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
228*e4b17023SJohn Marino       void
229*e4b17023SJohn Marino       insert(std::initializer_list<value_type> __list)
230*e4b17023SJohn Marino       { _Base::insert(__list); }
231*e4b17023SJohn Marino #endif
232*e4b17023SJohn Marino 
233*e4b17023SJohn Marino       iterator
234*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
235*e4b17023SJohn Marino       insert(const_iterator __position, const value_type& __x)
236*e4b17023SJohn Marino #else
237*e4b17023SJohn Marino       insert(iterator __position, const value_type& __x)
238*e4b17023SJohn Marino #endif
239*e4b17023SJohn Marino       {
240*e4b17023SJohn Marino 	__glibcxx_check_insert(__position);
241*e4b17023SJohn Marino 	return iterator(_Base::insert(__position.base(), __x), this);
242*e4b17023SJohn Marino       }
243*e4b17023SJohn Marino 
244*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
245*e4b17023SJohn Marino       template<typename _Pair, typename = typename
246*e4b17023SJohn Marino 	       std::enable_if<std::is_constructible<value_type,
247*e4b17023SJohn Marino 						    _Pair&&>::value>::type>
248*e4b17023SJohn Marino         iterator
249*e4b17023SJohn Marino         insert(const_iterator __position, _Pair&& __x)
250*e4b17023SJohn Marino         {
251*e4b17023SJohn Marino 	  __glibcxx_check_insert(__position);
252*e4b17023SJohn Marino 	  return iterator(_Base::insert(__position.base(),
253*e4b17023SJohn Marino 					std::forward<_Pair>(__x)), this);
254*e4b17023SJohn Marino 	}
255*e4b17023SJohn Marino #endif
256*e4b17023SJohn Marino 
257*e4b17023SJohn Marino       template<typename _InputIterator>
258*e4b17023SJohn Marino         void
259*e4b17023SJohn Marino         insert(_InputIterator __first, _InputIterator __last)
260*e4b17023SJohn Marino         {
261*e4b17023SJohn Marino 	  __glibcxx_check_valid_range(__first, __last);
262*e4b17023SJohn Marino 	  _Base::insert(__gnu_debug::__base(__first),
263*e4b17023SJohn Marino 			__gnu_debug::__base(__last));
264*e4b17023SJohn Marino 	}
265*e4b17023SJohn Marino 
266*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
267*e4b17023SJohn Marino       iterator
268*e4b17023SJohn Marino       erase(const_iterator __position)
269*e4b17023SJohn Marino       {
270*e4b17023SJohn Marino 	__glibcxx_check_erase(__position);
271*e4b17023SJohn Marino 	this->_M_invalidate_if(_Equal(__position.base()));
272*e4b17023SJohn Marino 	return iterator(_Base::erase(__position.base()), this);
273*e4b17023SJohn Marino       }
274*e4b17023SJohn Marino 
275*e4b17023SJohn Marino       iterator
276*e4b17023SJohn Marino       erase(iterator __position)
277*e4b17023SJohn Marino       { return erase(const_iterator(__position)); }
278*e4b17023SJohn Marino #else
279*e4b17023SJohn Marino       void
280*e4b17023SJohn Marino       erase(iterator __position)
281*e4b17023SJohn Marino       {
282*e4b17023SJohn Marino 	__glibcxx_check_erase(__position);
283*e4b17023SJohn Marino 	this->_M_invalidate_if(_Equal(__position.base()));
284*e4b17023SJohn Marino 	_Base::erase(__position.base());
285*e4b17023SJohn Marino       }
286*e4b17023SJohn Marino #endif
287*e4b17023SJohn Marino 
288*e4b17023SJohn Marino       size_type
289*e4b17023SJohn Marino       erase(const key_type& __x)
290*e4b17023SJohn Marino       {
291*e4b17023SJohn Marino 	_Base_iterator __victim = _Base::find(__x);
292*e4b17023SJohn Marino 	if (__victim == _Base::end())
293*e4b17023SJohn Marino 	  return 0;
294*e4b17023SJohn Marino 	else
295*e4b17023SJohn Marino 	  {
296*e4b17023SJohn Marino 	    this->_M_invalidate_if(_Equal(__victim));
297*e4b17023SJohn Marino 	    _Base::erase(__victim);
298*e4b17023SJohn Marino 	    return 1;
299*e4b17023SJohn Marino 	  }
300*e4b17023SJohn Marino       }
301*e4b17023SJohn Marino 
302*e4b17023SJohn Marino #ifdef __GXX_EXPERIMENTAL_CXX0X__
303*e4b17023SJohn Marino       iterator
304*e4b17023SJohn Marino       erase(const_iterator __first, const_iterator __last)
305*e4b17023SJohn Marino       {
306*e4b17023SJohn Marino 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
307*e4b17023SJohn Marino 	// 151. can't currently clear() empty container
308*e4b17023SJohn Marino 	__glibcxx_check_erase_range(__first, __last);
309*e4b17023SJohn Marino 	for (_Base_const_iterator __victim = __first.base();
310*e4b17023SJohn Marino 	     __victim != __last.base(); ++__victim)
311*e4b17023SJohn Marino 	  {
312*e4b17023SJohn Marino 	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
313*e4b17023SJohn Marino 				  _M_message(__gnu_debug::__msg_valid_range)
314*e4b17023SJohn Marino 				  ._M_iterator(__first, "first")
315*e4b17023SJohn Marino 				  ._M_iterator(__last, "last"));
316*e4b17023SJohn Marino 	    this->_M_invalidate_if(_Equal(__victim));
317*e4b17023SJohn Marino 	  }
318*e4b17023SJohn Marino 	return iterator(_Base::erase(__first.base(), __last.base()), this);
319*e4b17023SJohn Marino       }
320*e4b17023SJohn Marino #else
321*e4b17023SJohn Marino       void
322*e4b17023SJohn Marino       erase(iterator __first, iterator __last)
323*e4b17023SJohn Marino       {
324*e4b17023SJohn Marino 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
325*e4b17023SJohn Marino 	// 151. can't currently clear() empty container
326*e4b17023SJohn Marino 	__glibcxx_check_erase_range(__first, __last);
327*e4b17023SJohn Marino 	for (_Base_iterator __victim = __first.base();
328*e4b17023SJohn Marino 	     __victim != __last.base(); ++__victim)
329*e4b17023SJohn Marino 	  {
330*e4b17023SJohn Marino 	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
331*e4b17023SJohn Marino 				  _M_message(__gnu_debug::__msg_valid_range)
332*e4b17023SJohn Marino 				  ._M_iterator(__first, "first")
333*e4b17023SJohn Marino 				  ._M_iterator(__last, "last"));
334*e4b17023SJohn Marino 	    this->_M_invalidate_if(_Equal(__victim));
335*e4b17023SJohn Marino 	  }
336*e4b17023SJohn Marino 	_Base::erase(__first.base(), __last.base());
337*e4b17023SJohn Marino       }
338*e4b17023SJohn Marino #endif
339*e4b17023SJohn Marino 
340*e4b17023SJohn Marino       void
341*e4b17023SJohn Marino       swap(map& __x)
342*e4b17023SJohn Marino       {
343*e4b17023SJohn Marino 	_Base::swap(__x);
344*e4b17023SJohn Marino 	this->_M_swap(__x);
345*e4b17023SJohn Marino       }
346*e4b17023SJohn Marino 
347*e4b17023SJohn Marino       void
348*e4b17023SJohn Marino       clear() _GLIBCXX_NOEXCEPT
349*e4b17023SJohn Marino       {
350*e4b17023SJohn Marino 	this->_M_invalidate_all();
351*e4b17023SJohn Marino 	_Base::clear();
352*e4b17023SJohn Marino       }
353*e4b17023SJohn Marino 
354*e4b17023SJohn Marino       // observers:
355*e4b17023SJohn Marino       using _Base::key_comp;
356*e4b17023SJohn Marino       using _Base::value_comp;
357*e4b17023SJohn Marino 
358*e4b17023SJohn Marino       // 23.3.1.3 map operations:
359*e4b17023SJohn Marino       iterator
360*e4b17023SJohn Marino       find(const key_type& __x)
361*e4b17023SJohn Marino       { return iterator(_Base::find(__x), this); }
362*e4b17023SJohn Marino 
363*e4b17023SJohn Marino       const_iterator
364*e4b17023SJohn Marino       find(const key_type& __x) const
365*e4b17023SJohn Marino       { return const_iterator(_Base::find(__x), this); }
366*e4b17023SJohn Marino 
367*e4b17023SJohn Marino       using _Base::count;
368*e4b17023SJohn Marino 
369*e4b17023SJohn Marino       iterator
370*e4b17023SJohn Marino       lower_bound(const key_type& __x)
371*e4b17023SJohn Marino       { return iterator(_Base::lower_bound(__x), this); }
372*e4b17023SJohn Marino 
373*e4b17023SJohn Marino       const_iterator
374*e4b17023SJohn Marino       lower_bound(const key_type& __x) const
375*e4b17023SJohn Marino       { return const_iterator(_Base::lower_bound(__x), this); }
376*e4b17023SJohn Marino 
377*e4b17023SJohn Marino       iterator
378*e4b17023SJohn Marino       upper_bound(const key_type& __x)
379*e4b17023SJohn Marino       { return iterator(_Base::upper_bound(__x), this); }
380*e4b17023SJohn Marino 
381*e4b17023SJohn Marino       const_iterator
382*e4b17023SJohn Marino       upper_bound(const key_type& __x) const
383*e4b17023SJohn Marino       { return const_iterator(_Base::upper_bound(__x), this); }
384*e4b17023SJohn Marino 
385*e4b17023SJohn Marino       std::pair<iterator,iterator>
386*e4b17023SJohn Marino       equal_range(const key_type& __x)
387*e4b17023SJohn Marino       {
388*e4b17023SJohn Marino 	std::pair<_Base_iterator, _Base_iterator> __res =
389*e4b17023SJohn Marino 	_Base::equal_range(__x);
390*e4b17023SJohn Marino 	return std::make_pair(iterator(__res.first, this),
391*e4b17023SJohn Marino 			      iterator(__res.second, this));
392*e4b17023SJohn Marino       }
393*e4b17023SJohn Marino 
394*e4b17023SJohn Marino       std::pair<const_iterator,const_iterator>
395*e4b17023SJohn Marino       equal_range(const key_type& __x) const
396*e4b17023SJohn Marino       {
397*e4b17023SJohn Marino 	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
398*e4b17023SJohn Marino 	_Base::equal_range(__x);
399*e4b17023SJohn Marino 	return std::make_pair(const_iterator(__res.first, this),
400*e4b17023SJohn Marino 			      const_iterator(__res.second, this));
401*e4b17023SJohn Marino       }
402*e4b17023SJohn Marino 
403*e4b17023SJohn Marino       _Base&
404*e4b17023SJohn Marino       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
405*e4b17023SJohn Marino 
406*e4b17023SJohn Marino       const _Base&
407*e4b17023SJohn Marino       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
408*e4b17023SJohn Marino 
409*e4b17023SJohn Marino     private:
410*e4b17023SJohn Marino       void
411*e4b17023SJohn Marino       _M_invalidate_all()
412*e4b17023SJohn Marino       {
413*e4b17023SJohn Marino 	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
414*e4b17023SJohn Marino 	this->_M_invalidate_if(_Not_equal(_M_base().end()));
415*e4b17023SJohn Marino       }
416*e4b17023SJohn Marino     };
417*e4b17023SJohn Marino 
418*e4b17023SJohn Marino   template<typename _Key, typename _Tp,
419*e4b17023SJohn Marino 	   typename _Compare, typename _Allocator>
420*e4b17023SJohn Marino     inline bool
421*e4b17023SJohn Marino     operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
422*e4b17023SJohn Marino 	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
423*e4b17023SJohn Marino     { return __lhs._M_base() == __rhs._M_base(); }
424*e4b17023SJohn Marino 
425*e4b17023SJohn Marino   template<typename _Key, typename _Tp,
426*e4b17023SJohn Marino 	   typename _Compare, typename _Allocator>
427*e4b17023SJohn Marino     inline bool
428*e4b17023SJohn Marino     operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
429*e4b17023SJohn Marino 	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
430*e4b17023SJohn Marino     { return __lhs._M_base() != __rhs._M_base(); }
431*e4b17023SJohn Marino 
432*e4b17023SJohn Marino   template<typename _Key, typename _Tp,
433*e4b17023SJohn Marino 	   typename _Compare, typename _Allocator>
434*e4b17023SJohn Marino     inline bool
435*e4b17023SJohn Marino     operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
436*e4b17023SJohn Marino 	      const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
437*e4b17023SJohn Marino     { return __lhs._M_base() < __rhs._M_base(); }
438*e4b17023SJohn Marino 
439*e4b17023SJohn Marino   template<typename _Key, typename _Tp,
440*e4b17023SJohn Marino 	   typename _Compare, typename _Allocator>
441*e4b17023SJohn Marino     inline bool
442*e4b17023SJohn Marino     operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
443*e4b17023SJohn Marino 	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
444*e4b17023SJohn Marino     { return __lhs._M_base() <= __rhs._M_base(); }
445*e4b17023SJohn Marino 
446*e4b17023SJohn Marino   template<typename _Key, typename _Tp,
447*e4b17023SJohn Marino 	   typename _Compare, typename _Allocator>
448*e4b17023SJohn Marino     inline bool
449*e4b17023SJohn Marino     operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
450*e4b17023SJohn Marino 	       const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
451*e4b17023SJohn Marino     { return __lhs._M_base() >= __rhs._M_base(); }
452*e4b17023SJohn Marino 
453*e4b17023SJohn Marino   template<typename _Key, typename _Tp,
454*e4b17023SJohn Marino 	   typename _Compare, typename _Allocator>
455*e4b17023SJohn Marino     inline bool
456*e4b17023SJohn Marino     operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs,
457*e4b17023SJohn Marino 	      const map<_Key, _Tp, _Compare, _Allocator>& __rhs)
458*e4b17023SJohn Marino     { return __lhs._M_base() > __rhs._M_base(); }
459*e4b17023SJohn Marino 
460*e4b17023SJohn Marino   template<typename _Key, typename _Tp,
461*e4b17023SJohn Marino 	   typename _Compare, typename _Allocator>
462*e4b17023SJohn Marino     inline void
463*e4b17023SJohn Marino     swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs,
464*e4b17023SJohn Marino 	 map<_Key, _Tp, _Compare, _Allocator>& __rhs)
465*e4b17023SJohn Marino     { __lhs.swap(__rhs); }
466*e4b17023SJohn Marino 
467*e4b17023SJohn Marino } // namespace __debug
468*e4b17023SJohn Marino } // namespace std
469*e4b17023SJohn Marino 
470*e4b17023SJohn Marino #endif
471