从C ++中的成对列表访问特定元素

Question

如果有多个边缘，我想跳过较大的权重。我认为，如果我可以直接访问边缘u和v之间的权重，则可以优化代码。该代码来自Dijkstra算法，使用优先级队列。我可以反复检查，但我认为效率不高。如何优化代码？

void Graph::addEdge(long long int u, long long int v, long long int weight){

    list<pair<long long int,long long int> >::iterator i;

    int flag = 0;
    for(i = adj[u].begin(); i!= adj[u].end(); ++i){
        if((*i).first == v && weight>(*i).second){
            flag = 1;
            break;
        }
    }
    if(flag == 1){
        return;
    }

    adj[u].push_back(make_pair(v, weight));
    adj[v].push_back(make_pair(u, weight));
}

Answer 1

我可以建议对此代码进行一些优化：

1. 使用std :: vector或std :: array代替std :: list。 list被实现为链接列表，遍历为slow。向量和数组也更易于缓存，因为数据是顺序存储的，因此，一次将在缓存中加载多个元素。
2. 使用unordered_map的数组/向量而不是每对，使得adj[u]对应于以节点v为键且最小权重为值的哈希图。为了进一步改善此哈希映射的性能，在经过默认行为并且适合您的情况之后，您还可以提供自定义哈希函数和自定义冲突解决方法。否则，std :: unordered_map仍然非常有效。请注意，仅在插入/查询的情况下使用unordered_map才更有好处对于遍历而言，这很可悲。