libstdc++
safe_iterator.h
Go to the documentation of this file.
00001 // Safe iterator implementation  -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2009, 2010, 2011, 2012
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /** @file debug/safe_iterator.h
00027  *  This file is a GNU debug extension to the Standard C++ Library.
00028  */
00029 
00030 #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H
00031 #define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1
00032 
00033 #include <debug/debug.h>
00034 #include <debug/macros.h>
00035 #include <debug/functions.h>
00036 #include <debug/safe_base.h>
00037 #include <bits/stl_pair.h>
00038 #include <bits/stl_iterator_base_types.h> // for _Iter_base
00039 #include <ext/type_traits.h>
00040 
00041 namespace __gnu_debug
00042 {
00043   /** Helper struct to deal with sequence offering a before_begin
00044    *  iterator.
00045    **/
00046   template <typename _Sequence>
00047     struct _BeforeBeginHelper
00048     {
00049       typedef typename _Sequence::const_iterator _It;
00050       typedef typename _It::iterator_type _BaseIt;
00051 
00052       static bool
00053       _M_Is(_BaseIt __it, const _Sequence* __seq)
00054       { return false; }
00055     };
00056 
00057   /** Iterators that derive from _Safe_iterator_base but that aren't
00058    *  _Safe_iterators can be determined singular or non-singular via
00059    *  _Safe_iterator_base.
00060    */
00061   inline bool 
00062   __check_singular_aux(const _Safe_iterator_base* __x)
00063   { return __x->_M_singular(); }
00064 
00065   /** \brief Safe iterator wrapper.
00066    *
00067    *  The class template %_Safe_iterator is a wrapper around an
00068    *  iterator that tracks the iterator's movement among sequences and
00069    *  checks that operations performed on the "safe" iterator are
00070    *  legal. In additional to the basic iterator operations (which are
00071    *  validated, and then passed to the underlying iterator),
00072    *  %_Safe_iterator has member functions for iterator invalidation,
00073    *  attaching/detaching the iterator from sequences, and querying
00074    *  the iterator's state.
00075    */
00076   template<typename _Iterator, typename _Sequence>
00077     class _Safe_iterator : public _Safe_iterator_base
00078     {
00079       typedef _Safe_iterator _Self;
00080 
00081       /** The precision to which we can calculate the distance between
00082        *  two iterators.
00083        */
00084       enum _Distance_precision
00085     {
00086       __dp_equality, //< Can compare iterator equality, only
00087       __dp_sign,     //< Can determine equality and ordering
00088       __dp_exact     //< Can determine distance precisely
00089     };
00090 
00091       /// The underlying iterator
00092       _Iterator _M_current;
00093 
00094       /// Determine if this is a constant iterator.
00095       bool
00096       _M_constant() const
00097       {
00098     typedef typename _Sequence::const_iterator const_iterator;
00099     return std::__are_same<const_iterator, _Safe_iterator>::__value;
00100       }
00101 
00102       typedef std::iterator_traits<_Iterator> _Traits;
00103 
00104     public:
00105       typedef _Iterator                           iterator_type;
00106       typedef typename _Traits::iterator_category iterator_category;
00107       typedef typename _Traits::value_type        value_type;
00108       typedef typename _Traits::difference_type   difference_type;
00109       typedef typename _Traits::reference         reference;
00110       typedef typename _Traits::pointer           pointer;
00111 
00112       /// @post the iterator is singular and unattached
00113       _Safe_iterator() : _M_current() { }
00114 
00115       /**
00116        * @brief Safe iterator construction from an unsafe iterator and
00117        * its sequence.
00118        *
00119        * @pre @p seq is not NULL
00120        * @post this is not singular
00121        */
00122       _Safe_iterator(const _Iterator& __i, const _Sequence* __seq)
00123       : _Safe_iterator_base(__seq, _M_constant()), _M_current(__i)
00124       {
00125     _GLIBCXX_DEBUG_VERIFY(! this->_M_singular(),
00126                   _M_message(__msg_init_singular)
00127                   ._M_iterator(*this, "this"));
00128       }
00129 
00130       /**
00131        * @brief Copy construction.
00132        */
00133       _Safe_iterator(const _Safe_iterator& __x)
00134       : _Safe_iterator_base(__x, _M_constant()), _M_current(__x._M_current)
00135       {
00136     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00137     // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00138     _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00139                   || __x._M_current == _Iterator(),
00140                   _M_message(__msg_init_copy_singular)
00141                   ._M_iterator(*this, "this")
00142                   ._M_iterator(__x, "other"));
00143       }
00144 
00145 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00146       /**
00147        * @brief Move construction.
00148        * @post __x is singular and unattached
00149        */
00150       _Safe_iterator(_Safe_iterator&& __x) : _M_current()
00151       {
00152     _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00153                   || __x._M_current == _Iterator(),
00154                   _M_message(__msg_init_copy_singular)
00155                   ._M_iterator(*this, "this")
00156                   ._M_iterator(__x, "other"));
00157     std::swap(_M_current, __x._M_current);
00158     this->_M_attach(__x._M_sequence);
00159     __x._M_detach();
00160       }
00161 #endif
00162 
00163       /**
00164        *  @brief Converting constructor from a mutable iterator to a
00165        *  constant iterator.
00166       */
00167       template<typename _MutableIterator>
00168         _Safe_iterator(
00169           const _Safe_iterator<_MutableIterator,
00170           typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
00171                       typename _Sequence::iterator::iterator_type>::__value),
00172                    _Sequence>::__type>& __x)
00173     : _Safe_iterator_base(__x, _M_constant()), _M_current(__x.base())
00174         {
00175       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00176       // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00177       _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00178                 || __x.base() == _Iterator(),
00179                 _M_message(__msg_init_const_singular)
00180                 ._M_iterator(*this, "this")
00181                 ._M_iterator(__x, "other"));
00182     }
00183 
00184       /**
00185        * @brief Copy assignment.
00186        */
00187       _Safe_iterator&
00188       operator=(const _Safe_iterator& __x)
00189       {
00190     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00191     // DR 408. Is vector<reverse_iterator<char*> > forbidden?
00192     _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00193                   || __x._M_current == _Iterator(),
00194                   _M_message(__msg_copy_singular)
00195                   ._M_iterator(*this, "this")
00196                   ._M_iterator(__x, "other"));
00197     _M_current = __x._M_current;
00198     this->_M_attach(__x._M_sequence);
00199     return *this;
00200       }
00201 
00202 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00203       /**
00204        * @brief Move assignment.
00205        * @post __x is singular and unattached
00206        */
00207       _Safe_iterator&
00208       operator=(_Safe_iterator&& __x)
00209       {
00210     _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
00211                   || __x._M_current == _Iterator(),
00212                   _M_message(__msg_copy_singular)
00213                   ._M_iterator(*this, "this")
00214                   ._M_iterator(__x, "other"));
00215     _M_current = __x._M_current;
00216     _M_attach(__x._M_sequence);
00217     __x._M_detach();
00218     __x._M_current = _Iterator();
00219     return *this;
00220       }
00221 #endif
00222 
00223       /**
00224        *  @brief Iterator dereference.
00225        *  @pre iterator is dereferenceable
00226        */
00227       reference
00228       operator*() const
00229       {
00230     _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00231                   _M_message(__msg_bad_deref)
00232                   ._M_iterator(*this, "this"));
00233     return *_M_current;
00234       }
00235 
00236       /**
00237        *  @brief Iterator dereference.
00238        *  @pre iterator is dereferenceable
00239        *  @todo Make this correct w.r.t. iterators that return proxies
00240        *  @todo Use addressof() instead of & operator
00241        */
00242       pointer
00243       operator->() const
00244       {
00245     _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
00246                   _M_message(__msg_bad_deref)
00247                   ._M_iterator(*this, "this"));
00248     return &*_M_current;
00249       }
00250 
00251       // ------ Input iterator requirements ------
00252       /**
00253        *  @brief Iterator preincrement
00254        *  @pre iterator is incrementable
00255        */
00256       _Safe_iterator&
00257       operator++()
00258       {
00259     _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00260                   _M_message(__msg_bad_inc)
00261                   ._M_iterator(*this, "this"));
00262     ++_M_current;
00263     return *this;
00264       }
00265 
00266       /**
00267        *  @brief Iterator postincrement
00268        *  @pre iterator is incrementable
00269        */
00270       _Safe_iterator
00271       operator++(int)
00272       {
00273     _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
00274                   _M_message(__msg_bad_inc)
00275                   ._M_iterator(*this, "this"));
00276     _Safe_iterator __tmp(*this);
00277     ++_M_current;
00278     return __tmp;
00279       }
00280 
00281       // ------ Bidirectional iterator requirements ------
00282       /**
00283        *  @brief Iterator predecrement
00284        *  @pre iterator is decrementable
00285        */
00286       _Safe_iterator&
00287       operator--()
00288       {
00289     _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
00290                   _M_message(__msg_bad_dec)
00291                   ._M_iterator(*this, "this"));
00292     --_M_current;
00293     return *this;
00294       }
00295 
00296       /**
00297        *  @brief Iterator postdecrement
00298        *  @pre iterator is decrementable
00299        */
00300       _Safe_iterator
00301       operator--(int)
00302       {
00303     _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
00304                   _M_message(__msg_bad_dec)
00305                   ._M_iterator(*this, "this"));
00306     _Safe_iterator __tmp(*this);
00307     --_M_current;
00308     return __tmp;
00309       }
00310 
00311       // ------ Random access iterator requirements ------
00312       reference
00313       operator[](const difference_type& __n) const
00314       {
00315     _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
00316                   && this->_M_can_advance(__n+1),
00317                   _M_message(__msg_iter_subscript_oob)
00318                   ._M_iterator(*this)._M_integer(__n));
00319 
00320     return _M_current[__n];
00321       }
00322 
00323       _Safe_iterator&
00324       operator+=(const difference_type& __n)
00325       {
00326     _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
00327                   _M_message(__msg_advance_oob)
00328                   ._M_iterator(*this)._M_integer(__n));
00329     _M_current += __n;
00330     return *this;
00331       }
00332 
00333       _Safe_iterator
00334       operator+(const difference_type& __n) const
00335       {
00336     _Safe_iterator __tmp(*this);
00337     __tmp += __n;
00338     return __tmp;
00339       }
00340 
00341       _Safe_iterator&
00342       operator-=(const difference_type& __n)
00343       {
00344     _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
00345                   _M_message(__msg_retreat_oob)
00346                   ._M_iterator(*this)._M_integer(__n));
00347     _M_current += -__n;
00348     return *this;
00349       }
00350 
00351       _Safe_iterator
00352       operator-(const difference_type& __n) const
00353       {
00354     _Safe_iterator __tmp(*this);
00355     __tmp -= __n;
00356     return __tmp;
00357       }
00358 
00359       // ------ Utilities ------
00360       /**
00361        * @brief Return the underlying iterator
00362        */
00363       _Iterator
00364       base() const { return _M_current; }
00365 
00366       /**
00367        * @brief Conversion to underlying non-debug iterator to allow
00368        * better interaction with non-debug containers.
00369        */
00370       operator _Iterator() const { return _M_current; }
00371 
00372       /** Attach iterator to the given sequence. */
00373       void
00374       _M_attach(_Safe_sequence_base* __seq)
00375       {
00376     _Safe_iterator_base::_M_attach(__seq, _M_constant());
00377       }
00378 
00379       /** Likewise, but not thread-safe. */
00380       void
00381       _M_attach_single(_Safe_sequence_base* __seq)
00382       {
00383     _Safe_iterator_base::_M_attach_single(__seq, _M_constant());
00384       }
00385 
00386       /// Is the iterator dereferenceable?
00387       bool
00388       _M_dereferenceable() const
00389       { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); }
00390 
00391       /// Is the iterator before a dereferenceable one?
00392       bool
00393       _M_before_dereferenceable() const
00394       {
00395     _Self __it = *this;
00396     return __it._M_incrementable() && (++__it)._M_dereferenceable();
00397       }
00398 
00399       /// Is the iterator incrementable?
00400       bool
00401       _M_incrementable() const
00402       { return !this->_M_singular() && !_M_is_end(); }
00403 
00404       // Is the iterator decrementable?
00405       bool
00406       _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
00407 
00408       // Can we advance the iterator @p __n steps (@p __n may be negative)
00409       bool
00410       _M_can_advance(const difference_type& __n) const;
00411 
00412       // Is the iterator range [*this, __rhs) valid?
00413       template<typename _Other>
00414         bool
00415         _M_valid_range(const _Safe_iterator<_Other, _Sequence>& __rhs) const;
00416 
00417       // The sequence this iterator references.
00418       const _Sequence*
00419       _M_get_sequence() const
00420       { return static_cast<const _Sequence*>(_M_sequence); }
00421 
00422     /** Determine the distance between two iterators with some known
00423      *  precision.
00424     */
00425     template<typename _Iterator1, typename _Iterator2>
00426       static std::pair<difference_type, _Distance_precision>
00427       _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs)
00428       {
00429         typedef typename std::iterator_traits<_Iterator1>::iterator_category
00430       _Category;
00431         return _M_get_distance(__lhs, __rhs, _Category());
00432       }
00433 
00434     template<typename _Iterator1, typename _Iterator2>
00435       static std::pair<difference_type, _Distance_precision>
00436       _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
00437               std::random_access_iterator_tag)
00438       { return std::make_pair(__rhs - __lhs, __dp_exact); }
00439 
00440     template<typename _Iterator1, typename _Iterator2>
00441       static std::pair<difference_type, _Distance_precision>
00442       _M_get_distance(const _Iterator1& __lhs, const _Iterator2& __rhs,
00443             std::forward_iterator_tag)
00444       { return std::make_pair(__lhs == __rhs? 0 : 1, __dp_equality); }
00445 
00446       /// Is this iterator equal to the sequence's begin() iterator?
00447       bool _M_is_begin() const
00448       { return base() == _M_get_sequence()->_M_base().begin(); }
00449 
00450       /// Is this iterator equal to the sequence's end() iterator?
00451       bool _M_is_end() const
00452       { return base() == _M_get_sequence()->_M_base().end(); }
00453 
00454       /// Is this iterator equal to the sequence's before_begin() iterator if
00455       /// any?
00456       bool _M_is_before_begin() const
00457       {
00458     return _BeforeBeginHelper<_Sequence>::_M_Is(base(), _M_get_sequence());
00459       }
00460     };
00461 
00462   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00463     inline bool
00464     operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00465            const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00466     {
00467       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00468                 _M_message(__msg_iter_compare_bad)
00469                 ._M_iterator(__lhs, "lhs")
00470                 ._M_iterator(__rhs, "rhs"));
00471       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00472                 _M_message(__msg_compare_different)
00473                 ._M_iterator(__lhs, "lhs")
00474                 ._M_iterator(__rhs, "rhs"));
00475       return __lhs.base() == __rhs.base();
00476     }
00477 
00478   template<typename _Iterator, typename _Sequence>
00479     inline bool
00480     operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00481                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00482     {
00483       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00484                 _M_message(__msg_iter_compare_bad)
00485                 ._M_iterator(__lhs, "lhs")
00486                 ._M_iterator(__rhs, "rhs"));
00487       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00488                 _M_message(__msg_compare_different)
00489                 ._M_iterator(__lhs, "lhs")
00490                 ._M_iterator(__rhs, "rhs"));
00491       return __lhs.base() == __rhs.base();
00492     }
00493 
00494   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00495     inline bool
00496     operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00497            const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00498     {
00499       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00500                 _M_message(__msg_iter_compare_bad)
00501                 ._M_iterator(__lhs, "lhs")
00502                 ._M_iterator(__rhs, "rhs"));
00503       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00504                 _M_message(__msg_compare_different)
00505                 ._M_iterator(__lhs, "lhs")
00506                 ._M_iterator(__rhs, "rhs"));
00507       return __lhs.base() != __rhs.base();
00508     }
00509 
00510   template<typename _Iterator, typename _Sequence>
00511     inline bool
00512     operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00513                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00514     {
00515       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00516                 _M_message(__msg_iter_compare_bad)
00517                 ._M_iterator(__lhs, "lhs")
00518                 ._M_iterator(__rhs, "rhs"));
00519       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00520                 _M_message(__msg_compare_different)
00521                 ._M_iterator(__lhs, "lhs")
00522                 ._M_iterator(__rhs, "rhs"));
00523       return __lhs.base() != __rhs.base();
00524     }
00525 
00526   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00527     inline bool
00528     operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00529           const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00530     {
00531       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00532                 _M_message(__msg_iter_order_bad)
00533                 ._M_iterator(__lhs, "lhs")
00534                 ._M_iterator(__rhs, "rhs"));
00535       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00536                 _M_message(__msg_order_different)
00537                 ._M_iterator(__lhs, "lhs")
00538                 ._M_iterator(__rhs, "rhs"));
00539       return __lhs.base() < __rhs.base();
00540     }
00541 
00542   template<typename _Iterator, typename _Sequence>
00543     inline bool
00544     operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00545           const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00546     {
00547       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00548                 _M_message(__msg_iter_order_bad)
00549                 ._M_iterator(__lhs, "lhs")
00550                 ._M_iterator(__rhs, "rhs"));
00551       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00552                 _M_message(__msg_order_different)
00553                 ._M_iterator(__lhs, "lhs")
00554                 ._M_iterator(__rhs, "rhs"));
00555       return __lhs.base() < __rhs.base();
00556     }
00557 
00558   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00559     inline bool
00560     operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00561            const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00562     {
00563       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00564                 _M_message(__msg_iter_order_bad)
00565                 ._M_iterator(__lhs, "lhs")
00566                 ._M_iterator(__rhs, "rhs"));
00567       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00568                 _M_message(__msg_order_different)
00569                 ._M_iterator(__lhs, "lhs")
00570                 ._M_iterator(__rhs, "rhs"));
00571       return __lhs.base() <= __rhs.base();
00572     }
00573 
00574   template<typename _Iterator, typename _Sequence>
00575     inline bool
00576     operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00577                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00578     {
00579       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00580                 _M_message(__msg_iter_order_bad)
00581                 ._M_iterator(__lhs, "lhs")
00582                 ._M_iterator(__rhs, "rhs"));
00583       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00584                 _M_message(__msg_order_different)
00585                 ._M_iterator(__lhs, "lhs")
00586                 ._M_iterator(__rhs, "rhs"));
00587       return __lhs.base() <= __rhs.base();
00588     }
00589 
00590   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00591     inline bool
00592     operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00593           const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00594     {
00595       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00596                 _M_message(__msg_iter_order_bad)
00597                 ._M_iterator(__lhs, "lhs")
00598                 ._M_iterator(__rhs, "rhs"));
00599       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00600                 _M_message(__msg_order_different)
00601                 ._M_iterator(__lhs, "lhs")
00602                 ._M_iterator(__rhs, "rhs"));
00603       return __lhs.base() > __rhs.base();
00604     }
00605 
00606   template<typename _Iterator, typename _Sequence>
00607     inline bool
00608     operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00609           const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00610     {
00611       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00612                 _M_message(__msg_iter_order_bad)
00613                 ._M_iterator(__lhs, "lhs")
00614                 ._M_iterator(__rhs, "rhs"));
00615       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00616                 _M_message(__msg_order_different)
00617                 ._M_iterator(__lhs, "lhs")
00618                 ._M_iterator(__rhs, "rhs"));
00619       return __lhs.base() > __rhs.base();
00620     }
00621 
00622   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00623     inline bool
00624     operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00625            const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00626     {
00627       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00628                 _M_message(__msg_iter_order_bad)
00629                 ._M_iterator(__lhs, "lhs")
00630                 ._M_iterator(__rhs, "rhs"));
00631       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00632                 _M_message(__msg_order_different)
00633                 ._M_iterator(__lhs, "lhs")
00634                 ._M_iterator(__rhs, "rhs"));
00635       return __lhs.base() >= __rhs.base();
00636     }
00637 
00638   template<typename _Iterator, typename _Sequence>
00639     inline bool
00640     operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00641                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00642     {
00643       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00644                 _M_message(__msg_iter_order_bad)
00645                 ._M_iterator(__lhs, "lhs")
00646                 ._M_iterator(__rhs, "rhs"));
00647       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00648                 _M_message(__msg_order_different)
00649                 ._M_iterator(__lhs, "lhs")
00650                 ._M_iterator(__rhs, "rhs"));
00651       return __lhs.base() >= __rhs.base();
00652     }
00653 
00654   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00655   // According to the resolution of DR179 not only the various comparison
00656   // operators but also operator- must accept mixed iterator/const_iterator
00657   // parameters.
00658   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
00659     inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
00660     operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
00661           const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
00662     {
00663       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00664                 _M_message(__msg_distance_bad)
00665                 ._M_iterator(__lhs, "lhs")
00666                 ._M_iterator(__rhs, "rhs"));
00667       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00668                 _M_message(__msg_distance_different)
00669                 ._M_iterator(__lhs, "lhs")
00670                 ._M_iterator(__rhs, "rhs"));
00671       return __lhs.base() - __rhs.base();
00672     }
00673 
00674    template<typename _Iterator, typename _Sequence>
00675      inline typename _Safe_iterator<_Iterator, _Sequence>::difference_type
00676      operator-(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
00677            const _Safe_iterator<_Iterator, _Sequence>& __rhs)
00678      {
00679        _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
00680                  _M_message(__msg_distance_bad)
00681                  ._M_iterator(__lhs, "lhs")
00682                  ._M_iterator(__rhs, "rhs"));
00683        _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
00684                  _M_message(__msg_distance_different)
00685                  ._M_iterator(__lhs, "lhs")
00686                  ._M_iterator(__rhs, "rhs"));
00687        return __lhs.base() - __rhs.base();
00688      }
00689 
00690   template<typename _Iterator, typename _Sequence>
00691     inline _Safe_iterator<_Iterator, _Sequence>
00692     operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
00693           const _Safe_iterator<_Iterator, _Sequence>& __i)
00694     { return __i + __n; }
00695 
00696   // Helper struct to detect random access safe iterators.
00697   template<typename _Iterator>
00698     struct __is_safe_random_iterator
00699     {
00700       enum { __value = 0 };
00701       typedef std::__false_type __type;
00702     };
00703 
00704   template<typename _Iterator, typename _Sequence>
00705     struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
00706     : std::__are_same<std::random_access_iterator_tag,
00707                       typename std::iterator_traits<_Iterator>::
00708               iterator_category>
00709     { };
00710 
00711   template<typename _Iterator>
00712     struct _Siter_base
00713     : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value>
00714     { };
00715 
00716   /** Helper function to extract base iterator of random access safe iterator
00717       in order to reduce performance impact of debug mode.  Limited to random
00718       access iterator because it is the only category for which it is possible
00719       to check for correct iterators order in the __valid_range function
00720       thanks to the < operator.
00721   */
00722   template<typename _Iterator>
00723     inline typename _Siter_base<_Iterator>::iterator_type
00724     __base(_Iterator __it)
00725     { return _Siter_base<_Iterator>::_S_base(__it); }
00726 } // namespace __gnu_debug
00727 
00728 #include <debug/safe_iterator.tcc>
00729 
00730 #endif