Re: [Boost-users] iterators 2

From: jens-theisen_at_[hidden]
Date: 2006-01-10 14:08:00

Sebastian Redl wrote:

>> - 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.·

I put this comment of yours at the beginning because I find it most  
important to answer.

I guess this is a very common opinion that performance is one of the key  
points of C++. But it's not the only one, and among the others, some  
certainly are undervalued, the one being relevant here is expressitivity.

Unlike C++ iterators, iterators in other languages have a relatively  
consise notation. The good thing about C++ is now that it's possible to  
write C++ iterators (incompatible to but convertible to and from the old  
ones), which have an even more consise syntax than the iterators in those  
other languages. The price being less efficiency, but the loss of  
efficiency will not be measurable in the applications where it would  
matter, whereas the efficiency loss that one suffers by using one of the  
languages with a more consise notation matters indeed.

>> 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.

and MoveNext, which returns whether or not the end has been reached; this  
is very important: .NET IEnumerators are aware of their end. If C++ had  
this property, there would be no need for ranges in many situations.

.NET IEnumerators not really Iterators in the c++ sense; they are, as  
Python iterators, more like C++ forward ranges.

>> 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.

Let this whole thing participate in an overload resolution where there is  
no fitting candidate and have a look at the error message. As you said  
somewhere else, this is in part a compilers problem. But 1. it's not only  
the compiler's fault (but also a bit the language design) and 2. as a  
langugage designer it doesn't really matter whose fault this is; you just  
want to have a usable library.

>> 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;

It would not look like C++ iterators, but like .NET enumerators or Python  
iterators. How often have you seen a declaration like the following:

struct special_stuff_provider
{
  virtual bool exhausted() = 0;
  virtual special_type provide_next_special_thing() = 0;
};

I wouldn't even dare to count. And how likely is it that this sort of  
thing will disappear in the future replaces by a range of any iterators?
I don't think that this is likely at all.

>> - 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?

The advantage is illustrated with the initial problem of my original  
posting. (The virtual function return type thing)

>> - 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.

Templates are fine, but only for type safety. Let's throw away everything  
which is unnecessary for type safety.

> I like templates ...

Who doesnt?

>>  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?

Because the iterator itself isn't what you usually need, it's a range. You  
can get the range from the iterators, right, but then you end up with a  
fairly complex type for what should be a simple one. That's what I call  
awkward about it.

>> - 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.

This is true for the range concept, not for the iterator concept.

>> - 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.

Yes, the implementations are allocated on the heap, using the usual  
handle-body idiom. Reference counting is deleting them. The free functions
allocate new implementations holding on the old ones.

>> - 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.

How do you mean? If you get an element from a list< T >, it's a copy, you  
can safely modify that copy.

I'm not aware of that rationale (or anything else of Java generics for  
that matter). Can you point me to a resource about that? (I mean the  
rationale)

> 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.

Sorry for being ambiguous: They do provide the interface semantically, but  
don't model the interator concepts directly. The things that maps the  
iterator model implementation to this other interface is what's not  
mandatory.

This is not really an important point in the design, however.

>> 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?

Bidirectional and random access traversal is what's lacking.

>> 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.

There is incrementable and single pass (or input/output in STL).

>> 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.

Random access is often needed when performing some algorithmic task, sure,  
but do you have an example of when this is necessary in a virtualised  
form?

> In my opinion, that time would be better spent writing more funky
> iterators such as zip_iterator.

I agree on zip_iterator being funky.

Cheers,

Jens