source: NonGTP/Boost/boost/detail/iterator.hpp @ 857

Revision 857, 15.9 KB checked in by igarcia, 19 years ago (diff)
Line 
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   
77namespace boost { namespace detail {
78
79// Define a new template so it can be specialized
80template <class Iterator>
81struct iterator_traits
82    : std::iterator_traits<Iterator>
83{};
84using 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
95namespace 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!
100template <class Iterator>
101struct 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
110template <class T>
111struct 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
120template <class T>
121struct 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
153namespace boost { namespace detail {
154
155BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type)
156BOOST_MPL_HAS_XXX_TRAIT_DEF(reference)
157BOOST_MPL_HAS_XXX_TRAIT_DEF(pointer)
158BOOST_MPL_HAS_XXX_TRAIT_DEF(difference_type)
159BOOST_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.
172template <class T>
173type_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.
178template <class T> T* mutable_iterator_lvalue_helper(T& x);
179int mutable_iterator_lvalue_helper(...);
180
181
182// This one detects output iterators such as ostream_iterator which
183// return references to themselves.
184template <class T>
185type_traits::yes_type is_mutable_iterator_helper(T const*, T const*);
186
187type_traits::no_type is_mutable_iterator_helper(...);
188
189template <class T>
190struct 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
204BOOST_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.
213template <class T>
214struct 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
225BOOST_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
230BOOST_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.
237template <class T>
238struct 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
249BOOST_TT_AUX_BOOL_TRAIT_DEF1(
250    is_stlport_40_debug_iterator,T,::boost::detail::is_stlport_40_debug_iterator_impl<T>::value)
251
252template <class T>
253struct 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
263template <class T> struct pointer_iterator_traits;
264
265#   ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
266template <class T>
267struct 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
282template<class P> class please_invoke_BOOST_TT_BROKEN_COMPILER_SPEC_on_cv_unqualified_pointee;
283
284template<class P>
285struct 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
297template<class P>
298struct 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
307template <class T>
308struct 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
322template <class Iterator>
323struct 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
332template <class Iterator>
333struct 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
341template <class Iterator>
342struct 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
351template <class Iterator>
352struct 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
359struct 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.
371template <class Iterator>
372struct 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
380template <class Iterator>
381struct 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
402template <class Iterator>
403struct 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
412template <class Iterator>
413struct 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.
437template <> 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
450namespace boost { namespace detail {
451
452namespace 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
475template <class Iterator>
476inline typename iterator_traits<Iterator>::difference_type
477distance(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_
Note: See TracBrowser for help on using the repository browser.