c++ - 存储定义列表以实现最快查找的最佳方式

Question

我有一些类似这样的字典文件:

 UTM University of Tennessee at Martin
 UMD University of Maryland

它是一个 3 个字母的首字母缩略词，后跟定义，以换行符分隔。该文件总共有 9282 个定义。

我的问题是:

1) 存储这些定义的最佳方式是什么？我应该将它们放在 map 中， vector 中，将它们存储在数组中，将它们留在 txt 文件中并扫描它以查找我需要的首字母缩略词吗？其他？速度是关键。2) 根据您的回答，我应该使用哪些函数来查找首字母缩略词然后仅检索定义？

预先感谢您的帮助。

编辑/新相关问题:如果我不希望我的应用程序依赖于外部 txt 文件，最好的方法是什么？

Answer 1

std::map很简单，是基本 STL 的一部分。这可能是您最简单的选择。

如果速度真的很重要，您可以对几个选项进行基准测试:

• 使用哈希表( tr1::hash_map 或 boost::unordered_map )进行 O(1) 查找(它需要哈希)。
• 使用 std::map O(log n) 次查找
• 创建一个 vector<string> (或 vector<const char*> )有 26^3 个元素(假设首字母缩写词都是字母 A-Z)，并将首字母缩写词转换为索引。

我猜 vector 选项(到目前为止)是最快的，但它也是最不明显、最难维护并且最难扩展到更大的数据集。

你可以转const char *acronym;用这样的东西进入索引:

const char *vector_of_names[26*26*26];

// Input 3-letter acronym, outputs the associated name.
const char *getName(const char* acronym) {
  return vector_of_names[
      ((acronyms[0]-'A') * 26*26) +
      ((acronyms[1]-'A') * 26) +
       (acronyms[2]-'A')];
}