Re: [libcvd-members] libcvd/cvd image.h [subimage2]

[Edward Rosten]

On Mon, 3 Jul 2006, Gerhard Reitmayr wrote:

> Edward Rosten wrote:
> > > Hi Ed,
> > >
> > > I am following your iterator work with interest. did you think about
> > > deriving from
> > > stl::iterator defined in <iterator> ? this would probably define all
> > > your types to make them work properly with stl.
> >
> > According to my Stroustrup book, std::iterator provided the 5 typedefs
> > I've now put in to iterator. I could make ConstSubImageIterator derive
> > from std::iterator, but I'd still have to override the pointer and
> > reference in SubImageIterator to be non-const types.
> >
> > Is there additional benefit, or is it just a helper class?
>
> I don't think so. I guess defining the same things is enough.
>
> > What do  you think of the iterator design? I'm not 100% sure about it,
> > since it has a const_cast<>(). It shouldn't invoke undefined behaviour,
> > since there is no way to access the pointer as non-const, and it allows
> > non-const iterators to degenerate to const ones (just like the normal
> > const keyword), and all comparisons keep on working.
>
> how does a typical stl implementation solve this? just implementing all
> the different comparison operators and constructors?


OK, so I just lookes that up in the GCC STL.

Here's how, esentially:

template<class Pointer, class Container> iterator
{
    template<class Pointer> bool operator==(iterator<Pointer, Container> i);

    //etc
};


A container of T always makes an iterator<T, Container<T> >, or 
iterator<const T, Container<T> >.

However, an iterator<T> does not degenerate to an iterator<const T>, like 
normal pointers, or my iterators. I suspect there is a cast operator 
sitting in there somewhere.


> > Also, what about .end() versus .fastend()? It makes the common case
> > cheap, but not for STL algorithms, unfortunately.
>
> well, I am amazed that the fastend version is so much faster.

It saves a whole test. The test loops are pretty trivial, and only have a 
single test and assignment. The extra test doubles the workload.

I do find the difference in optimization with -funroll-loops interesting.

> Of course,
> it is annoying that the user has to know about this optimisation and use
> it on purpose.

Yes. I agree. It's a possible fault of the STL algorithms for not allowing 
this.


> I also had a similar problem that stl only takes the same iterators, it
> is annoying. the solution could be to make the *End type a real iterator
> and just pass both begin and end to stl functions. so you could have a
> fastbegin() than as well and simply use fastbegin/fastend for stl.

That would work, but its kind of annoying that there is the extra 
complexity, either way. At least fastbegin would allow one to use the STL 
algorithms.

Althought, currently, fastend is a placeholder struct and contains little 
data. I expect having a fat fastend struct wouldn't matter, since the 
optimizer would deal with it.

> I do something similar for a member_iterator: check out tag/fn.h it
> contains a member_iterator that accesses the member of a struct/class
> stored in containers. If algorithm functions are written to take
> iterators, then this allows them to work both on simple types or members
> of more complex types.

Nice. I'm going to use that one.


-Ed