Hi.
Let me introduce an iterator to you, the so-called "Abstract Iterator"
I developed the other day.
I actually have no idea if there's another "Abstract Iterator" out
there, as I have never looked for one on the net (I did browse the
boost library though). It doesn't matter right now, anyway.
To put it simply, Abstract Iterator is mainly a wrapper class. It helps
you implement some design decisions (though they are not many) you
couldn't implement otherwise. Here's a good example:
Let's say you are designing a database or something similar. Databases
have tables. You want those tables to be as flexible as possible - each
one with a different implementation. You design tables implemented with
std::vector, std::list and so on. There is, of course, an abstract data
type named 'Table'. You finally end up having this:
template<class Typeclass Table
{
public:
typedef Type value_type;
typedef ?? iterator;
typedef ?? const_iterator;
virtual void insert(iterator where,value_type const&)=0;
virtual void erase(iterator where)=0;
virtual void erase(iterator a,iterator b)=0;
virtual void clear()=0;
virtual std::size_t size() const=0;
virtual std::size_t max_size() const=0;
virtual iterator begin()=0;
virtual const_iterator begin() const=0;
virtual iterator end()=0;
virtual const_iterator end() const=0;
virtual ~Table() {}
};
template<class Typeclass Vector_table:
public Table<Type>
{
public:
typedef Type value_type;
typedef ?? iterator;
typedef ?? const_iterator;
void insert(iterator,value_type const&);
void erase(iterator);
void erase(iterator,iterator);
void clear();
std::size_t size() const;
std::size_t max_size() const;
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
private:
std::vector<value_type c;
};
template<class Typeclass List_table:
public Table<Type>
{
public:
typedef Type value_type;
typedef ?? iterator;
typedef ?? const_iterator;
void insert(iterator,value_type const&);
void erase(iterator);
void erase(iterator,iterator);
void clear();
std::size_t size() const;
std::size_t max_size() const;
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
private:
std::list<value_typec;
};
I have no idea how it was implemented, but I saw this option in
MySQL/Apache where you can choose a specific implementation for each
table at any time. I did not saw such an option in MS Access.
Anyway, we want to have the same nice flexibilty. We can't, though. As
you see, each derivation uses a different iterator. List_table uses
std::list<Type>::iterator and Vector_table std::vector<Type>::iterater.
To make a function (like begin()) in a derivation virtual, it needs to
have an identical signature as the base class' function. That's not
possible with all those different iterators, though.
Giving all these iterators an identical interface & name should do the
trick. Let's call it abstract iterator, as it is some kind of
'abstract' (nobody cares what it is called anyway). And let's fill the
gap:
template<class Typeclass Table
{
public:
typedef Type value_type;
typedef abstract_iterator<value_typeiterator;
typedef const_abstract_iterator<value_typeconst_iterator;
...
};
template<class Typeclass Vector_table: public Table<Type>
{
public:
typedef Type value_type;
typedef abstract_iterator<value_typeiterator;
typedef const_abstract_iterator<value_typeconst_iterator;
...
};
template<class Typeclass List_table: public Table<Type>
{
public:
typedef Type value_type;
typedef abstract_iterator<value_typeiterator;
typedef const_abstract_iterator<value_typeconst_iterator;
...
};
That's all.
The Abstract Iterator can be used like this:
std::vector<intvec;
vec.push_back(3);
abstract_iterator<intai = vec.begin();
std::cout<<*ai<<std::endl;
std::list<intli;
li.push_back(4);
ai = li.begin(); // ai is still the same object
std::cout<<*ai;
You may implement the begin() method like this:
// Please note: The type of Vector_table<Type>::iterator is a typedef
to
// an abstract_iterator<Type>
// c is an object of std::vector<Type>
template<class TypeVector_table<Type>::iterator
Vector_table<Type>::begin()
{
return c.begin();
}
This convenience of wrapping any* iterator is not free of charge. The
Abstract Iterator is implemented using the Handle/Body idiom. Once the
Abstract Iterator wraps an iterator, that iterator can't be retrieved
anymore. _Unless_ you know its type:
// Please note: 'iterator' is a type of abstract_iterator<Type>, which
wraps
// another std::vector<Type>::iterator.
template<class Typevoid Vector_table<Type>::erase(iterator where)
{
// We know what type 'where' is wrapping, as it is
// us doing the implementation of Vector_table.
c.erase(where.unwrap<std::vector<value_type>::iter ator>());
}
If the programmer happens to unwrap the wrong type, an exception will
be thrown.
Abstract Iterator has a fairly small interface in the first place. This
is what the public interface looks like:
template<class Typeclass abstract_iterator:
public std::iterator<std::bidirectional_iterator_tag,Type >
{
public:
typedef Type value_type;
typedef Type& reference;
typedef Type const& const_reference;
typedef Type* pointer;
typedef Type const* const_pointer;
abstract_iterator();
abstract_iterator(abstract_iterator<value_typecons t&);
template<class Iteratorabstract_iterator(Iterator const&);
~abstract_iterator();
template<class Iteratorabstract_iterator<value_type>&
operator=(Iterator const&);
abstract_iterator<value_type>&
operator=(abstract_iterator <value_typeconst&);
reference operator*();
const_reference operator*() const;
pointer operator->();
const_pointer operator->() const;
abstract_iterator& operator++();
abstract_iterator operator++(int);
abstract_iterator& operator--();
abstract_iterator operator--(int);
bool operator==(abstract_iterator<value_typeconst&) const;
bool operator==(const_abstract_iterator<value_typeconst &) const;
bool operator!=(abstract_iterator<value_typeconst&) const;
bool operator!=(const_abstract_iterator<value_typeconst &) const;
template<class Wrapped_iterator>
Wrapped_iterator& unwrap(); // might throw
template<class Wrapped_iterator>
Wrapped_iterator const& unwrap() const; // might throw
};
There is also a constant version called const_abstract_iterator that
has almost the same public interface and, as the name suggests, a
stricter usage.
* Requirements of the wrapped type:
Whatever you wrap within an Abstract Iterator, make sure its public
interface supports the following operators:
operator*
operator->
operator++ (only the prefix operator is needed)
operator-- (only the prefix operator is needed)
More is not required.
It doesn't matter whether your type implements an operator== and/or an
operator!= method, as they are not needed by the Abstract Iterator.
Though the Abstract Iterator itself does provide both of these
comparison operations, the comparison is done in a different way and
does not require these operators from the wrapped type.
The wrapped type must be default constructable.
The wrapped type must be copyable.
You also need to switch on the RTTI compiler option.
********
There's a minor problem with the unwrap function of the
const_abstract_iterator right now. Technically, it is possible to wrap
both a non-const iterator and a const_iterator within a
const_abstract_iterator. It doesn't matter which type it is. _But_ it
does matter when it comes to unwrapping a iterator. Which one is
wrapped? You can either unwrap a non-const or an const_iterator, but
not both.
Principally, it should be possible to backtrack the actual type, I
think. But there might be some pitfalls that won't be allowing you to
do that. This problem needs to be fixed sooner or later.
********
So what do you think?
********
Here's the code anyway (from "abstract_iterator.h"; may contain some
bugs; not the final version):
// RTTI is required.
#include <iterator>
#include <cassert>
#include <stdexcept>
class bad_ai_conversion: public std::exception
{
public:
bad_ai_conversion(): std::exception("abstract iterator conversion
failed")
{
}
};
template<class Typeclass const_abstract_iterator_base
{
public:
typedef Type value_type;
typedef const Type& const_reference;
typedef const Type* const_pointer;
virtual const_reference operator*() const=0;
virtual const_pointer operator->() const=0;
virtual const_abstract_iterator_base<value_type>& operator--()=0;
virtual const_abstract_iterator_base<value_type>& operator++()=0;
virtual void const* get_value_address() const=0;
virtual const_abstract_iterator_base* factory() const=0;
virtual ~const_abstract_iterator_base() {}
};
template<class Typeclass abstract_iterator_base:
public const_abstract_iterator_base<Type>
{
public:
typedef Type value_type;
typedef Type& reference;
typedef Type* pointer;
using const_abstract_iterator_base<value_type>::operator *;
virtual reference operator*()=0;
using const_abstract_iterator_base<value_type>::operator->;
virtual pointer operator->()=0;
};
template<class Type, class Iteratorclass
const_abstract_iterator_impl:
public const_abstract_iterator_base<Type>
{
Iterator it;
public:
typedef Type value_type;
typedef Iterator iterator_type;
typedef const Type& const_reference;
typedef const Type* const_pointer;
const_abstract_iterator_impl(iterator_type const& ref)
:it(ref)
{
}
const_abstract_iterator_impl(const_abstract_iterat or_impl<value_type,iterator_type>
const& aii)
:it(aii.it)
{
}
const_abstract_iterator_impl<value_type,iterator_t ype>& operator=
(const_abstract_iterator_impl<value_type,iterator_ typeconst&
aii)
{
it=aii.it;
}
const_reference operator*() const
{
return it.operator*();
}
const_pointer operator->() const
{
return it.operator->();
}
const_abstract_iterator_base<value_type>& operator--()
{
--it;
return *this;
}
const_abstract_iterator_base<value_type>& operator++()
{
++it;
return *this;
}
void const* get_value_address() const
{
return &*it;
}
const_abstract_iterator_base<value_type>* factory() const
{
return new
const_abstract_iterator_impl<value_type,iterator_t ype>(*this);
}
Iterator& get_iterator()
{
return it;
}
Iterator const& get_iterator() const
{
return it;
}
};
template<class Type, class Iteratorclass abstract_iterator_impl:
public abstract_iterator_base<Type>
{
Iterator it;
public:
typedef Type value_type;
typedef Iterator iterator_type;
typedef Type& reference;
typedef const Type& const_reference;
typedef Type* pointer;
typedef const Type* const_pointer;
abstract_iterator_impl(iterator_type const& ref)
:it(ref)
{
}
abstract_iterator_impl(abstract_iterator_impl<valu e_type,iterator_type>
const& aii)
:it(aii.it)
{
}
abstract_iterator_impl<value_type,iterator_type>& operator=
(abstract_iterator_impl<value_type,iterator_typeco nst& aii)
{
it=aii.it;
}
reference operator*()
{
return it.operator*();
}
const_reference operator*() const
{
return it.operator*();
}
pointer operator->()
{
return it.operator->();
}
const_pointer operator->() const
{
return it.operator->();
}
abstract_iterator_base<value_type>& operator--()
{
--it;
return *this;
}
abstract_iterator_base<value_type>& operator++()
{
++it;
return *this;
}
void const* get_value_address() const
{
return &*it;
}
abstract_iterator_base<value_type>* factory() const
{
return new
abstract_iterator_impl<value_type,iterator_type>(* this);
}
Iterator& get_iterator()
{
return it;
}
Iterator const& get_iterator() const
{
return it;
}
};
template<class Typeclass abstract_iterator;
template<class Typeclass const_abstract_iterator
//:public std::iterator<std::bidirectional_iterator_tag,Type >
{
public:
typedef Type value_type;
typedef const Type& const_reference;
typedef const Type* const_pointer;
const_abstract_iterator()
:base(0)
{
}
template<class Iteratorconst_abstract_iterator(Iterator const&
it)
:base(new const_abstract_iterator_impl<typename
Iterator::value_type,Iterator>(it))
{
}
const_abstract_iterator(const_abstract_iterator<va lue_typeconst&
ai)
{
assert(ai.base);
base=ai.base->factory();
}
const_abstract_iterator(abstract_iterator<value_ty peconst&); //
See below for implementation
~const_abstract_iterator()
{
delete base;
}
template<class Iteratorconst_abstract_iterator<value_type>&
operator=(Iterator const& it)
{
delete base;
base=new const_abstract_iterator_impl<typename
Iterator::value_type,Iterator>(it);
return *this;
}
const_abstract_iterator<value_type>&
operator=(const_abstract_iterator<value_typeconst& ai)
{
if(this==&ai)
return *this;
delete base;
base=ai.base->factory();
return *this;
}
const_abstract_iterator<value_type>&
operator=(abstract_iterator<value_typeconst&);
// See below for implementation
const_reference operator*() const
{
assert(base);
return base->operator*();
}
const_pointer operator->() const
{
assert(base);
return base->operator->();
}
const_abstract_iterator& operator++()
{
assert(base);
base->operator++();
return *this;
}
const_abstract_iterator operator++(int)
{
assert(base);
const_abstract_iterator temp(*this);
base->operator++();
return temp;
}
const_abstract_iterator& operator--()
{
assert(base);
base->operator--();
return *this;
}
const_abstract_iterator operator--(int)
{
assert(base);
const_abstract_iterator temp(*this);
base->operator--();
return temp;
}
bool operator==(const_abstract_iterator<value_typeconst & rhs)
const
{
assert(base);
assert(rhs.base);
return
base->get_value_address()==rhs.base->get_value_address();
}
bool operator!=(const_abstract_iterator<value_typeconst & rhs)
const
{
assert(base);
assert(rhs.base);
return
base->get_value_address()!=rhs.base->get_value_address();
}
bool operator==(abstract_iterator<value_typeconst&) const; // See
below for implementation
bool operator!=(abstract_iterator<value_typeconst&) const; // See
below for implementation
template<class Wrapped_iteratorWrapped_iterator& unwrap()
{
try
{
const_abstract_iterator_impl<value_type,Wrapped_it erator>&
impl=
dynamic_cast<const_abstract_iterator_impl<value_ty pe,Wrapped_iterator>&>(*base);
return impl.get_iterator();
}
catch(std::bad_cast)
{
throw bad_ai_conversion();
}
}
template<class Wrapped_iteratorWrapped_iterator const& unwrap()
const
{
try
{
const_abstract_iterator_impl<value_type,Wrapped_it erator>
const& impl=
dynamic_cast<const_abstract_iterator_impl<value_ty pe,Wrapped_iterator>
const&>(*base);
return impl.get_iterator();
}
catch(std::bad_cast)
{
throw bad_ai_conversion();
}
}
private:
const_abstract_iterator_base<value_type>* base;
template<class Tfriend class abstract_iterator;
};
template<class Typeclass abstract_iterator
//:public std::iterator<std::bidirectional_iterator_tag,Type >
{
public:
typedef Type value_type;
typedef Type& reference;
typedef const Type& const_reference;
typedef Type* pointer;
typedef const Type* const_pointer;
abstract_iterator()
:base(0)
{
}
template<class Iteratorabstract_iterator(Iterator const& it)
:base(new abstract_iterator_impl<typename
Iterator::value_type,Iterator>(it))
{
}
abstract_iterator(abstract_iterator<value_typecons t& ai)
{
assert(ai.base);
base=static_cast<abstract_iterator_base<value_type >*>(ai.base->factory());
}
~abstract_iterator()
{
delete base;
}
template<class Iteratorabstract_iterator<value_type>&
operator=(Iterator const& it)
{
delete base;
base=new abstract_iterator_impl<typename
Iterator::value_type,Iterator>(it);
return *this;
}
abstract_iterator<value_type>&
operator=(abstract_iterator<value_typeconst& ai)
{
if(this==&ai)
return *this;
delete base;
base=static_cast<abstract_iterator_base<value_type >*>(ai.base->factory());
return *this;
}
reference operator*()
{
assert(base);
return base->operator*();
}
const_reference operator*() const
{
assert(base);
return base->operator*();
}
pointer operator->()
{
assert(base);
return base->operator->();
}
const_pointer operator->() const
{
assert(base);
return base->operator->();
}
abstract_iterator& operator++()
{
assert(base);
base->operator++();
return *this;
}
abstract_iterator operator++(int)
{
assert(base);
abstract_iterator temp(*this);
base->operator++();
return temp;
}
abstract_iterator& operator--()
{
assert(base);
base->operator--();
return *this;
}
abstract_iterator operator--(int)
{
assert(base);
abstract_iterator temp(*this);
base->operator--();
return temp;
}
bool operator==(abstract_iterator<value_typeconst& rhs) const
{
assert(base);
assert(rhs.base);
return
base->get_value_address()==rhs.base->get_value_address();
}
bool operator!=(abstract_iterator<value_typeconst& rhs) const
{
assert(base);
assert(rhs.base);
return
!(base->get_value_address()==rhs.base->get_value_address());
}
bool operator==(const_abstract_iterator<value_typeconst & rhs)
const
{
assert(base);
assert(rhs.base);
return
base->get_value_address()==rhs.base->get_value_address();
}
bool operator!=(const_abstract_iterator<value_typeconst & rhs)
const
{
assert(base);
assert(rhs.base);
return
!(base->get_value_address()==rhs.base->get_value_address());
}
template<class Wrapped_iteratorWrapped_iterator& unwrap()
{
try
{
abstract_iterator_impl<value_type,Wrapped_iterator >& impl=
dynamic_cast<abstract_iterator_impl<value_type,Wra pped_iterator>&>(*base);
return impl.get_iterator();
}
catch(std::bad_cast)
{
throw bad_ai_conversion();
}
}
template<class Wrapped_iteratorWrapped_iterator const& unwrap()
const
{
try
{
abstract_iterator_impl<value_type,Wrapped_iterator const&
impl=
dynamic_cast<abstract_iterator_impl<value_type,Wra pped_iterator>
const&>(*base);
return impl.get_iterator();
}
catch(std::bad_cast)
{
throw bad_ai_conversion();
}
}
private:
abstract_iterator_base<value_type>* base;
abstract_iterator(const_abstract_iterator<value_ty peconst&);
abstract_iterator& operator=(const_abstract_iterator<value_type>
const&);
template<class Tfriend class const_abstract_iterator;
};
template<class Typeinline const_abstract_iterator<Type>::
const_abstract_iterator(abstract_iterator<value_ty peconst& ai)
{
assert(ai.base);
base=ai.base->factory();
}
template<class Typeinline const_abstract_iterator<Type>&
const_abstract_iterator<Type>::operator=(abstract_ iterator<value_type>
const& rhs)
{
assert(rhs.base);
delete base;
base=rhs.base->factory();
return *this;
}
template<class Typeinline bool const_abstract_iterator<Type>::
operator==(abstract_iterator<value_typeconst& rhs) const
{
assert(base);
assert(rhs.base);
return base->get_value_address()==rhs.base->get_value_address();
}
template<class Typeinline bool const_abstract_iterator<Type>::
operator!=(abstract_iterator<value_typeconst& rhs) const
{
assert(base);
assert(rhs.base);
return base->get_value_address()!=rhs.base->get_value_address();
}
// Comparison operations for non-abstract iterators:
template <class Another_iterator, class Typeinline bool
operator==(Another_iterator const& lhs, abstract_iterator<Typeconst&
rhs)
{
// It is safer to make rhs a const_abstract_iterator rather than a
non-const one,
// for rhs may be a const iterator itself.
const_abstract_iterator<Typetemp(lhs);
return temp==rhs;
}
template <class Another_iterator, class Typeinline bool
operator==(abstract_iterator<Typeconst& lhs, Another_iterator const&
rhs)
{
const_abstract_iterator<Typetemp(rhs);
return lhs==temp;
}
template <class Another_iterator, class Typeinline bool
operator!=(Another_iterator const& lhs, abstract_iterator<Typeconst&
rhs)
{
const_abstract_iterator<Typetemp(lhs);
return temp!=rhs;
}
template <class Another_iterator, class Typeinline bool
operator!=(abstract_iterator<Typeconst& lhs, Another_iterator const&
rhs)
{
const_abstract_iterator<Typetemp(rhs);
return lhs!=temp;
}
template <class Another_iterator, class Typeinline bool
operator==(Another_iterator const& lhs, const_abstract_iterator<Type>
const& rhs)
{
const_abstract_iterator<Typetemp(lhs);
return temp==rhs;
}
template <class Another_iterator, class Typeinline bool
operator==(const_abstract_iterator<Typeconst& lhs, Another_iterator
const& rhs)
{
const_abstract_iterator<Typetemp(rhs);
return lhs==temp;
}
template <class Another_iterator, class Typeinline bool
operator!=(Another_iterator const& lhs, const_abstract_iterator<Type>
const& rhs)
{
const_abstract_iterator<Typetemp(lhs);
return temp!=rhs;
}
template <class Another_iterator, class Typeinline bool
operator!=(const_abstract_iterator<Typeconst& lhs, Another_iterator
const& rhs)
{
const_abstract_iterator<Typetemp(rhs);
return lhs!=temp;
}
