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

From: Hugh Hoover (hugh_at_[hidden])
Date: 2005-12-07 12:15:28

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.

Hugh Hoover
Enumclaw Software