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

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

我使用哪个容器？<​​/p>

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

A,B,C,D 在

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

还有B、C在

A->B,C

Answer 1

std::multimap想到......基本上是一张 map ，但允许在 map 键中重复(即你可以有多个“A”键，每个映射到“B”，“C”或“D”键，继续你的例子).

编辑:作为对 Chris 的评论的回应:您以与映射相同的方式将项目插入到多重映射中 - 您创建一个 std::pair 对象包含键和值，然后是 insert进入多重 map :

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 等并不是其他内容的替代品。如果他们是替身，请适当调整。

然后您可以查询 multimap 中键“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返回一个包含迭代器的 对 到第一个与键匹配的条目，以及紧跟在最后一个与键匹配的条目之后的条目。因此，这些可用于迭代条目，如所示。

EDIT 2 刚刚意识到您的评论的真正含义。 Multimap 本身不支持双向操作(即查找值和键)，因此您可能需要维护两个 multimaps - 每个方向一个。但这可能会很痛苦 - 确保两者保持正确同步可能很棘手。

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