c++ - 如何遍历以值为对的 map ？

Question

我必须实现 MST。我想成对添加值。我的问题是如何迭代具有值对的 map 以及如何访问 map 。

    void addedge(multimap<int, pair<int, int> > dirgraph, int source, int dest, int weight)     // graph, source, dest, weight
    {
         dirgraph.insert(make_pair(weight, make_pair(source, dest)));
    }

    multimap<int, pair<int,int> > dirgraph;
    addedge(dirgraph, 0, 1, 5);
    addedge(dirgraph, 0, 4, 3);
    addedge(dirgraph, 1, 2, 1);
    addedge(dirgraph, 1, 4, 4);
    addedge(dirgraph, 4, 3, 3);
    addedge(dirgraph, 2, 3, 2);

    multimap<int, pair<int, int> >::iterator it = dirgraph.begin();
    multimap<int, pair<int, int> >::iterator itend = dirgraph.end();

    for (; it != itend; it++)
           cout << (*it).first << " from " << (*it).second.first << " to " << (*it).second.second << endl; // This dosen't work.

Answer 1

由于您的问题没有另外标记，我假设是 C++11。这是代码的注释和改进版本。

using edge = std::pair<int,int>;                    // for clarity
using directional_graph = std::multimap<int,edge>;  // not std::map<edge,weight> ?

void add_edge(directional_graph &dirgraph,          // pass by reference
              int source, int dest, int weight)
{
  dirgraph.insert(std::make_pair(weight, std::make_pair(source, dest)));
}

directional_graph dirgraph;
add_edge(dirgraph, 0, 1, 5);
add_edge(dirgraph, 0, 4, 3);
add_edge(dirgraph, 1, 2, 1);
add_edge(dirgraph, 1, 4, 4);
add_edge(dirgraph, 4, 3, 3);
add_edge(dirgraph, 2, 3, 2);

for(const auto&x : dirgraph)
  std::cout << x.first << " from " << x.second.first << " to "
            << x.second.second << std::endl;

请注意，这段代码更加清晰明了。我使用 std:: 来避免糟糕的 using namespace std;。最重要的是，这段代码是正确的，因为 add_edge() 实际上改变了第一个参数。在您的代码中，您创建了图形的本地拷贝，对其进行了修改，但对实际图形没有任何影响。

请注意:我发现您使用图的权重作为键很奇怪:您真的想通过权重来识别边吗？我本以为 edge 类型更适合作为键。在这种情况下，如果边是唯一的，则不需要 multimap，而只需要普通的 map。