c++ - 具有高效 "remove"函数的数据结构

Question

我正在寻找改善代码性能瓶颈的方法。 在我的代码中，我构建了一个图，其中每个顶点都维护传出和传入边的列表。破坏我的代码性能的是这些边缘经常从列表中删除的事实。

目前，我的实现使用的是 C++ 的 STL 库中可用的列表。所以我想知道是否有任何数据结构可以提供高效的删除功能。

下面是删除顶点的代码部分。你可以看到 在外部 for 循环的每次迭代中
(*inedge_it)->src->out_edges.remove(*inedge_it) 被调用以从传入边列表中删除 (*inedge_it)。 同样在内部 for 循环中 (*outedge_it)->tgt->in_edges.remove(*outedge_it 被调用以从出边列表中删除 (*outedge_it)。

int dag_vertex::eliminate( int & edge_counter )
{
    int nMults = 0;

    list<dag_edge*>::iterator inedge_it;
    list<dag_edge*>::iterator outedge_it;

    int m = in_edges.size();
    int n  = out_edges.size();

    for( inedge_it=in_edges.begin() ; inedge_it!=in_edges.end() ; inedge_it++ )
    {
        (*inedge_it)->src->out_edges.remove(*inedge_it);

        for( outedge_it=out_edges.begin() ; outedge_it!=out_edges.end() ; outedge_it++ )
        {
            (*outedge_it)->tgt->in_edges.remove(*outedge_it);

            double cij = (*inedge_it)->partial*(*outedge_it)->partial;

            nMults++;

            dag_edge * direct_link = NULL;

            list<dag_edge*>::reverse_iterator src_outedge_it;

            for( src_outedge_it=(*inedge_it)->src->out_edges.rbegin() ; src_outedge_it!=(*inedge_it)->src->out_edges.rend() ; src_outedge_it++ )
            {
                if( (*src_outedge_it)->tgt==(*outedge_it)->tgt )
                {
                    direct_link = (*src_outedge_it);
                    break;
                }
            } 

            if(direct_link)
            {
                direct_link->partial += cij;
            }else
            {
                (*outedge_it)->tgt->add_in_edge( (*inedge_it)->src , cij );
                edge_counter++;
            }
        }

        delete (*inedge_it);    
    }

    for( outedge_it=out_edges.begin() ; outedge_it!=out_edges.end() ; outedge_it++ )
    {   
        delete (*outedge_it);
    }

    in_edges.clear();
    out_edges.clear();

    edge_counter -= (m+n);

    return nMults;
}

这里是添加入边的函数定义

dag_edge* dag_vertex::add_in_edge(dag_vertex* src , double partial)
{
    dag_edge* the_in_edge= new dag_edge(src, this, partial);
    in_edges.push_back(the_in_edge);
    src->out_edges.push_back(the_in_edge);
    return the_in_edge;
}

下面是dag_edge的定义。

dag_edge::dag_edge(class dag_vertex* s, class dag_vertex* t, double cij) : 
src(s), tgt(t), partial(cij),alive(true)
{

}

dag_edge::~dag_edge()
{
     //std::cout<<"~dag_edge("<<src->idx<<","<<tgt->idx<<")"<<std::endl;
}

dag_vertex* dag_edge::getsrc()
{
    return src;
}

dag_vertex* dag_edge::gettgt()
{
    return tgt;
}

void dag_edge::dump_to_dot(FILE* file)
{
    fprintf(file,"%d->%d [label=\"%f\"]\n",src->idx, tgt->idx, partial); 
}

void dag_edge::display() 
{

}

Answer 1

在 vector 中按值存储边缘可能会更有效，当您需要删除索引 i 处的 edge 时您可以通过将 i 边替换为 vector 中的最后一个边并弹出最后一个

来实现

edges[i] = edges.back();
edges.pop_back();

如果对 edge 使用 move semantics，效率会更高