Re: [Boost-users] iterators 2

From: Sebastian Redl (sebastian.redl_at_[hidden])
Date: 2006-01-09 19:34:21

jens-theisen_at_[hidden] wrote:

>In many other programming languages there is a good notion for talking
>about a collection of things conveniently. Python and the .NET
>languages have this with their iterator concepts.
>  
>
.Net's iterators are no more powerful than C++'s iterators. A simple 
typedef on an any_iterator with boost::any and forward_iterator_tag has 
exactly the same capabilities, with the exception of the Reset() method.

>C++ only has it's iterators currently, which is not always a very good
>solution for reasons alread said.
>  
>
What were those again?

>It's still a monstrosity, however, given that any_iterator has 4
>template parameters, is derived from iterator_facade, and the
>iterator_range doubles this even.
>  
>
How does iterator_facade matter? And the other problem is what typedefs 
are for. You only need to supply two of the four template parameters 
anyway: the type and the category.

>Presumably, a library author would quickly write his own little
>nonstandard iterator interface himself and have the virtual function
>return this instead.
>  
>
Why? No sane library author would prefer writing a complete concept 
(that would only end up looking the same as the existing iterators 
anyway) to a few lines of typedefs.
typedef adobe::any_iterator<std::string, std::forward_iterator_tag> 
any_string_forward_iterator;
typedef boost::iterator_range<any_string_forward_iterator> string_any_range;

>- the "notion" of a collection of things as a concrete type
>  rather than a concept
>  
>
To what purpose? What are the advantages of a single type over a 
concept? Why can't any_iterator or a range of it fulfill the role?

>- fast to compile, simple error messages,
>
That's really an issue for compiler writers. But turn it how you will, 
in the end it comes down to templates, even if you use type erasure to 
hide it. Boost.Function doesn't produce pretty error messages either.

> fun to use,
>  
>
I like templates ...

>  it should be the obvious choice for a library programmer
>    to give collections of things (rather than awkward input
>      iterators derived from iterator_facade)
>  
>
How are they awkward?

>- a toolbox of free functions to combine them in all the
>  ways I can do with linked lists in functional languages
>  
>
That's possible to do based on the current iterator concept. You only 
need to write them.

>- performance and memory usage don't have to be optimal
>  if we're just talking about the cost of a virtualisation
>  
>
Several people might disagree with you here. Performance is, after all, 
one of C++'s key points.

>- There is no concept, but just one templated type:
>
>class list< typename reference >;
>
>  which has various implementations
>
How would they work? Derived classes? Doesn't that mean you always have 
to handle them on the heap to avoid splicing? Who is responsible for 
their deletion? Especially considering the transforming free functions 
you mention below.

>- lists have conversion operators along the line of the
>  conversion of their underlying reference type, which
>    especially enables list< T const& > to be used where
>      list< T > is expected.
>  
>
Assuming that accessing list elements returns refernces, this destroys 
const safety. You could attempt to modify an element of such a list, 
even though its underlying type is const. See also the rationale for 
disallowing implicit conversion between different parametrizations of 
the same base type in Java5.

>- lists are not iterators, but they can export that
>  behaviour. If this feature isn't used, iterator_facade
>    don't have to be present. (If viewed as iterators, their
>      end is a default constructed list, as usual.)
>  
>
That doesn't make sense. Either the single type you want provides this 
interface, or it doesn't. This is a compile-time decision. If you want 
it your way, you'd have to make list<T> a smart pointer that checks 
whether the pointee supports the given function and throws if not. In 
other words, you delay a very important compile-time check to runtime.

>The most important thing that's lacking, however, is that lists are
>conceptually forward traversal only.
>  
>
I'm not sure how you can call that a lack. All existing containers and 
iterators support forward traversal - how is providing more if possible 
a lack?

>Actually, I'm not entirely convinced that it would really be necessary
>to have more than that (or less).
>
Actually I don't think it's even possible to have less.

>My impression is that virtualisation
>for more than forward traversal is less dearly needed. I can only
>think of somewhat contrived examples. What do you think?
>  
>
Random access is often needed. Backwards traversal less often.

>How do people think on this matter? What direction to go?  Is this
>worth spending time on?
>  
>
In my opinion, that time would be better spent writing more funky 
iterators such as zip_iterator.

Sebastian Redl