From: Doug Gregor (dgregor_at_[hidden])
Date: 2006-06-27 09:56:55
On Jun 23, 2006, at 3:37 PM, me22 wrote:
> On 6/23/06, nicola <vitacolo_at_[hidden]> wrote:
>> One design choice in the BGL is that there are "visitor"
>> functions, e.g.
>> breadth_first_search() and depth_first_search(), but there are no
>> "bfs_iterator" or "dfs_iterator". What are the motivations that
>> lead to
>> such choice? Might they be applied to trees as well?
>>
> My guess for that would be that iterators are intended to be cheap to
> copy but duplicating the stacks, queues, or sets of visited/pending
> nodes would be very expensive.
If the iterators stored a shared_ptr to all of the data needed to
make the traversal work, the cost of copying the iterators would be
greatly reduced.
I think BFS/DFS (and Dijkstra, A*, Prim, topological sort, etc)
iterators would be extremely interesting for the BGL. They better
support incremental uses of these algorithms, and offer an
interesting alternative for simple visitors.
Doug