如何最有效地插入对列表？

Question

我有

(A,B)
(A,C)
(A,D)
(B,C)
(B,D)
(C,D)
(D,E)

在文本文件中.我将使用正则表达式提取它.

我想将数据插入到容器中,使其看起来像这样.

A->B,C,D
B->C,D
C->D
D->E

我使用哪个容器？

我需要能够在容器的左手侧和右手侧查找数据,即通过键值.所以我需要能够搜索/查找

A,B,C,D in

A->B,C
B->C,D
C->D
D->E

和B,C in

A->B,C

Answer 1

std :: multimap浮现在脑海中......基本上是一个地图,但允许在地图键中重复(即你可以有多个"A"键,每个键都映射到"B","C"或"D"键,继续你的例子).

编辑:回应Chris的评论:您以与地图相同的方式将项目插入到多图中 - 您创建一个std::pair包含键和值的对象,然后将insert其添加到多图中:

std::multimap<char, char> myMap;
myMap.insert(std::pair<char, char>('A', 'B'));
myMap.insert(std::pair<char, char>('A', 'C'));
myMap.insert(std::pair<char, char>('A', 'D'));
myMap.insert(std::pair<char, char>('B', 'C'));
// ... etc

这里假设你从字面上正在检查字符,并且A,B,C等不是替身别的东西.如果它们是替身,请根据需要进行调整.

然后,您可以在多重映射中查询键"A"下的所有值,如下所示:

typedef std::multimap<char, char>::iterator mmIter; // For brevity...
std::pair<mmIter, mmIter> iters = myMap.equal_range('A');
// Iterate over values for key
for (mmIter iter = iters.first ; iter != iters.second; ++iter)
{
    // Print out value.
    cout << " " << (*iter).second;
}

multimap.equal_range将pair包含迭代器的迭代器返回到与键匹配的第一个条目,以及紧跟在与键匹配的最后一个条目之后的条目.因此,如所示,这些可用于迭代条目.

编辑2刚刚意识到你的评论意味着什么.Multimap本身不支持双向操作(即在值和键上查找),因此您可能需要维护两个多图 - 每个方向一个.这可能是一件痛苦的事情 - 确保两者保持正确同步可能很棘手.

或者,我确定有一些Boost类可以达到目的(我实际上并不知道 - 我自己不使用Boost,但我确信其他人应该能够提供更多细节).