Boost logo

Boost Users :

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-07-25 16:55:28


On Jul 24, 2005, at 1:59 AM, Feldman, Yulik wrote:

> Iíve also noticed that when in/out edge lists are stored in an
> associative container and the parallel edges are allowed, i.e multiset
> is used, the functions remove_edge()/clear_vertex() do not work as
> efficient as they could. The calls to these functions (in my case)
> result in the following sequence of calls:
> [snip code]
> The complexity of the search operation is linear, so multiset doesnít
> provide a performance advantage over containers such as vector or set.
> However, the function erase_if_dispatch() could use multisetís
> equal_range() member function, which would result in O(log n)
> complexity of the search. I understand that the reason
> erase_if_dispatch() is written in the way it is written, is probably
> that the function is generic with regard to the predicate and doesnít
> do assumptions on it. However, in the case erase_if_dispatch() is
> called from erase_from_incidence_list(), where the predicate is set,
> the function (its special specialization) could make assumption that
> the predicate is actually the same as the predicate used to sort the
> in/out edge list itself (the target vertex), and therefore could use
> equal_range() to boost the performance of the function.

We did some work in this area for 1.33.0, but we didn't fix this
particular performance problem. It seems that erase_from_incidence_list
should really look at the selector for the edge list to determine if we
should (1) erase one element quickly, (2) erase an element range
quickly, or (3) step through the list linearly erasing elements.

Would you be able to supply a patch to do this? I'll be happy to review
it and put it in for the next (post-1.33.0) Boost release.

        Doug



Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net