1 // (C) Copyright David Abrahams 2000. Permission to copy, use,
2 // modify, 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.
7 // (C) Copyright Jeremy Siek 2000. Permission to copy, use, modify,
8 // sell and distribute this software is granted provided this
9 // copyright notice appears in all copies. This software is provided
10 // "as is" without express or implied warranty, and with no claim as
11 // to its suitability for any purpose.
15 // 01 Feb 2002 Jeremy Siek
16 // Added more comments in default_iterator_policies.
17 // 08 Jan 2001 David Abrahams
18 // Moved concept checks into a separate class, which makes MSVC
19 // better at dealing with them.
20 // 07 Jan 2001 David Abrahams
21 // Choose proxy for operator->() only if the reference type is not a reference.
22 // Updated workarounds for __MWERKS__ == 0x2406
23 // 20 Dec 2001 David Abrahams
24 // Adjusted is_convertible workarounds for __MWERKS__ == 0x2406
25 // 03 Nov 2001 Jeremy Siek
26 // Changed the named template parameter interface and internal.
27 // 04 Oct 2001 Jeremy Siek
28 // Changed projection_iterator to not rely on the default reference,
29 // working around a limitation of detail::iterator_traits.
30 // 04 Oct 2001 David Abrahams
31 // Applied indirect_iterator patch from George A. Heintzelman <georgeh@aya.yale.edu>
32 // Changed name of "bind" to "select" to avoid problems with MSVC.
33 // 26 Sep 2001 David Abrahams
34 // Added borland bug fix
35 // 08 Mar 2001 Jeremy Siek
36 // Added support for optional named template parameters.
37 // 19 Feb 2001 David Abrahams
38 // Rolled back reverse_iterator_pair_generator again, as it doesn't
39 // save typing on a conforming compiler.
40 // 18 Feb 2001 David Abrahams
41 // Reinstated reverse_iterator_pair_generator
42 // 16 Feb 2001 David Abrahams
43 // Add an implicit conversion operator to operator_arrow_proxy
44 // as CW and BCC workarounds.
45 // 11 Feb 2001 David Abrahams
46 // Switch to use of BOOST_STATIC_CONSTANT where possible
47 // 11 Feb 2001 Jeremy Siek
48 // Removed workaround for older MIPSpro compiler. The workaround
49 // was preventing the proper functionality of the underlying
50 // iterator being carried forward into the iterator adaptor.
51 // Also added is_bidirectional enum to avoid EDG compiler error.
52 // 11 Feb 2001 David Abrahams
53 // Borland fixes up the wazoo. It finally works!
54 // 10 Feb 2001 David Abrahams
55 // Removed traits argument from iterator_adaptor<> and switched to
56 // explicit trait specification for maximum ease-of-use.
57 // Added comments to detail::iterator_defaults<>
58 // Began using detail::iterator_defaults<> unconditionally for code clarity
59 // Changed uses of `Iterator' to `Base' where non-iterators can be used.
61 // 10 Feb 2001 David Abrahams
62 // Rolled in supposed Borland fixes from John Maddock, but not seeing any
64 // Changed argument order to indirect_ generator, for convenience in the
65 // case of input iterators (where Reference must be a value type).
66 // Removed derivation of filter_iterator_policies from
67 // default_iterator_policies, since the iterator category is likely to be
68 // reduced (we don't want to allow illegal operations like decrement).
69 // Support for a simpler filter iterator interface.
71 // 09 Feb 2001 David Abrahams
72 // Improved interface to indirect_ and reverse_ iterators
73 // Rolled back Jeremy's new constructor for now; it was causing
74 // problems with counting_iterator_test
75 // Attempted fix for Borland
77 // 09 Feb 2001 Jeremy Siek
78 // Added iterator constructor to allow const adaptor
79 // from non-const adaptee.
80 // Changed make_xxx to pass iterators by-value to
81 // get arrays converted to pointers.
82 // Removed InnerIterator template parameter from
83 // indirect_iterator_generator.
84 // Rearranged parameters for make_filter_iterator
86 // 07 Feb 2001 Jeremy Siek
87 // Removed some const iterator adaptor generators.
88 // Added make_xxx_iterator() helper functions for remaining
90 // Removed some traits template parameters where they
91 // where no longer needed thanks to detail::iterator_traits.
92 // Moved some of the compile-time logic into enums for
95 // 07 Feb 2001 David Abrahams
96 // Removed iterator_adaptor_pair_generator and
97 // reverse_iterator_pair_generator (more such culling to come)
99 // Changed all uses of std::iterator_traits as default arguments
100 // to boost::detail::iterator_traits for improved utility in
101 // non-generic contexts
102 // Fixed naming convention of non-template parameter names
104 // 06 Feb 2001 David Abrahams
105 // Produce operator-> proxy objects for InputIterators
106 // Added static assertions to do some basic concept checks
107 // Renamed single-type generators -> xxx_generator
108 // Renamed const/nonconst iterator generators -> xxx_pair_generator
109 // Added make_transform_iterator(iter, function)
110 // The existence of boost::detail::iterator_traits allowed many
111 // template arguments to be defaulted. Some arguments had to be
112 // moved to accomplish it.
114 // 04 Feb 2001 MWERKS bug workaround, concept checking for proper
115 // reference types (David Abrahams)
117 #ifndef BOOST_ITERATOR_ADAPTOR_DWA053000_HPP_
118 # define BOOST_ITERATOR_ADAPTOR_DWA053000_HPP_
120 # include <boost/iterator.hpp>
121 # include <boost/utility.hpp>
122 # include <boost/compressed_pair.hpp>
123 # include <boost/concept_check.hpp>
124 # include <boost/type.hpp>
125 # include <boost/static_assert.hpp>
126 # include <boost/type_traits.hpp>
127 # include <boost/detail/iterator.hpp>
128 # include <boost/detail/select_type.hpp>
130 // I was having some problems with VC6. I couldn't tell whether our hack for
131 // stock GCC was causing problems so I needed an easy way to turn it on and
132 // off. Now we can test the hack with various compilers and still have an
133 // "out" if it doesn't work. -dwa 7/31/00
134 # if __GNUC__ == 2 && __GNUC_MINOR__ <= 96 && !defined(__STL_USE_NAMESPACES)
135 # define BOOST_RELOPS_AMBIGUITY_BUG 1
140 //============================================================================
141 // Concept checking classes that express the requirements for iterator
142 // policies and adapted types. These classes are mostly for
143 // documentation purposes, and are not used in this header file. They
144 // merely provide a more succinct statement of what is expected of the
145 // iterator policies.
147 template <class Policies, class Adapted, class Traits>
148 struct TrivialIteratorPoliciesConcept
150 typedef typename Traits::reference reference;
152 function_requires< AssignableConcept<Policies> >();
153 function_requires< DefaultConstructibleConcept<Policies> >();
154 function_requires< AssignableConcept<Adapted> >();
155 function_requires< DefaultConstructibleConcept<Adapted> >();
159 void const_constraints() const {
160 reference r = p.dereference(x);
162 ignore_unused_variable_warning(r);
169 // Add InputIteratorPoliciesConcept?
171 template <class Policies, class Adapted, class Traits>
172 struct ForwardIteratorPoliciesConcept
174 typedef typename Traits::iterator_category iterator_category;
177 TrivialIteratorPoliciesConcept<Policies, Adapted, Traits>
181 std::forward_iterator_tag t = iterator_category();
182 ignore_unused_variable_warning(t);
186 iterator_category category;
189 template <class Policies, class Adapted, class Traits>
190 struct BidirectionalIteratorPoliciesConcept
192 typedef typename Traits::iterator_category iterator_category;
195 ForwardIteratorPoliciesConcept<Policies, Adapted, Traits>
199 std::bidirectional_iterator_tag t = iterator_category();
200 ignore_unused_variable_warning(t);
206 template <class Policies, class Adapted, class Traits>
207 struct RandomAccessIteratorPoliciesConcept
209 typedef typename Traits::difference_type DifferenceType;
210 typedef typename Traits::iterator_category iterator_category;
213 BidirectionalIteratorPoliciesConcept<Policies, Adapted, Traits>
217 std::random_access_iterator_tag t = iterator_category();
219 ignore_unused_variable_warning(t);
221 void const_constraints() const {
222 n = p.distance(x, x);
226 mutable DifferenceType n;
231 //============================================================================
232 // Default policies for iterator adaptors. You can use this as a base
233 // class if you want to customize particular policies.
234 struct default_iterator_policies
236 // Some of the member functions were defined static, but Borland
237 // got confused and thought they were non-const. Also, Sun C++
238 // does not like static function templates.
240 // The reason some members were defined static is because there is
241 // not state (data members) needed by those members of the
242 // default_iterator_policies class. If your policies class member
243 // functions need to access state stored in the policies object,
244 // then the member functions should not be static (they can't be).
246 template <class Base>
247 void initialize(Base&)
250 template <class IteratorAdaptor>
251 typename IteratorAdaptor::reference dereference(const IteratorAdaptor& x) const
252 { return *x.base(); }
254 template <class IteratorAdaptor>
255 void increment(IteratorAdaptor& x)
258 template <class IteratorAdaptor>
259 void decrement(IteratorAdaptor& x)
262 template <class IteratorAdaptor, class DifferenceType>
263 void advance(IteratorAdaptor& x, DifferenceType n)
266 template <class IteratorAdaptor1, class IteratorAdaptor2>
267 typename IteratorAdaptor1::difference_type
268 distance(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
269 { return y.base() - x.base(); }
271 template <class IteratorAdaptor1, class IteratorAdaptor2>
272 bool equal(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
273 { return x.base() == y.base(); }
276 // putting the comparisons in a base class avoids the g++
277 // ambiguous overload bug due to the relops operators
279 #ifdef BOOST_RELOPS_AMBIGUITY_BUG
280 template <class Derived, class Base>
281 struct iterator_comparisons : Base { };
283 template <class D1, class D2, class Base1, class Base2>
284 inline bool operator==(const iterator_comparisons<D1,Base1>& xb,
285 const iterator_comparisons<D2,Base2>& yb)
287 const D1& x = static_cast<const D1&>(xb);
288 const D2& y = static_cast<const D2&>(yb);
289 return x.policies().equal(x, y);
292 template <class D1, class D2, class Base1, class Base2>
293 inline bool operator!=(const iterator_comparisons<D1,Base1>& xb,
294 const iterator_comparisons<D2,Base2>& yb)
296 const D1& x = static_cast<const D1&>(xb);
297 const D2& y = static_cast<const D2&>(yb);
298 return !x.policies().equal(x, y);
301 template <class D1, class D2, class Base1, class Base2>
302 inline bool operator<(const iterator_comparisons<D1,Base1>& xb,
303 const iterator_comparisons<D2,Base2>& yb)
305 const D1& x = static_cast<const D1&>(xb);
306 const D2& y = static_cast<const D2&>(yb);
307 return x.policies().distance(y, x) < 0;
310 template <class D1, class D2, class Base1, class Base2>
311 inline bool operator>(const iterator_comparisons<D1,Base1>& xb,
312 const iterator_comparisons<D2,Base2>& yb)
314 const D1& x = static_cast<const D1&>(xb);
315 const D2& y = static_cast<const D2&>(yb);
316 return x.policies().distance(y, x) > 0;
319 template <class D1, class D2, class Base1, class Base2>
320 inline bool operator>=(const iterator_comparisons<D1,Base1>& xb,
321 const iterator_comparisons<D2,Base2>& yb)
323 const D1& x = static_cast<const D1&>(xb);
324 const D2& y = static_cast<const D2&>(yb);
325 return x.policies().distance(y, x) >= 0;
328 template <class D1, class D2, class Base1, class Base2>
329 inline bool operator<=(const iterator_comparisons<D1,Base1>& xb,
330 const iterator_comparisons<D2,Base2>& yb)
332 const D1& x = static_cast<const D1&>(xb);
333 const D2& y = static_cast<const D2&>(yb);
334 return x.policies().distance(y, x) <= 0;
340 // operator->() needs special support for input iterators to strictly meet the
341 // standard's requirements. If *i is not a reference type, we must still
342 // produce a (constant) lvalue to which a pointer can be formed. We do that by
343 // returning an instantiation of this special proxy class template.
346 struct operator_arrow_proxy
348 operator_arrow_proxy(const T& x) : m_value(x) {}
349 const T* operator->() const { return &m_value; }
350 // This function is needed for MWCW and BCC, which won't call operator->
351 // again automatically per 13.3.1.2 para 8
352 operator const T*() const { return &m_value; }
356 template <class Iter>
357 inline operator_arrow_proxy<typename Iter::value_type>
358 operator_arrow(const Iter& i, std::input_iterator_tag) {
359 typedef typename Iter::value_type value_t; // VC++ needs this typedef
360 return operator_arrow_proxy<value_t>(*i);
363 template <class Iter>
364 inline typename Iter::pointer
365 operator_arrow(const Iter& i, std::forward_iterator_tag) {
369 template <class Value, class Reference, class Pointer>
370 struct operator_arrow_result_generator
372 typedef operator_arrow_proxy<Value> proxy;
373 // Borland chokes unless it's an actual enum (!)
374 enum { use_proxy = !boost::is_reference<Reference>::value };
376 typedef typename boost::detail::if_true<(use_proxy)>::template
385 # ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
387 // Select default pointer and reference types for adapted non-pointer
388 // iterators based on the iterator and the value_type. Poor man's partial
389 // specialization is in use here.
390 template <bool is_pointer>
391 struct iterator_defaults_select
393 template <class Iterator,class Value>
396 // The assumption is that iterator_traits can deduce these types
397 // properly as long as the iterator is not a pointer.
398 typedef typename boost::detail::iterator_traits<Iterator>::pointer pointer;
399 typedef typename boost::detail::iterator_traits<Iterator>::reference reference;
403 // Select default pointer and reference types for adapted pointer iterators
404 // given a (possibly-const) value_type.
406 struct iterator_defaults_select<true>
408 template <class Iterator,class Value>
411 typedef Value* pointer;
412 typedef Value& reference;
416 // Consolidate selection of the default pointer and reference type
417 template <class Iterator,class Value>
418 struct iterator_defaults
420 BOOST_STATIC_CONSTANT(bool, is_ptr = boost::is_pointer<Iterator>::value);
422 typedef typename iterator_defaults_select<is_ptr>::template traits<Iterator,Value> traits;
423 typedef typename traits::pointer pointer;
424 typedef typename traits::reference reference;
427 template <class Iterator,class Value>
428 struct iterator_defaults : iterator_traits<Iterator>
430 // Trying to factor the common is_same expression into an enum or a
431 // static bool constant confused Borland.
432 typedef typename if_true<(
433 ::boost::is_same<Value,typename iterator_traits<Iterator>::value_type>::value
435 typename iterator_traits<Iterator>::pointer,
439 typedef typename if_true<(
440 ::boost::is_same<Value,typename iterator_traits<Iterator>::value_type>::value
442 typename iterator_traits<Iterator>::reference,
449 //===========================================================================
450 // Specify the defaults for iterator_adaptor's template parameters
452 struct default_argument { };
453 // This class template is a workaround for MSVC.
454 struct dummy_default_gen {
455 template <class Base, class Traits>
456 struct select { typedef default_argument type; };
458 // This class template is a workaround for MSVC.
459 template <class Gen> struct default_generator {
460 typedef dummy_default_gen type;
463 struct default_value_type {
464 template <class Base, class Traits>
466 typedef typename boost::detail::iterator_traits<Base>::value_type type;
469 template <> struct default_generator<default_value_type>
470 { typedef default_value_type type; }; // VC++ workaround
472 struct default_difference_type {
473 template <class Base, class Traits>
475 typedef typename boost::detail::iterator_traits<Base>::difference_type type;
478 template <> struct default_generator<default_difference_type>
479 { typedef default_difference_type type; }; // VC++ workaround
481 struct default_iterator_category {
482 template <class Base, class Traits>
484 typedef typename boost::detail::iterator_traits<Base>::iterator_category type;
487 template <> struct default_generator<default_iterator_category>
488 { typedef default_iterator_category type; }; // VC++ workaround
490 struct default_pointer {
491 template <class Base, class Traits>
493 typedef typename Traits::value_type Value;
494 typedef typename boost::detail::iterator_defaults<Base,Value>::pointer
498 template <> struct default_generator<default_pointer>
499 { typedef default_pointer type; }; // VC++ workaround
501 struct default_reference {
502 template <class Base, class Traits>
504 typedef typename Traits::value_type Value;
505 typedef typename boost::detail::iterator_defaults<Base,Value>::reference
509 template <> struct default_generator<default_reference>
510 { typedef default_reference type; }; // VC++ workaround
512 } // namespace detail
515 //===========================================================================
516 // Support for named template parameters
518 struct named_template_param_base { };
521 struct value_type_tag { };
522 struct reference_tag { };
523 struct pointer_tag { };
524 struct difference_type_tag { };
525 struct iterator_category_tag { };
527 // avoid using std::pair because A or B might be a reference type, and g++
528 // complains about forming references to references inside std::pair
529 template <class A, class B>
531 typedef A first_type;
532 typedef B second_type;
535 } // namespace detail
537 template <class Value> struct value_type_is : public named_template_param_base
539 typedef detail::cons_type<detail::value_type_tag, Value> type;
541 template <class Reference> struct reference_is : public named_template_param_base
543 typedef detail::cons_type<detail::reference_tag, Reference> type;
545 template <class Pointer> struct pointer_is : public named_template_param_base
547 typedef detail::cons_type<detail::pointer_tag, Pointer> type;
549 template <class Difference> struct difference_type_is
550 : public named_template_param_base
552 typedef detail::cons_type<detail::difference_type_tag, Difference> type;
554 template <class IteratorCategory> struct iterator_category_is
555 : public named_template_param_base
557 typedef detail::cons_type<detail::iterator_category_tag, IteratorCategory> type;
562 struct end_of_list { };
564 // Given an associative list, find the value with the matching key.
565 // An associative list is a list of key-value pairs. The list is
566 // built out of cons_type's and is terminated by end_of_list.
568 # if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) || defined(__BORLANDC__)
569 template <class AssocList, class Key>
572 struct find_param_continue {
573 template <class AssocList, class Key2> struct select {
574 typedef typename AssocList::first_type Head;
575 typedef typename Head::first_type Key1;
576 typedef typename Head::second_type Value;
577 typedef typename if_true<(is_same<Key1, Key2>::value)>::template
579 typename find_param<typename AssocList::second_type, Key2>::type
583 struct find_param_end {
584 template <class AssocList, class Key>
585 struct select { typedef detail::default_argument type; };
587 template <class AssocList> struct find_param_helper1
588 { typedef find_param_continue type; };
589 template <> struct find_param_helper1<end_of_list>
590 { typedef find_param_end type; };
592 template <class AssocList, class Key>
594 typedef typename find_param_helper1<AssocList>::type select1;
595 typedef typename select1::template select<AssocList, Key>::type type;
598 template <class AssocList, class Key> struct find_param;
601 struct find_param<end_of_list, Key> { typedef default_argument type; };
603 // Found a matching Key, return the associated Value
604 template <class Key, class Value, class Rest>
605 struct find_param<detail::cons_type< detail::cons_type<Key, Value>, Rest>, Key> {
609 // Non-matching keys, continue the search
610 template <class Key1, class Value, class Rest, class Key2>
611 struct find_param<detail::cons_type< detail::cons_type<Key1, Value>, Rest>, Key2> {
612 typedef typename find_param<Rest, Key2>::type type;
616 struct make_named_arg {
617 template <class Key, class Value>
618 struct select { typedef typename Value::type type; };
620 struct make_key_value {
621 template <class Key, class Value>
622 struct select { typedef detail::cons_type<Key, Value> type; };
625 template <class Value>
626 struct is_named_parameter
628 enum { value = is_convertible< typename add_reference< Value >::type, add_reference< named_template_param_base >::type >::value };
631 # if defined(__MWERKS__) && __MWERKS__ <= 0x2406 // workaround for broken is_convertible implementation
632 template <class T> struct is_named_parameter<value_type_is<T> > { enum { value = true }; };
633 template <class T> struct is_named_parameter<reference_is<T> > { enum { value = true }; };
634 template <class T> struct is_named_parameter<pointer_is<T> > { enum { value = true }; };
635 template <class T> struct is_named_parameter<difference_type_is<T> > { enum { value = true }; };
636 template <class T> struct is_named_parameter<iterator_category_is<T> > { enum { value = true }; };
639 template <class Key, class Value>
642 // Borland C++ doesn't like the extra indirection of is_named_parameter
644 if_true<(is_convertible<Value,named_template_param_base>::value)>::
645 template then<make_named_arg, make_key_value>::type Make;
647 enum { is_named = is_named_parameter<Value>::value };
648 typedef typename if_true<(is_named)>::template
649 then<make_named_arg, make_key_value>::type Make;
651 typedef typename Make::template select<Key, Value>::type type;
654 // Mechanism for resolving the default argument for a template parameter.
656 template <class T> struct is_default { typedef type_traits::no_type type; };
657 template <> struct is_default<default_argument>
658 { typedef type_traits::yes_type type; };
660 struct choose_default {
661 template <class Arg, class DefaultGen, class Base, class Traits>
663 typedef typename default_generator<DefaultGen>::type Gen;
664 typedef typename Gen::template select<Base,Traits>::type type;
668 template <class Arg, class DefaultGen, class Base, class Traits>
674 template <class UseDefault>
675 struct choose_arg_or_default { typedef choose_arg type; };
676 template <> struct choose_arg_or_default<type_traits::yes_type> {
677 typedef choose_default type;
680 template <class Arg, class DefaultGen, class Base, class Traits>
681 class resolve_default {
682 typedef typename choose_arg_or_default<typename is_default<Arg>::type>::type
685 typedef typename Selector
686 ::template select<Arg, DefaultGen, Base, Traits>::type type;
689 template <class Base, class Value, class Reference, class Pointer,
690 class Category, class Distance>
691 class iterator_adaptor_traits_gen
693 // Form an associative list out of the template parameters
694 // If the argument is a normal parameter (not named) then make_arg
695 // creates a key-value pair. If the argument is a named parameter,
696 // then make_arg extracts the key-value pair defined inside the
698 typedef detail::cons_type< typename make_arg<value_type_tag, Value>::type,
699 detail::cons_type<typename make_arg<reference_tag, Reference>::type,
700 detail::cons_type<typename make_arg<pointer_tag, Pointer>::type,
701 detail::cons_type<typename make_arg<iterator_category_tag, Category>::type,
702 detail::cons_type<typename make_arg<difference_type_tag, Distance>::type,
703 end_of_list> > > > > ArgList;
705 // Search the list for particular parameters
706 typedef typename find_param<ArgList, value_type_tag>::type Val;
707 typedef typename find_param<ArgList, difference_type_tag>::type Diff;
708 typedef typename find_param<ArgList, iterator_category_tag>::type Cat;
709 typedef typename find_param<ArgList, pointer_tag>::type Ptr;
710 typedef typename find_param<ArgList, reference_tag>::type Ref;
712 typedef boost::iterator<Category, Value, Distance, Pointer, Reference>
715 // Compute the defaults if necessary
716 typedef typename resolve_default<Val, default_value_type, Base, Traits0>::type
718 // if getting default value type from iterator_traits, then it won't be const
719 typedef typename resolve_default<Diff, default_difference_type, Base,
720 Traits0>::type difference_type;
721 typedef typename resolve_default<Cat, default_iterator_category, Base,
722 Traits0>::type iterator_category;
724 typedef boost::iterator<iterator_category, value_type, difference_type,
725 Pointer, Reference> Traits1;
727 // Compute the defaults for pointer and reference. This is done as a
728 // separate step because the defaults for pointer and reference depend
730 typedef typename resolve_default<Ptr, default_pointer, Base, Traits1>::type
732 typedef typename resolve_default<Ref, default_reference, Base, Traits1>::type
736 typedef boost::iterator<iterator_category,
737 typename remove_const<value_type>::type,
738 difference_type, pointer, reference> type;
741 // This is really a partial concept check for iterators. Should it
742 // be moved or done differently?
743 template <class Category, class Value, class Difference, class Pointer, class Reference>
746 BOOST_STATIC_CONSTANT(
747 bool, is_input_or_output_iter
748 = (boost::is_convertible<Category*,std::input_iterator_tag*>::value
749 | boost::is_convertible<Category*,std::output_iterator_tag*>::value));
751 // Iterators should satisfy one of the known categories
752 BOOST_STATIC_ASSERT(is_input_or_output_iter);
754 // Iterators >= ForwardIterator must produce real references
755 // as required by the C++ standard requirements in Table 74.
756 BOOST_STATIC_CONSTANT(
757 bool, forward_iter_with_real_reference
758 = ((!boost::is_convertible<Category*,std::forward_iterator_tag*>::value)
759 | boost::is_same<Reference,Value&>::value
760 | boost::is_same<Reference,typename add_const<Value>::type&>::value));
762 BOOST_STATIC_ASSERT(forward_iter_with_real_reference);
764 } // namespace detail
768 // This macro definition is only temporary in this file
769 # if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
770 # define BOOST_ARG_DEPENDENT_TYPENAME typename
772 # define BOOST_ARG_DEPENDENT_TYPENAME
775 //============================================================================
776 //iterator_adaptor - Adapts a generic piece of data as an iterator. Adaptation
777 // is especially easy if the data being adapted is itself an iterator
779 // Base - the base (usually iterator) type being wrapped.
781 // Policies - a set of policies determining how the resulting iterator
784 // Value - if supplied, the value_type of the resulting iterator, unless
785 // const. If const, a conforming compiler strips constness for the
786 // value_type. If not supplied, iterator_traits<Base>::value_type is used
788 // Reference - the reference type of the resulting iterator, and in
789 // particular, the result type of operator*(). If not supplied but
790 // Value is supplied, Value& is used. Otherwise
791 // iterator_traits<Base>::reference is used.
793 // Pointer - the pointer type of the resulting iterator, and in
794 // particular, the result type of operator->(). If not
795 // supplied but Value is supplied, Value* is used. Otherwise
796 // iterator_traits<Base>::pointer is used.
798 // Category - the iterator_category of the resulting iterator. If not
799 // supplied, iterator_traits<Base>::iterator_category is used.
801 // Distance - the difference_type of the resulting iterator. If not
802 // supplied, iterator_traits<Base>::difference_type is used.
803 template <class Base, class Policies,
804 class Value = ::boost::detail::default_argument,
805 class Reference = ::boost::detail::default_argument,
806 class Pointer = ::boost::detail::default_argument,
807 class Category = ::boost::detail::default_argument,
808 class Distance = ::boost::detail::default_argument
810 struct iterator_adaptor :
811 #ifdef BOOST_RELOPS_AMBIGUITY_BUG
812 iterator_comparisons<
813 iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance>,
814 typename detail::iterator_adaptor_traits_gen<Base,Value,Reference,Pointer,Category, Distance>::type
817 detail::iterator_adaptor_traits_gen<Base,Value,Reference,Pointer,Category,Distance>::type
820 typedef iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance> self;
822 typedef detail::iterator_adaptor_traits_gen<Base,Value,Reference,Pointer,Category,Distance> TraitsGen;
823 typedef typename TraitsGen::type Traits;
825 typedef typename Traits::difference_type difference_type;
826 typedef typename Traits::value_type value_type;
827 typedef typename Traits::pointer pointer;
828 typedef typename Traits::reference reference;
829 typedef typename Traits::iterator_category iterator_category;
831 typedef Base base_type;
832 typedef Policies policies_type;
835 typedef detail::validator<
836 iterator_category,value_type,difference_type,pointer,reference
845 iterator_adaptor(const Base& it, const Policies& p = Policies())
847 policies().initialize(base());
850 template <class Iter2, class Value2, class Pointer2, class Reference2>
852 const iterator_adaptor<Iter2,Policies,Value2,Reference2,Pointer2,Category,Distance>& src)
853 : m_iter_p(src.base(), src.policies())
855 policies().initialize(base());
858 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 || defined(__BORLANDC__)
859 // This is required to prevent a bug in how VC++ generates
860 // the assignment operator for compressed_pair
861 iterator_adaptor& operator= (const iterator_adaptor& x) {
862 m_iter_p = x.m_iter_p;
866 reference operator*() const {
867 return policies().dereference(*this);
871 # pragma warning(push)
872 # pragma warning( disable : 4284 )
875 typename boost::detail::operator_arrow_result_generator<value_type,reference,pointer>::type
877 { return detail::operator_arrow(*this, iterator_category()); }
880 # pragma warning(pop)
883 value_type operator[](difference_type n) const
884 { return *(*this + n); }
887 #if !defined(__MWERKS__) || __MWERKS__ >= 0x2405
888 policies().increment(*this);
890 // Odd bug, MWERKS couldn't deduce the type for the member template
891 // Workaround by explicitly specifying the type.
892 policies().increment<self>(*this);
897 self operator++(int) { self tmp(*this); ++*this; return tmp; }
900 #if !defined(__MWERKS__) || __MWERKS__ >= 0x2405
901 policies().decrement(*this);
903 policies().decrement<self>(*this);
908 self operator--(int) { self tmp(*this); --*this; return tmp; }
910 self& operator+=(difference_type n) {
911 policies().advance(*this, n);
915 self& operator-=(difference_type n) {
916 policies().advance(*this, -n);
920 base_type const& base() const { return m_iter_p.first(); }
922 // Moved from global scope to avoid ambiguity with the operator-() which
923 // subtracts iterators from one another.
924 self operator-(difference_type x) const
925 { self result(*this); return result -= x; }
927 compressed_pair<Base,Policies> m_iter_p;
929 public: // implementation details (too many compilers have trouble when these are private).
930 base_type& base() { return m_iter_p.first(); }
931 Policies& policies() { return m_iter_p.second(); }
932 const Policies& policies() const { return m_iter_p.second(); }
935 template <class Base, class Policies, class Value, class Reference, class Pointer,
936 class Category, class Distance1, class Distance2>
937 iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance1>
939 iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance1> p,
945 template <class Base, class Policies, class Value, class Reference, class Pointer,
946 class Category, class Distance1, class Distance2>
947 iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance1>
950 iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance1> p)
955 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
956 class Reference1, class Reference2, class Pointer1, class Pointer2, class Category,
958 typename iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>::difference_type
960 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
961 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
963 typedef typename iterator_adaptor<Iterator1,Policies,Value1,Reference1,
964 Pointer1,Category,Distance>::difference_type difference_type;
965 return x.policies().distance(y, x);
968 #ifndef BOOST_RELOPS_AMBIGUITY_BUG
969 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
970 class Reference1, class Reference2, class Pointer1, class Pointer2,
971 class Category, class Distance>
974 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
975 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
977 return x.policies().equal(x, y);
980 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
981 class Reference1, class Reference2, class Pointer1, class Pointer2,
982 class Category, class Distance>
985 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
986 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
988 return x.policies().distance(y, x) < 0;
991 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
992 class Reference1, class Reference2, class Pointer1, class Pointer2,
993 class Category, class Distance>
996 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
997 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
999 return x.policies().distance(y, x) > 0;
1002 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
1003 class Reference1, class Reference2, class Pointer1, class Pointer2,
1004 class Category, class Distance>
1007 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
1008 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
1010 return x.policies().distance(y, x) >= 0;
1013 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
1014 class Reference1, class Reference2, class Pointer1, class Pointer2,
1015 class Category, class Distance>
1018 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
1019 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
1021 return x.policies().distance(y, x) <= 0;
1024 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
1025 class Reference1, class Reference2, class Pointer1, class Pointer2,
1026 class Category, class Distance>
1029 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
1030 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
1032 return !x.policies().equal(x, y);
1036 //=============================================================================
1037 // Transform Iterator Adaptor
1039 // Upon deference, apply some unary function object and return the
1042 template <class AdaptableUnaryFunction>
1043 struct transform_iterator_policies : public default_iterator_policies
1045 transform_iterator_policies() { }
1046 transform_iterator_policies(const AdaptableUnaryFunction& f) : m_f(f) { }
1048 template <class IteratorAdaptor>
1049 typename IteratorAdaptor::reference
1050 dereference(const IteratorAdaptor& iter) const
1051 { return m_f(*iter.base()); }
1053 AdaptableUnaryFunction m_f;
1056 template <class AdaptableUnaryFunction, class Iterator>
1057 class transform_iterator_generator
1059 typedef typename AdaptableUnaryFunction::result_type value_type;
1061 typedef iterator_adaptor<Iterator,
1062 transform_iterator_policies<AdaptableUnaryFunction>,
1063 value_type, value_type, value_type*, std::input_iterator_tag>
1067 template <class AdaptableUnaryFunction, class Iterator>
1068 inline typename transform_iterator_generator<AdaptableUnaryFunction,Iterator>::type
1069 make_transform_iterator(
1071 const AdaptableUnaryFunction& f = AdaptableUnaryFunction())
1073 typedef typename transform_iterator_generator<AdaptableUnaryFunction,Iterator>::type result_t;
1074 return result_t(base, f);
1077 //=============================================================================
1078 // Indirect Iterators Adaptor
1080 // Given a pointer to pointers (or iterator to iterators),
1081 // apply a double dereference inside operator*().
1083 // We use the term "outer" to refer to the first level iterator type
1084 // and "inner" to refer to the second level iterator type. For
1085 // example, given T**, T* is the inner iterator type and T** is the
1086 // outer iterator type. Also, const T* would be the const inner
1089 // We tried to implement this with transform_iterator, but that required
1090 // using boost::remove_ref, which is not compiler portable.
1092 struct indirect_iterator_policies : public default_iterator_policies
1094 template <class IteratorAdaptor>
1095 typename IteratorAdaptor::reference dereference(const IteratorAdaptor& x) const
1096 { return **x.base(); }
1100 # if !defined(BOOST_MSVC) || BOOST_MSVC > 1300 // strangely instantiated even when unused! Maybe try a recursive template someday ;-)
1102 struct traits_of_value_type {
1103 typedef typename boost::detail::iterator_traits<T>::value_type outer_value;
1104 typedef typename boost::detail::iterator_traits<outer_value>::value_type value_type;
1105 typedef typename boost::detail::iterator_traits<outer_value>::reference reference;
1106 typedef typename boost::detail::iterator_traits<outer_value>::pointer pointer;
1111 template <class OuterIterator, // Mutable or Immutable, does not matter
1113 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1114 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1115 OuterIterator>::value_type
1118 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1119 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1120 OuterIterator>::reference
1124 , class Category = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<
1125 OuterIterator>::iterator_category
1127 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1128 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1129 OuterIterator>::pointer
1134 struct indirect_iterator_generator
1136 typedef iterator_adaptor<OuterIterator,
1137 indirect_iterator_policies,Value,Reference,Pointer,Category> type;
1140 template <class OuterIterator, // Mutable or Immutable, does not matter
1142 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1143 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1144 OuterIterator>::value_type
1147 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1148 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1149 OuterIterator>::reference
1153 , class ConstReference = const Value&
1154 , class Category = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<
1155 OuterIterator>::iterator_category
1157 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1158 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1159 OuterIterator>::pointer
1163 , class ConstPointer = const Value*
1165 struct indirect_iterator_pair_generator
1167 typedef typename indirect_iterator_generator<OuterIterator,
1168 Value, Reference,Category,Pointer>::type iterator;
1169 typedef typename indirect_iterator_generator<OuterIterator,
1170 Value, ConstReference,Category,ConstPointer>::type const_iterator;
1173 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1174 template <class OuterIterator>
1175 inline typename indirect_iterator_generator<OuterIterator>::type
1176 make_indirect_iterator(OuterIterator base)
1178 typedef typename indirect_iterator_generator
1179 <OuterIterator>::type result_t;
1180 return result_t(base);
1184 //=============================================================================
1185 // Reverse Iterators Adaptor
1187 struct reverse_iterator_policies : public default_iterator_policies
1189 template <class IteratorAdaptor>
1190 typename IteratorAdaptor::reference dereference(const IteratorAdaptor& x) const
1191 { return *boost::prior(x.base()); }
1193 template <class BidirectionalIterator>
1194 void increment(BidirectionalIterator& x) const
1197 template <class BidirectionalIterator>
1198 void decrement(BidirectionalIterator& x) const
1201 template <class BidirectionalIterator, class DifferenceType>
1202 void advance(BidirectionalIterator& x, DifferenceType n) const
1205 template <class Iterator1, class Iterator2>
1206 typename Iterator1::difference_type distance(
1207 const Iterator1& x, const Iterator2& y) const
1208 { return x.base() - y.base(); }
1210 template <class Iterator1, class Iterator2>
1211 bool equal(const Iterator1& x, const Iterator2& y) const
1212 { return x.base() == y.base(); }
1215 template <class BidirectionalIterator,
1216 class Value = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<BidirectionalIterator>::value_type,
1217 class Reference = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<BidirectionalIterator,Value>::reference,
1218 class Pointer = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<BidirectionalIterator,Value>::pointer,
1219 class Category = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<BidirectionalIterator>::iterator_category,
1220 class Distance = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<BidirectionalIterator>::difference_type
1222 struct reverse_iterator_generator
1224 typedef iterator_adaptor<BidirectionalIterator,reverse_iterator_policies,
1225 Value,Reference,Pointer,Category,Distance> type;
1228 template <class BidirectionalIterator>
1229 inline typename reverse_iterator_generator<BidirectionalIterator>::type
1230 make_reverse_iterator(BidirectionalIterator base)
1232 typedef typename reverse_iterator_generator<BidirectionalIterator>::type result_t;
1233 return result_t(base);
1236 //=============================================================================
1237 // Projection Iterators Adaptor
1239 template <class AdaptableUnaryFunction>
1240 struct projection_iterator_policies : public default_iterator_policies
1242 projection_iterator_policies() { }
1243 projection_iterator_policies(const AdaptableUnaryFunction& f) : m_f(f) { }
1245 template <class IteratorAdaptor>
1246 typename IteratorAdaptor::reference dereference(IteratorAdaptor const& iter) const {
1247 return m_f(*iter.base());
1250 AdaptableUnaryFunction m_f;
1253 template <class AdaptableUnaryFunction, class Iterator>
1254 class projection_iterator_generator {
1255 typedef typename AdaptableUnaryFunction::result_type value_type;
1256 typedef projection_iterator_policies<AdaptableUnaryFunction> policies;
1258 typedef iterator_adaptor<Iterator,policies,value_type,value_type&,value_type*> type;
1261 template <class AdaptableUnaryFunction, class Iterator>
1262 class const_projection_iterator_generator {
1263 typedef typename AdaptableUnaryFunction::result_type value_type;
1264 typedef projection_iterator_policies<AdaptableUnaryFunction> policies;
1266 typedef iterator_adaptor<Iterator,policies,value_type,const value_type&,const value_type*> type;
1269 template <class AdaptableUnaryFunction, class Iterator, class ConstIterator>
1270 struct projection_iterator_pair_generator {
1271 typedef typename projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type iterator;
1272 typedef typename const_projection_iterator_generator<AdaptableUnaryFunction, ConstIterator>::type const_iterator;
1276 template <class AdaptableUnaryFunction, class Iterator>
1277 inline typename projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type
1278 make_projection_iterator(
1280 const AdaptableUnaryFunction& f = AdaptableUnaryFunction())
1282 typedef typename projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type result_t;
1283 return result_t(iter, f);
1286 template <class AdaptableUnaryFunction, class Iterator>
1287 inline typename const_projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type
1288 make_const_projection_iterator(
1290 const AdaptableUnaryFunction& f = AdaptableUnaryFunction())
1292 typedef typename const_projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type result_t;
1293 return result_t(iter, f);
1296 //=============================================================================
1297 // Filter Iterator Adaptor
1299 template <class Predicate, class Iterator>
1300 class filter_iterator_policies
1303 filter_iterator_policies() { }
1305 filter_iterator_policies(const Predicate& p, const Iterator& end)
1306 : m_predicate(p), m_end(end) { }
1308 void initialize(Iterator& x) {
1309 satisfy_predicate(x);
1312 // The Iter template argument is neccessary for compatibility with a MWCW
1314 template <class IteratorAdaptor>
1315 void increment(IteratorAdaptor& x) {
1317 satisfy_predicate(x.base());
1320 template <class IteratorAdaptor>
1321 typename IteratorAdaptor::reference dereference(const IteratorAdaptor& x) const
1322 { return *x.base(); }
1324 template <class IteratorAdaptor1, class IteratorAdaptor2>
1325 bool equal(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
1326 { return x.base() == y.base(); }
1329 void satisfy_predicate(Iterator& iter);
1330 Predicate m_predicate;
1334 template <class Predicate, class Iterator>
1335 void filter_iterator_policies<Predicate,Iterator>::satisfy_predicate(
1338 while (m_end != iter && !m_predicate(*iter))
1345 // A type generator returning Base if T is derived from Base, and T otherwise.
1346 template <class Base, class T>
1347 struct reduce_to_base_class
1349 typedef typename if_true<(
1350 ::boost::is_convertible<T*,Base*>::value
1351 )>::template then<Base,T>::type type;
1354 // "Steps down" the category of iterators below bidirectional so the category
1355 // can be used with filter iterators.
1356 template <class Iterator>
1357 struct non_bidirectional_category
1359 # if !defined(__MWERKS__) || __MWERKS__ > 0x2406
1360 typedef typename reduce_to_base_class<
1361 std::forward_iterator_tag,
1362 typename iterator_traits<Iterator>::iterator_category
1365 // For some reason, putting this assertion in filter_iterator_generator fails inexplicably under MSVC
1366 BOOST_STATIC_CONSTANT(
1367 bool, is_bidirectional
1368 = (!boost::is_convertible<type*, std::bidirectional_iterator_tag*>::value));
1369 BOOST_STATIC_ASSERT(is_bidirectional);
1371 // is_convertible doesn't work with MWERKS
1372 typedef typename iterator_traits<Iterator>::iterator_category input_category;
1374 typedef typename if_true<(
1375 boost::is_same<input_category,std::random_access_iterator_tag>::value
1376 || boost::is_same<input_category,std::bidirectional_iterator_tag>::value
1378 std::forward_iterator_tag,
1385 template <class Predicate, class Iterator,
1386 class Value = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<Iterator>::value_type,
1387 class Reference = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<Iterator,Value>::reference,
1388 class Pointer = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<Iterator,Value>::pointer,
1389 class Category = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::non_bidirectional_category<Iterator>::type,
1390 class Distance = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<Iterator>::difference_type
1392 class filter_iterator_generator {
1393 BOOST_STATIC_CONSTANT(bool, is_bidirectional
1394 = (boost::is_convertible<Category*, std::bidirectional_iterator_tag*>::value));
1395 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300 // I don't have any idea why this occurs, but it doesn't seem to hurt too badly.
1396 BOOST_STATIC_ASSERT(!is_bidirectional);
1398 typedef filter_iterator_policies<Predicate,Iterator> policies_type;
1400 typedef iterator_adaptor<Iterator,policies_type,
1401 Value,Reference,Pointer,Category,Distance> type;
1404 // This keeps MSVC happy; it doesn't like to deduce default template arguments
1405 // for template function return types
1407 template <class Predicate, class Iterator>
1408 struct filter_generator {
1409 typedef typename boost::filter_iterator_generator<Predicate,Iterator>::type type;
1413 template <class Predicate, class Iterator>
1414 inline typename detail::filter_generator<Predicate, Iterator>::type
1415 make_filter_iterator(Iterator first, Iterator last, const Predicate& p = Predicate())
1417 typedef filter_iterator_generator<Predicate, Iterator> Gen;
1418 typedef filter_iterator_policies<Predicate,Iterator> policies_t;
1419 typedef typename Gen::type result_t;
1420 return result_t(first, policies_t(p, last));
1423 } // namespace boost
1424 # undef BOOST_ARG_DEPENDENT_TYPENAME