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

From: David Abrahams (dave_at_[hidden])
Date: 2005-12-08 00:44:39

Hugh Hoover <hugh_at_[hidden]> writes:

> On Dec 6, 2005, at 12:43, David Abrahams wrote:
>
>> Hugh Hoover <hugh_at_[hidden]> writes:
>>
>>> On Dec 3, 2005, at 15:44, David Abrahams wrote:
>>>
>>>> Hugh Hoover <hugh_at_[hidden]> 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