boost/detail/iterator.hpp

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