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)
  66 #  include <xtree>
  67 #  include <deque>
  68 #  include <list>
  69 #  if 0 && defined(__ICL) // Re-enable this to pick up the Intel fixes where they left off
  70 #   include <iosfwd>
  71 #   include <memory>
  72 #  endif
  73 # endif
  74
  75
  76 // STLPort 4.0 and betas have a bug when debugging is enabled and there is no
  77 // partial specialization: instead of an iterator_category typedef, the standard
  78 // container iterators have _Iterator_category.
  79 //
  80 // Also, whether debugging is enabled or not, there is a broken specialization
  81 // of std::iterator<output_iterator_tag,void,void,void,void> which has no
  82 // typedefs but iterator_category.
  83 # if defined(__SGI_STL_PORT) && (__SGI_STL_PORT <= 0x410) && !defined(__STL_CLASS_PARTIAL_SPECIALIZATION)
  84
  85 #  ifdef __STL_DEBUG
  86 #   define BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
  87 #  endif
  88
  89 #  define BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
  90
  91 # endif // STLPort <= 4.1b4 && no partial specialization
  92
  93 namespace boost { namespace detail {
  94 # if !defined(BOOST_NO_STD_ITERATOR_TRAITS) && !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) && !defined(BOOST_MSVC_STD_ITERATOR)
  95 using std::iterator_traits;
  96 using std::distance;
  97 # else
  98
  99 namespace iterator_traits_ {
 100
 101 // Workarounds for less-capable implementations
 102 template <bool is_ptr> struct iterator_traits_select;
 103
 104 template <class T> struct undefined;
 105 template <> struct iterator_traits_select<true>
 106 {
 107     template <class Ptr>
 108     struct traits
 109     {
 110         typedef std::ptrdiff_t difference_type;
 111         typedef std::random_access_iterator_tag iterator_category;
 112         typedef Ptr pointer;
 113 #ifdef BOOST_MSVC
 114 // Keeps MSVC happy under certain circumstances. It seems class template default
 115 // arguments are partly instantiated even when not used when the class template
 116 // is the return type of a function template.
 117         typedef undefined<void> value_type;
 118         typedef undefined<void> reference;
 119 #endif
 120     };
 121 };
 122
 123
 124 typedef char yes_type;
 125 typedef double no_type;
 126
 127 # ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 128
 129 no_type bad_category_helper(...);
 130 template <class C, class T> yes_type bad_category_helper(std::_DBG_iter<C,T>*);
 131
 132 template <bool has_bad_category_typedef> struct bad_category_select;
 133 template <>
 134 struct bad_category_select<true>
 135 {
 136     template <class Iterator>
 137     struct category { typedef typename Iterator::_Iterator_category type; };
 138 };
 139 template <>
 140 struct bad_category_select<false>
 141 {
 142     template <class Iterator>
 143     struct category { typedef typename Iterator::iterator_category type; };
 144 };
 145
 146 template <class Iterator>
 147 struct iterator_category_select
 148 {
 149  private:
 150     static Iterator p;
 151     enum { has_bad_category
 152            = sizeof(bad_category_helper(&p)) == sizeof(yes_type) };
 153     typedef bad_category_select<has_bad_category> category_select;
 154  public:
 155     typedef typename category_select::template category<Iterator>::type type;
 156 };
 157
 158 # endif
 159
 160 # ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
 161 template <bool is_bad_output_iterator> struct bad_output_iterator_select;
 162 template <>
 163 struct bad_output_iterator_select<true>
 164 {
 165     template <class Iterator>
 166     struct non_category_traits {
 167         typedef void value_type;
 168         typedef void difference_type;
 169         typedef void pointer;
 170         typedef void reference;
 171     };
 172 };
 173 template <>
 174 struct bad_output_iterator_select<false>
 175 {
 176     template <class Iterator>
 177     struct non_category_traits {
 178         typedef typename Iterator::value_type value_type;
 179         typedef typename Iterator::difference_type difference_type;
 180         typedef typename Iterator::pointer pointer;
 181         typedef typename Iterator::reference reference;
 182     };
 183 };
 184 # endif
 185
 186 # if defined(BOOST_MSVC_STD_ITERATOR)
 187
 188 // We'll sort iterator types into one of these classifications, from which we
 189 // can determine the difference_type, pointer, reference, and value_type
 190 enum {
 191     not_msvc_stdlib_iterator,
 192     msvc_stdlib_const_iterator,
 193     msvc_stdlib_mutable_iterator,
 194     msvc_stdlib_ostream_iterator
 195 };
 196
 197 template <unsigned> struct msvc_traits_select;
 198
 199 template <> struct msvc_traits_select<not_msvc_stdlib_iterator>
 200 {
 201     template <class Iterator>
 202     struct traits_     // calling this "traits" will confuse VC.
 203     {
 204         typedef typename Iterator::difference_type difference_type;
 205         typedef typename Iterator::value_type value_type;
 206         typedef typename Iterator::pointer pointer;
 207         typedef typename Iterator::reference reference;
 208     };
 209 };
 210
 211 template <> struct msvc_traits_select<msvc_stdlib_mutable_iterator>
 212 {
 213     template <class Iterator>
 214     struct traits_
 215     {
 216         typedef typename Iterator::distance_type difference_type;
 217         typedef typename Iterator::value_type value_type;
 218         typedef value_type* pointer;
 219         typedef value_type& reference;
 220     };
 221 };
 222
 223 template <> struct msvc_traits_select<msvc_stdlib_const_iterator>
 224 {
 225     template <class Iterator>
 226     struct traits_
 227     {
 228         typedef typename Iterator::distance_type difference_type;
 229         typedef typename Iterator::value_type value_type;
 230         typedef const value_type* pointer;
 231         typedef const value_type& reference;
 232     };
 233 };
 234
 235 template <> struct msvc_traits_select<msvc_stdlib_ostream_iterator>
 236 {
 237     template <class Iterator>
 238     struct traits_
 239     {
 240         typedef typename Iterator::distance_type difference_type;
 241         typedef typename Iterator::value_type value_type;
 242         typedef void pointer;
 243         typedef void reference;
 244     };
 245 };
 246
 247 // These functions allow us to detect which classification a given iterator type
 248 // falls into.
 249
 250 // Is the iterator derived from std::iterator?
 251 no_type is_std_iterator_helper(...);
 252 template <class V, class D, class C>
 253 yes_type is_std_iterator_helper(const volatile std::iterator<V,D,C>*);
 254
 255 // Is the iterator derived from boost::iterator?
 256 template <class C, class T, class D, class P, class R>
 257 yes_type is_boost_iterator_helper(const volatile boost::iterator<C,T,D,P,R>*);
 258 no_type is_boost_iterator_helper(...);
 259
 260 // Is the iterator one of the known mutable container iterators?
 261 template<class K, class Ty, class Kfn, class Pr, class A>
 262 yes_type is_mutable_iterator_helper(const volatile typename std::_Tree<K,Ty,Kfn,Pr,A>::iterator*);
 263 template<class Ty, class A>
 264 yes_type is_mutable_iterator_helper(const volatile typename std::list<Ty,A>::iterator*);
 265 template<class Ty, class A>
 266 yes_type is_mutable_iterator_helper(const volatile typename std::deque<Ty,A>::iterator*);
 267 no_type is_mutable_iterator_helper(...);
 268
 269 // Is the iterator an ostream_iterator?
 270 template<class T, class CharT, class Traits>
 271 yes_type is_ostream_iterator_helper(const volatile std::ostream_iterator<T,CharT,Traits>*);
 272 no_type is_ostream_iterator_helper(...);
 273
 274 template <class T>
 275 struct msvc_iterator_classification {
 276     BOOST_STATIC_CONSTANT(unsigned,
 277         value = (sizeof(is_ostream_iterator_helper((T*)0)) == sizeof(yes_type))
 278           ? msvc_stdlib_ostream_iterator
 279         : (sizeof(is_mutable_iterator_helper((T*)0)) == sizeof(yes_type))
 280           ? msvc_stdlib_mutable_iterator
 281         : (sizeof(is_std_iterator_helper((T*)0)) == sizeof(yes_type)
 282            && sizeof(is_boost_iterator_helper((T*)0)) == sizeof(no_type))
 283         ? msvc_stdlib_const_iterator
 284         : not_msvc_stdlib_iterator
 285         );
 286 };
 287 # endif
 288
 289 template <> struct iterator_traits_select<false>
 290 {
 291     template <class Iterator>
 292     struct traits
 293     {
 294 #   if defined(BOOST_MSVC_STD_ITERATOR)
 295         typedef msvc_traits_select<(
 296             msvc_iterator_classification<Iterator>::value
 297         )>::template traits_<Iterator> inner_traits;
 298
 299         typedef typename inner_traits::difference_type difference_type;
 300         typedef typename inner_traits::value_type value_type;
 301         typedef typename inner_traits::pointer pointer;
 302         typedef typename inner_traits::reference reference;
 303 #   elif !defined(BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION)
 304         typedef typename Iterator::difference_type difference_type;
 305         typedef typename Iterator::value_type value_type;
 306         typedef typename Iterator::pointer pointer;
 307         typedef typename Iterator::reference reference;
 308 #   else
 309         typedef bad_output_iterator_select<
 310           is_convertible<const volatile Iterator*,
 311             const volatile std::iterator<std::output_iterator_tag,void,void,void,void>*
 312           >::value> non_category_traits_select;
 313         typedef non_category_traits_select::template non_category_traits<Iterator> non_category_traits;
 314      public:
 315         typedef typename non_category_traits::value_type value_type;
 316         typedef typename non_category_traits::difference_type difference_type;
 317         typedef typename non_category_traits::pointer pointer;
 318         typedef typename non_category_traits::reference reference;
 319 #   endif
 320
 321 #   if !defined(BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF)
 322         typedef typename Iterator::iterator_category iterator_category;
 323 #   else
 324         typedef typename iterator_category_select<Iterator>::type iterator_category;
 325 #   endif
 326     };
 327 };
 328
 329 } // namespace boost::detail::iterator_traits_
 330
 331 template <class Iterator>
 332 struct iterator_traits
 333     : iterator_traits_::iterator_traits_select<is_pointer<Iterator>::value>::template traits<Iterator>
 334 {
 335  private:
 336     typedef typename iterator_traits_::iterator_traits_select<
 337         is_pointer<remove_cv<Iterator>::type>::value>::template traits<Iterator> traits;
 338  public:
 339     // Why do I need to define these typedefs? It keeps MSVC happy somehow.
 340     // Why don't I need to define the other typedefs? Who knows?!?
 341     typedef typename traits::difference_type difference_type;
 342     typedef typename traits::iterator_category iterator_category;
 343 };
 344
 345 namespace iterator_traits_ {
 346
 347 template <class Category>
 348 struct distance_select {
 349     template <class Iterator>
 350     static typename ::boost::detail::iterator_traits<Iterator>::difference_type
 351     distance(Iterator i1, const Iterator i2)
 352     {
 353         typename ::boost::detail::iterator_traits<Iterator>::difference_type result = 0;
 354         while (i1 != i2)
 355         {
 356             ++i1;
 357             ++result;
 358         }
 359         return result;
 360     }
 361 };
 362
 363 template <>
 364 struct distance_select<std::random_access_iterator_tag> {
 365     template <class Iterator>
 366     static typename ::boost::detail::iterator_traits<Iterator>::difference_type
 367     distance(const Iterator i1, const Iterator i2)
 368     {
 369         return i2 - i1;
 370     }
 371 };
 372
 373 } // namespace boost::detail::iterator_traits_
 374
 375 template <class Iterator>
 376 inline typename ::boost::detail::iterator_traits<Iterator>::difference_type
 377 distance(const Iterator& first, const Iterator& last)
 378 {
 379     typedef typename ::boost::detail::iterator_traits<Iterator>::iterator_category iterator_category;
 380     return iterator_traits_::distance_select<iterator_category>::distance(first, last);
 381 }
 382 # endif // workarounds
 383
 384 }} // namespace boost::detail
 385
 386 # undef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
 387 # undef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
 388
 389 #endif // ITERATOR_DWA122600_HPP_