c++ - 测试许多离散值的首选方法？

Question

我有以下情况：

variable in {12, 4, 999, ... }:

列表中有大约 100 个离散值。我正在编写一个解析器来将其转换为 C++，我能想到的唯一方法是 100 个 case 语句，或者 100 个 if ==

一个比另一个更喜欢，还是有一个全面的更好的方法来做到这一点？

我应该澄清一下，这些值是常量整数。谢谢

Answer 1

如果您的任何一个离散值的最大值足够小，则std::vector<bool>根据该条目是否在列表中设置为真或假的标志应该是非常最佳的 - 假设这些值以大致相等的概率出现。

Answer 2

一种方法是按顺序排列值并使用二进制搜索来检查值是否包含在您的集合中。

您可以使用std::lower_bound插入点将值按排序顺序放入向量中，然后用于std::binary_search测试成员资格，或者您可以将值放入std::set并免费获得该功能（std::set::find()用于成员资格测试）。

有一些较小的性能考虑可能会使任一选项更可取；配置文件并自己决定。

第二种方法是将您的值放入一个哈希表中，例如std::unordered_set（或者如果您的值是静态已知的，则为某种静态等效项）。

Answer 3

假设这些值是常量，您当然可以使用switch语句。编译器将非常有效地执行此操作，使用二进制搜索类型方法或表 [或表和二进制搜索的组合]。长长的 if 语句列表不会那么有效，除非您对数字进行排序并采用二进制搜索类型的方法 - switch 语句更容易生成，因为编译器会找出最好的方法来决定哪些数字是在列表中，哪些不在列表中。

如果这些值不是常数，那么 switch 语句显然不是解决方案。位图可能会起作用 - 再次取决于实际范围 - 值的范围很大，那么这不是一个好的解决方案，因为它会使用大量内存 [但它可能是最快的方法之一，因为它只是用 2^n 数进行除法/取模的情况，可以使用简单的>>和&运算符完成，然后读取一次内存]。