On Jul 24, 2005, at 1:59 AM, Feldman, Yulik wrote: ArialI’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: Arial[snip code] ArialThe 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