[LC++]STL Iterators and integers

[Mark Phillips]

Hi!

Grzegorz Mazur wrote:
> 
> Hi,
> 
> On Fri, 10 Aug 2001, Mark Phillips wrote:
> 
> [snip]
> 
> >
> > Suppose you want to define an "offset vector" class.  Ie it is a vector
> > of integers, but has an "offset" value associated with it.  The value
> > of the "offset vector" at position i, is equal to the value stored in
> > an associated STL vector at position i, plus the offset value.
> >
> > class offsetVectorTy: public vector<int> {
> > private:
> >   int offsetPrv;
> > public:
> >   int offset() const {return offsetPrv;}
> >   void setOffset(int offsetArg) {offsetPrv=offsetArg;}
> >   int operator[](int i) const {return vector<int>::operator[](i)+offset();}
> >   offsetVectorTy(): vector<int>() {}
> > }
> >
> > By inheriting from vector<int>, it is very easy to set up what we
> > want.  offsetVectorTy _is_ a vector, so it has all the behaviour
> > and properties of vector<int>, except those which we have
> 
> No, you are wrong. This is no longer a vector, and it wouldn't be so easy
> to make it behave as a vector.

Hmmm.  Why is it no longer a vector?  Being a public inheritance
of vector<int> I thought it meant it _is_ a version of vector<int>.
Where am I wrong in my thinking?  (I am still quite new to c++ thinking
so it's quite possible I'm wrong:-)

> > redefined.  It's advantages:
> >
> > 1. It is very easy to set up.
> >
> > 2. With the possible exception of base class pointer problems, it
> > is exactly what we want.
> >
> > 3. We can use STL algorithms on it.
> 
> As I've already wrote, the STL algorithms work on iterators, not
> containers. So to achieve such effect in STL, you define a special kind of
> iterator, which transforms somehow values obtained from the underlying
> iterator. This way you can achieve the same effect without run-time
> polymorphism.

Okay.  I still haven't fully come to terms with how "generic 
programming" works.  I'm getting there though.

It would at least be true, I think, to say that inheritance makes it
_easier_ to work with the STL algorithms, because it means you have
all the iterator stuff setup for you.  (But the virtual stuff makes
it problematic --- agreed.)


> > 4. For large vectors, we can very quickly and easily change the
> > offset value, so it is an efficient implementation.
> 
> It can't be efficient all the member functions virtual.

The definition above doesn't use virtual functions, and that was
what I was referring to as efficient.  Later on I said that making
member functions virtual was one solution to the problem of
base pointer references.  The other solution is simply not to use
or allow base pointer references.  I know you don't like the latter
because it relies on documentation --- but then so does STL ---
it defines "concepts" which the programmer must adhere to, but which
the compiler doesn't enforce.

> > 2. Write a wrapper class for vector, call it "baseVectorTy"
> > for example, and make everything virtual.  Then with your
> > general algorithm, let it take a pointer to baseVectorTy
> > as its parameter.
> 
> And you always pay the price of polymorphism? No, thanks.

What is the price?  I don't have a good feel for it.  Ie, should
I throw away runtime polymorphism because it is too inefficient?
How much of an inefficiency is it?

Moving to a related aside...

It sounds like "generic programming" is a better way to go if you
can.  But generic programming doesn't seem to work when certain
crucial information is only knowable at runtime.

But perhaps there are ways of getting around these difficulties,
and perhaps the STL iterators are one such technique????  Forgive
me, I am thinking out aloud.


> > 3. Rewrite the c++ standard so that the "virtual" keyword
> > is "clever", so that it only adds the virtual runtime overheads
> > when they are needed.  (And implement compliant compilers.)  This
> > way, the STL could define things as virtual without worrying about
> > efficiency.  (For that matter, get rid of the virtual keyword
> > all together.)  From what I have read, this option is not done
> > because it would be very tricky to write compilers which do this.
> > (But not impossible it would seem.)
> 
> To me it seems impossible and I can't imagine how could it work. Could you
> send any reference?

I read it in a post to comp.lang.c++.  From what I remember, the poster
was saying that to make it work you would need to depart from
conventional compiler construction ideas and be willing to move much
more of the work to the linking stage.  His idea was to have the
compiler generate two versions of code --- one a virtual one and one
a non-virtual one.  You would then link in the right one for the 
situation.

Cheers,

Mark.