Re: [Boost-users] iteration from pure abstract classes

Hugh Hoover writes:

On Dec 6, 2005, at 12:43, David Abrahams wrote:

...

Hugh Hoover writes:

...

On Dec 3, 2005, at 15:44, David Abrahams wrote:

...

Hugh Hoover writes:

...

I have a need to provide STL compliant iterators from an abstract class A, that is, without knowing the runtime type of the actual "collection" being iterated.. As near as I can tell, these things

<snip>

...

Have you looked at boost::indirect_iterator? Just make a container of pointers to the abstract base and iterate over that :)

Thanks for the suggestion, but that won't really work.

Why?

mainly performance. Imagine a tree structure where the nodes are of different concrete types based on a common abstract interface. So far, no problem... But, the nodes have subtree arity ranging from 0 to >10,000 - to walk the structure means creating a new vector for each node visited with a size equal to the node's arity, and initializing from another structure (which may not be a vector).

If I use some kind of abstract iterator interface, the >iterator< gets allocated, but can walk the concrete structure directly. Clearly, there's a tradeoff here - and I'm betting that the abstract iterator is cheaper than the vector - I haven't proven that.

Oh, are you iterating over homogeneous containers of X1,...Xn where every Xi is derived from some common base class, B? If instead you are iterating over containers of heterogeneous derived classes, I can't understand how you can do better than what I proposed. -- Dave Abrahams Boost Consulting www.boost-consulting.com