Newsgroup: it.comp.lang.c++
Titolo: virtual iterators

I'm probably not the first one coming up with this idea...
Iterators are a great concept in generic programming. They make a good 
abstraction layer isolating algorithms from the containers they operate on 
and they even do it with no (or very small) loss of efficiency.
However, iterators are still bound to their containers at run time in a way 
that might be very inconveninent in some cases. Information hiding and 
extensibility requires that a library (or a class-set) does not show so 
much of its inner guts to outside users.
think about a class like this:
   class SymbolTable
   {
   public:
       define(const string &name, Var *var);
       Var *lookup(const string &name) const;
       ...
   };
 Perhaps this class uses a map<string,Var> internally or perhaps something 
else. This interface hides the implementation detail to the user. So far 
it's ok, but what happens if you want to provade some interface to scan all 
variables in the symbol table? If you want to give users of your class 
enough flexibility to use generic algorithms over the symbol table, you'd 
need to provide iterators for the inner container used by your class.
Adding these methods to class SymbolTable would suffice
    map<string,Var *>::iterator begin();
    map<string,Var *>::iterator end();
This works fine, but it exposes the map<> container out of the class! It 
bounds all code using the class to the internal representation of the 
symbol table in a way that prevents any kind of future enhancement
retaining 100% source and binary compatibility with the existing
interface.
What I want is something like this:
    bidirectional_viterator<Var *> begin() const;
    bidirectional_viterator<Var *> end() const;
 This would provide the same flexibility without revealing anything
about the container used to store the symbol table.
 How does such an iterator work? Of course you need to make all methods 
such as operator ++() and operator *() virtual, so the code using them
will call the real methods without knowing about the concrete iterator
class.
 My original naive idea was to make an abstract base "viterator" class 
template and then derive the concrete iterator from it:
    template<class Tp>
    class viterator
    {
        virtual viterator<Tp> & operator++() = 0;
        virtual Tp & operator*() = 0;
        ...
    };
    template<class It>
    class viterator_impl
    {
        It it; // the real iterator
        virtual viterator<Tp> & operator++() { return ++it; }
        virtual Tp & operator*() { return *it; }
    };
 But this simple design does not work at all! Most algorithms
must be able to create copies of iterator. You need copy constructor
and assignment operator to provide a full iterator interface.
 Since you can't have virtual constructors, you need to provide
a proxy class which contains a pointer to another private class doing
the real work. Basically, I'm using the pimpl pattern together with
a clone() method (the "virtual constructor" pattern?).
 Our hierarchy now looks like this:
    viterator_abs<Tp>  <-- pimpl * -- viterator<Tp>
            ^                             ^
            |                             |
   viterator_concr<It> <-- new -- viterator_impl<It>
 Users will just see the viterator<Tp> template, whose methods are just 
dummies calling viterator_abs<Tp> methods.  Both viterator<Tp> and 
viterator_impl<It> need not have any virtual methods. As its name suggests, 
viterator_abs<Tp> is an abstract class.
 Providers of virtual iterators will istantiate a viterator_impl<It> object 
which creates its underlying concrete viterator. The only place where the 
real iterator is buried is inside viterator_concr<It>.
 This makes code like this possible:
   // this function does not know what kind of container it's working with!
   template<class T>
   void print_viter(
       viterator<T> it,
       const viterator<T> & end,
       ostream_iterator<T> & out)
   {
       for (/**/; it != end; ++it, ++out)
            *out = *it;
   }
 
   // example code using it...
   list<int> cont;
   cont.push_back(10);
   cont.push_back(20);
   cont.push_back(30);
   print_viter(
       viterator_impl<list<int>::iterator>(cont.begin()),
       viterator_impl<list<int>::iterator>(cont.end()),
       ostream_iterator<int>(cout, "\n"));
 My implementation is in fact a bidirectional iterator. I now
want to make my viterator generic enough to support all kinds 
of basic iterators.
 I need to find out some way to generate all kinds of iterators
(input, forward, bidirectional and random access) out of this
class hierarchy. If possible, I wish this could be done in a way
that keeps my code indepentent from particular STL incarnations.
If this isn't possible or convenient, I'd like it to work at least with 
STLPort.
 My first idea was to do it the way other iterator adaptors such as 
reverse_iterator are done. These just define all methods required for a 
random access iterator and they work fine with lesser iterator categories 
too, as long as one doesn't try to use the forbidden operators.
 Unfortunately, this wouldn't work with virtual iterators because the 
compiler can't defer creation of virtual members like it does for 
non-virtual ones, so it would immediately generate an error for trying to 
use things such as operator[] on non random access iterators.
 So I guess the only choice is to force the provider of viterators to
choose a particular kind of iterator she want to create:
   bidirectional_viterator_impl<list<int>::iterator>(cont.begin())
 
 and code using viterators will also have to specify which kind of
iterator it's going to use:
   void print_viter(
       forward_viterator<T> it,
       const forward_viterator<T> & end,
       ostream_iterator<T> & out)
 Of course it must be possible to pass a bidirectional_viterator to a
function expecting a forward_viterator...
 I won't start cutting & pasting code from my only viterator class
(which is a bidirectional iterator) to create all other possibilities
until I find a design that doesn't suck so much.
 I've uploaded my quick & dirty code on my web site for inspection. I'd 
like some input and suggestions for improvement and expecially some elegant 
solution for the above issues.
-- 
  // Bernardo Innocenti
\X/  
http://www.codewiz.org/~bernie
      [ Send an empty e-mail to 
c++-...@netlab.cs.rpi.edu
 for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

 wrote in message
9fb4i2$npd$1...@serv1.iunet.it...

ti rispondo in italiano perchè questo ng è in italiano! :)
l'idea non è mica brutta, ma devi considerare il fatto che ogni
chiamata agli operatori ++ e -- nonchè la dereferenziazione si
tradurrebbero in una chiamata ad una funzione virtuale. Questo
significa che le prestazioni ne perderebbero in maniera molto
significativa, e visto che il c++ dovrebbe essere stato progettato con
l'efficienza ai primi posti in ordine di importanza, la tua idea non
mi sembra francamente molto utilizzabile (JMHO).
Un altro punto a sfavore:
viterator< tipo> f();
una funzione del genere non la puoi dichiarare, essendo viterator una
classe astratta. A questo punto dovrai restituire puntatori o
reference. Il che presuppone che ci dovrà essere una new da qualche
parte (e chi si preoccupa della relativa delete?) oppure un oggetto di
tipo derivato da viterator già allocato da qualche parte dentro il
container che dovra restituire istanze di questo tipo.
Queste sono solo delle considerazioni buttate così abbastanza
superficialmente, ma come vedi secondo me ci sono molti argomenti
contro la tua idea, che se non sbaglio salta fuori per non dover
scrivere qualcosa come
class SymbolTable
{
    public:
    typedef map< string, Var *>::iterator sym_iterator;
    define(const string & name, Var * var);
    Var * lookup(const string & name) const;
    sym_iterator begin();
    sym_iterator end();
};
o sbaglio?