Re: [Boost-users] iterators 2

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 any_string_forward_iterator; typedef boost::iterator_range 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