boost/boost/detail/iterator.hpp

   1 // (C) Copyright David Abrahams 2001. 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 // CAVEAT: When using the VC6 standard library, an iterator derived from
  24 // std::iterator but not boost::iterator or from one supplied by the standard
  25 // will always have pointer == const value_type* and reference == const
  26 // value_type&, whether that's correct or not.
  27
  28 // See http://www.boost.org for most recent version including documentation.
  29
  30 // Revision History
  31 // 04 Mar 2001 - More attempted fixes for Intel C++ (David Abrahams)
  32 // 03 Mar 2001 - Put all implementation into namespace
  33 //               boost::detail::iterator_traits_. Some progress made on fixes
  34 //               for Intel compiler. (David Abrahams)
  35 // 02 Mar 2001 - Changed BOOST_MSVC to BOOST_MSVC_STD_ITERATOR in a few
  36 //               places. (Jeremy Siek)
  37 // 19 Feb 2001 - Improved workarounds for stock MSVC6; use yes_type and
  38 //               no_type from type_traits.hpp; stopped trying to remove_cv
  39 //               before detecting is_pointer, in honor of the new type_traits
  40 //               semantics. (David Abrahams)
  41 // 13 Feb 2001 - Make it work with nearly all standard-conforming iterators
  42 //               under raw VC6. The one category remaining which will fail is
  43 //               that of iterators derived from std::iterator but not
  44 //               boost::iterator and which redefine difference_type.
  45 // 11 Feb 2001 - Clean away code which can never be used (David Abrahams)
  46 // 09 Feb 2001 - Always have a definition for each traits member, even if it
  47 //               can't be properly deduced. These will be incomplete types in
  48 //               some cases (undefined<void>), but it helps suppress MSVC errors
  49 //               elsewhere (David Abrahams)
  50 // 07 Feb 2001 - Support for more of the traits members where possible, making
  51 //               this useful as a replacement for std::iterator_traits<T> when
  52 //               used as a default template parameter.
  53 // 06 Feb 2001 - Removed useless #includes of standard library headers
  54 //               (David Abrahams)
  55
  56 #ifndef ITERATOR_DWA122600_HPP_
  57 # define ITERATOR_DWA122600_HPP_
  58
  59 # include <boost/config.hpp>
  60 # include <boost/type_traits.hpp>
  61 # include <boost/iterator.hpp>
  62 # include <iterator>
  63 # include <cstddef>
  64
  65 # if defined(BOOST_MSVC_STD_ITERATOR) && !defined(__SGI_STL_PORT)
  66 #  include <xtree>
  67 #  include <deque>
  68 #  include <list>
  69 # endif
  70
  71
  72 // STLPort 4.0 and betas have a bug when debugging is enabled and there is no
  73 // partial specialization: instead of an iterator_category typedef, the standard
  74 // container iterators have _Iterator_category.
  75 //
  76 // Also, whether debugging is enabled or not, there is a broken specialization
  77 // of std::iterator<output_iterator_tag,void,void,void,void> which has no
  78 // typedefs but iterator_category.
  79 # if defined(__SGI_STL_PORT) && (__SGI_STL_PORT <= 0x410) && !defined(__STL_CLASS_PARTIAL_SPECIALIZATION)
  80
  81 #  ifdef __STL_DEBUG
  82 #   define BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
  83 #  endif
  84
  85 #  define BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
  86
  87 # endif // STLPort <= 4.1b4 && no partial specialization
  88
  89 namespace boost { namespace detail {
  90 # if !defined(BOOST_NO_STD_ITERATOR_TRAITS) && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) && !defined(BOOST_MSVC_STD_ITERATOR)
  91 using std::iterator_traits;
  92 using std::distance;
  93 # else
  94
  95 namespace iterator_traits_ {
  96
  97 // Workarounds for less-capable implementations
  98 template <bool is_ptr> struct iterator_traits_select;
  99
 100 template <class T> struct undefined;
 101 template <> struct iterator_traits_select<true>
 102 {
 103     template <class Ptr>
 104     struct traits
 105     {
 106         typedef std::ptrdiff_t difference_type;
 107         typedef std::random_access_iterator_tag iterator_category;
 108         typedef Ptr pointer;
 109 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
 110 // Keeps MSVC happy under certain circumstances. It seems class template default
 111 // arguments are partly instantiated even when not used when the class template
 112 // is the return type of a function template.
 113         typedef undefined<void> value_type;
 114         typedef undefined<void> reference;
 115 #endif
 116     };
 117 };
 118
 119
 120 typedef char yes_type;
 121 typedef double no_type;
 122
 123 # ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 124
 125 no_type bad_category_helper(...);
 126 template <class C, class T> yes_type bad_category_helper(std::_DBG_iter<C,T>*);
 127
 128 template <bool has_bad_category_typedef> struct bad_category_select;
 129 template <>
 130 struct bad_category_select<true>
 131 {
 132     template <class Iterator>
 133     struct category { typedef typename Iterator::_Iterator_category type; };
 134 };
 135 template <>
 136 struct bad_category_select<false>
 137 {
 138     template <class Iterator>
 139     struct category { typedef typename Iterator::iterator_category type; };
 140 };
 141
 142 template <class Iterator>
 143 struct iterator_category_select
 144 {
 145  private:
 146     static Iterator p;
 147     enum { has_bad_category
 148            = sizeof(bad_category_helper(&p)) == sizeof(yes_type) };
 149     typedef bad_category_select<has_bad_category> category_select;
 150  public:
 151     typedef typename category_select::template category<Iterator>::type type;
 152 };
 153
 154 # endif
 155
 156 # ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
 157 template <bool is_bad_output_iterator> struct bad_output_iterator_select;
 158 template <>
 159 struct bad_output_iterator_select<true>
 160 {
 161     template <class Iterator>
 162     struct non_category_traits {
 163         typedef void value_type;
 164         typedef void difference_type;
 165         typedef void pointer;
 166         typedef void reference;
 167     };
 168 };
 169 template <>
 170 struct bad_output_iterator_select<false>
 171 {
 172     template <class Iterator>
 173     struct non_category_traits {
 174         typedef typename Iterator::value_type value_type;
 175         typedef typename Iterator::difference_type difference_type;
 176         typedef typename Iterator::pointer pointer;
 177         typedef typename Iterator::reference reference;
 178     };
 179 };
 180 # endif
 181
 182 # if defined(BOOST_MSVC_STD_ITERATOR) && !defined(__SGI_STL_PORT)
 183
 184 // We'll sort iterator types into one of these classifications, from which we
 185 // can determine the difference_type, pointer, reference, and value_type
 186 enum {
 187     not_msvc_stdlib_iterator,
 188     msvc_stdlib_const_iterator,
 189     msvc_stdlib_mutable_iterator,
 190     msvc_stdlib_ostream_iterator
 191 };
 192
 193 template <unsigned> struct msvc_traits_select;
 194
 195 template <> struct msvc_traits_select<not_msvc_stdlib_iterator>
 196 {
 197     template <class Iterator>
 198     struct traits_     // calling this "traits" will confuse VC.
 199     {
 200         typedef typename Iterator::difference_type difference_type;
 201         typedef typename Iterator::value_type value_type;
 202         typedef typename Iterator::pointer pointer;
 203         typedef typename Iterator::reference reference;
 204     };
 205 };
 206
 207 template <> struct msvc_traits_select<msvc_stdlib_mutable_iterator>
 208 {
 209     template <class Iterator>
 210     struct traits_
 211     {
 212         typedef typename Iterator::distance_type difference_type;
 213         typedef typename Iterator::value_type value_type;
 214         typedef value_type* pointer;
 215         typedef value_type& reference;
 216     };
 217 };
 218
 219 template <> struct msvc_traits_select<msvc_stdlib_const_iterator>
 220 {
 221     template <class Iterator>
 222     struct traits_
 223     {
 224         typedef typename Iterator::distance_type difference_type;
 225         typedef typename Iterator::value_type value_type;
 226         typedef const value_type* pointer;
 227         typedef const value_type& reference;
 228     };
 229 };
 230
 231 template <> struct msvc_traits_select<msvc_stdlib_ostream_iterator>
 232 {
 233     template <class Iterator>
 234     struct traits_
 235     {
 236         typedef typename Iterator::distance_type difference_type;
 237         typedef typename Iterator::value_type value_type;
 238         typedef void pointer;
 239         typedef void reference;
 240     };
 241 };
 242
 243 // These functions allow us to detect which classification a given iterator type
 244 // falls into.
 245
 246 // Is the iterator derived from std::iterator?
 247 no_type is_std_iterator_helper(...);
 248 template <class V, class D, class C>
 249 yes_type is_std_iterator_helper(const volatile std::iterator<V,D,C>*);
 250
 251 // Is the iterator derived from boost::iterator?
 252 template <class C, class T, class D, class P, class R>
 253 yes_type is_boost_iterator_helper(const volatile boost::iterator<C,T,D,P,R>*);
 254 no_type is_boost_iterator_helper(...);
 255
 256 // Is the iterator one of the known mutable container iterators?
 257 template<class K, class Ty, class Kfn, class Pr, class A>
 258 yes_type is_mutable_iterator_helper(const volatile typename std::_Tree<K,Ty,Kfn,Pr,A>::iterator*);
 259 template<class Ty, class A>
 260 yes_type is_mutable_iterator_helper(const volatile typename std::list<Ty,A>::iterator*);
 261 template<class Ty, class A>
 262 yes_type is_mutable_iterator_helper(const volatile typename std::deque<Ty,A>::iterator*);
 263 no_type is_mutable_iterator_helper(...);
 264
 265 // Is the iterator an ostream_iterator?
 266 template<class T, class CharT, class Traits>
 267 yes_type is_ostream_iterator_helper(const volatile std::ostream_iterator<T,CharT,Traits>*);
 268 no_type is_ostream_iterator_helper(...);
 269
 270 template <class T>
 271 struct msvc_iterator_classification {
 272     BOOST_STATIC_CONSTANT(unsigned,
 273         value = (sizeof(is_ostream_iterator_helper((T*)0)) == sizeof(yes_type))
 274           ? msvc_stdlib_ostream_iterator
 275         : (sizeof(is_mutable_iterator_helper((T*)0)) == sizeof(yes_type))
 276           ? msvc_stdlib_mutable_iterator
 277         : (sizeof(is_std_iterator_helper((T*)0)) == sizeof(yes_type)
 278            && sizeof(is_boost_iterator_helper((T*)0)) == sizeof(no_type))
 279         ? msvc_stdlib_const_iterator
 280         : not_msvc_stdlib_iterator
 281         );
 282 };
 283 # endif
 284
 285 template <> struct iterator_traits_select<false>
 286 {
 287     template <class Iterator>
 288     struct traits
 289     {
 290 #   if defined(BOOST_MSVC_STD_ITERATOR) && !defined(__SGI_STL_PORT)
 291         typedef msvc_traits_select<(
 292             msvc_iterator_classification<Iterator>::value
 293         )>::template traits_<Iterator> inner_traits;
 294
 295         typedef typename inner_traits::difference_type difference_type;
 296         typedef typename inner_traits::value_type value_type;
 297         typedef typename inner_traits::pointer pointer;
 298         typedef typename inner_traits::reference reference;
 299 #   elif !defined(BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION)
 300         typedef typename Iterator::difference_type difference_type;
 301         typedef typename Iterator::value_type value_type;
 302         typedef typename Iterator::pointer pointer;
 303         typedef typename Iterator::reference reference;
 304 #   else
 305         typedef bad_output_iterator_select<
 306           is_convertible<const volatile Iterator*,
 307             const volatile std::iterator<std::output_iterator_tag,void,void,void,void>*
 308           >::value> non_category_traits_select;
 309         typedef non_category_traits_select::template non_category_traits<Iterator> non_category_traits;
 310      public:
 311         typedef typename non_category_traits::value_type value_type;
 312         typedef typename non_category_traits::difference_type difference_type;
 313         typedef typename non_category_traits::pointer pointer;
 314         typedef typename non_category_traits::reference reference;
 315 #   endif
 316
 317 #   if !defined(BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF)
 318         typedef typename Iterator::iterator_category iterator_category;
 319 #   else
 320         typedef typename iterator_category_select<Iterator>::type iterator_category;
 321 #   endif
 322     };
 323 };
 324
 325 } // namespace boost::detail::iterator_traits_
 326
 327 template <class Iterator>
 328 struct iterator_traits
 329     : iterator_traits_::iterator_traits_select<is_pointer<Iterator>::value>::template traits<Iterator>
 330 {
 331  private:
 332     typedef typename iterator_traits_::iterator_traits_select<
 333         is_pointer<remove_cv<Iterator>::type>::value>::template traits<Iterator> traits;
 334  public:
 335     // Why do I need to define these typedefs? It keeps MSVC happy somehow.
 336     // Why don't I need to define the other typedefs? Who knows?!?
 337     typedef typename traits::difference_type difference_type;
 338     typedef typename traits::iterator_category iterator_category;
 339 };
 340
 341 namespace iterator_traits_ {
 342
 343 template <class Category>
 344 struct distance_select {
 345     template <class Iterator>
 346     static typename ::boost::detail::iterator_traits<Iterator>::difference_type
 347     distance(Iterator i1, const Iterator i2)
 348     {
 349         typename ::boost::detail::iterator_traits<Iterator>::difference_type result = 0;
 350         while (i1 != i2)
 351         {
 352             ++i1;
 353             ++result;
 354         }
 355         return result;
 356     }
 357 };
 358
 359 template <>
 360 struct distance_select<std::random_access_iterator_tag> {
 361     template <class Iterator>
 362     static typename ::boost::detail::iterator_traits<Iterator>::difference_type
 363     distance(const Iterator i1, const Iterator i2)
 364     {
 365         return i2 - i1;
 366     }
 367 };
 368
 369 } // namespace boost::detail::iterator_traits_
 370
 371 template <class Iterator>
 372 inline typename ::boost::detail::iterator_traits<Iterator>::difference_type
 373 distance(const Iterator& first, const Iterator& last)
 374 {
 375     typedef typename ::boost::detail::iterator_traits<Iterator>::iterator_category iterator_category;
 376     return iterator_traits_::distance_select<iterator_category>::distance(first, last);
 377 }
 378 # endif // workarounds
 379
 380 }} // namespace boost::detail
 381
 382 # undef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 383 # undef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
 384
 385 #endif // ITERATOR_DWA122600_HPP_