c++ - 使用multimap c++​​打印邻接表

Question

我根据以下链接构建了一个邻接列表:Adjacency list

---

struct Node
{
    string name;
    int id;
};

typedef std::multimap<Node,Node> Graph;
Graph g;

g.insert (Graph::value_type(node1, node3));
g.insert (Graph::value_type(node1, node4));
g.insert (Graph::value_type(node1, node5));
g.insert (Graph::value_type(node2, node6));
g.insert (Graph::value_type(node3, node6));

---

如何按照下图 ( Adjacency list ) 的结构打印多重图？

Answer 1

Graph::const_iterator it = g.begin();
while (it != g.end())
{
    std::pair<Graph::const_iterator, Graph::const_iterator> range
        = g.equal_range(it->first);

    std::cout << it->first << ": "; // print vertex

    for (; range.first != range.second; ++range.first)
    {
        std::cout << range.first->second << ", "; // print adjacent vertices
    }
    std::cout << std::endl;

    it = range.second;
}

输出:

1: 3, 4, 5, 
2: 6, 
3: 6, 
4: 7, 
5: 7, 8, 9, 
9: 5,

DEMO

---

如果您不希望进行冗余 equal_range 调用，只要两个相邻元素相等，您就可以使用单个迭代器进行操作在订购方面:

Graph::key_compare cmp = g.key_comp();
Graph::const_iterator it = g.begin(), itEnd = g.end(), prev;
while (it != itEnd)
{
    std::cout << it->first << ": "; // print vertex

    do
    {
        std::cout << it->second << ", "; // print adjacent vertices
        prev = it++;
    }        
    while (it != itEnd && !cmp(prev->first, it->first));

    std::cout << std::endl;
}

DEMO 2