关于使用哪种数据结构来实现快速搜索的建议 C++

Question

我目前正在思考可能用于当前项目的数据结构。我不需要删除项目，因为我正在加载数据库，使用它，然后退出程序。唯一的限制涉及搜索时间。（第二次记忆，但主要是时间）。

概述我打算做什么。 我正在解析文件并提取用于创建各种对象的信息。 读取文件并创建对象后，我有一组多个对象，它们以字符串形式引用其他对象。

这里的目标是找到哪个网络从一个域到另一个域

例如：文本输入文件：

module Blabla 
netTomodule Foo
domain 1
..../*Other parameters of the module*/
end module

module Foo 
netTomodule Blabla
netTomodule Foo2
domain 2
..../*Other parameters of the module*/
end module

module Foo2
netTomodule Foo
domain 2
..../*Other parameters of the module*/
end module

读完本文后，我得到 3 个模块对象 Foo Foo2 和 Blabla ，它们的属性如下：

class Module{
private :
string name;
int domain;
netlist * mynetlist;
...
}  

My意见和我想获得建议的事情：

考虑到这一点后，我认为我最好的办法是：

1. 在读取文件并提取信息时，我应该创建一个 Module.txt 的链接列表。
2. 然后，根据我读取的模块数量，我创建一个两倍大小的数组。
3. 对于每个模块，我使用哈希函数来哈希模块名称，并将指向该模块的指针放在数组中的给定索引处
4. 现在，当我想要查找模块时，我只需计算哈希值并获取指针在给定的索引处（如果由于之前在制作数组时发生冲突而不是好的模块，则增加）

这基本上是哈希表的实现，或者至少是我从我的类中知道的哈希表的实现。

我的问题是这是一个好主意吗？有没有我可以使用的哈希表库来做到这一点？（我听说过并寻找 unordered_map 和 map，但我不知道它是否非常适合我的需求）

这是一个很大的文本，所以我希望它是足够详细，所以如果您有勇气阅读所有内容，谢谢您！

Answer 1

只需使用标准库附带的或来自 boost 的任何哈希表即可。大多数将具有 unordered_map （由 TR1 指定并建议用于 C++0x），就像 boost 一样，但有些将具有 std::hash_map 或 stdext ::hash_map 不同的实现略有不同，例如原始的 SGI 与 Microsoft。

不需要构建列表，直接将对象放入哈希表即可；它允许顺序迭代，尽管它将采用某种固定的随机顺序。

Answer 2

您可以维护一个哈希表（字符串 => 指向模块类型对象的指针）而不是链接列表。

再次在类 Module 中，再次维护一个 hashmap 或 string => 的映射指针

Answer 3

如果您也对间接关系感兴趣（Foo2->Foo->BlaBla），那么您基本上就有了一个图表。在这种情况下，您可以使用 Boost.Graph 。