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

Object of size dependent on runtime information

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

举例说明。第二行表示哪些其他对象与给定对象兼容(即 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 个条目进行测试。 我这样做是因为我认为与存储更复杂的对象(例如向量)并进行交集相比,位操作更快并且占用的内存更少。

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

这个问题有有效的解决方案吗?如果证明速度更快,我很乐意使用这种检查方式的另一种替代方法 'compatibility'。

正如 CoryKramer in a comment, I went for boost::dynamic_bitset 所建议的那样,成功了。