1 // (C) Copyright David Abrahams 2002.
2 // (C) Copyright Jeremy Siek 2002.
3 // (C) Copyright Thomas Witt 2002.
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 #ifndef BOOST_ITERATOR_FACADE_23022003THW_HPP
8 #define BOOST_ITERATOR_FACADE_23022003THW_HPP
10 #include <boost/iterator.hpp>
11 #include <boost/iterator/interoperable.hpp>
12 #include <boost/iterator/iterator_traits.hpp>
14 #include <boost/iterator/detail/facade_iterator_category.hpp>
15 #include <boost/iterator/detail/enable_if.hpp>
17 #include <boost/static_assert.hpp>
18 #include <boost/utility/addressof.hpp>
20 #include <boost/type_traits/is_same.hpp>
21 #include <boost/type_traits/add_const.hpp>
22 #include <boost/type_traits/add_pointer.hpp>
23 #include <boost/type_traits/remove_const.hpp>
24 #include <boost/type_traits/remove_reference.hpp>
25 #include <boost/type_traits/is_convertible.hpp>
26 #include <boost/type_traits/is_pod.hpp>
28 #include <boost/mpl/eval_if.hpp>
29 #include <boost/mpl/if.hpp>
30 #include <boost/mpl/or.hpp>
31 #include <boost/mpl/and.hpp>
32 #include <boost/mpl/not.hpp>
33 #include <boost/mpl/always.hpp>
34 #include <boost/mpl/apply.hpp>
35 #include <boost/mpl/identity.hpp>
37 #include <boost/iterator/detail/config_def.hpp> // this goes last
41 // This forward declaration is required for the friend declaration
42 // in iterator_core_access
43 template <class I, class V, class TC, class R, class D> class iterator_facade;
47 // A binary metafunction class that always returns bool. VC6
48 // ICEs on mpl::always<bool>, probably because of the default
52 template <class T, class U>
60 // enable if for use in operator implementation.
67 struct enable_if_interoperable
68 #if BOOST_WORKAROUND(BOOST_MSVC, <= 1300)
70 typedef typename mpl::if_<
72 is_convertible<Facade1, Facade2>
73 , is_convertible<Facade2, Facade1>
80 : ::boost::iterators::enable_if<
82 is_convertible<Facade1, Facade2>
83 , is_convertible<Facade2, Facade1>
91 // Generates associated types for an iterator_facade with the
96 , class CategoryOrTraversal
100 struct iterator_facade_types
102 typedef typename facade_iterator_category<
103 CategoryOrTraversal, ValueParam, Reference
104 >::type iterator_category;
106 typedef typename remove_const<ValueParam>::type value_type;
108 // Not the real associated pointer type
109 typedef typename mpl::eval_if<
110 boost::detail::iterator_writability_disabled<ValueParam,Reference>
111 , add_pointer<const value_type>
112 , add_pointer<value_type>
115 # if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) \
116 && (BOOST_WORKAROUND(_STLPORT_VERSION, BOOST_TESTED_AT(0x452)) \
117 || BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, BOOST_TESTED_AT(310))) \
118 || BOOST_WORKAROUND(BOOST_RWSTD_VER, BOOST_TESTED_AT(0x20101)) \
119 || BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, <= 310)
121 // To interoperate with some broken library/compiler
122 // combinations, user-defined iterators must be derived from
123 // std::iterator. It is possible to implement a standard
124 // library for broken compilers without this limitation.
125 # define BOOST_ITERATOR_FACADE_NEEDS_ITERATOR_BASE 1
128 iterator<iterator_category, value_type, Difference, pointer, Reference>
133 // iterators whose dereference operators reference the same value
134 // for all iterators into the same sequence (like many input
135 // iterators) need help with their postfix ++: the referenced
136 // value must be read and stored away before the increment occurs
137 // so that *a++ yields the originally referenced element and not
139 template <class Iterator>
140 class postfix_increment_proxy
142 typedef typename iterator_value<Iterator>::type value_type;
144 explicit postfix_increment_proxy(Iterator const& x)
148 // Returning a mutable reference allows nonsense like
149 // (*r++).mutate(), but it imposes fewer assumptions about the
150 // behavior of the value_type. In particular, recall that
151 // (*r).mutate() is legal if operator* returns by value.
155 return this->stored_value;
158 mutable value_type stored_value;
162 // In general, we can't determine that such an iterator isn't
163 // writable -- we also need to store a copy of the old iterator so
164 // that it can be written into.
165 template <class Iterator>
166 class writable_postfix_increment_proxy
168 typedef typename iterator_value<Iterator>::type value_type;
170 explicit writable_postfix_increment_proxy(Iterator const& x)
175 // Dereferencing must return a proxy so that both *r++ = o and
176 // value_type(*r++) can work. In this case, *r is the same as
177 // *r++, and the conversion operator below is used to ensure
179 writable_postfix_increment_proxy const&
185 // Provides readability of *r++
186 operator value_type&() const
191 // Provides writability of *r++
193 T const& operator=(T const& x) const
195 *this->stored_iterator = x;
199 // This overload just in case only non-const objects are writable
201 T& operator=(T& x) const
203 *this->stored_iterator = x;
208 operator Iterator const&() const
210 return stored_iterator;
214 mutable value_type stored_value;
215 Iterator stored_iterator;
218 # ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
220 template <class Reference, class Value>
221 struct is_non_proxy_reference_impl
226 static typename mpl::if_<
229 , Value const volatile*
233 >::type& helper(R const&);
235 BOOST_STATIC_CONSTANT(bool, value = sizeof(helper(r)) == 1);
238 template <class Reference, class Value>
239 struct is_non_proxy_reference
241 is_non_proxy_reference_impl<Reference, Value>::value
245 template <class Reference, class Value>
246 struct is_non_proxy_reference
248 typename remove_reference<Reference>::type
250 , Value const volatile*
255 // A metafunction to choose the result type of postfix ++
257 // Because the C++98 input iterator requirements say that *r++ has
258 // type T (value_type), implementations of some standard
259 // algorithms like lexicographical_compare may use constructions
264 // If *r++ returns a proxy (as required if r is writable but not
265 // multipass), this sort of expression will fail unless the proxy
266 // supports the operator<. Since there are any number of such
267 // operations, we're not going to try to support them. Therefore,
268 // even if r++ returns a proxy, *r++ will only return a proxy if
269 // *r also returns a proxy.
270 template <class Iterator, class Value, class Reference, class CategoryOrTraversal>
271 struct postfix_increment_result
274 // A proxy is only needed for readable iterators
275 is_convertible<Reference,Value const&>
277 // No multipass iterator can have values that disappear
278 // before positions can be re-visited
281 typename iterator_category_to_traversal<CategoryOrTraversal>::type
282 , forward_traversal_tag
287 is_non_proxy_reference<Reference,Value>
288 , postfix_increment_proxy<Iterator>
289 , writable_postfix_increment_proxy<Iterator>
291 , mpl::identity<Iterator>
295 // operator->() needs special support for input iterators to strictly meet the
296 // standard's requirements. If *i is not a reference type, we must still
297 // produce an lvalue to which a pointer can be formed. We do that by
298 // returning a proxy object containing an instance of the reference object.
299 template <class Reference, class Pointer>
300 struct operator_arrow_dispatch // proxy references
304 explicit proxy(Reference const & x) : m_ref(x) {}
305 Reference* operator->() { return boost::addressof(m_ref); }
306 // This function is needed for MWCW and BCC, which won't call
307 // operator-> again automatically per 13.3.1.2 para 8
308 operator Reference*() { return boost::addressof(m_ref); }
311 typedef proxy result_type;
312 static result_type apply(Reference const & x)
314 return result_type(x);
318 template <class T, class Pointer>
319 struct operator_arrow_dispatch<T&, Pointer> // "real" references
321 typedef Pointer result_type;
322 static result_type apply(T& x)
324 return boost::addressof(x);
328 # if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
331 struct operator_arrow_dispatch<int, int>
333 typedef int result_type;
337 // A proxy return type for operator[], needed to deal with
338 // iterators that may invalidate referents upon destruction.
339 // Consider the temporary iterator in *(a + n)
340 template <class Iterator>
341 class operator_brackets_proxy
343 // Iterator is actually an iterator_facade, so we do not have to
344 // go through iterator_traits to access the traits.
345 typedef typename Iterator::reference reference;
346 typedef typename Iterator::value_type value_type;
349 operator_brackets_proxy(Iterator const& iter)
353 operator reference() const
358 operator_brackets_proxy& operator=(value_type const& val)
368 // A metafunction that determines whether operator[] must return a
369 // proxy, or whether it can simply return a copy of the value_type.
370 template <class ValueType, class Reference>
371 struct use_operator_brackets_proxy
374 // Really we want an is_copy_constructible trait here,
375 // but is_POD will have to suffice in the meantime.
376 boost::is_POD<ValueType>
377 , iterator_writability_disabled<ValueType,Reference>
382 template <class Iterator, class Value, class Reference>
383 struct operator_brackets_result
385 typedef typename mpl::if_<
386 use_operator_brackets_proxy<Value,Reference>
387 , operator_brackets_proxy<Iterator>
392 template <class Iterator>
393 operator_brackets_proxy<Iterator> make_operator_brackets_result(Iterator const& iter, mpl::true_)
395 return operator_brackets_proxy<Iterator>(iter);
398 template <class Iterator>
399 typename Iterator::value_type make_operator_brackets_result(Iterator const& iter, mpl::false_)
404 struct choose_difference_type
406 template <class I1, class I2>
409 # ifdef BOOST_NO_ONE_WAY_ITERATOR_INTEROP
410 iterator_difference<I1>
411 # elif BOOST_WORKAROUND(BOOST_MSVC, < 1300)
413 is_convertible<I2,I1>
414 , typename I1::difference_type
415 , typename I2::difference_type
419 is_convertible<I2,I1>
420 , iterator_difference<I1>
421 , iterator_difference<I2>
427 } // namespace detail
430 // Macros which describe the declarations of binary operators
431 # ifdef BOOST_NO_STRICT_ITERATOR_INTEROPERABILITY
432 # define BOOST_ITERATOR_FACADE_INTEROP_HEAD(prefix, op, result_type) \
434 class Derived1, class V1, class TC1, class Reference1, class Difference1 \
435 , class Derived2, class V2, class TC2, class Reference2, class Difference2 \
437 prefix typename mpl::apply2<result_type,Derived1,Derived2>::type \
439 iterator_facade<Derived1, V1, TC1, Reference1, Difference1> const& lhs \
440 , iterator_facade<Derived2, V2, TC2, Reference2, Difference2> const& rhs)
442 # define BOOST_ITERATOR_FACADE_INTEROP_HEAD(prefix, op, result_type) \
444 class Derived1, class V1, class TC1, class Reference1, class Difference1 \
445 , class Derived2, class V2, class TC2, class Reference2, class Difference2 \
447 prefix typename boost::detail::enable_if_interoperable< \
449 , typename mpl::apply2<result_type,Derived1,Derived2>::type \
452 iterator_facade<Derived1, V1, TC1, Reference1, Difference1> const& lhs \
453 , iterator_facade<Derived2, V2, TC2, Reference2, Difference2> const& rhs)
456 # define BOOST_ITERATOR_FACADE_PLUS_HEAD(prefix,args) \
457 template <class Derived, class V, class TC, class R, class D> \
458 prefix Derived operator+ args
461 // Helper class for granting access to the iterator core interface.
463 // The simple core interface is used by iterator_facade. The core
464 // interface of a user/library defined iterator type should not be made public
465 // so that it does not clutter the public interface. Instead iterator_core_access
466 // should be made friend so that iterator_facade can access the core
467 // interface through iterator_core_access.
469 class iterator_core_access
471 # if defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
472 // Tasteless as this may seem, making all members public allows member templates
473 // to work in the absence of member template friends.
477 template <class I, class V, class TC, class R, class D> friend class iterator_facade;
479 # define BOOST_ITERATOR_FACADE_RELATION(op) \
480 BOOST_ITERATOR_FACADE_INTEROP_HEAD(friend,op, boost::detail::always_bool2);
482 BOOST_ITERATOR_FACADE_RELATION(==)
483 BOOST_ITERATOR_FACADE_RELATION(!=)
485 BOOST_ITERATOR_FACADE_RELATION(<)
486 BOOST_ITERATOR_FACADE_RELATION(>)
487 BOOST_ITERATOR_FACADE_RELATION(<=)
488 BOOST_ITERATOR_FACADE_RELATION(>=)
489 # undef BOOST_ITERATOR_FACADE_RELATION
491 BOOST_ITERATOR_FACADE_INTEROP_HEAD(
492 friend, -, boost::detail::choose_difference_type)
495 BOOST_ITERATOR_FACADE_PLUS_HEAD(
497 , (iterator_facade<Derived, V, TC, R, D> const&
498 , typename Derived::difference_type)
502 BOOST_ITERATOR_FACADE_PLUS_HEAD(
504 , (typename Derived::difference_type
505 , iterator_facade<Derived, V, TC, R, D> const&)
511 template <class Facade>
512 static typename Facade::reference dereference(Facade const& f)
514 return f.dereference();
517 template <class Facade>
518 static void increment(Facade& f)
523 template <class Facade>
524 static void decrement(Facade& f)
529 template <class Facade1, class Facade2>
530 static bool equal(Facade1 const& f1, Facade2 const& f2, mpl::true_)
535 template <class Facade1, class Facade2>
536 static bool equal(Facade1 const& f1, Facade2 const& f2, mpl::false_)
541 template <class Facade>
542 static void advance(Facade& f, typename Facade::difference_type n)
547 template <class Facade1, class Facade2>
548 static typename Facade1::difference_type distance_from(
549 Facade1 const& f1, Facade2 const& f2, mpl::true_)
551 return -f1.distance_to(f2);
554 template <class Facade1, class Facade2>
555 static typename Facade2::difference_type distance_from(
556 Facade1 const& f1, Facade2 const& f2, mpl::false_)
558 return f2.distance_to(f1);
562 // Curiously Recurring Template interface.
564 template <class I, class V, class TC, class R, class D>
565 static I& derived(iterator_facade<I,V,TC,R,D>& facade)
567 return *static_cast<I*>(&facade);
570 template <class I, class V, class TC, class R, class D>
571 static I const& derived(iterator_facade<I,V,TC,R,D> const& facade)
573 return *static_cast<I const*>(&facade);
577 // objects of this class are useless
578 iterator_core_access(); //undefined
582 // iterator_facade - use as a public base class for defining new
583 // standard-conforming iterators.
586 class Derived // The derived iterator type being constructed
588 , class CategoryOrTraversal
589 , class Reference = Value&
590 , class Difference = std::ptrdiff_t
592 class iterator_facade
593 # ifdef BOOST_ITERATOR_FACADE_NEEDS_ITERATOR_BASE
594 : public boost::detail::iterator_facade_types<
595 Value, CategoryOrTraversal, Reference, Difference
597 # undef BOOST_ITERATOR_FACADE_NEEDS_ITERATOR_BASE
602 // Curiously Recurring Template interface.
606 return *static_cast<Derived*>(this);
609 Derived const& derived() const
611 return *static_cast<Derived const*>(this);
614 typedef boost::detail::iterator_facade_types<
615 Value, CategoryOrTraversal, Reference, Difference
618 typedef boost::detail::operator_arrow_dispatch<
620 , typename associated_types::pointer
621 > operator_arrow_dispatch_;
624 // For use by derived classes
625 typedef iterator_facade<Derived,Value,CategoryOrTraversal,Reference,Difference> iterator_facade_;
629 typedef typename associated_types::value_type value_type;
630 typedef Reference reference;
631 typedef Difference difference_type;
633 typedef typename operator_arrow_dispatch_::result_type pointer;
635 typedef typename associated_types::iterator_category iterator_category;
637 reference operator*() const
639 return iterator_core_access::dereference(this->derived());
642 pointer operator->() const
644 return operator_arrow_dispatch_::apply(*this->derived());
647 typename boost::detail::operator_brackets_result<Derived,Value,reference>::type
648 operator[](difference_type n) const
650 typedef boost::detail::use_operator_brackets_proxy<Value,Reference> use_proxy;
652 return boost::detail::make_operator_brackets_result<Derived>(
658 Derived& operator++()
660 iterator_core_access::increment(this->derived());
661 return this->derived();
664 # if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
665 typename boost::detail::postfix_increment_result<Derived,Value,Reference,CategoryOrTraversal>::type
668 typename boost::detail::postfix_increment_result<Derived,Value,Reference,CategoryOrTraversal>::type
669 tmp(this->derived());
675 Derived& operator--()
677 iterator_core_access::decrement(this->derived());
678 return this->derived();
681 Derived operator--(int)
683 Derived tmp(this->derived());
688 Derived& operator+=(difference_type n)
690 iterator_core_access::advance(this->derived(), n);
691 return this->derived();
694 Derived& operator-=(difference_type n)
696 iterator_core_access::advance(this->derived(), -n);
697 return this->derived();
700 Derived operator-(difference_type x) const
702 Derived result(this->derived());
706 # if BOOST_WORKAROUND(BOOST_MSVC, < 1300)
707 // There appears to be a bug which trashes the data of classes
708 // derived from iterator_facade when they are assigned unless we
709 // define this assignment operator. This bug is only revealed
710 // (so far) in STLPort debug mode, but it's clearly a codegen
711 // problem so we apply the workaround for all MSVC6.
712 iterator_facade& operator=(iterator_facade const&)
719 # if !BOOST_WORKAROUND(BOOST_MSVC, < 1300)
720 template <class I, class V, class TC, class R, class D>
721 inline typename boost::detail::postfix_increment_result<I,V,R,TC>::type
723 iterator_facade<I,V,TC,R,D>& i
727 typename boost::detail::postfix_increment_result<I,V,R,TC>::type
728 tmp(*static_cast<I*>(&i));
738 // Comparison operator implementation. The library supplied operators
739 // enables the user to provide fully interoperable constant/mutable
740 // iterator types. I.e. the library provides all operators
741 // for all mutable/constant iterator combinations.
743 // Note though that this kind of interoperability for constant/mutable
744 // iterators is not required by the standard for container iterators.
745 // All the standard asks for is a conversion mutable -> constant.
746 // Most standard library implementations nowadays provide fully interoperable
747 // iterator implementations, but there are still heavily used implementations
748 // that do not provide them. (Actually it's even worse, they do not provide
749 // them for only a few iterators.)
751 // ?? Maybe a BOOST_ITERATOR_NO_FULL_INTEROPERABILITY macro should
752 // enable the user to turn off mixed type operators
754 // The library takes care to provide only the right operator overloads.
757 // bool operator==(Iterator, Iterator);
758 // bool operator==(ConstIterator, Iterator);
759 // bool operator==(Iterator, ConstIterator);
760 // bool operator==(ConstIterator, ConstIterator);
764 // In order to do so it uses c++ idioms that are not yet widely supported
765 // by current compiler releases. The library is designed to degrade gracefully
766 // in the face of compiler deficiencies. In general compiler
767 // deficiencies result in less strict error checking and more obscure
768 // error messages, functionality is not affected.
770 // For full operation compiler support for "Substitution Failure Is Not An Error"
771 // (aka. enable_if) and boost::is_convertible is required.
773 // The following problems occur if support is lacking.
778 // AdaptorA<Iterator1> a1;
779 // AdaptorA<Iterator2> a2;
781 // // This will result in a no such overload error in full operation
782 // // If enable_if or is_convertible is not supported
783 // // The instantiation will fail with an error hopefully indicating that
784 // // there is no operator== for Iterator1, Iterator2
785 // // The same will happen if no enable_if is used to remove
786 // // false overloads from the templated conversion constructor
792 // AdaptorA<Iterator> a;
793 // AdaptorB<Iterator> b;
795 // // This will result in a no such overload error in full operation
796 // // If enable_if is not supported the static assert used
797 // // in the operator implementation will fail.
798 // // This will accidently work if is_convertible is not supported.
804 # ifdef BOOST_NO_ONE_WAY_ITERATOR_INTEROP
805 # define BOOST_ITERATOR_CONVERTIBLE(a,b) mpl::true_()
807 # define BOOST_ITERATOR_CONVERTIBLE(a,b) is_convertible<a,b>()
810 # define BOOST_ITERATOR_FACADE_INTEROP(op, result_type, return_prefix, base_op) \
811 BOOST_ITERATOR_FACADE_INTEROP_HEAD(inline, op, result_type) \
813 /* For those compilers that do not support enable_if */ \
814 BOOST_STATIC_ASSERT(( \
815 is_interoperable< Derived1, Derived2 >::value \
817 return_prefix iterator_core_access::base_op( \
818 *static_cast<Derived1 const*>(&lhs) \
819 , *static_cast<Derived2 const*>(&rhs) \
820 , BOOST_ITERATOR_CONVERTIBLE(Derived2,Derived1) \
824 # define BOOST_ITERATOR_FACADE_RELATION(op, return_prefix, base_op) \
825 BOOST_ITERATOR_FACADE_INTEROP( \
827 , boost::detail::always_bool2 \
832 BOOST_ITERATOR_FACADE_RELATION(==, return, equal)
833 BOOST_ITERATOR_FACADE_RELATION(!=, return !, equal)
835 BOOST_ITERATOR_FACADE_RELATION(<, return 0 >, distance_from)
836 BOOST_ITERATOR_FACADE_RELATION(>, return 0 <, distance_from)
837 BOOST_ITERATOR_FACADE_RELATION(<=, return 0 >=, distance_from)
838 BOOST_ITERATOR_FACADE_RELATION(>=, return 0 <=, distance_from)
839 # undef BOOST_ITERATOR_FACADE_RELATION
841 // operator- requires an additional part in the static assertion
842 BOOST_ITERATOR_FACADE_INTEROP(
844 , boost::detail::choose_difference_type
848 # undef BOOST_ITERATOR_FACADE_INTEROP
849 # undef BOOST_ITERATOR_FACADE_INTEROP_HEAD
851 # define BOOST_ITERATOR_FACADE_PLUS(args) \
852 BOOST_ITERATOR_FACADE_PLUS_HEAD(inline, args) \
854 Derived tmp(static_cast<Derived const&>(i)); \
858 BOOST_ITERATOR_FACADE_PLUS((
859 iterator_facade<Derived, V, TC, R, D> const& i
860 , typename Derived::difference_type n
863 BOOST_ITERATOR_FACADE_PLUS((
864 typename Derived::difference_type n
865 , iterator_facade<Derived, V, TC, R, D> const& i
867 # undef BOOST_ITERATOR_FACADE_PLUS
868 # undef BOOST_ITERATOR_FACADE_PLUS_HEAD
872 #include <boost/iterator/detail/config_undef.hpp>
874 #endif // BOOST_ITERATOR_FACADE_23022003THW_HPP