Объект размера, зависящий от информации о времени выполнения

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, что сделало трюк.