c++ - 如何遍历具有成对值的 map ？

我必须执行MST。我想将值成对添加。我的问题是如何遍历具有成对值的地图以及如何访问地图。

    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.

最佳答案

由于您的问题没有用其他方式标记，因此我假设使用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。

关于c++ - 如何遍历具有成对值的 map ？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44526392/