c++ - 使用位数组？

Question

想象一下，有一组固定不变的“选项”（例如技能）。每个对象（例如人类）都可以有或没有任何选项。

我应该为每个对象维护一个成员选项列表并用选项填充它吗？

或者：

使用每个位代表相应选项的已采用（或未采用）状态的位数组是否更有效（更快）？

-编辑：-

更具体地说，技能列表是一个字符串向量（选项名称），绝对小于 256。目标是让程序尽可能快（不考虑内存问题）。

Answer 1

这取决于。如果选项的数量很少，则使用几个bool成员来表示它们。如果列表变大，那么您的两种选择都可行：

• 一个位集（它适合enum象征性地表示选项）占用一个恒定且非常小的空间量，并且获得某个选项需要 O(1) 时间；
• 选项列表，或者更确切地说是其中的一个std::set或多个选项unordered_set，可能更节省空间，但前提是选项的数量很大，并且预计每个对象将设置非常少的选项。

如有疑问，请使用一堆bool成员或bitset. 仅当分析表明存储选项成为负担时，才考虑动态列表或集合表示（即使这样，您也可能需要重新考虑您的设计）。

编辑：如果选项少于 256 个，abitset最多需要 64 个字节，这在内存和可能的速度方面肯定会超过任何列表或集合表示。一堆bools，甚至是一个数组unsigned char，可能仍然更快，因为访问一个字节通常比访问一个位更快。但是复制结构会比较慢，所以尝试几个选项并测量结果。YMMV。

Answer 2

在一次操作中测试一个人是否存在多种技能时，使用位数组更快。

如果您使用选项列表，那么您将不得不一次检查一个项目以查找技能集是否退出，这显然需要更多时间并需要许多比较操作。

Answer 3

位数组通常编辑速度更快，搜索速度更快。至于所需的空间，只是做数学。选项列表需要一个动态大小的数组（这比选项集本身有一些开销）；但如果有大量选项，如果（通常）只设置少量选项，它可能会更小。