Boost logo

Boost Users :

From: Feldman, Yulik (yulik.feldman_at_[hidden])
Date: 2005-07-24 01:59:04

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:


// O(E/V)

    template <class EdgeList, class vertex_descriptor>

    void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,








template <class Container, class Predicate>

  void erase_if(Container& c, Predicate p)


    erase_if_dispatch(c, p, container_category(c),





template <class AssociativeContainer, class Predicate>

  void erase_if_dispatch(AssociativeContainer& c, Predicate p,

                         associative_container_tag, stable_tag)


    typename AssociativeContainer::iterator i, next;

    for (i = next = c.begin(); next != c.end(); i = next) {


      if (p(*i))





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.



Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at