c++ - 大小取决于运行时信息的对象

Question

我想测试存储在数组中的对象的不同子组如果组合在一起是否会满足特定条件，并且我知道如果与其他对象组合在一起某些对象不能满足它。

举个例子来说明。第二行表示哪些其他对象与给定对象兼容(即 1 与 2、4 和 5 兼容；2 与 1、3 和 5...兼容)。

+----------+----------+----------+----------+----------+
| Object 1 | Object 2 | Object 3 | Object 4 | Object 5 |
+----------+----------+----------+----------+----------+
|   2 4 5  |   1 3 5  |   1 2    | 1   5    |   1 2 4  |
+----------+----------+----------+----------+----------+

我想删除不必要的比较，因为它们会大大加快代码速度。也就是说，当检查 1 和 2 一起是否可以满足与其他东西分组时的条件时，我可以避免检查 3(因为 1 不能满足它，当与 3 分组时)和 4(因为 2 不能满足它，当与 4 分组时) .

由于这种情况在代码中发生了数百万次，我需要一种快速的方法来获取与对象子集兼容的对象列表。我想到了使用一系列位，每个位代表数组的一个条目，如果与之关联的对象与数组第 n 个条目中的对象兼容，则设置第 n 个位。

因此，如果我们想象使用 5 位，我们将得到:

+----------+----------+----------+----------+----------+
| Object 1 | Object 2 | Object 3 | Object 4 | Object 5 |
+----------+----------+----------+----------+----------+
|  01011   |  10101   |  11000   |  10001   |  11010   |
+----------+----------+----------+----------+----------+

要查看值得测试 1-2 的对象，可以对两组位执行 AND: 01011 & 10101 = 00001 也就是说，只应针对第 5 个条目进行测试。 我这样做是因为我认为与存储更复杂的对象(例如 vector )并进行交集相比，位操作更快并且占用的内存更少。

问题是我不知道在编译时我将拥有多少个对象(最多可以有数百个)。那我可以用什么类型来表示这组位呢？ 我可以想到一些技巧，例如:

• 使用巨大的类型(一个包含几十个 uint64 的结构):这会浪费内存，而且如果我只有几个对象(例如，当我只有 8 个对象时必须比较数千位，则速度可能会变慢) ).
• 使用动态数组:我认为动态分配可能会很昂贵，尽管我没有考虑太多。另外，我不知道遍历两个数组并对每个入口进行运算是否与对相同大小的对象进行运算一样快，但我怀疑不会。

这个问题有有效的解决方案吗？如果这种检查“兼容性”的方法被证明更快，我会很高兴有另一种替代方法。

Answer 1

根据 CoryKramer 的建议在评论中，我选择了boost::dynamic_bitset , 成功了。