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/type_traits/conversion_traits.hpp>
128 # include <boost/detail/iterator.hpp>
129 # include <boost/detail/select_type.hpp>
131 // I was having some problems with VC6. I couldn't tell whether our hack for
132 // stock GCC was causing problems so I needed an easy way to turn it on and
133 // off. Now we can test the hack with various compilers and still have an
134 // "out" if it doesn't work. -dwa 7/31/00
135 # if __GNUC__ == 2 && __GNUC_MINOR__ <= 96 && !defined(__STL_USE_NAMESPACES)
136 # define BOOST_RELOPS_AMBIGUITY_BUG 1
141 //============================================================================
142 // Concept checking classes that express the requirements for iterator
143 // policies and adapted types. These classes are mostly for
144 // documentation purposes, and are not used in this header file. They
145 // merely provide a more succinct statement of what is expected of the
146 // iterator policies.
148 template <class Policies, class Adapted, class Traits>
149 struct TrivialIteratorPoliciesConcept
151 typedef typename Traits::reference reference;
153 function_requires< AssignableConcept<Policies> >();
154 function_requires< DefaultConstructibleConcept<Policies> >();
155 function_requires< AssignableConcept<Adapted> >();
156 function_requires< DefaultConstructibleConcept<Adapted> >();
160 void const_constraints() const {
161 reference r = p.dereference(x);
163 ignore_unused_variable_warning(r);
170 // Add InputIteratorPoliciesConcept?
172 template <class Policies, class Adapted, class Traits>
173 struct ForwardIteratorPoliciesConcept
175 typedef typename Traits::iterator_category iterator_category;
178 TrivialIteratorPoliciesConcept<Policies, Adapted, Traits>
182 std::forward_iterator_tag t = iterator_category();
183 ignore_unused_variable_warning(t);
187 iterator_category category;
190 template <class Policies, class Adapted, class Traits>
191 struct BidirectionalIteratorPoliciesConcept
193 typedef typename Traits::iterator_category iterator_category;
196 ForwardIteratorPoliciesConcept<Policies, Adapted, Traits>
200 std::bidirectional_iterator_tag t = iterator_category();
201 ignore_unused_variable_warning(t);
207 template <class Policies, class Adapted, class Traits>
208 struct RandomAccessIteratorPoliciesConcept
210 typedef typename Traits::difference_type DifferenceType;
211 typedef typename Traits::iterator_category iterator_category;
214 BidirectionalIteratorPoliciesConcept<Policies, Adapted, Traits>
218 std::random_access_iterator_tag t = iterator_category();
220 ignore_unused_variable_warning(t);
222 void const_constraints() const {
223 n = p.distance(x, x);
227 mutable DifferenceType n;
232 //============================================================================
233 // Default policies for iterator adaptors. You can use this as a base
234 // class if you want to customize particular policies.
235 struct default_iterator_policies
237 // Some of the member functions were defined static, but Borland
238 // got confused and thought they were non-const. Also, Sun C++
239 // does not like static function templates.
241 // The reason some members were defined static is because there is
242 // not state (data members) needed by those members of the
243 // default_iterator_policies class. If your policies class member
244 // functions need to access state stored in the policies object,
245 // then the member functions should not be static (they can't be).
247 template <class Base>
248 void initialize(Base&)
251 template <class IteratorAdaptor>
252 typename IteratorAdaptor::reference dereference(const IteratorAdaptor& x) const
253 { return *x.base(); }
255 template <class IteratorAdaptor>
256 void increment(IteratorAdaptor& x)
259 template <class IteratorAdaptor>
260 void decrement(IteratorAdaptor& x)
263 template <class IteratorAdaptor, class DifferenceType>
264 void advance(IteratorAdaptor& x, DifferenceType n)
267 template <class IteratorAdaptor1, class IteratorAdaptor2>
268 typename IteratorAdaptor1::difference_type
269 distance(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
270 { return y.base() - x.base(); }
272 template <class IteratorAdaptor1, class IteratorAdaptor2>
273 bool equal(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
274 { return x.base() == y.base(); }
277 // putting the comparisons in a base class avoids the g++
278 // ambiguous overload bug due to the relops operators
280 #ifdef BOOST_RELOPS_AMBIGUITY_BUG
281 template <class Derived, class Base>
282 struct iterator_comparisons : Base { };
284 template <class D1, class D2, class Base1, class Base2>
285 inline bool operator==(const iterator_comparisons<D1,Base1>& xb,
286 const iterator_comparisons<D2,Base2>& yb)
288 const D1& x = static_cast<const D1&>(xb);
289 const D2& y = static_cast<const D2&>(yb);
290 return x.policies().equal(x, y);
293 template <class D1, class D2, class Base1, class Base2>
294 inline bool operator!=(const iterator_comparisons<D1,Base1>& xb,
295 const iterator_comparisons<D2,Base2>& yb)
297 const D1& x = static_cast<const D1&>(xb);
298 const D2& y = static_cast<const D2&>(yb);
299 return !x.policies().equal(x, y);
302 template <class D1, class D2, class Base1, class Base2>
303 inline bool operator<(const iterator_comparisons<D1,Base1>& xb,
304 const iterator_comparisons<D2,Base2>& yb)
306 const D1& x = static_cast<const D1&>(xb);
307 const D2& y = static_cast<const D2&>(yb);
308 return x.policies().distance(y, x) < 0;
311 template <class D1, class D2, class Base1, class Base2>
312 inline bool operator>(const iterator_comparisons<D1,Base1>& xb,
313 const iterator_comparisons<D2,Base2>& yb)
315 const D1& x = static_cast<const D1&>(xb);
316 const D2& y = static_cast<const D2&>(yb);
317 return x.policies().distance(y, x) > 0;
320 template <class D1, class D2, class Base1, class Base2>
321 inline bool operator>=(const iterator_comparisons<D1,Base1>& xb,
322 const iterator_comparisons<D2,Base2>& yb)
324 const D1& x = static_cast<const D1&>(xb);
325 const D2& y = static_cast<const D2&>(yb);
326 return x.policies().distance(y, x) >= 0;
329 template <class D1, class D2, class Base1, class Base2>
330 inline bool operator<=(const iterator_comparisons<D1,Base1>& xb,
331 const iterator_comparisons<D2,Base2>& yb)
333 const D1& x = static_cast<const D1&>(xb);
334 const D2& y = static_cast<const D2&>(yb);
335 return x.policies().distance(y, x) <= 0;
341 // operator->() needs special support for input iterators to strictly meet the
342 // standard's requirements. If *i is not a reference type, we must still
343 // produce a (constant) lvalue to which a pointer can be formed. We do that by
344 // returning an instantiation of this special proxy class template.
347 struct operator_arrow_proxy
349 operator_arrow_proxy(const T& x) : m_value(x) {}
350 const T* operator->() const { return &m_value; }
351 // This function is needed for MWCW and BCC, which won't call operator->
352 // again automatically per 13.3.1.2 para 8
353 operator const T*() const { return &m_value; }
357 template <class Iter>
358 inline operator_arrow_proxy<typename Iter::value_type>
359 operator_arrow(const Iter& i, std::input_iterator_tag) {
360 typedef typename Iter::value_type value_t; // VC++ needs this typedef
361 return operator_arrow_proxy<value_t>(*i);
364 template <class Iter>
365 inline typename Iter::pointer
366 operator_arrow(const Iter& i, std::forward_iterator_tag) {
370 template <class Value, class Reference, class Pointer>
371 struct operator_arrow_result_generator
373 typedef operator_arrow_proxy<Value> proxy;
374 // Borland chokes unless it's an actual enum (!)
375 enum { use_proxy = !boost::is_reference<Reference>::value };
377 typedef typename boost::detail::if_true<(use_proxy)>::template
386 # if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) || defined(BOOST_NO_STD_ITERATOR_TRAITS)
388 // Select default pointer and reference types for adapted non-pointer
389 // iterators based on the iterator and the value_type. Poor man's partial
390 // specialization is in use here.
391 template <bool is_pointer>
392 struct iterator_defaults_select
394 template <class Iterator,class Value>
397 // The assumption is that iterator_traits can deduce these types
398 // properly as long as the iterator is not a pointer.
399 typedef typename boost::detail::iterator_traits<Iterator>::pointer pointer;
400 typedef typename boost::detail::iterator_traits<Iterator>::reference reference;
404 // Select default pointer and reference types for adapted pointer iterators
405 // given a (possibly-const) value_type.
407 struct iterator_defaults_select<true>
409 template <class Iterator,class Value>
412 typedef Value* pointer;
413 typedef Value& reference;
417 // Consolidate selection of the default pointer and reference type
418 template <class Iterator,class Value>
419 struct iterator_defaults
421 BOOST_STATIC_CONSTANT(bool, is_ptr = boost::is_pointer<Iterator>::value);
423 typedef typename iterator_defaults_select<is_ptr>::template traits<Iterator,Value> traits;
424 typedef typename traits::pointer pointer;
425 typedef typename traits::reference reference;
428 template <class Iterator,class Value>
429 struct iterator_defaults : iterator_traits<Iterator>
431 // Trying to factor the common is_same expression into an enum or a
432 // static bool constant confused Borland.
433 typedef typename if_true<(
434 ::boost::is_same<Value,typename iterator_traits<Iterator>::value_type>::value
436 typename iterator_traits<Iterator>::pointer,
440 typedef typename if_true<(
441 ::boost::is_same<Value,typename iterator_traits<Iterator>::value_type>::value
443 typename iterator_traits<Iterator>::reference,
450 //===========================================================================
451 // Specify the defaults for iterator_adaptor's template parameters
453 struct default_argument { };
454 // This class template is a workaround for MSVC.
455 struct dummy_default_gen {
456 template <class Base, class Traits>
457 struct select { typedef default_argument type; };
459 // This class template is a workaround for MSVC.
460 template <class Gen> struct default_generator {
461 typedef dummy_default_gen type;
464 struct default_value_type {
465 template <class Base, class Traits>
467 typedef typename boost::detail::iterator_traits<Base>::value_type type;
470 template <> struct default_generator<default_value_type>
471 { typedef default_value_type type; }; // VC++ workaround
473 struct default_difference_type {
474 template <class Base, class Traits>
476 typedef typename boost::detail::iterator_traits<Base>::difference_type type;
479 template <> struct default_generator<default_difference_type>
480 { typedef default_difference_type type; }; // VC++ workaround
482 struct default_iterator_category {
483 template <class Base, class Traits>
485 typedef typename boost::detail::iterator_traits<Base>::iterator_category type;
488 template <> struct default_generator<default_iterator_category>
489 { typedef default_iterator_category type; }; // VC++ workaround
491 struct default_pointer {
492 template <class Base, class Traits>
494 typedef typename Traits::value_type Value;
495 typedef typename boost::detail::iterator_defaults<Base,Value>::pointer
499 template <> struct default_generator<default_pointer>
500 { typedef default_pointer type; }; // VC++ workaround
502 struct default_reference {
503 template <class Base, class Traits>
505 typedef typename Traits::value_type Value;
506 typedef typename boost::detail::iterator_defaults<Base,Value>::reference
510 template <> struct default_generator<default_reference>
511 { typedef default_reference type; }; // VC++ workaround
513 } // namespace detail
516 //===========================================================================
517 // Support for named template parameters
519 struct named_template_param_base { };
522 struct value_type_tag { };
523 struct reference_tag { };
524 struct pointer_tag { };
525 struct difference_type_tag { };
526 struct iterator_category_tag { };
528 // avoid using std::pair because A or B might be a reference type, and g++
529 // complains about forming references to references inside std::pair
530 template <class A, class B>
532 typedef A first_type;
533 typedef B second_type;
536 } // namespace detail
538 template <class Value> struct value_type_is : public named_template_param_base
540 typedef detail::cons_type<detail::value_type_tag, Value> type;
542 template <class Reference> struct reference_is : public named_template_param_base
544 typedef detail::cons_type<detail::reference_tag, Reference> type;
546 template <class Pointer> struct pointer_is : public named_template_param_base
548 typedef detail::cons_type<detail::pointer_tag, Pointer> type;
550 template <class Difference> struct difference_type_is
551 : public named_template_param_base
553 typedef detail::cons_type<detail::difference_type_tag, Difference> type;
555 template <class IteratorCategory> struct iterator_category_is
556 : public named_template_param_base
558 typedef detail::cons_type<detail::iterator_category_tag, IteratorCategory> type;
563 struct end_of_list { };
565 // Given an associative list, find the value with the matching key.
566 // An associative list is a list of key-value pairs. The list is
567 // built out of cons_type's and is terminated by end_of_list.
569 # if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) || defined(__BORLANDC__)
570 template <class AssocList, class Key>
573 struct find_param_continue {
574 template <class AssocList, class Key2> struct select {
575 typedef typename AssocList::first_type Head;
576 typedef typename Head::first_type Key1;
577 typedef typename Head::second_type Value;
578 typedef typename if_true<(is_same<Key1, Key2>::value)>::template
580 typename find_param<typename AssocList::second_type, Key2>::type
584 struct find_param_end {
585 template <class AssocList, class Key>
586 struct select { typedef detail::default_argument type; };
588 template <class AssocList> struct find_param_helper1
589 { typedef find_param_continue type; };
590 template <> struct find_param_helper1<end_of_list>
591 { typedef find_param_end type; };
593 template <class AssocList, class Key>
595 typedef typename find_param_helper1<AssocList>::type select1;
596 typedef typename select1::template select<AssocList, Key>::type type;
599 template <class AssocList, class Key> struct find_param;
602 struct find_param<end_of_list, Key> { typedef default_argument type; };
604 // Found a matching Key, return the associated Value
605 template <class Key, class Value, class Rest>
606 struct find_param<detail::cons_type< detail::cons_type<Key, Value>, Rest>, Key> {
610 // Non-matching keys, continue the search
611 template <class Key1, class Value, class Rest, class Key2>
612 struct find_param<detail::cons_type< detail::cons_type<Key1, Value>, Rest>, Key2> {
613 typedef typename find_param<Rest, Key2>::type type;
617 struct make_named_arg {
618 template <class Key, class Value>
619 struct select { typedef typename Value::type type; };
621 struct make_key_value {
622 template <class Key, class Value>
623 struct select { typedef detail::cons_type<Key, Value> type; };
626 template <class Value>
627 struct is_named_parameter
629 enum { value = is_convertible< typename add_reference< Value >::type, add_reference< named_template_param_base >::type >::value };
632 # if defined(__MWERKS__) && __MWERKS__ <= 0x2406 // workaround for broken is_convertible implementation
633 template <class T> struct is_named_parameter<value_type_is<T> > { enum { value = true }; };
634 template <class T> struct is_named_parameter<reference_is<T> > { enum { value = true }; };
635 template <class T> struct is_named_parameter<pointer_is<T> > { enum { value = true }; };
636 template <class T> struct is_named_parameter<difference_type_is<T> > { enum { value = true }; };
637 template <class T> struct is_named_parameter<iterator_category_is<T> > { enum { value = true }; };
640 template <class Key, class Value>
643 // Borland C++ doesn't like the extra indirection of is_named_parameter
645 if_true<(is_convertible<Value,named_template_param_base>::value)>::
646 template then<make_named_arg, make_key_value>::type Make;
648 enum { is_named = is_named_parameter<Value>::value };
649 typedef typename if_true<(is_named)>::template
650 then<make_named_arg, make_key_value>::type Make;
652 typedef typename Make::template select<Key, Value>::type type;
655 // Mechanism for resolving the default argument for a template parameter.
657 template <class T> struct is_default { typedef type_traits::no_type type; };
658 template <> struct is_default<default_argument>
659 { typedef type_traits::yes_type type; };
661 struct choose_default {
662 template <class Arg, class DefaultGen, class Base, class Traits>
664 typedef typename default_generator<DefaultGen>::type Gen;
665 typedef typename Gen::template select<Base,Traits>::type type;
669 template <class Arg, class DefaultGen, class Base, class Traits>
675 template <class UseDefault>
676 struct choose_arg_or_default { typedef choose_arg type; };
677 template <> struct choose_arg_or_default<type_traits::yes_type> {
678 typedef choose_default type;
681 template <class Arg, class DefaultGen, class Base, class Traits>
682 class resolve_default {
683 typedef typename choose_arg_or_default<typename is_default<Arg>::type>::type
686 typedef typename Selector
687 ::template select<Arg, DefaultGen, Base, Traits>::type type;
690 template <class Base, class Value, class Reference, class Pointer,
691 class Category, class Distance>
692 class iterator_adaptor_traits_gen
694 // Form an associative list out of the template parameters
695 // If the argument is a normal parameter (not named) then make_arg
696 // creates a key-value pair. If the argument is a named parameter,
697 // then make_arg extracts the key-value pair defined inside the
699 typedef detail::cons_type< typename make_arg<value_type_tag, Value>::type,
700 detail::cons_type<typename make_arg<reference_tag, Reference>::type,
701 detail::cons_type<typename make_arg<pointer_tag, Pointer>::type,
702 detail::cons_type<typename make_arg<iterator_category_tag, Category>::type,
703 detail::cons_type<typename make_arg<difference_type_tag, Distance>::type,
704 end_of_list> > > > > ArgList;
706 // Search the list for particular parameters
707 typedef typename find_param<ArgList, value_type_tag>::type Val;
708 typedef typename find_param<ArgList, difference_type_tag>::type Diff;
709 typedef typename find_param<ArgList, iterator_category_tag>::type Cat;
710 typedef typename find_param<ArgList, pointer_tag>::type Ptr;
711 typedef typename find_param<ArgList, reference_tag>::type Ref;
713 typedef boost::iterator<Category, Value, Distance, Pointer, Reference>
716 // Compute the defaults if necessary
717 typedef typename resolve_default<Val, default_value_type, Base, Traits0>::type
719 // if getting default value type from iterator_traits, then it won't be const
720 typedef typename resolve_default<Diff, default_difference_type, Base,
721 Traits0>::type difference_type;
722 typedef typename resolve_default<Cat, default_iterator_category, Base,
723 Traits0>::type iterator_category;
725 typedef boost::iterator<iterator_category, value_type, difference_type,
726 Pointer, Reference> Traits1;
728 // Compute the defaults for pointer and reference. This is done as a
729 // separate step because the defaults for pointer and reference depend
731 typedef typename resolve_default<Ptr, default_pointer, Base, Traits1>::type
733 typedef typename resolve_default<Ref, default_reference, Base, Traits1>::type
737 typedef boost::iterator<iterator_category,
738 typename remove_const<value_type>::type,
739 difference_type, pointer, reference> type;
742 // This is really a partial concept check for iterators. Should it
743 // be moved or done differently?
744 template <class Category, class Value, class Difference, class Pointer, class Reference>
747 BOOST_STATIC_CONSTANT(
748 bool, is_input_or_output_iter
749 = (boost::is_convertible<Category*,std::input_iterator_tag*>::value
750 | boost::is_convertible<Category*,std::output_iterator_tag*>::value));
752 // Iterators should satisfy one of the known categories
753 BOOST_STATIC_ASSERT(is_input_or_output_iter);
755 // Iterators >= ForwardIterator must produce real references
756 // as required by the C++ standard requirements in Table 74.
757 BOOST_STATIC_CONSTANT(
758 bool, forward_iter_with_real_reference
759 = ((!boost::is_convertible<Category*,std::forward_iterator_tag*>::value)
760 | boost::is_same<Reference,Value&>::value
761 | boost::is_same<Reference,typename add_const<Value>::type&>::value));
763 BOOST_STATIC_ASSERT(forward_iter_with_real_reference);
766 template <class T, class Result> struct dependent
771 } // namespace detail
775 // This macro definition is only temporary in this file
776 # if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
777 # define BOOST_ARG_DEPENDENT_TYPENAME typename
779 # define BOOST_ARG_DEPENDENT_TYPENAME
782 //============================================================================
783 //iterator_adaptor - Adapts a generic piece of data as an iterator. Adaptation
784 // is especially easy if the data being adapted is itself an iterator
786 // Base - the base (usually iterator) type being wrapped.
788 // Policies - a set of policies determining how the resulting iterator
791 // Value - if supplied, the value_type of the resulting iterator, unless
792 // const. If const, a conforming compiler strips constness for the
793 // value_type. If not supplied, iterator_traits<Base>::value_type is used
795 // Reference - the reference type of the resulting iterator, and in
796 // particular, the result type of operator*(). If not supplied but
797 // Value is supplied, Value& is used. Otherwise
798 // iterator_traits<Base>::reference is used.
800 // Pointer - the pointer type of the resulting iterator, and in
801 // particular, the result type of operator->(). If not
802 // supplied but Value is supplied, Value* is used. Otherwise
803 // iterator_traits<Base>::pointer is used.
805 // Category - the iterator_category of the resulting iterator. If not
806 // supplied, iterator_traits<Base>::iterator_category is used.
808 // Distance - the difference_type of the resulting iterator. If not
809 // supplied, iterator_traits<Base>::difference_type is used.
810 template <class Base, class Policies,
811 class Value = ::boost::detail::default_argument,
812 class Reference = ::boost::detail::default_argument,
813 class Pointer = ::boost::detail::default_argument,
814 class Category = ::boost::detail::default_argument,
815 class Distance = ::boost::detail::default_argument
817 struct iterator_adaptor :
818 #ifdef BOOST_RELOPS_AMBIGUITY_BUG
819 iterator_comparisons<
820 iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance>,
821 typename detail::iterator_adaptor_traits_gen<Base,Value,Reference,Pointer,Category, Distance>::type
824 detail::iterator_adaptor_traits_gen<Base,Value,Reference,Pointer,Category,Distance>::type
827 typedef iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance> self;
829 typedef detail::iterator_adaptor_traits_gen<Base,Value,Reference,Pointer,Category,Distance> TraitsGen;
830 typedef typename TraitsGen::type Traits;
832 typedef typename Traits::difference_type difference_type;
833 typedef typename Traits::value_type value_type;
834 typedef typename Traits::pointer pointer;
835 typedef typename Traits::reference reference;
836 typedef typename Traits::iterator_category iterator_category;
838 typedef Base base_type;
839 typedef Policies policies_type;
842 typedef detail::validator<
843 iterator_category,value_type,difference_type,pointer,reference
852 iterator_adaptor(const Base& it, const Policies& p = Policies())
854 policies().initialize(base());
857 template <class Iter2, class Value2, class Pointer2, class Reference2>
859 const iterator_adaptor<Iter2,Policies,Value2,Reference2,Pointer2,Category,Distance>& src)
860 : m_iter_p(src.base(), src.policies())
862 policies().initialize(base());
865 #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 || defined(__BORLANDC__)
866 // This is required to prevent a bug in how VC++ generates
867 // the assignment operator for compressed_pair
868 iterator_adaptor& operator= (const iterator_adaptor& x) {
869 m_iter_p = x.m_iter_p;
873 reference operator*() const {
874 return policies().dereference(*this);
878 # pragma warning(push)
879 # pragma warning( disable : 4284 )
882 typename boost::detail::operator_arrow_result_generator<value_type,reference,pointer>::type
884 { return detail::operator_arrow(*this, iterator_category()); }
887 # pragma warning(pop)
890 template <class diff_type>
891 typename detail::dependent<diff_type, value_type>::type operator[](diff_type n) const
892 { return *(*this + n); }
895 #if !defined(__MWERKS__) || __MWERKS__ >= 0x2405
896 policies().increment(*this);
898 // Odd bug, MWERKS couldn't deduce the type for the member template
899 // Workaround by explicitly specifying the type.
900 policies().increment<self>(*this);
905 self operator++(int) { self tmp(*this); ++*this; return tmp; }
908 #if !defined(__MWERKS__) || __MWERKS__ >= 0x2405
909 policies().decrement(*this);
911 policies().decrement<self>(*this);
916 self operator--(int) { self tmp(*this); --*this; return tmp; }
918 self& operator+=(difference_type n) {
919 policies().advance(*this, n);
923 self& operator-=(difference_type n) {
924 policies().advance(*this, -n);
928 base_type const& base() const { return m_iter_p.first(); }
930 // Moved from global scope to avoid ambiguity with the operator-() which
931 // subtracts iterators from one another.
932 self operator-(difference_type x) const
933 { self result(*this); return result -= x; }
935 compressed_pair<Base,Policies> m_iter_p;
937 public: // implementation details (too many compilers have trouble when these are private).
938 base_type& base() { return m_iter_p.first(); }
939 Policies& policies() { return m_iter_p.second(); }
940 const Policies& policies() const { return m_iter_p.second(); }
943 template <class Base, class Policies, class Value, class Reference, class Pointer,
944 class Category, class Distance1, class Distance2>
945 iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance1>
947 iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance1> p,
953 template <class Base, class Policies, class Value, class Reference, class Pointer,
954 class Category, class Distance1, class Distance2>
955 iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance1>
958 iterator_adaptor<Base,Policies,Value,Reference,Pointer,Category,Distance1> p)
963 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
964 class Reference1, class Reference2, class Pointer1, class Pointer2, class Category,
966 typename iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>::difference_type
968 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
969 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
971 typedef typename iterator_adaptor<Iterator1,Policies,Value1,Reference1,
972 Pointer1,Category,Distance>::difference_type difference_type;
973 return x.policies().distance(y, x);
976 #ifndef BOOST_RELOPS_AMBIGUITY_BUG
977 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
978 class Reference1, class Reference2, class Pointer1, class Pointer2,
979 class Category, class Distance>
982 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
983 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
985 return x.policies().equal(x, y);
988 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
989 class Reference1, class Reference2, class Pointer1, class Pointer2,
990 class Category, class Distance>
993 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
994 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
996 return x.policies().distance(y, x) < 0;
999 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
1000 class Reference1, class Reference2, class Pointer1, class Pointer2,
1001 class Category, class Distance>
1004 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
1005 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
1007 return x.policies().distance(y, x) > 0;
1010 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
1011 class Reference1, class Reference2, class Pointer1, class Pointer2,
1012 class Category, class Distance>
1015 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
1016 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
1018 return x.policies().distance(y, x) >= 0;
1021 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
1022 class Reference1, class Reference2, class Pointer1, class Pointer2,
1023 class Category, class Distance>
1026 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
1027 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
1029 return x.policies().distance(y, x) <= 0;
1032 template <class Iterator1, class Iterator2, class Policies, class Value1, class Value2,
1033 class Reference1, class Reference2, class Pointer1, class Pointer2,
1034 class Category, class Distance>
1037 const iterator_adaptor<Iterator1,Policies,Value1,Reference1,Pointer1,Category,Distance>& x,
1038 const iterator_adaptor<Iterator2,Policies,Value2,Reference2,Pointer2,Category,Distance>& y)
1040 return !x.policies().equal(x, y);
1044 //=============================================================================
1045 // Transform Iterator Adaptor
1047 // Upon deference, apply some unary function object and return the
1050 template <class AdaptableUnaryFunction>
1051 struct transform_iterator_policies : public default_iterator_policies
1053 transform_iterator_policies() { }
1054 transform_iterator_policies(const AdaptableUnaryFunction& f) : m_f(f) { }
1056 template <class IteratorAdaptor>
1057 typename IteratorAdaptor::reference
1058 dereference(const IteratorAdaptor& iter) const
1059 { return m_f(*iter.base()); }
1061 AdaptableUnaryFunction m_f;
1064 template <class AdaptableUnaryFunction, class Iterator>
1065 class transform_iterator_generator
1067 typedef typename AdaptableUnaryFunction::result_type value_type;
1069 typedef iterator_adaptor<Iterator,
1070 transform_iterator_policies<AdaptableUnaryFunction>,
1071 value_type, value_type, value_type*, std::input_iterator_tag>
1075 template <class AdaptableUnaryFunction, class Iterator>
1076 inline typename transform_iterator_generator<AdaptableUnaryFunction,Iterator>::type
1077 make_transform_iterator(
1079 const AdaptableUnaryFunction& f = AdaptableUnaryFunction())
1081 typedef typename transform_iterator_generator<AdaptableUnaryFunction,Iterator>::type result_t;
1082 return result_t(base, f);
1085 //=============================================================================
1086 // Indirect Iterators Adaptor
1088 // Given a pointer to pointers (or iterator to iterators),
1089 // apply a double dereference inside operator*().
1091 // We use the term "outer" to refer to the first level iterator type
1092 // and "inner" to refer to the second level iterator type. For
1093 // example, given T**, T* is the inner iterator type and T** is the
1094 // outer iterator type. Also, const T* would be the const inner
1097 // We tried to implement this with transform_iterator, but that required
1098 // using boost::remove_ref, which is not compiler portable.
1100 struct indirect_iterator_policies : public default_iterator_policies
1102 template <class IteratorAdaptor>
1103 typename IteratorAdaptor::reference dereference(const IteratorAdaptor& x) const
1104 { return **x.base(); }
1108 # if !defined(BOOST_MSVC) || BOOST_MSVC > 1300 // strangely instantiated even when unused! Maybe try a recursive template someday ;-)
1110 struct traits_of_value_type {
1111 typedef typename boost::detail::iterator_traits<T>::value_type outer_value;
1112 typedef typename boost::detail::iterator_traits<outer_value>::value_type value_type;
1113 typedef typename boost::detail::iterator_traits<outer_value>::reference reference;
1114 typedef typename boost::detail::iterator_traits<outer_value>::pointer pointer;
1119 template <class OuterIterator, // Mutable or Immutable, does not matter
1121 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1122 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1123 OuterIterator>::value_type
1126 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1127 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1128 OuterIterator>::reference
1132 , class Category = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<
1133 OuterIterator>::iterator_category
1135 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1136 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1137 OuterIterator>::pointer
1142 struct indirect_iterator_generator
1144 typedef iterator_adaptor<OuterIterator,
1145 indirect_iterator_policies,Value,Reference,Pointer,Category> type;
1148 template <class OuterIterator, // Mutable or Immutable, does not matter
1150 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1151 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1152 OuterIterator>::value_type
1155 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1156 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1157 OuterIterator>::reference
1161 , class ConstReference = Value const&
1162 , class Category = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<
1163 OuterIterator>::iterator_category
1165 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1166 = BOOST_ARG_DEPENDENT_TYPENAME detail::traits_of_value_type<
1167 OuterIterator>::pointer
1171 , class ConstPointer = Value const*
1173 struct indirect_iterator_pair_generator
1175 typedef typename indirect_iterator_generator<OuterIterator,
1176 Value, Reference,Category,Pointer>::type iterator;
1177 typedef typename indirect_iterator_generator<OuterIterator,
1178 Value, ConstReference,Category,ConstPointer>::type const_iterator;
1181 #if !defined(BOOST_MSVC) || BOOST_MSVC > 1300
1182 template <class OuterIterator>
1183 inline typename indirect_iterator_generator<OuterIterator>::type
1184 make_indirect_iterator(OuterIterator base)
1186 typedef typename indirect_iterator_generator
1187 <OuterIterator>::type result_t;
1188 return result_t(base);
1192 //=============================================================================
1193 // Reverse Iterators Adaptor
1195 struct reverse_iterator_policies : public default_iterator_policies
1197 template <class IteratorAdaptor>
1198 typename IteratorAdaptor::reference dereference(const IteratorAdaptor& x) const
1199 { return *boost::prior(x.base()); }
1201 template <class BidirectionalIterator>
1202 void increment(BidirectionalIterator& x) const
1205 template <class BidirectionalIterator>
1206 void decrement(BidirectionalIterator& x) const
1209 template <class BidirectionalIterator, class DifferenceType>
1210 void advance(BidirectionalIterator& x, DifferenceType n) const
1213 template <class Iterator1, class Iterator2>
1214 typename Iterator1::difference_type distance(
1215 const Iterator1& x, const Iterator2& y) const
1216 { return x.base() - y.base(); }
1218 template <class Iterator1, class Iterator2>
1219 bool equal(const Iterator1& x, const Iterator2& y) const
1220 { return x.base() == y.base(); }
1223 template <class BidirectionalIterator,
1224 class Value = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<BidirectionalIterator>::value_type,
1225 class Reference = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<BidirectionalIterator,Value>::reference,
1226 class Pointer = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<BidirectionalIterator,Value>::pointer,
1227 class Category = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<BidirectionalIterator>::iterator_category,
1228 class Distance = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<BidirectionalIterator>::difference_type
1230 struct reverse_iterator_generator
1232 typedef iterator_adaptor<BidirectionalIterator,reverse_iterator_policies,
1233 Value,Reference,Pointer,Category,Distance> type;
1236 template <class BidirectionalIterator>
1237 inline typename reverse_iterator_generator<BidirectionalIterator>::type
1238 make_reverse_iterator(BidirectionalIterator base)
1240 typedef typename reverse_iterator_generator<BidirectionalIterator>::type result_t;
1241 return result_t(base);
1244 //=============================================================================
1245 // Projection Iterators Adaptor
1247 template <class AdaptableUnaryFunction>
1248 struct projection_iterator_policies : public default_iterator_policies
1250 projection_iterator_policies() { }
1251 projection_iterator_policies(const AdaptableUnaryFunction& f) : m_f(f) { }
1253 template <class IteratorAdaptor>
1254 typename IteratorAdaptor::reference dereference(IteratorAdaptor const& iter) const {
1255 return m_f(*iter.base());
1258 AdaptableUnaryFunction m_f;
1261 template <class AdaptableUnaryFunction, class Iterator>
1262 class 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,value_type&,value_type*> type;
1269 template <class AdaptableUnaryFunction, class Iterator>
1270 class const_projection_iterator_generator {
1271 typedef typename AdaptableUnaryFunction::result_type value_type;
1272 typedef projection_iterator_policies<AdaptableUnaryFunction> policies;
1274 typedef iterator_adaptor<Iterator,policies,value_type,const value_type&,const value_type*> type;
1277 template <class AdaptableUnaryFunction, class Iterator, class ConstIterator>
1278 struct projection_iterator_pair_generator {
1279 typedef typename projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type iterator;
1280 typedef typename const_projection_iterator_generator<AdaptableUnaryFunction, ConstIterator>::type const_iterator;
1284 template <class AdaptableUnaryFunction, class Iterator>
1285 inline typename projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type
1286 make_projection_iterator(
1288 const AdaptableUnaryFunction& f = AdaptableUnaryFunction())
1290 typedef typename projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type result_t;
1291 return result_t(iter, f);
1294 template <class AdaptableUnaryFunction, class Iterator>
1295 inline typename const_projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type
1296 make_const_projection_iterator(
1298 const AdaptableUnaryFunction& f = AdaptableUnaryFunction())
1300 typedef typename const_projection_iterator_generator<AdaptableUnaryFunction, Iterator>::type result_t;
1301 return result_t(iter, f);
1304 //=============================================================================
1305 // Filter Iterator Adaptor
1307 template <class Predicate, class Iterator>
1308 class filter_iterator_policies
1311 filter_iterator_policies() { }
1313 filter_iterator_policies(const Predicate& p, const Iterator& end)
1314 : m_predicate(p), m_end(end) { }
1316 void initialize(Iterator& x) {
1317 satisfy_predicate(x);
1320 // The Iter template argument is neccessary for compatibility with a MWCW
1322 template <class IteratorAdaptor>
1323 void increment(IteratorAdaptor& x) {
1325 satisfy_predicate(x.base());
1328 template <class IteratorAdaptor>
1329 typename IteratorAdaptor::reference dereference(const IteratorAdaptor& x) const
1330 { return *x.base(); }
1332 template <class IteratorAdaptor1, class IteratorAdaptor2>
1333 bool equal(const IteratorAdaptor1& x, const IteratorAdaptor2& y) const
1334 { return x.base() == y.base(); }
1337 void satisfy_predicate(Iterator& iter);
1338 Predicate m_predicate;
1342 template <class Predicate, class Iterator>
1343 void filter_iterator_policies<Predicate,Iterator>::satisfy_predicate(
1346 while (m_end != iter && !m_predicate(*iter))
1353 // A type generator returning Base if T is derived from Base, and T otherwise.
1354 template <class Base, class T>
1355 struct reduce_to_base_class
1357 typedef typename if_true<(
1358 ::boost::is_convertible<T*,Base*>::value
1359 )>::template then<Base,T>::type type;
1362 // "Steps down" the category of iterators below bidirectional so the category
1363 // can be used with filter iterators.
1364 template <class Iterator>
1365 struct non_bidirectional_category
1367 # if !defined(__MWERKS__) || __MWERKS__ > 0x2406
1368 typedef typename reduce_to_base_class<
1369 std::forward_iterator_tag,
1370 typename iterator_traits<Iterator>::iterator_category
1373 // For some reason, putting this assertion in filter_iterator_generator fails inexplicably under MSVC
1374 BOOST_STATIC_CONSTANT(
1375 bool, is_bidirectional
1376 = (!boost::is_convertible<type*, std::bidirectional_iterator_tag*>::value));
1377 BOOST_STATIC_ASSERT(is_bidirectional);
1379 // is_convertible doesn't work with MWERKS
1380 typedef typename iterator_traits<Iterator>::iterator_category input_category;
1382 typedef typename if_true<(
1383 boost::is_same<input_category,std::random_access_iterator_tag>::value
1384 || boost::is_same<input_category,std::bidirectional_iterator_tag>::value
1386 std::forward_iterator_tag,
1393 template <class Predicate, class Iterator,
1394 class Value = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<Iterator>::value_type,
1395 class Reference = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<Iterator,Value>::reference,
1396 class Pointer = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_defaults<Iterator,Value>::pointer,
1397 class Category = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::non_bidirectional_category<Iterator>::type,
1398 class Distance = BOOST_ARG_DEPENDENT_TYPENAME boost::detail::iterator_traits<Iterator>::difference_type
1400 class filter_iterator_generator {
1401 BOOST_STATIC_CONSTANT(bool, is_bidirectional
1402 = (boost::is_convertible<Category*, std::bidirectional_iterator_tag*>::value));
1403 #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.
1404 BOOST_STATIC_ASSERT(!is_bidirectional);
1406 typedef filter_iterator_policies<Predicate,Iterator> policies_type;
1408 typedef iterator_adaptor<Iterator,policies_type,
1409 Value,Reference,Pointer,Category,Distance> type;
1412 // This keeps MSVC happy; it doesn't like to deduce default template arguments
1413 // for template function return types
1415 template <class Predicate, class Iterator>
1416 struct filter_generator {
1417 typedef typename boost::filter_iterator_generator<Predicate,Iterator>::type type;
1421 template <class Predicate, class Iterator>
1422 inline typename detail::filter_generator<Predicate, Iterator>::type
1423 make_filter_iterator(Iterator first, Iterator last, const Predicate& p = Predicate())
1425 typedef filter_iterator_generator<Predicate, Iterator> Gen;
1426 typedef filter_iterator_policies<Predicate,Iterator> policies_t;
1427 typedef typename Gen::type result_t;
1428 return result_t(first, policies_t(p, last));
1431 } // namespace boost
1432 # undef BOOST_ARG_DEPENDENT_TYPENAME