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 <iterator>
  56
  57 // STLPort 4.0 and betas have a bug when debugging is enabled and there is no
  58 // partial specialization: instead of an iterator_category typedef, the standard
  59 // container iterators have _Iterator_category.
  60 //
  61 // Also, whether debugging is enabled or not, there is a broken specialization
  62 // of std::iterator<output_iterator_tag,void,void,void,void> which has no
  63 // typedefs but iterator_category.
  64 # if defined(__SGI_STL_PORT)
  65
  66 #  if (__SGI_STL_PORT <= 0x410) && !defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && defined(__STL_DEBUG)
  67 #   define BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
  68 #  endif
  69
  70 #  define BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
  71
  72 # endif // STLPort <= 4.1b4 && no partial specialization
  73
  74 # if !defined(BOOST_NO_STD_ITERATOR_TRAITS)             \
  75   && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \
  76   && !defined(BOOST_MSVC_STD_ITERATOR)
  77
  78 namespace boost { namespace detail {
  79
  80 // Define a new template so it can be specialized
  81 template <class Iterator>
  82 struct iterator_traits
  83     : std::iterator_traits<Iterator>
  84 {};
  85 using std::distance;
  86
  87 }} // namespace boost::detail
  88
  89 # else
  90
  91 #  if  !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)  \
  92     && !defined(BOOST_MSVC_STD_ITERATOR)
  93
  94 // This is the case where everything conforms except BOOST_NO_STD_ITERATOR_TRAITS
  95
  96 namespace boost { namespace detail {
  97
  98 // Rogue Wave Standard Library fools itself into thinking partial
  99 // specialization is missing on some platforms (e.g. Sun), so fails to
 100 // supply iterator_traits!
 101 template <class Iterator>
 102 struct iterator_traits
 103 {
 104     typedef typename Iterator::value_type value_type;
 105     typedef typename Iterator::reference reference;
 106     typedef typename Iterator::pointer pointer;
 107     typedef typename Iterator::difference_type difference_type;
 108     typedef typename Iterator::iterator_category iterator_category;
 109 };
 110
 111 template <class T>
 112 struct iterator_traits<T*>
 113 {
 114     typedef T value_type;
 115     typedef T& reference;
 116     typedef T* pointer;
 117     typedef std::ptrdiff_t difference_type;
 118     typedef std::random_access_iterator_tag iterator_category;
 119 };
 120
 121 template <class T>
 122 struct iterator_traits<T const*>
 123 {
 124     typedef T value_type;
 125     typedef T const& reference;
 126     typedef T const* pointer;
 127     typedef std::ptrdiff_t difference_type;
 128     typedef std::random_access_iterator_tag iterator_category;
 129 };
 130
 131 }} // namespace boost::detail
 132
 133 #  else
 134
 135 # include <boost/type_traits/remove_const.hpp>
 136 # include <boost/type_traits/detail/yes_no_type.hpp>
 137 # include <boost/type_traits/is_pointer.hpp>
 138
 139 # ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 140 #  include <boost/type_traits/is_same.hpp>
 141 #  include <boost/type_traits/remove_pointer.hpp>
 142 # endif
 143 # ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
 144 #  include <boost/type_traits/is_base_and_derived.hpp>
 145 # endif
 146
 147 # include <boost/mpl/if.hpp>
 148 # include <boost/mpl/aux_/has_xxx.hpp>
 149 # include <cstddef>
 150
 151 // should be the last #include
 152 # include "boost/type_traits/detail/bool_trait_def.hpp"
 153
 154 namespace boost { namespace detail {
 155
 156 BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type)
 157 BOOST_MPL_HAS_XXX_TRAIT_DEF(reference)
 158 BOOST_MPL_HAS_XXX_TRAIT_DEF(pointer)
 159 BOOST_MPL_HAS_XXX_TRAIT_DEF(difference_type)
 160 BOOST_MPL_HAS_XXX_TRAIT_DEF(iterator_category)
 161
 162 // is_mutable_iterator --
 163 //
 164 //   A metafunction returning true iff T is a mutable iterator type
 165 //   with a nested value_type. Will only work portably with iterators
 166 //   whose operator* returns a reference, but that seems to be OK for
 167 //   the iterators supplied by Dinkumware. Some input iterators may
 168 //   compile-time if they arrive here, and if the compiler is strict
 169 //   about not taking the address of an rvalue.
 170
 171 // This one detects ordinary mutable iterators - the result of
 172 // operator* is convertible to the value_type.
 173 template <class T>
 174 type_traits::yes_type is_mutable_iterator_helper(T const*, BOOST_DEDUCED_TYPENAME T::value_type*);
 175
 176 // Since you can't take the address of an rvalue, the guts of
 177 // is_mutable_iterator_impl will fail if we use &*t directly.  This
 178 // makes sure we can still work with non-lvalue iterators.
 179 template <class T> T* mutable_iterator_lvalue_helper(T& x);
 180 int mutable_iterator_lvalue_helper(...);
 181
 182
 183 // This one detects output iterators such as ostream_iterator which
 184 // return references to themselves.
 185 template <class T>
 186 type_traits::yes_type is_mutable_iterator_helper(T const*, T const*);
 187
 188 type_traits::no_type is_mutable_iterator_helper(...);
 189
 190 template <class T>
 191 struct is_mutable_iterator_impl
 192 {
 193     static T t;
 194
 195     BOOST_STATIC_CONSTANT(
 196         bool, value = sizeof(
 197             detail::is_mutable_iterator_helper(
 198                 (T*)0
 199               , mutable_iterator_lvalue_helper(*t) // like &*t
 200             ))
 201         == sizeof(type_traits::yes_type)
 202     );
 203 };
 204
 205 BOOST_TT_AUX_BOOL_TRAIT_DEF1(
 206     is_mutable_iterator,T,::boost::detail::is_mutable_iterator_impl<T>::value)
 207
 208
 209 // is_full_iterator_traits --
 210 //
 211 //   A metafunction returning true iff T has all the requisite nested
 212 //   types to satisfy the requirements for a fully-conforming
 213 //   iterator_traits implementation.
 214 template <class T>
 215 struct is_full_iterator_traits_impl
 216 {
 217     enum { value =
 218            has_value_type<T>::value
 219            & has_reference<T>::value
 220            & has_pointer<T>::value
 221            & has_difference_type<T>::value
 222            & has_iterator_category<T>::value
 223     };
 224 };
 225
 226 BOOST_TT_AUX_BOOL_TRAIT_DEF1(
 227     is_full_iterator_traits,T,::boost::detail::is_full_iterator_traits_impl<T>::value)
 228
 229
 230 #   ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 231 BOOST_MPL_HAS_XXX_TRAIT_DEF(_Iterator_category)
 232
 233 // is_stlport_40_debug_iterator --
 234 //
 235 //   A metafunction returning true iff T has all the requisite nested
 236 //   types to satisfy the requirements of an STLPort 4.0 debug iterator
 237 //   iterator_traits implementation.
 238 template <class T>
 239 struct is_stlport_40_debug_iterator_impl
 240 {
 241     enum { value =
 242            has_value_type<T>::value
 243            & has_reference<T>::value
 244            & has_pointer<T>::value
 245            & has_difference_type<T>::value
 246            & has__Iterator_category<T>::value
 247     };
 248 };
 249
 250 BOOST_TT_AUX_BOOL_TRAIT_DEF1(
 251     is_stlport_40_debug_iterator,T,::boost::detail::is_stlport_40_debug_iterator_impl<T>::value)
 252
 253 template <class T>
 254 struct stlport_40_debug_iterator_traits
 255 {
 256     typedef typename T::value_type value_type;
 257     typedef typename T::reference reference;
 258     typedef typename T::pointer pointer;
 259     typedef typename T::difference_type difference_type;
 260     typedef typename T::_Iterator_category iterator_category;
 261 };
 262 #   endif // BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 263
 264 template <class T> struct pointer_iterator_traits;
 265
 266 #   ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 267 template <class T>
 268 struct pointer_iterator_traits<T*>
 269 {
 270     typedef remove_const<T>::type value_type;
 271     typedef T* pointer;
 272     typedef T& reference;
 273     typedef std::random_access_iterator_tag iterator_category;
 274     typedef std::ptrdiff_t difference_type;
 275 };
 276 #   else
 277
 278 // In case of no template partial specialization, and if T is a
 279 // pointer, iterator_traits<T>::value_type can still be computed.  For
 280 // some basic types, remove_pointer is manually defined in
 281 // type_traits/broken_compiler_spec.hpp. For others, do it yourself.
 282
 283 template<class P> class please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee;
 284
 285 template<class P>
 286 struct pointer_value_type
 287   : mpl::if_<
 288         is_same<P, typename remove_pointer<P>::type>
 289       , please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P>
 290       , typename remove_const<
 291             typename remove_pointer<P>::type
 292         >::type
 293     >
 294 {
 295 };
 296
 297
 298 template<class P>
 299 struct pointer_reference
 300   : mpl::if_<
 301         is_same<P, typename remove_pointer<P>::type>
 302       , please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee<P>
 303       , typename remove_pointer<P>::type&
 304     >
 305 {
 306 };
 307
 308 template <class T>
 309 struct pointer_iterator_traits
 310 {
 311     typedef T pointer;
 312     typedef std::random_access_iterator_tag iterator_category;
 313     typedef std::ptrdiff_t difference_type;
 314
 315     typedef typename pointer_value_type<T>::type value_type;
 316     typedef typename pointer_reference<T>::type reference;
 317 };
 318
 319 #   endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 320
 321 // We'll sort iterator types into one of these classifications, from which we
 322 // can determine the difference_type, pointer, reference, and value_type
 323 template <class Iterator>
 324 struct standard_iterator_traits
 325 {
 326     typedef typename Iterator::difference_type difference_type;
 327     typedef typename Iterator::value_type value_type;
 328     typedef typename Iterator::pointer pointer;
 329     typedef typename Iterator::reference reference;
 330     typedef typename Iterator::iterator_category iterator_category;
 331 };
 332
 333 template <class Iterator>
 334 struct msvc_stdlib_mutable_traits
 335     : std::iterator_traits<Iterator>
 336 {
 337     typedef typename std::iterator_traits<Iterator>::distance_type difference_type;
 338     typedef value_type* pointer;
 339     typedef value_type& reference;
 340 };
 341
 342 template <class Iterator>
 343 struct msvc_stdlib_const_traits
 344     : std::iterator_traits<Iterator>
 345 {
 346     typedef typename std::iterator_traits<Iterator>::distance_type difference_type;
 347     typedef const value_type* pointer;
 348     typedef const value_type& reference;
 349 };
 350
 351 #   ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
 352 template <class Iterator>
 353 struct is_bad_output_iterator
 354     : is_base_and_derived<
 355         std::iterator<std::output_iterator_tag,void,void,void,void>
 356         , Iterator>
 357 {
 358 };
 359
 360 struct bad_output_iterator_traits
 361 {
 362     typedef void value_type;
 363     typedef void difference_type;
 364     typedef std::output_iterator_tag iterator_category;
 365     typedef void pointer;
 366     typedef void reference;
 367 };
 368 #   endif
 369
 370 // If we're looking at an MSVC6 (old Dinkumware) ``standard''
 371 // iterator, this will generate an appropriate traits class.
 372 template <class Iterator>
 373 struct msvc_stdlib_iterator_traits
 374     : mpl::if_<
 375        is_mutable_iterator<Iterator>
 376        , msvc_stdlib_mutable_traits<Iterator>
 377        , msvc_stdlib_const_traits<Iterator>
 378       >::type
 379 {};
 380
 381 template <class Iterator>
 382 struct non_pointer_iterator_traits
 383     : mpl::if_<
 384         // if the iterator contains all the right nested types...
 385         is_full_iterator_traits<Iterator>
 386         // Use a standard iterator_traits implementation
 387         , standard_iterator_traits<Iterator>
 388 #   ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 389         // Check for STLPort 4.0 broken _Iterator_category type
 390         , mpl::if_<
 391              is_stlport_40_debug_iterator<Iterator>
 392              , stlport_40_debug_iterator_traits<Iterator>
 393 #   endif
 394         // Otherwise, assume it's a Dinkum iterator
 395         , msvc_stdlib_iterator_traits<Iterator>
 396 #   ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 397         >::type
 398 #   endif
 399     >::type
 400 {
 401 };
 402
 403 template <class Iterator>
 404 struct iterator_traits_aux
 405     : mpl::if_<
 406         is_pointer<Iterator>
 407         , pointer_iterator_traits<Iterator>
 408         , non_pointer_iterator_traits<Iterator>
 409     >::type
 410 {
 411 };
 412
 413 template <class Iterator>
 414 struct iterator_traits
 415 {
 416     // Explicit forwarding from base class needed to keep MSVC6 happy
 417     // under some circumstances.
 418  private:
 419 #   ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
 420     typedef
 421     typename mpl::if_<
 422         is_bad_output_iterator<Iterator>
 423         , bad_output_iterator_traits
 424         , iterator_traits_aux<Iterator>
 425     >::type base;
 426 #   else
 427     typedef iterator_traits_aux<Iterator> base;
 428 #   endif
 429  public:
 430     typedef typename base::value_type value_type;
 431     typedef typename base::pointer pointer;
 432     typedef typename base::reference reference;
 433     typedef typename base::difference_type difference_type;
 434     typedef typename base::iterator_category iterator_category;
 435 };
 436
 437 // This specialization cuts off ETI (Early Template Instantiation) for MSVC.
 438 template <> struct iterator_traits<int>
 439 {
 440     typedef int value_type;
 441     typedef int pointer;
 442     typedef int reference;
 443     typedef int difference_type;
 444     typedef int iterator_category;
 445 };
 446
 447 }} // namespace boost::detail
 448
 449 #  endif // workarounds
 450
 451 namespace boost { namespace detail {
 452
 453 namespace iterator_traits_
 454 {
 455   template <class Iterator, class Difference>
 456   struct distance_select
 457   {
 458       static Difference execute(Iterator i1, const Iterator i2, ...)
 459       {
 460           Difference result = 0;
 461           while (i1 != i2)
 462           {
 463               ++i1;
 464               ++result;
 465           }
 466           return result;
 467       }
 468
 469       static Difference execute(Iterator i1, const Iterator i2, std::random_access_iterator_tag*)
 470       {
 471           return i2 - i1;
 472       }
 473   };
 474 } // namespace boost::detail::iterator_traits_
 475
 476 template <class Iterator>
 477 inline typename iterator_traits<Iterator>::difference_type
 478 distance(Iterator first, Iterator last)
 479 {
 480     typedef typename iterator_traits<Iterator>::difference_type diff_t;
 481     typedef typename ::boost::detail::iterator_traits<Iterator>::iterator_category iterator_category;
 482
 483     return iterator_traits_::distance_select<Iterator,diff_t>::execute(
 484         first, last, (iterator_category*)0);
 485 }
 486
 487 }}
 488
 489 # endif
 490
 491
 492 # undef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 493 # undef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
 494
 495 #endif // ITERATOR_DWA122600_HPP_