對象的大小取決於運行時信息

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的對象，一個會做和這兩組位： 10101 = 00001 也就是說，只能對第5個條目進行測試。 我這樣做是因爲我認爲位操作比存儲更復雜的對象（如向量）和執行交叉操作更快，佔用的內存更少。

問題是，我不知道在編譯時有多少個對象（我可以有多達幾百個）。我可以用什麼類型來表示一組位？ 我能想到黑客，如：

• 使用一個巨大的類型（幾UINT64的結構）：這將是浪費內存，如果我只有幾個對象可能慢（有比較例如，當我只有8個對象時，有數千位）。
• 使用動態數組：我認爲動態分配可能證明是昂貴的，儘管我沒有考慮太多。此外，我不知道是否遍歷兩個數組，並且每個入口的速度與和同一大小的對象一樣快，但我懷疑不是。

是否有解決此問題的有效方法？如果證明速度更快，我會很高興用另一種方法來檢查「兼容性」。

Answer 1

正如CoryKramer在評論中建議的那樣，我去了boost::dynamic_bitset，這有訣竅。