boost/boost/detail/iterator.hpp

   1 // (C) Copyright David Abrahams 2002. Permission to copy, use, modify,
   2 // sell and distribute this software is granted provided this
   3 // copyright notice appears in all copies. This software is provided
   4 // "as is" without express or implied warranty, and with no claim as
   5 // to its suitability for any purpose.
   6
   7 // Boost versions of
   8 //
   9 //    std::iterator_traits<>::iterator_category
  10 //    std::iterator_traits<>::difference_type
  11 //    std::distance()
  12 //
  13 // ...for all compilers and iterators
  14 //
  15 // Additionally, if X is a pointer
  16 //    std::iterator_traits<X>::pointer
  17
  18 // Otherwise, if partial specialization is supported or X is not a pointer
  19 //    std::iterator_traits<X>::value_type
  20 //    std::iterator_traits<X>::pointer
  21 //    std::iterator_traits<X>::reference
  22 //
  23 // See http://www.boost.org for most recent version including documentation.
  24
  25 // Revision History
  26 // 04 Mar 2001 - More attempted fixes for Intel C++ (David Abrahams)
  27 // 03 Mar 2001 - Put all implementation into namespace
  28 //               boost::detail::iterator_traits_. Some progress made on fixes
  29 //               for Intel compiler. (David Abrahams)
  30 // 02 Mar 2001 - Changed BOOST_MSVC to BOOST_MSVC_STD_ITERATOR in a few
  31 //               places. (Jeremy Siek)
  32 // 19 Feb 2001 - Improved workarounds for stock MSVC6; use yes_type and
  33 //               no_type from type_traits.hpp; stopped trying to remove_cv
  34 //               before detecting is_pointer, in honor of the new type_traits
  35 //               semantics. (David Abrahams)
  36 // 13 Feb 2001 - Make it work with nearly all standard-conforming iterators
  37 //               under raw VC6. The one category remaining which will fail is
  38 //               that of iterators derived from std::iterator but not
  39 //               boost::iterator and which redefine difference_type.
  40 // 11 Feb 2001 - Clean away code which can never be used (David Abrahams)
  41 // 09 Feb 2001 - Always have a definition for each traits member, even if it
  42 //               can't be properly deduced. These will be incomplete types in
  43 //               some cases (undefined<void>), but it helps suppress MSVC errors
  44 //               elsewhere (David Abrahams)
  45 // 07 Feb 2001 - Support for more of the traits members where possible, making
  46 //               this useful as a replacement for std::iterator_traits<T> when
  47 //               used as a default template parameter.
  48 // 06 Feb 2001 - Removed useless #includes of standard library headers
  49 //               (David Abrahams)
  50
  51 #ifndef ITERATOR_DWA122600_HPP_
  52 # define ITERATOR_DWA122600_HPP_
  53
  54 # include <boost/config.hpp>
  55 # include <boost/type_traits/remove_const.hpp>
  56 # include <boost/type_traits/detail/yes_no_type.hpp>
  57 # include <boost/type_traits/is_pointer.hpp>
  58 # include <boost/type_traits/is_base_and_derived.hpp>
  59 # include <boost/mpl/if.hpp>
  60 # include <boost/mpl/aux_/has_xxx.hpp>
  61 # include <iterator>
  62 # include <cstddef>
  63
  64 // should be the last #include
  65 #include "boost/type_traits/detail/bool_trait_def.hpp"
  66
  67 // STLPort 4.0 and betas have a bug when debugging is enabled and there is no
  68 // partial specialization: instead of an iterator_category typedef, the standard
  69 // container iterators have _Iterator_category.
  70 //
  71 // Also, whether debugging is enabled or not, there is a broken specialization
  72 // of std::iterator<output_iterator_tag,void,void,void,void> which has no
  73 // typedefs but iterator_category.
  74 # if defined(__SGI_STL_PORT)
  75
  76 #  if (__SGI_STL_PORT <= 0x410) && !defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && defined(__STL_DEBUG)
  77 #   define BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
  78 #  endif
  79
  80 #  define BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
  81
  82 # endif // STLPort <= 4.1b4 && no partial specialization
  83
  84 namespace boost { namespace detail {
  85
  86 BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type)
  87 BOOST_MPL_HAS_XXX_TRAIT_DEF(reference)
  88 BOOST_MPL_HAS_XXX_TRAIT_DEF(pointer)
  89 BOOST_MPL_HAS_XXX_TRAIT_DEF(difference_type)
  90 BOOST_MPL_HAS_XXX_TRAIT_DEF(iterator_category)
  91
  92 # if !defined(BOOST_NO_STD_ITERATOR_TRAITS)             \
  93   && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \
  94   && !defined(BOOST_MSVC_STD_ITERATOR)
  95 // Define a new template so it can be specialized
  96 template <class Iterator>
  97 struct iterator_traits
  98     : std::iterator_traits<Iterator>
  99 {};
 100 using std::distance;
 101 # elif  !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \
 102      && !defined(BOOST_MSVC_STD_ITERATOR)
 103
 104 // Rogue Wave Standard Library fools itself into thinking partial
 105 // specialization is missing on some platforms (e.g. Sun), so fails to
 106 // supply iterator_traits!
 107 template <class Iterator>
 108 struct iterator_traits
 109 {
 110     typedef typename Iterator::value_type value_type;
 111     typedef typename Iterator::reference reference;
 112     typedef typename Iterator::pointer pointer;
 113     typedef typename Iterator::difference_type difference_type;
 114     typedef typename Iterator::iterator_category iterator_category;
 115 };
 116
 117 template <class T>
 118 struct iterator_traits<T*>
 119 {
 120     typedef T value_type;
 121     typedef T& reference;
 122     typedef T* pointer;
 123     typedef std::ptrdiff_t difference_type;
 124     typedef std::random_access_iterator_tag iterator_category;
 125 };
 126
 127 template <class T>
 128 struct iterator_traits<T const*>
 129 {
 130     typedef T value_type;
 131     typedef T const& reference;
 132     typedef T const* pointer;
 133     typedef std::ptrdiff_t difference_type;
 134     typedef std::random_access_iterator_tag iterator_category;
 135 };
 136
 137 # else
 138
 139 // is_mutable_iterator --
 140 //
 141 //   A metafunction returning true iff T is a mutable iterator type
 142 //   with a nested value_type. Will only work portably with iterators
 143 //   whose operator* returns a reference, but that seems to be OK for
 144 //   the iterators supplied by Dinkumware. Some input iterators may
 145 //   compile-time if they arrive here, and if the compiler is strict
 146 //   about not taking the address of an rvalue.
 147
 148 // This one detects ordinary mutable iterators - the result of
 149 // operator* is convertible to the value_type.
 150 template <class T>
 151 type_traits::yes_type is_mutable_iterator_helper(T const*, BOOST_DEDUCED_TYPENAME T::value_type*);
 152
 153 // This one detects output iterators such as ostream_iterator which
 154 // return references to themselves.
 155 template <class T>
 156 type_traits::yes_type is_mutable_iterator_helper(T const*, T const*);
 157
 158 type_traits::no_type is_mutable_iterator_helper(...);
 159
 160 template <class T>
 161 struct is_mutable_iterator_impl
 162 {
 163     static T t;
 164
 165     BOOST_STATIC_CONSTANT(bool, value = sizeof(
 166                detail::is_mutable_iterator_helper((T*)0, &*t))
 167            == sizeof(type_traits::yes_type)
 168         );
 169 };
 170
 171 BOOST_TT_AUX_BOOL_TRAIT_DEF1(
 172     is_mutable_iterator,T,::boost::detail::is_mutable_iterator_impl<T>::value)
 173
 174
 175 // is_full_iterator_traits --
 176 //
 177 //   A metafunction returning true iff T has all the requisite nested
 178 //   types to satisfy the requirements for a fully-conforming
 179 //   iterator_traits implementation.
 180 template <class T>
 181 struct is_full_iterator_traits_impl
 182 {
 183     enum { value =
 184            has_value_type<T>::value
 185            & has_reference<T>::value
 186            & has_pointer<T>::value
 187            & has_difference_type<T>::value
 188            & has_iterator_category<T>::value
 189     };
 190 };
 191
 192 BOOST_TT_AUX_BOOL_TRAIT_DEF1(
 193     is_full_iterator_traits,T,::boost::detail::is_full_iterator_traits_impl<T>::value)
 194
 195
 196 #  ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 197 BOOST_MPL_HAS_XXX_TRAIT_DEF(_Iterator_category)
 198
 199 // is_stlport_40_debug_iterator --
 200 //
 201 //   A metafunction returning true iff T has all the requisite nested
 202 //   types to satisfy the requirements of an STLPort 4.0 debug iterator
 203 //   iterator_traits implementation.
 204 template <class T>
 205 struct is_stlport_40_debug_iterator_impl
 206 {
 207     enum { value =
 208            has_value_type<T>::value
 209            & has_reference<T>::value
 210            & has_pointer<T>::value
 211            & has_difference_type<T>::value
 212            & has__Iterator_category<T>::value
 213     };
 214 };
 215
 216 BOOST_TT_AUX_BOOL_TRAIT_DEF1(
 217     is_stlport_40_debug_iterator,T,::boost::detail::is_stlport_40_debug_iterator_impl<T>::value)
 218
 219 template <class T>
 220 struct stlport_40_debug_iterator_traits
 221 {
 222     typedef typename T::value_type value_type;
 223     typedef typename T::reference reference;
 224     typedef typename T::pointer pointer;
 225     typedef typename T::difference_type difference_type;
 226     typedef typename T::_Iterator_category iterator_category;
 227 };
 228 # endif // BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 229
 230 template <class T> struct pointer_iterator_traits;
 231
 232 # ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 233 template <class T>
 234 struct pointer_iterator_traits<T*>
 235 {
 236     typedef remove_const<T>::type value_type;
 237     typedef T* pointer;
 238     typedef T& reference;
 239     typedef std::random_access_iterator_tag iterator_category;
 240     typedef std::ptrdiff_t difference_type;
 241 };
 242 # else
 243 template <class Ptr>
 244 struct must_manually_specialize_boost_detail_iterator_traits;
 245
 246 template <class T>
 247 struct pointer_iterator_traits
 248 {
 249     typedef T pointer;
 250     typedef std::random_access_iterator_tag iterator_category;
 251     typedef std::ptrdiff_t difference_type;
 252
 253     // Makes MSVC6 happy under some circumstances
 254     typedef must_manually_specialize_boost_detail_iterator_traits<T> value_type;
 255     typedef must_manually_specialize_boost_detail_iterator_traits<T> reference;
 256 };
 257
 258 // Use this as a base class in manual iterator_traits specializations
 259 // for pointer types. T should be the value_type. CV should be the
 260 // cv-qualified value_type to which */& is added in order to produce
 261 // pointer/reference.
 262 template <class T, class CV = T>
 263 struct ptr_iter_traits
 264 {
 265     typedef T value_type;
 266     typedef CV* pointer;
 267     typedef CV& reference;
 268     typedef std::random_access_iterator_tag iterator_category;
 269     typedef std::ptrdiff_t difference_type;
 270 };
 271 # endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 272
 273 // We'll sort iterator types into one of these classifications, from which we
 274 // can determine the difference_type, pointer, reference, and value_type
 275 template <class Iterator>
 276 struct standard_iterator_traits
 277 {
 278     typedef typename Iterator::difference_type difference_type;
 279     typedef typename Iterator::value_type value_type;
 280     typedef typename Iterator::pointer pointer;
 281     typedef typename Iterator::reference reference;
 282     typedef typename Iterator::iterator_category iterator_category;
 283 };
 284
 285 template <class Iterator>
 286 struct msvc_stdlib_mutable_traits
 287     : std::iterator_traits<Iterator>
 288 {
 289     typedef typename std::iterator_traits<Iterator>::distance_type difference_type;
 290     typedef value_type* pointer;
 291     typedef value_type& reference;
 292 };
 293
 294 template <class Iterator>
 295 struct msvc_stdlib_const_traits
 296     : std::iterator_traits<Iterator>
 297 {
 298     typedef typename std::iterator_traits<Iterator>::distance_type difference_type;
 299     typedef const value_type* pointer;
 300     typedef const value_type& reference;
 301 };
 302
 303 # ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
 304 template <class Iterator>
 305 struct is_bad_output_iterator
 306     : is_base_and_derived<
 307         std::iterator<std::output_iterator_tag,void,void,void,void>
 308         , Iterator>
 309 {
 310 };
 311
 312 struct bad_output_iterator_traits
 313 {
 314     typedef void value_type;
 315     typedef void difference_type;
 316     typedef std::output_iterator_tag iterator_category;
 317     typedef void pointer;
 318     typedef void reference;
 319 };
 320 # endif
 321
 322 // If we're looking at an MSVC6 (old Dinkumware) ``standard''
 323 // iterator, this will generate an appropriate traits class.
 324 template <class Iterator>
 325 struct msvc_stdlib_iterator_traits
 326     : mpl::if_<
 327        is_mutable_iterator<Iterator>
 328        , msvc_stdlib_mutable_traits<Iterator>
 329        , msvc_stdlib_const_traits<Iterator>
 330       >::type
 331 {};
 332
 333 template <class Iterator>
 334 struct non_pointer_iterator_traits
 335     : mpl::if_<
 336         // if the iterator contains all the right nested types...
 337         is_full_iterator_traits<Iterator>
 338         // Use a standard iterator_traits implementation
 339         , standard_iterator_traits<Iterator>
 340 # ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 341         // Check for STLPort 4.0 broken _Iterator_category type
 342         , mpl::if_<
 343              is_stlport_40_debug_iterator<Iterator>
 344              , stlport_40_debug_iterator_traits<Iterator>
 345 # endif
 346         // Otherwise, assume it's a Dinkum iterator
 347         , msvc_stdlib_iterator_traits<Iterator>
 348 # ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 349         >::type
 350 # endif
 351     >::type
 352 {
 353 };
 354
 355 template <class Iterator>
 356 struct iterator_traits_aux
 357     : mpl::if_<
 358         is_pointer<Iterator>
 359         , pointer_iterator_traits<Iterator>
 360         , non_pointer_iterator_traits<Iterator>
 361     >::type
 362 {
 363 };
 364
 365 template <class Iterator>
 366 struct iterator_traits
 367 {
 368     // Explicit forwarding from base class needed to keep MSVC6 happy
 369     // under some circumstances.
 370  private:
 371 # ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
 372     typedef
 373     typename mpl::if_<
 374         is_bad_output_iterator<Iterator>
 375         , bad_output_iterator_traits
 376         , iterator_traits_aux<Iterator>
 377     >::type base;
 378 # else
 379     typedef iterator_traits_aux<Iterator> base;
 380 # endif
 381  public:
 382     typedef typename base::value_type value_type;
 383     typedef typename base::pointer pointer;
 384     typedef typename base::reference reference;
 385     typedef typename base::difference_type difference_type;
 386     typedef typename base::iterator_category iterator_category;
 387 };
 388
 389 // This specialization cuts off ETI (Early Template Instantiation) for MSVC.
 390 template <> struct iterator_traits<int>{};
 391
 392 namespace iterator_traits_
 393 {
 394   template <class Iterator, class Difference>
 395   struct distance_select
 396   {
 397       static Difference execute(Iterator i1, const Iterator i2, ...)
 398       {
 399           typename Difference result = 0;
 400           while (i1 != i2)
 401           {
 402               ++i1;
 403               ++result;
 404           }
 405           return result;
 406       }
 407
 408       static Difference execute(Iterator i1, const Iterator i2, std::random_access_iterator_tag*)
 409       {
 410           return i2 - i1;
 411       }
 412   };
 413 } // namespace boost::detail::iterator_traits_
 414
 415 template <class Iterator>
 416 inline typename iterator_traits<Iterator>::difference_type
 417 distance(Iterator first, Iterator last)
 418 {
 419     typedef typename iterator_traits<Iterator>::difference_type diff_t;
 420     typedef typename ::boost::detail::iterator_traits<Iterator>::iterator_category iterator_category;
 421
 422     return iterator_traits_::distance_select<Iterator,diff_t>::execute(
 423         first, last, (iterator_category*)0);
 424 }
 425 # endif // workarounds
 426
 427 }} // namespace boost::detail
 428
 429 # undef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 430 # undef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
 431
 432 #endif // ITERATOR_DWA122600_HPP_