[Boost-users] iterators 2

From: jens-theisen_at_[hidden]
Date: 2006-01-09 17:24:00

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