|
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_ |