Virtual and Multi Iterators
Kevin Atkinson
--------------CE64994A70A4B27E6EA1F9A3
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Virtual and Multi Iterators
Attached are some iterator classes that I developed for my Aspell spell
checker in order to handle multiple dictionaries of different types.
The file fiterators.hh is the implementation and the file main.cc is a
small test file.
It uses a mixture of templates and virtual functions to be able to
iterate through several different iterator ranges, one after another, as
through they where one. Virtual functions are used because these
iterators are not all of the same type. For example one might be a
vector<string> and an other might be a deque<string>. However they are
all at least forward iterators and have a reference that is convertible
to a specific type (for example string).
I would be most interested in comments or suggestions any one might have
as far as style and efficacy go as I am a rather new C++ programmer.
Thanks again.
--
Kevin Atkinson
kevi...@home.com
http://metalab.unc.edu/kevina/
--------------CE64994A70A4B27E6EA1F9A3
Content-Type: text/plain; charset=us-ascii;
name="fiterators.hh"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="fiterators.hh"
//
// Copyright (c) 1999
// Kevin Atkinson
//
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without
// fee, provided that the above copyright notice appear in all copies
// and that both that copyright notice and this permission notice
// appear in supporting documentation. I make no representations
// about the suitability of this software for any purpose. It is
// provided "as is" without express or implied warranty.
//
// Enhancements and big fixes are encouraged. Although you are not
// required to submit changes back it is strongly encouraged. I can
// be reached at kevi...@home.com.
//
#ifndef fiterators___
#define fiterators___
#include <iterator>
//
// virtual_forward_iterator is an abstract base clase for a forward iterator
//
template <class Ref>
class virtual_forward_iterator {
public:
typedef Ref reference;
virtual reference dereference() const = 0;
virtual void increment() = 0;
// like operator++ but doesn't return anything
virtual virtual_forward_iterator * clone() const = 0;
// return a copy of itself allocated with new
virtual ~virtual_forward_iterator() {}
virtual bool is_equal (const virtual_forward_iterator&) const = 0;
friend bool operator== (const virtual_forward_iterator& rhs,
const virtual_forward_iterator& lhs)
{return rhs.is_equal(lhs);}
friend bool operator!= (const virtual_forward_iterator& rhs,
const virtual_forward_iterator& lhs)
{return !rhs.is_equal(lhs);}
};
//
// A valid forward iterator that inherates from add_virtual_forward_iterator
// will also become a virtual_forward_iterator
//
template <class Itr, class VirRef = iterator_traits<Itr>::reference>
class add_virtual_forward_iterator : public virtual_forward_iterator<VirRef> {
private:
typedef virtual_forward_iterator<VirRef> Base;
typedef Itr Derived;
public:
typedef VirRef virtual_reference;
bool is_equal (const Base &other) const;
// Note: other must be an Itr or else is_equal is undefined
void increment();
Base * clone() const;
virtual_reference dereference() const;
};
//
// Makes a normal forward iterator a virtual forward iterator
//
template <class Iterator,
class VirReference = iterator_traits<Iterator>::reference>
class make_virtual_forward_iterator
: public add_virtual_forward_iterator
<
make_virtual_forward_iterator<Iterator,VirReference>,
VirReference
>
{
public:
typedef forward_iterator_tag iterator_category;
typedef iterator_traits<Iterator>::value_type value_type;
typedef iterator_traits<Iterator>::difference_type difference_type;
typedef iterator_traits<Iterator>::reference reference;
typedef iterator_traits<Iterator>::pointer pointer;
private:
Iterator itr;
typedef make_virtual_forward_iterator Self;
public:
make_virtual_forward_iterator() {}
make_virtual_forward_iterator(Iterator i) : itr(i) {}
reference operator*() const {return *itr;}
Self& operator++() {++itr; return *this;}
Self operator++(int) {Self temp = *this; ++itr; return temp;}
friend bool operator==(Self rhs, Self lhs) {return rhs.itr==lhs.itr;}
friend bool operator!=(Self rhs, Self lhs) {return rhs.itr!=lhs.itr;}
};
template <class VirRef, class Itr>
make_virtual_forward_iterator<Itr, VirRef> make_virtual_forward_iteratorr(Itr i) {
return make_virtual_forward_iterator<Itr, VirRef>(i);
}
//
// virtual_forward_iterator_proxy hides the fact that you are really
// dealing with a virtual object. It behaves just like any other
// forward iterator with a few extra member functions.
//
template <class Value, class Ref = const Value &,
class Pointer = const Value *, class Difference = long>
class virtual_forward_iterator_proxy {
public:
typedef forward_iterator_tag iterator_category;
typedef Value value_type;
typedef Difference difference_type;
typedef Ref reference;
typedef Pointer pointer;
private:
typedef virtual_forward_iterator<Ref> RealItr;
typedef virtual_forward_iterator_proxy Self;
RealItr *itr;
public:
virtual_forward_iterator_proxy() {itr = 0;}
virtual_forward_iterator_proxy(const RealItr& i) {itr = i.clone();}
virtual_forward_iterator_proxy(const Self& other)
{if (other.itr) itr = other.itr->clone(); else itr = 0;}
Self& operator= (const Self& other) {
if (this != &other) {
delete itr;
if (other.itr)
itr = other.itr->clone();
else
itr = 0;
}
return *this;
}
~virtual_forward_iterator_proxy() {delete itr;}
Ref operator*() const {return itr->dereference();}
Self& operator++() {itr->increment(); return *this;}
Self operator++(int) {Self temp=*this; itr->increment(); return temp;}
const type_info & id() const {return typeid(*itr);}
friend bool operator==(const Self &lhs, const Self &rhs) {
return *lhs.itr == *rhs.itr;
}
friend bool operator!=(const Self &lhs, const Self &rhs) {
return *lhs.itr != *rhs.itr;
}
};
//
// MultiForwardIterator will iterate through the range of a series
// of iterators as if there where one iterator.
//
// MultiItr must be a Forward iterator that has a value type that is a
// class that has the members begin() & end() that return a RealItr
// RealItr must also be a forward_iterator.
//
//
template < class MultiItr,
class RealItr = typename iterator_traits<MultiItr>::value_type::const_iterator
>
class multi_forward_iterator
{
public:
typedef MultiItr outer_iterator;
typedef RealItr inner_iterator;
typedef forward_iterator_tag iterator_category;
typedef iterator_traits<RealItr>::value_type value_type;
typedef iterator_traits<RealItr>::difference_type difference_type;
typedef iterator_traits<RealItr>::pointer pointer;
typedef iterator_traits<RealItr>::reference reference;
private:
typedef multi_forward_iterator Self;
MultiItr cur;
MultiItr end;
RealItr itr;
public:
multi_forward_iterator() {}
multi_forward_iterator(MultiItr c, MultiItr e, RealItr i)
: cur(c), end(e), itr(i) {}
multi_forward_iterator(MultiItr c, MultiItr e)
: cur(c), end(e) {}
reference operator*() const {return *itr;}
Self& operator++();
Self operator++(int) {Self temp=*this; operator++(); return temp;}
friend bool operator==(const Self &lhs, const Self &rhs) {
return lhs.cur == rhs.cur && (lhs.cur == lhs.end || lhs.itr == rhs.itr);
}
friend bool operator!=(const Self &lhs, const Self &rhs) {
return !(lhs == rhs);
}
};
//
// ConstMultiForwardContainer is a forward container which simply holds
// another container of container like objects and iterates through them
// as if they where one.
//
// IteCon is a forward container whoes value type is a structure which
// has at least the following public members begin(), end(), and
// size(). begin() and end() must return forward iterators.
template <class ItrCon>
class const_multi_forward_container {
private:
public:
typedef ItrCon outer_container;
typedef typename outer_container::const_iterator outer_iterator;
typedef
typename iterator_traits<outer_iterator>::value_type::const_iterator
inner_iterator;
typedef iterator_traits<inner_iterator>::value_type value_type;
typedef typename ItrCon::value_type::size_type size_type;
typedef multi_forward_iterator<outer_iterator> const_iterator;
typedef const_iterator iterator;
static const size_type npos = -1;
private:
ItrCon itrs;
mutable size_type size_;
public:
const_multi_forward_container() {}
const_multi_forward_container(const ItrCon& c) {itrs=c;}
const_multi_forward_container& swap_in(ItrCon &c) {swap(itrs,c);}
const_multi_forward_container& copy_in(const ItrCon &c) {itrs = c;}
const_iterator begin() const;
const_iterator end() const {return const_iterator(itrs.end(), itrs.end());}
size_type size() const;
bool empty() const {return itrs.empty();}
};
template <class Itr, class Size = size_t>
struct begin_end_size {
typedef Itr iterator;
typedef Itr const_iterator;
typedef Size size_type;
Itr begin_;
Itr end_;
Size size_;
Itr begin() const {return begin_;}
Itr end() const {return end_;}
Size size() const {return size_;}
bool empty() const {return !size_;}
begin_end_size() : size_(0) {}
begin_end_size(Itr b, Itr e, Size s) : begin_(b), end_(e), size_(s) {}
};
#define ITR typename Con::const_iterator
#define ITRT iterator_traits<ITR>
template <class Con>
begin_end_size<virtual_forward_iterator_proxy<ITRT::value_type, ITRT::reference> >
make_virtual_const_begin_end_sizer(const Con& con)
{
return begin_end_size
<virtual_forward_iterator_proxy<ITRT::value_type,ITRT::reference > >
(
make_virtual_forward_iterator<ITR>(con.begin()),
make_virtual_forward_iterator<ITR>(con.end()),
con.size()
);
}
#undef ITR
#undef ITRT
template <class MultiItr, class RealItr>
multi_forward_iterator<MultiItr, RealItr>&
multi_forward_iterator<MultiItr, RealItr>::operator++() {
++itr;
if (itr == cur->end()) {
++cur;
if (cur != end)
itr = cur->begin();
}
return *this;
}
#define TL template <class Itr, class VRef>
#define SELF add_virtual_forward_iterator<Itr, VRef>
TL bool SELF::is_equal (const SELF::Base &other) const {
return *static_cast<const Itr *>(this) == *static_cast<const Itr *>(&other);
}
TL void SELF::increment() {
static_cast<Itr *>(this)->operator++();
}
TL SELF::Base * SELF::clone() const {
return new Itr(*static_cast<const Itr *>(this));
}
TL SELF::virtual_reference SELF::dereference() const {
return static_cast<const Itr *>(this)->operator*();
}
#undef TL
#undef SELF
template <class ItrCon>
const_multi_forward_container<ItrCon>::const_iterator
const_multi_forward_container<ItrCon>::begin() const {
if (itrs.begin() != itrs.end())
return const_iterator(itrs.begin(), itrs.end(), itrs.begin()->begin());
else
return end();
}
template <class ItrCon>
const_multi_forward_container<ItrCon>::size_type
const_multi_forward_container<ItrCon>::size() const {
if (size_ == npos) {
size_ = 0;
outer_iterator i = itrs.begin();
outer_iterator e = itrs.end();
for (; i != e; ++i)
size_ += i->size();
}
return size_;
}
#endif
--------------CE64994A70A4B27E6EA1F9A3
Content-Type: text/plain; charset=us-ascii;
name="main.cc"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="main.cc"
#include <algorithm>
#include <vector>
#include <list>
#include <deque>
#include "fiterators.hh"
int main() {
{
vector<vector<int> > con(4);
for (int i = 0; i != 4; ++i) con[0].push_back(1);
for (int i = 0; i != 4; ++i) con[1].push_back(2);
for (int i = 0; i != 4; ++i) con[2].push_back(3);
for (int i = 0; i != 4; ++i) con[3].push_back(4);
const_multi_forward_container<vector<vector<int> > > mcon;
mcon.swap_in(con);
copy(mcon.begin(), mcon.end(), ostream_iterator<int>(cout, " "));
cout << endl;
} {
list<int> con;
for (int i = 0; i != 4; ++i) con.push_back(i);
typedef list<int>::const_iterator Itr;
virtual_forward_iterator_proxy<int>
begin = make_virtual_forward_iterator<Itr>(con.begin());
virtual_forward_iterator_proxy<int>
end = make_virtual_forward_iterator<Itr>(con.end());
copy(begin, end, ostream_iterator<int>(cout, " "));
cout << endl;
} {
typedef
vector<begin_end_size<virtual_forward_iterator_proxy<int, const int&> > >
bes_con;
bes_con con;
vector<int> con1;
for (int i = 0; i != 4; ++i) con1.push_back(1);
list<int> con2;
for (int i = 0; i != 4; ++i) con2.push_back(2);
deque<int> con3;
for (int i = 0; i != 4; ++i) con3.push_back(3);
con.push_back(make_virtual_const_begin_end_sizer(con1));
con.push_back(make_virtual_const_begin_end_sizer(con2));
con.push_back(make_virtual_const_begin_end_sizer(con3));
const_multi_forward_container<bes_con> mcon;
mcon.swap_in(con);
copy(mcon.begin(), mcon.end(), ostream_iterator<int>(cout, " "));
cout << endl;
}
}
--------------CE64994A70A4B27E6EA1F9A3--
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
Siemel Naran
>I would be most interested in comments or suggestions any one might have
>as far as style and efficacy go as I am a rather new C++ programmer.
Please ask more specific questions.
Is this GNUWare (ie, GPL, OpenSource)?
Use shorter names. Will make code much easier to read.
In the code below, why do you use 'increment' and 'dereference'?
Why not use 'operator++' and 'operator*', both of which can be
virtual functions. Operator++ returns a "virtual_forward_iterator&".
The derived class operator++ returns a
"derived_virtual_forward_iterator&". This is called covariant
return.
Function 'is_equal' can be called 'equal' and can be protected.
If the function is public, then there is no need for friendship.
>template <class Ref>
>class virtual_forward_iterator {
>public:
> typedef Ref reference;
>
> virtual reference dereference() const = 0;
>
> virtual void increment() = 0;
> // like operator++ but doesn't return anything
>
> virtual virtual_forward_iterator * clone() const = 0;
> // return a copy of itself allocated with new
>
> virtual ~virtual_forward_iterator() {}
>
> virtual bool is_equal (const virtual_forward_iterator&) const = 0;
>
> friend bool operator== (const virtual_forward_iterator& rhs,
> const virtual_forward_iterator& lhs)
> {return rhs.is_equal(lhs);}
> friend bool operator!= (const virtual_forward_iterator& rhs,
> const virtual_forward_iterator& lhs)
> {return !rhs.is_equal(lhs);}
>};
>template <class Itr, class VirRef = iterator_traits<Itr>::reference>
>class add_virtual_forward_iterator : public virtual_forward_iterator<VirRef> {
>// Makes a normal forward iterator a virtual forward iterator
>//
>template <class Iterator,
> class VirReference = iterator_traits<Iterator>::reference>
>class make_virtual_forward_iterator
> : public add_virtual_forward_iterator
> <
> make_virtual_forward_iterator<Iterator,VirReference>,
> VirReference
> >
Why not derive this directly from "virtual_forward_iterator"?
Then override virtual_forward_iterator::operator++ and have it
call the private data member's operator++.
>template <class VirRef, class Itr>
>make_virtual_forward_iterator<Itr, VirRef>
>make_virtual_forward_iteratorr(Itr i) {
Perhaps call this "make_virtual_forward_iteratorr" and call the
class "make_virtual_forward_iterator_t". This seems to be the
convention in <functional>. Look at class mem_fun_t and function
mem_fun(...).
>template < class MultiItr,
> class RealItr = typename
> iterator_traits<MultiItr>::value_type::const_iterator
> >
>class multi_forward_iterator
>{
Interesting.
--
----------------------------------
Siemel B. Naran (sbn...@uiuc.edu)
----------------------------------
Kevin Atkinson
have
> >as far as style and efficacy go as I am a rather new C++ programmer.
>
> Is this GNUWare (ie, GPL, OpenSource)?
If you want to call it that. I think my copyright is clear.
> Use shorter names. Will make code much easier to read.
I wan't to be clear in what they do. If you can suggest shorter names
I may use them.
> In the code below, why do you use 'increment' and 'dereference'?
> Why not use 'operator++' and 'operator*', both of which can be
> virtual functions. Operator++ returns a "virtual_forward_iterator&".
> The derived class operator++ returns a
> "derived_virtual_forward_iterator&". This is called covariant
> return.
Several Reasons:
1) To allow inlining when a refrence to the derived class is used.
2) Becuase operator* may not always return the exact same type. It
could return a type that is convertable to the type dereference
returns. For example in my Aspell classes I use const char * as
the return type. Some of my iterators may return a light weight
proxy clasess which can convert to const char *, some will return
a refrence to const char *, etc..
3) To simplify matters.
>
> Function 'is_equal' can be called 'equal' and can be protected.
> If the function is public, then there is no need for friendship.
I decided to remove the friend equality operators thus is_equal must be
public.
> >// Makes a normal forward iterator a virtual forward iterator
> >//
> >template <class Iterator,
> > class VirReference = iterator_traits<Iterator>::reference>
> >class make_virtual_forward_iterator
> > : public add_virtual_forward_iterator
> > <
> > make_virtual_forward_iterator<Iterator,VirReference>,
> > VirReference
> > >
>
> Why not derive this directly from "virtual_forward_iterator"?
> Then override virtual_forward_iterator::operator++ and have it
> call the private data member's operator++.
I have the add_virtual_forward_iterator class so that other iterators
can derive from it if they so desire. Since I have it, I might as well
use it.
>
> >template <class VirRef, class Itr>
> >make_virtual_forward_iterator<Itr, VirRef>
> >make_virtual_forward_iteratorr(Itr i) {
>
> Perhaps call this "make_virtual_forward_iteratorr" and call the
> class "make_virtual_forward_iterator_t". This seems to be the
> convention in <functional>. Look at class mem_fun_t and function
> mem_fun(...).
Thanks, I think I will do that.
> >template < class MultiItr,
> > class RealItr = typename
> >
iterator_traits<MultiItr>::value_type::const_iterator
> > >
> >class multi_forward_iterator
> >{
>
> Interesting.
By that you mean...
--
Kevin Atkinson
kevi...@home.com
http://metalab.unc.edu/kevina/
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Siemel Naran
>> Is this GNUWare (ie, GPL, OpenSource)?
>If you want to call it that. I think my copyright is clear.
>I wan't to be clear in what they do. If you can suggest shorter names
>I may use them.
namespace myspace
{
namespace PolymorphicIterators // got something shorter?
{
class ForwardIter; // like your virtual_forward_iterator
}
}
Clients can use typedefs, 'using' declarations, namespace aliases,
and 'using' directives to simplify their code.
>> In the code below, why do you use 'increment' and 'dereference'?
>> Why not use 'operator++' and 'operator*', both of which can be
>> virtual functions. Operator++ returns a "virtual_forward_iterator&".
>> The derived class operator++ returns a
>> "derived_virtual_forward_iterator&". This is called covariant
>> return.
>
>Several Reasons:
>
>1) To allow inlining when a refrence to the derived class is used.
>2) Becuase operator* may not always return the exact same type. It
> could return a type that is convertable to the type dereference
> returns. For example in my Aspell classes I use const char * as
> the return type. Some of my iterators may return a light weight
> proxy clasess which can convert to const char *, some will return
> a refrence to const char *, etc..
>3) To simplify matters.
Clients expect iterators to have op* and op++, which is the main
reason to make these functions.
>1) To allow inlining when a refrence to the derived class is used.
However, in these cases we probably use pass by value. When calling
a virtual function on an object, as opposed to a pointer or reference,
the virtual function mechanism is not used. Technically, it is an
optimization that your compiler may or may not do. Eg,
void f(Derived d) {
d.virtualfunction(); // no need for virtual function mechanism
}
void f(const Derived& d) {
d.virtualfunction(); // virtual function mechanism used
}
void f(Derived const * d) {
d->virtualfunction(); // virtual function mechanism used
}
Functions like for_each and so on receive their arguments by
value. So if you say
for_each(DerivedIter(),DerivedIter(),Pred());
then for_each<Iter,Predicate> is called with Iter==DerivedIter
and Predicate==Pred, and the iterators are passed by value. So
provided you have a good optimizer, there is no runtime penalty.
Since clients expect your iterator to have operator++, operator*,
you might as well define them. Functions like for_each and so
on rely on these.
Moreover, what happens when you do this?
void f(BaseIter& begin, const BaseIter& end) {
for_each(begin,end,Action());
}
Guess which function is called?
The answer is
for_each<Iter,Pred>(Iter begin, Iter end, Pred)
with Iter==BaseIter and Pred==Action
As the for_each function employs pass by value, there will be a call to
BaseIter::BaseIter(const BaseIter&);
to copy 'begin' and 'end'. That is, the derived part is sliced
off! Anyway, since class BaseIter is abstract, the call to for_each
should fail anyway.
So the solution is to make a non-polymorphic class PolyIter
(short for PolymorphicIterator) that contains your polymorphic
BaseIter class as a private data member. Clients will use
class PolyIter directly, as when they call for_each, so they
expect operator++ operator* and so on. The implementation of
PolyIter::operator++() can call the internal object's virtual
'increment' function.
>2) Becuase operator* may not always return the exact same type. It
> could return a type that is convertable to the type dereference
> returns. For example in my Aspell classes I use const char * as
> the return type. Some of my iterators may return a light weight
> proxy clasess which can convert to const char *, some will return
> a refrence to const char *, etc..
Good reason.
4)
Virtual operators look strange to me, but that's my bias. Virtual
operators that return values usually complicate maintainance, but
virtual operators that return references need not.
>> Function 'is_equal' can be called 'equal' and can be protected.
>> If the function is public, then there is no need for friendship.
>
>I decided to remove the friend equality operators thus is_equal must be
>public.
Fine. It's usually a good choice, but why did you do this?
>> Why not derive this directly from "virtual_forward_iterator"?
>> Then override virtual_forward_iterator::operator++ and have it
>> call the private data member's operator++.
>
>I have the add_virtual_forward_iterator class so that other iterators
>can derive from it if they so desire. Since I have it, I might as well
>use it.
Nope, not a good reason. It confused me when I was reading your
code, so it will probably confuse others. Just because the class
is there doesn't mean you should use it.
Perhaps class PolyIter can contain a BaseIter* as a data member.
The destructor of PolyIter deletes the iterator; the copy
constructor clones it. Assuming BaseIter::increment() is
virtual and there is no BaseIter::operator++(), then
PolyIter::operator++() can call BaseIter::increment().
Perhaps make BaseIter::increment() private? It might not be
a good design choice, but at least think about it. My reason
is that clients of DerivedIter should ideally deal with the
smallest, most minimal interface possible. So there should
either be op++ or increment, but not both.
>> >template < class MultiItr,
>> > class RealItr = typename
>> >
>iterator_traits<MultiItr>::value_type::const_iterator
>> > >
>> >class multi_forward_iterator
>> >{
>>
>> Interesting.
>
>By that you mean...
I didn't read it fully, but it's a neat idea. Say you want to
iterate through a 3d matrix, you have a multi-iterator that
contains a multi-iterator and an iterator. This mult-iterator
contains two iterators. Is this right?
--
----------------------------------
Siemel B. Naran (sbn...@uiuc.edu)
----------------------------------
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Kevin Atkinson
>
> On 18 Jan 1999 14:11:55 -0500, Kevin Atkinson <kevi...@home.com> wrote:
>
> >> Is this GNUWare (ie, GPL, OpenSource)?
> >If you want to call it that. I think my copyright is clear.
> Didn't see the word "GPL" or "OpenSource" anywhere there.
>
> >I wan't to be clear in what they do. If you can suggest shorter names
> >I may use them.
>
> Clients can use typedefs, 'using' declarations, namespace aliases,
> and 'using' directives to simplify their code.
>
I might do that.
> >> In the code below, why do you use 'increment' and 'dereference'?
> >> Why not use 'operator++' and 'operator*', both of which can be
> > [...]
> >
> >3) To simplify matters.
>
> Clients expect iterators to have op* and op++, which is the main
> reason to make these functions.
Except that also clients expect real iterators the virtual iterator is
not a real iterator. Also for it to be a real forward iterator
op++(int) must be defined. This is of course next to impossible.
> >1) To allow inlining when a refrence to the derived class is used.
>
> However, in these cases we probably use pass by value. When calling
> a virtual function on an object, as opposed to a pointer or reference,
> the virtual function mechanism is not used. Technically, it is an
> optimization that your compiler may or may not do. Eg,
> [...Example...]
Yes I know that.
> Since clients expect your iterator to have operator++, operator*,
> you might as well define them. Functions like for_each and so
> on rely on these.
I never said that the derived classes should not define them.
>
> Moreover, what happens when you do this?
> void f(BaseIter& begin, const BaseIter& end) {
> for_each(begin,end,Action());
> }
> Guess which function is called?
>
> The answer is
> for_each<Iter,Pred>(Iter begin, Iter end, Pred)
> with Iter==BaseIter and Pred==Action
> As the for_each function employs pass by value, there will be a call to
> BaseIter::BaseIter(const BaseIter&);
> to copy 'begin' and 'end'. That is, the derived part is sliced
> off! Anyway, since class BaseIter is abstract, the call to for_each
> should fail anyway.
>
> So the solution is to make a non-polymorphic class PolyIter
> (short for PolymorphicIterator) that contains your polymorphic
> BaseIter class as a private data member. Clients will use
> class PolyIter directly, as when they call for_each, so they
> expect operator++ operator* and so on. The implementation of
> PolyIter::operator++() can call the internal object's virtual
> 'increment' function.
Is that not what I already do with the virtual_forward_iterator_proxy
and the multi_forward_iterator classes?
>
> >2) Becuase operator* may not always return the exact same type. It
> > could return a type that is convertable to the type dereference
> > returns. For example in my Aspell classes I use const char * as
> > the return type. Some of my iterators may return a light weight
> > proxy clasess which can convert to const char *, some will return
> > a refrence to const char *, etc..
>
> Good reason.
And sense I have deference instead of operator() for consistency I also
use increment and is_equal instead of the equilvent operators.
> 4)
> Virtual operators look strange to me, but that's my bias. Virtual
> operators that return values usually complicate maintainance, but
> virtual operators that return references need not.
5) To emphases the fact that this is a virtual iterator and not a real
iterator. Thus it should not every be treated like a real iterator. If
the client wants to treat the virtual_iterator as a real iterator then
it should use the provided virtual_forward_iterator_proxy class.
> >> Function 'is_equal' can be called 'equal' and can be protected.
> >> If the function is public, then there is no need for friendship.
> >
> >I decided to remove the friend equality operators thus is_equal must be
> >public.
>
> Fine. It's usually a good choice, but why did you do this?
See reason number 5 above.
>
> >> Why not derive this directly from "virtual_forward_iterator"?
> >> Then override virtual_forward_iterator::operator++ and have it
> >> call the private data member's operator++.
> >
> >I have the add_virtual_forward_iterator class so that other iterators
> >can derive from it if they so desire. Since I have it, I might as well
> >use it.
>
> Nope, not a good reason. It confused me when I was reading your
> code, so it will probably confuse others. Just because the class
> is there doesn't mean you should use it.
Here I disagree with you. I think you should always reuse code when
possible. This way if I make a change in the
add_virtual_forward_iterator the change also caries over to the
make_virtual_forward_iterator class. Is code reuse not one of the
underlying principles behind the design of almost all modern languages
(from C functions to smalltalks class to C++ STL?).
> Perhaps make BaseIter::increment() private? It might not be
> a good design choice, but at least think about it. My reason
> is that clients of DerivedIter should ideally deal with the
> smallest, most minimal interface possible. So there should
> either be op++ or increment, but not both.
No it is not a good design choice because I would have to declare ALL
classes that contain BaseIter as friends.
> >> >class multi_forward_iterator
> >> Interesting.
> >By that you mean...
>
> I didn't read it fully, but it's a neat idea. Say you want to
> iterate through a 3d matrix, you have a multi-iterator that
> contains a multi-iterator and an iterator. This mult-iterator
> contains two iterators. Is this right?
That is the basic idea among other things.
--
Kevin Atkinson
kevi...@home.com
http://metalab.unc.edu/kevina/
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Don Bashford
and it works with nesting to arbitrary depth, while I think your
approach is only for one level of nesting. On the other hand, it
assumes that you don't strictly need iterators, but that a way to make
function templates like for_each or copy is sufficient.
Scheme, like all Lisp variants, has what are essentially linked lists
which can contain arbitrary objects, including other lists. (I'm
ignoring the existence of other sequence types, like vectors, in
Scheme.) So if one makes the definition:
(define input-s '(1 2 (3 4) 5 (6 (7 8) 9) 10))
then input-s is a structure with up to three levels of nesting.
Suppose we want to apply a function, f, recursively to every item in
the this structure. More generally, we want a function,
recursive-apply, that takes an arbitrarily nested list structure, s,
and a function, f, as its arguments and applies f to every element
within s. The solution can be expressed recursively: if s is empty,
return; otherwise, if the first element of s (the "car" of s, in Lisp
terms) is itself a list, call recursive-apply on it; otherwise it must
be an "item" so call f on it; whether (car s) is a list or not, we
should then call recursive-apply on the remainder of s (the "cdr" of
s). In Scheme this is expressed:
(define (recursive-apply s f)
(if (null? s)
'()
(begin
(if (list? (car s))
(recursive-apply (car s) f)
(f (car s)))
(recursive-apply (cdr s) f))))
With the above definitions, doing
(recursive-apply input-s (lambda (x) (write x) (newline)))
prints out the numbers one through 10.
So how to do this in C++? The problem is that we don't have any
direct equivalent of (list? x), a run-time method of asking an object
whether it is one of the standard containers. The C++ code below
adopts the strategy of getting the compiler's template instantiation
to some recursive descent for us. It relies on fact that the C++ type
system and the standard containers don't really allow for different
types of objects to be stored in the same container object, therefore
although the nesting can be arbitrarily deep, the depth must be
uniform, and the nesting must be fixed at compile time. In other
words, we can have the C++ equivalent of:
(((1)(2))((3)(4)) ;; list< list< list<int> > >
but not
(((1)(2)) (3 4) ) ;; list< list< list<int> > > or list< list<int> > ?
So here is the C++ solution (about 25 lines of actual code):
// ----------------------
template <class Valtype> // see below
void recurse_or_do(Valtype& x, void (*f) (Valtype));
template <class Valtype, class Container> // see below
void recurse_or_do(Container c, void (*f) (Valtype));
// The C++ equivalent of my Scheme recursive-apply function
// Applies f to the Valtype items between the Iters first
// and last, descending recursively into containers if the Iters
// point to containers.
template <class Valtype, class Iter>
void recursive_for_each(Iter first, Iter last, void (*f) (Valtype))
{
if (first == last) { // equivalent of Scheme (if (null? s) '()
;
}
else {
// recurse_or_do is equivalent Scheme (if (list? (car s))
// (recursive-apply (car s) f)
// (f (car s)) )
recurse_or_do<Valtype> (*first, f);
// below, equiv of Scheme (recursive-apply (cdr s) f)
recursive_for_each<Valtype>(++first, last, f);
}
}
// recurse_or_do should apply the function f to its first argument
// if it is of type, Valtype, or call recursive_for_each on it, if
// it is a container. Define a function template corresponding to
// each of these branches, and let compiler's template instantiation
// choose between them.
template <class Valtype>
void recurse_or_do(Valtype& x, void (*f) (Valtype))
// Since type of x matches type expected by f, apply f to x
{
f(x);
}
template <class Valtype, class Container>
void recurse_or_do(Container c, void (*f) (Valtype))
// Type of c doesn't match type expected by f, so assume it is a container
{
recursive_for_each<Valtype>(c.begin(), c.end(), f);
}
// --------- THAT'S IT!
// NOW SOME TESTS. FIRST A FUNCTION TO APPLY
#include<iostream>
void print(int i)
{
cout << i << endl;
}
// TRY IT WITH A LIST OF LISTS OF INTS
#include<list>
void f()
{
list< list<int> > cc;
list<int> c;
c.push_back(1);
c.push_back(2);
c.push_back(3);
cc.push_back(c);
c.clear();
c.push_back(4);
c.push_back(5);
c.push_back(6);
cc.push_back(c);
c.clear();
c.push_back(7);
c.push_back(8);
c.push_back(9);
c.push_back(10);
cc.push_back(c);
recursive_for_each<int> (cc.begin(), cc.end(), print);
}
// TRY IT WITH A VECTOR OF LISTS OF VECTORS OF INTS
#include<vector>
void g()
{
// (((1)(2))((3)(4)))
vector< list< vector<int> > > vlv;
list< vector<int> > lv;
lv.push_back( vector<int>(size_t(1), int(1)) );
lv.push_back( vector<int>(size_t(1), int(2)) );
vlv.push_back(lv);
lv.clear();
lv.push_back( vector<int>(size_t(1), int(3)) );
lv.push_back( vector<int>(size_t(1), int(4)) );
vlv.push_back(lv);
recursive_for_each<int> (vlv.begin(), vlv.end(), print);
}
main()
{
f();
g();
}
// --------------------------
Note that in the above, I'm assuming that we are dealing strictly with
items, containers of items, containers of containers, and so forth,
and NOT containers of polymorphic pointers. In the latter case, a
completely different approach based on either virtual function
mechanisms or RTTI could be used. I think that some of the complexity
of Kevin's solution was because it dealt with a blend of these two
situations.
Thanks Kevin, for an interesting problem,
Don Bashford
Assoc. Prof.
Mol. Biol.
Scripps Research Institute
bash...@scripps.edu
Kevin Atkinson
>
> Here is an approach (in C++) inspired by Scheme. It is much simpler,
> and it works with nesting to arbitrary depth, while I think your
> approach is only for one level of nesting.
Well you can nest more than one level by having a multi iterator of
multi iterators.
> On the other hand, it
> assumes that you don't strictly need iterators, but that a way to make
> function templates like for_each or copy is sufficient.
>
Yes it does. The problem I solved was to have an iterator that will
iterator through several different containers as if they where one. The
fact that the iterator is actually going through several different
containers is 100% transparent to the end user.
If all you want to do is just iterate through all elements of a nested
container then you approach is far simpler.