any_iteratorClass Template Declaration
any_iteratoris the analog to
boost::functionfor iterators. It allows you to have a single variable and assign to it iterators of different types, as long as these iterators have a suitable commonality.
For a more in-depth view of type erasure in
general and my
any_iterator in particular,
see my October 2007 article at The C++ Source.
any_iteratoris declared like this:
template< class Value, class CategoryOrTraversal, class Reference = Value&, class Difference = std::ptrdiff_t > class any_iterator;For the second template argument, you may use the old-style STL iterator categories such as
std::random_access_iterator_tag, or you may use the new traversal categories as set forth in the Boost iterator library.
std::vector<double>::const_iteratoras well as an
typedef any_iterator< double const, boost::bidirectional_traversal_tag > any_number_iterator; any_number_iterator number_iter; std::vector<double> number_vector(42, 43.0); number_iter = number_vector.begin(); double d = *number_iter; std::list<double> number_list(42, 44.0); number_iter = number_list.begin(); d = *number_iter;
Next, suppose you want the variable
hold not only the vector and list iterators, but also a Boost
transform iterator which, upon dereferencing, multiplies by 100.0,
number_iter = boost::make_transform_iterator( number_vector.begin(), boost::bind(std::multiplies<double>(), _1, 100) );The
any_iterator's assignment operator is not enabled for this assignment, and you will get an error message such as
binary '=': no operator found which takes a right-hand operand of type...Why is this assignment not allowed? The transform iterator's
double. If we were to pass that through our number iterator, which currently has a reference type of
double const&, then the number iterator's
operator*would be returning a reference to a temporary local variable. The solution is to change the
any_iterator's reference type so that it is no longer a reference:
typedef any_iterator< double const, // Value boost::bidirectional_traversal_tag, double const // Reference > any_number_iterator;Now all of the assignments above will compile and work. It should be intuitively clear by now what the rules are for assigning "concrete" iterators to
any_iteratorvariables. For example, an
any_iteratorthat's a bidirectional iterator will not accept something that's a forward iterator only, like an iterator into a singly linked list. That would not make sense: a variable whose iterator category is bidirectional cannot at runtime hold something that is only a forward iterator. Similarly, our
any_number_iteratorwould not accept anything that dereferences to something that does not convert to a
double. After such an assignment, dereferencing would not make sense anymore.
You can find more examples in the
any_iterator_demo.hpp that comes with the
distribution. The exact, formal rules for assigning "concrete"
any_iterator variables are stated
std::vector<int> int_vector; std::vector<int>::iterator it = int_vector.begin(); std::vector<int>::const_iterator cit = int_vector.begin();These two iterators are of course interoperable: the comparison
it == citwill compile, run, and give the correct answer (true in this case). If, however, you wrap these two iterators into
any_iterators, then their interoperability is lost. For example, if you define
typedef any_iterator<int, boost::random_access_traversal_tag, int const &> random_access_const_iterator_to_int; random_access_const_iterator_to_int ait_1 = it; random_access_const_iterator_to_int ait_2 = cit;then the comparison
ait_1 == ait_2; // bad comparison!behaves as if you were comparing iterators into different sequences: the behavior is undefined! (In my implementation, you will get an assertion in debug mode and a null pointer dereferencing in release mode.)
This behavior is most certainly highly undesirable and extremely dangerous. In fact, it is so bad
that I had at one point decided to declare the idea of the
But then it occurred to me that this pitfall is not entirely specific to the
It occurs with any type-erasing class that implements binary operators. Therefore, it is perhaps
beneficial to put all this out there and alert people to the problem.
Acknowledgment: I believe the first person to spot this problem with interoperability was Thomas Witt. The issue was pointed out to me independently by Sergei Politov.
any_iteratoris one level of indirection and a virtual function call. Construction and destruction of an
any_iteratorobject involve one heap access each.
any_iteratorclass template are Standard conforming iterators. Therefore, it would theoretically be possible to assign an object of one
any_iteratortype to a variable of another
any_iteratortype. However, this would lead to nesting levels greater than 1. Consequently, the overhead of using an
any_iteratorcould increase to several level of indirections and several virtual function calls. Therefore, assignments that would lead to nested
any_iteratorobjects are not allowed. Instead, there are certain conversions between
any_iteratortypes that behave nicely insofar as they do not cause nesting levels deeper than 1. The exact rules for these conversions are stated below.
any_iteratorobject from a "concrete" iterator is currently explicit. This is an unfortunate limitation that is caused by a technicality having to do with an arcane limitation of the SFINAE principle. This annoyance will go away once concepts will be available in C++.
For now, this means that a "concrete" iterator never converts to
any_iterator. There are only two ways to get a
"concrete" iterator object into an
either by ordinary assignment, as in
std::vector<int> vect; any_iterator<int, std::forward_iterator_tag> ait; ait = vect.begin();or using explicit construction:
std::vector<int>; any_iterator< int, std::forward_iterator_tag > ait_1(vect.begin()); // fine any_iterator< int, std::forward_iterator_tag > ait_2 = vect.begin(); // error, requires non-explicit copy ctor
any_iteratorhas been tested under Microsoft VC7.1, Microsoft VC8, Microsoft VC9, gcc 3.2.4, gcc 3.4.2, gcc 4.0.3, and gcc 4.1.2. More recent compilers and compiler versions seem to always work, probably because C++ template support has stabilized by now.
make_any_iterator_typewhich takes an iterator type as its argument and produces an instantiation of the
any_iteratorclass template with the same iterator traits. In other words, it allows you to create an
any_iteratortype "by example."
typedef make_any_iterator_type< std::vector<int>::iterator >::type ait;This has the same effect as
typedef any_iterator<int, std::random_access_iterator_tag> ait;
any_iteratorbe downloaded from here. The download contains the source code, this HTML documentation, a demo .cpp file, and regression tests.
any_iterator in the download contains the file
any_iterator.hpp and a subdirectory
detail. To use the
any_iterator.hpp and make sure the header
files in the subdirectory
detail are found
currently lives in the namespace
any_iterator makes ample use of Boost libraries; however, it uses
only header files. Therefore, no Boost binaries are needed. Just make sure that
Boost is in your include path.
If you wish to build and run the regression tests, you will find solution files for
Microsoft VC7.1 and Microsoft VC8 and a makefile for gcc in the corresponding subdirectories
of the directory
regression_tests. If you use the makefile, you will of course
have to fix the path variables to match your development environment. The Microsoft
solution files should work out of the box, except for the fact that you have to fix the include
directories so that the Boost headers are found.
some_any_iteratoris an instantiation of the
any_iteratorclass template with value type, traversal tag, reference type, and difference type equal to
AnyItDifference, respectively. Assume further that
some_iteratoris an iterator type with value type, traversal tag, reference type, and difference type equal to
ItDifference, respectively. Then a variable of type
some_any_iteratorwill accept an object of type
some_iteratorif and only if the following four conditions are met:
AnyItTraversalare equal, or the former is derived from the latter. This means that
some_iterator's traversal category is equal to or better than that of
AnyItReferenceis a reference, then so is
ItReferenceare both references, then the following is true: after stripping const qualifiers and references from
ItReference, the two are either the same, or the former is a base class of the latter.
operator*would return a reference to a temporary.
some_any_iteratoris a random access iterator, then
AnyItDifferenceare convertible to each other both ways. Here, we need convertibility in both directions because the difference type occurs as an argument type as well as a result type of iterator operators.
ait_targetbe two different instantiations of the
any_iteratorclass template. Then there is a conversion from
ait_targetif and only if either
ait_sourceis better than or equal to the traversal category of
ait_target, and all other iterator traits are exactly the same,
ait_targetis a const iterator version of