Hello, Thanks for the references, I briefly looked at them (Views and any_iterator) and wasn't aware of them beforehand. I'm not really looking for a solution to a particular problem I might have, but rather wondering if there is not something very basic missing from C++. 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. C++ only has it's iterators currently, which is not always a very good solution for reasons alread said. Especially, for the starting problem of my original posting, there is no natural solution. True, there is any_iterator: We can define the virtual function in my original problem as typedef boost::iterator_range< adobe::any_iterator< ... > > ret_range; class X : ... { virtual ret_range give_stuff() const; ... 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. Presumably, a library author would quickly write his own little nonstandard iterator interface himself and have the virtual function return this instead. It would be nice to have something lightweight enough to promote its use a bit like boost::shared_ptr has become "the obvious way" of dealing with dynamic objects in C++. What I like to have is something more lightweight, along the following requirements: - the "notion" of a collection of things as a concrete type rather than a concept - fast to compile, simple error messages, fun to use, it should be the obvious choice for a library programmer to give collections of things (rather than awkward input iterators derived from iterator_facade) - a toolbox of free functions to combine them in all the ways I can do with linked lists in functional languages - performance and memory usage don't have to be optimal if we're just talking about the cost of a virtualisation A while ago, I made a first attempt on this, making the following design decisions: - There is no concept, but just one templated type: class list< typename reference >; which has various implementations and is, despite the name, conceptually a forward traversal iterator which is aware of the end of its range. - lists are constructed by using a number of free functions only, notably - the make_list overload set, implementing construction from stuff like iterators, containers, etc. and - map, filter, concat, etc. for combining lists in useful ways. - 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. - 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.) The most important thing that's lacking, however, is that lists are conceptually forward traversal only. Actually, I'm not entirely convinced that it would really be necessary to have more than that (or 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? If other forms of traversal are important, this would complexify all of this quite a bit. Presumably there would be a class hierarchy reflecting the traversal concepts, and possibly each such hiearchy for the implementations as well. But what should free function like map return then? There would have to be overloads for each of the traversal types, and there are already other reasons for overloads. How do people think on this matter? What direction to go? Is this worth spending time on? Cheers, Jens
jens-theisen@gmx.de wrote:
.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?
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.
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
- 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 ...
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.
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.
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.
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.
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
Sebastian Redl wrote:
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.
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.
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.
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 advantage is illustrated with the initial problem of my original posting. (The virtual function return type thing)
Templates are fine, but only for type safety. Let's throw away everything which is unnecessary for type safety.
I like templates ...
Who doesnt?
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.
This is true for the range concept, not for the iterator concept.
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.
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)
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.
Bidirectional and random access traversal is what's lacking.
There is incrementable and single pass (or input/output in STL).
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
participants (2)
-
jens-theisen＠gmx.de -
Sebastian Redl