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