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.
9 // std::iterator_traits<>::iterator_category
10 // std::iterator_traits<>::difference_type
13 // ...for all compilers and iterators
15 // Additionally, if X is a pointer
16 // std::iterator_traits<X>::pointer
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
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.
28 // See http://www.boost.org for most recent version including documentation.
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
56 #ifndef ITERATOR_DWA122600_HPP_
57 # define ITERATOR_DWA122600_HPP_
59 # include <boost/config.hpp>
60 # include <boost/type_traits.hpp>
61 # include <boost/iterator.hpp>
65 # if defined(BOOST_MSVC_STD_ITERATOR)
69 # if 0 && defined(__ICL) // Re-enable this to pick up the Intel fixes where they left off
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.
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)
86 # define BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
89 # define BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
91 # endif // STLPort <= 4.1b4 && no partial specialization
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;
99 namespace iterator_traits_ {
101 // Workarounds for less-capable implementations
102 template <bool is_ptr> struct iterator_traits_select;
104 template <class T> struct undefined;
105 template <> struct iterator_traits_select<true>
110 typedef std::ptrdiff_t difference_type;
111 typedef std::random_access_iterator_tag iterator_category;
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;
124 typedef char yes_type;
125 typedef double no_type;
127 # ifdef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
129 no_type bad_category_helper(...);
130 template <class C, class T> yes_type bad_category_helper(std::_DBG_iter<C,T>*);
132 template <bool has_bad_category_typedef> struct bad_category_select;
134 struct bad_category_select<true>
136 template <class Iterator>
137 struct category { typedef typename Iterator::_Iterator_category type; };
140 struct bad_category_select<false>
142 template <class Iterator>
143 struct category { typedef typename Iterator::iterator_category type; };
146 template <class Iterator>
147 struct iterator_category_select
151 enum { has_bad_category
152 = sizeof(bad_category_helper(&p)) == sizeof(yes_type) };
153 typedef bad_category_select<has_bad_category> category_select;
155 typedef typename category_select::template category<Iterator>::type type;
160 # ifdef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
161 template <bool is_bad_output_iterator> struct bad_output_iterator_select;
163 struct bad_output_iterator_select<true>
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;
174 struct bad_output_iterator_select<false>
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;
186 # if defined(BOOST_MSVC_STD_ITERATOR)
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
191 not_msvc_stdlib_iterator,
192 msvc_stdlib_const_iterator,
193 msvc_stdlib_mutable_iterator,
194 msvc_stdlib_ostream_iterator
197 template <unsigned> struct msvc_traits_select;
199 template <> struct msvc_traits_select<not_msvc_stdlib_iterator>
201 template <class Iterator>
202 struct traits_ // calling this "traits" will confuse VC.
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;
211 template <> struct msvc_traits_select<msvc_stdlib_mutable_iterator>
213 template <class Iterator>
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;
223 template <> struct msvc_traits_select<msvc_stdlib_const_iterator>
225 template <class Iterator>
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;
235 template <> struct msvc_traits_select<msvc_stdlib_ostream_iterator>
237 template <class Iterator>
240 typedef typename Iterator::distance_type difference_type;
241 typedef typename Iterator::value_type value_type;
242 typedef void pointer;
243 typedef void reference;
247 // These functions allow us to detect which classification a given iterator type
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>*);
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(...);
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(...);
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(...);
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
289 template <> struct iterator_traits_select<false>
291 template <class Iterator>
294 # if defined(BOOST_MSVC_STD_ITERATOR)
295 typedef msvc_traits_select<(
296 msvc_iterator_classification<Iterator>::value
297 )>::template traits_<Iterator> inner_traits;
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;
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;
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;
321 # if !defined(BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF)
322 typedef typename Iterator::iterator_category iterator_category;
324 typedef typename iterator_category_select<Iterator>::type iterator_category;
329 } // namespace boost::detail::iterator_traits_
331 template <class Iterator>
332 struct iterator_traits
333 : iterator_traits_::iterator_traits_select<is_pointer<Iterator>::value>::template traits<Iterator>
336 typedef typename iterator_traits_::iterator_traits_select<
337 is_pointer<remove_cv<Iterator>::type>::value>::template traits<Iterator> traits;
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;
345 namespace iterator_traits_ {
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)
353 typename ::boost::detail::iterator_traits<Iterator>::difference_type result = 0;
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)
373 } // namespace boost::detail::iterator_traits_
375 template <class Iterator>
376 inline typename ::boost::detail::iterator_traits<Iterator>::difference_type
377 distance(const Iterator& first, const Iterator& last)
379 typedef typename ::boost::detail::iterator_traits<Iterator>::iterator_category iterator_category;
380 return iterator_traits_::distance_select<iterator_category>::distance(first, last);
382 # endif // workarounds
384 }} // namespace boost::detail
386 # undef BOOST_BAD_CONTAINER_ITERATOR_CATEGORY_TYPEDEF
387 # undef BOOST_BAD_OUTPUT_ITERATOR_SPECIALIZATION
389 #endif // ITERATOR_DWA122600_HPP_