boost/detail/iterator.hpp
// (C) Copyright David Abrahams 2002. // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // Boost versions of // // std::iterator_traits<>::iterator_category // std::iterator_traits<>::difference_type // std::distance() // // ...for all compilers and iterators // // Additionally, if X is a pointer // std::iterator_traits<X>::pointer // Otherwise, if partial specialization is supported or X is not a pointer // std::iterator_traits<X>::value_type // std::iterator_traits<X>::pointer // std::iterator_traits<X>::reference // // See http://www.boost.org for most recent version including documentation. // Revision History // 04 Mar 2001 - More attempted fixes for Intel C++ (David Abrahams) // 03 Mar 2001 - Put all implementation into namespace // boost::detail::iterator_traits_. Some progress made on fixes // for Intel compiler. (David Abrahams) // 02 Mar 2001 - Changed BOOST_MSVC to BOOST_MSVC_STD_ITERATOR in a few // places. (Jeremy Siek) // 19 Feb 2001 - Improved workarounds for stock MSVC6; use yes_type and // no_type from type_traits.hpp; stopped trying to remove_cv // before detecting is_pointer, in honor of the new type_traits // semantics. (David Abrahams) // 13 Feb 2001 - Make it work with nearly all standard-conforming iterators // under raw VC6. The one category remaining which will fail is // that of iterators derived from std::iterator but not // boost::iterator and which redefine difference_type. // 11 Feb 2001 - Clean away code which can never be used (David Abrahams) // 09 Feb 2001 - Always have a definition for each traits member, even if it // can't be properly deduced. These will be incomplete types in // some cases (undefined<void>), but it helps suppress MSVC errors // elsewhere (David Abrahams) // 07 Feb 2001 - Support for more of the traits members where possible, making // this useful as a replacement for std::iterator_traits<T> when // used as a default template parameter. // 06 Feb 2001 - Removed useless #includes of standard library headers // (David Abrahams) #ifndef ITERATOR_DWA122600_HPP_ # define ITERATOR_DWA122600_HPP_ # include <boost/config.hpp> # include <iterator> // STLPort 4.0 and betas have a bug when debugging is enabled and there is no // partial specialization: instead of an iterator_category typedef, the standard // container iterators have _Iterator_category. // // Also, whether debugging is enabled or not, there is a broken specialization // of std::iterator<output_iterator_tag,void,void,void,void> which has no // typedefs but iterator_category. # if defined(__SGI_STL_PORT) # if (__SGI_STL_PORT <= 0x410) && !defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && defined(__STL_DEBUG) # define BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF # endif # define BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION # endif // STLPort <= 4.1b4 && no partial specialization # if !defined(BOOST_NO_STD_ITERATOR_TRAITS) \ && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \ && !defined(BOOST_MSVC_STD_ITERATOR) namespace boost { namespace detail { // Define a new template so it can be specialized template <class Iterator> struct iterator_traits : std::iterator_traits<Iterator> {}; using std::distance; }} // namespace boost::detail # else # if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \ && !defined(BOOST_MSVC_STD_ITERATOR) // This is the case where everything conforms except BOOST_NO_STD_ITERATOR_TRAITS namespace boost { namespace detail { // Rogue Wave Standard Library fools itself into thinking partial // specialization is missing on some platforms (e.g. Sun), so fails to // supply iterator_traits! template <class Iterator> struct iterator_traits { typedef typename Iterator::value_type value_type; typedef typename Iterator::reference reference; typedef typename Iterator::pointer pointer; typedef typename Iterator::difference_type difference_type; typedef typename Iterator::iterator_category iterator_category; }; template <class T> struct iterator_traits<T*> { typedef T value_type; typedef T& reference; typedef T* pointer; typedef std::ptrdiff_t difference_type; typedef std::random_access_iterator_tag iterator_category; }; template <class T> struct iterator_traits<T const*> { typedef T value_type; typedef T const& reference; typedef T const* pointer; typedef std::ptrdiff_t difference_type; typedef std::random_access_iterator_tag iterator_category; }; }} // namespace boost::detail # else # include <boost/type_traits/remove_const.hpp> # include <boost/type_traits/detail/yes_no_type.hpp> # include <boost/type_traits/is_pointer.hpp> # ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION # include <boost/type_traits/is_same.hpp> # include <boost/type_traits/remove_pointer.hpp> # endif # ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION # include <boost/type_traits/is_base_and_derived.hpp> # endif # include <boost/mpl/if.hpp> # include <boost/mpl/has_xxx.hpp> # include <cstddef> // should be the last #include # include "boost/type_traits/detail/bool_trait_def.hpp" namespace boost { namespace detail { BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type) BOOST_MPL_HAS_XXX_TRAIT_DEF(reference) BOOST_MPL_HAS_XXX_TRAIT_DEF(pointer) BOOST_MPL_HAS_XXX_TRAIT_DEF(difference_type) BOOST_MPL_HAS_XXX_TRAIT_DEF(iterator_category) // is_mutable_iterator -- // // A metafunction returning true iff T is a mutable iterator type // with a nested value_type. Will only work portably with iterators // whose operator* returns a reference, but that seems to be OK for // the iterators supplied by Dinkumware. Some input iterators may // compile-time if they arrive here, and if the compiler is strict // about not taking the address of an rvalue. // This one detects ordinary mutable iterators - the result of // operator* is convertible to the value_type. template <class T> type_traits::yes_type is_mutable_iterator_helper(T const*, BOOST_DEDUCED_TYPENAME T::value_type*); // Since you can't take the address of an rvalue, the guts of // is_mutable_iterator_impl will fail if we use &*t directly. This // makes sure we can still work with non-lvalue iterators. template <class T> T* mutable_iterator_lvalue_helper(T& x); int mutable_iterator_lvalue_helper(...); // This one detects output iterators such as ostream_iterator which // return references to themselves. template <class T> type_traits::yes_type is_mutable_iterator_helper(T const*, T const*); type_traits::no_type is_mutable_iterator_helper(...); template <class T> struct is_mutable_iterator_impl { static T t; BOOST_STATIC_CONSTANT( bool, value = sizeof( detail::is_mutable_iterator_helper( (T*)0 , mutable_iterator_lvalue_helper(*t) // like &*t )) == sizeof(type_traits::yes_type) ); }; BOOST_TT_AUX_BOOL_TRAIT_DEF1( is_mutable_iterator,T,::boost::detail::is_mutable_iterator_impl<T>::value) // is_full_iterator_traits -- // // A metafunction returning true iff T has all the requisite nested // types to satisfy the requirements for a fully-conforming // iterator_traits implementation. template <class T> struct is_full_iterator_traits_impl { enum { value = has_value_type<T>::value & has_reference<T>::value & has_pointer<T>::value & has_difference_type<T>::value & has_iterator_category<T>::value }; }; BOOST_TT_AUX_BOOL_TRAIT_DEF1( is_full_iterator_traits,T,::boost::detail::is_full_iterator_traits_impl<T>::value) # ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF BOOST_MPL_HAS_XXX_TRAIT_DEF(_Iterator_category) // is_stlport_40_debug_iterator -- // // A metafunction returning true iff T has all the requisite nested // types to satisfy the requirements of an STLPort 4.0 debug iterator // iterator_traits implementation. template <class T> struct is_stlport_40_debug_iterator_impl { enum { value = has_value_type<T>::value & has_reference<T>::value & has_pointer<T>::value & has_difference_type<T>::value & has__Iterator_category<T>::value }; }; BOOST_TT_AUX_BOOL_TRAIT_DEF1( is_stlport_40_debug_iterator,T,::boost::detail::is_stlport_40_debug_iterator_impl<T>::value) template <class T> struct stlport_40_debug_iterator_traits { typedef typename T::value_type value_type; typedef typename T::reference reference; typedef typename T::pointer pointer; typedef typename T::difference_type difference_type; typedef typename T::_Iterator_category iterator_category; }; # endif // BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF template <class T> struct pointer_iterator_traits; # ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION template <class T> struct pointer_iterator_traits<T*> { typedef typename remove_const<T>::type value_type; typedef T* pointer; typedef T& reference; typedef std::random_access_iterator_tag iterator_category; typedef std::ptrdiff_t difference_type; }; # else // In case of no template partial specialization, and if T is a // pointer, iterator_traits<T>::value_type can still be computed. For // some basic types, remove_pointer is manually defined in // type_traits/broken_compiler_spec.hpp. For others, do it yourself. template<class P> class please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee; template<class P> struct pointer_value_type : mpl::if_< is_same<P, typename remove_pointer<P>::type> , please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P> , typename remove_const< typename remove_pointer<P>::type >::type > { }; template<class P> struct pointer_reference : mpl::if_< is_same<P, typename remove_pointer<P>::type> , please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P> , typename remove_pointer<P>::type& > { }; template <class T> struct pointer_iterator_traits { typedef T pointer; typedef std::random_access_iterator_tag iterator_category; typedef std::ptrdiff_t difference_type; typedef typename pointer_value_type<T>::type value_type; typedef typename pointer_reference<T>::type reference; }; # endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION // We'll sort iterator types into one of these classifications, from which we // can determine the difference_type, pointer, reference, and value_type template <class Iterator> struct standard_iterator_traits { typedef typename Iterator::difference_type difference_type; typedef typename Iterator::value_type value_type; typedef typename Iterator::pointer pointer; typedef typename Iterator::reference reference; typedef typename Iterator::iterator_category iterator_category; }; template <class Iterator> struct msvc_stdlib_mutable_traits : std::iterator_traits<Iterator> { typedef typename std::iterator_traits<Iterator>::distance_type difference_type; typedef typename std::iterator_traits<Iterator>::value_type* pointer; typedef typename std::iterator_traits<Iterator>::value_type& reference; }; template <class Iterator> struct msvc_stdlib_const_traits : std::iterator_traits<Iterator> { typedef typename std::iterator_traits<Iterator>::distance_type difference_type; typedef const typename std::iterator_traits<Iterator>::value_type* pointer; typedef const typename std::iterator_traits<Iterator>::value_type& reference; }; # ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION template <class Iterator> struct is_bad_output_iterator : is_base_and_derived< std::iterator<std::output_iterator_tag,void,void,void,void> , Iterator> { }; struct bad_output_iterator_traits { typedef void value_type; typedef void difference_type; typedef std::output_iterator_tag iterator_category; typedef void pointer; typedef void reference; }; # endif // If we're looking at an MSVC6 (old Dinkumware) ``standard'' // iterator, this will generate an appropriate traits class. template <class Iterator> struct msvc_stdlib_iterator_traits : mpl::if_< is_mutable_iterator<Iterator> , msvc_stdlib_mutable_traits<Iterator> , msvc_stdlib_const_traits<Iterator> >::type {}; template <class Iterator> struct non_pointer_iterator_traits : mpl::if_< // if the iterator contains all the right nested types... is_full_iterator_traits<Iterator> // Use a standard iterator_traits implementation , standard_iterator_traits<Iterator> # ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF // Check for STLPort 4.0 broken _Iterator_category type , mpl::if_< is_stlport_40_debug_iterator<Iterator> , stlport_40_debug_iterator_traits<Iterator> # endif // Otherwise, assume it's a Dinkum iterator , msvc_stdlib_iterator_traits<Iterator> # ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF >::type # endif >::type { }; template <class Iterator> struct iterator_traits_aux : mpl::if_< is_pointer<Iterator> , pointer_iterator_traits<Iterator> , non_pointer_iterator_traits<Iterator> >::type { }; template <class Iterator> struct iterator_traits { // Explicit forwarding from base class needed to keep MSVC6 happy // under some circumstances. private: # ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION typedef typename mpl::if_< is_bad_output_iterator<Iterator> , bad_output_iterator_traits , iterator_traits_aux<Iterator> >::type base; # else typedef iterator_traits_aux<Iterator> base; # endif public: typedef typename base::value_type value_type; typedef typename base::pointer pointer; typedef typename base::reference reference; typedef typename base::difference_type difference_type; typedef typename base::iterator_category iterator_category; }; // This specialization cuts off ETI (Early Template Instantiation) for MSVC. template <> struct iterator_traits<int> { typedef int value_type; typedef int pointer; typedef int reference; typedef int difference_type; typedef int iterator_category; }; }} // namespace boost::detail # endif // workarounds namespace boost { namespace detail { namespace iterator_traits_ { template <class Iterator, class Difference> struct distance_select { static Difference execute(Iterator i1, const Iterator i2, ...) { Difference result = 0; while (i1 != i2) { ++i1; ++result; } return result; } static Difference execute(Iterator i1, const Iterator i2, std::random_access_iterator_tag*) { return i2 - i1; } }; } // namespace boost::detail::iterator_traits_ template <class Iterator> inline typename iterator_traits<Iterator>::difference_type distance(Iterator first, Iterator last) { typedef typename iterator_traits<Iterator>::difference_type diff_t; typedef typename ::boost::detail::iterator_traits<Iterator>::iterator_category iterator_category; return iterator_traits_::distance_select<Iterator,diff_t>::execute( first, last, (iterator_category*)0); } }} # endif # undef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF # undef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION #endif // ITERATOR_DWA122600_HPP_