title: Object of size dependent on runtime information
body: <p>I want to test if different subgroups of objects stored in an array will satisfy a certain condition if grouped together, and I know that some objects cannot satisfy it if grouped with other objects.</p>
  
  <p>An example to make it clear. The second row indicates which other objects are compatible with that given object (i.e. 1 is compatible with 2, 4 and 5; 2 with 1, 3 and 5...).</p>
  
  <pre><code>+----------+----------+----------+----------+----------+
  | Object 1 | Object 2 | Object 3 | Object 4 | Object 5 |
  +----------+----------+----------+----------+----------+
  |   2 4 5  |   1 3 5  |   1 2    | 1   5    |   1 2 4  |
  +----------+----------+----------+----------+----------+
  </code></pre>
  
  <p>I want to remove unnecessary comparisons, since they would speed up the code a lot. That is, when checking if 1 and 2 together could satisfy the condition when grouped with something else, I can avoid checking against 3 (since 1 cannot satisfy it when grouped with 3) and 4 (since 2 cannot satisfy it when grouped with 4).</p>
  
  <p>Since this happens millions of time in the code, I need a quick way of getting the list of objects with which a subset of objects is compatible. I thought of using a series of bits, each of them representing an entry of the array, and having the nth bit set if the object associated with it is compatible with the object in the nth entry of the array.</p>
  
  <p>So if we imagine using 5 bits, we would get:</p>
  
  <pre><code>+----------+----------+----------+----------+----------+
  | Object 1 | Object 2 | Object 3 | Object 4 | Object 5 |
  +----------+----------+----------+----------+----------+
  |  01011   |  10101   |  11000   |  10001   |  11010   |
  +----------+----------+----------+----------+----------+
  </code></pre>
  
  <p>To see the objects against which it is worth testing 1-2, one would do the AND to both sets of bits:
  01011 &amp; 10101 = 00001
  That is, only should test against the 5th entry.
  I do this because I assume bit operations are faster and take less memory than storing more complex objects such as vectors and doing their intersection.</p>
  
  <p>The problem is that I do not know in compile time how many objects I'll have (I can have up to hundreds). What type could I use to represent the set of bits then?
  I can think of hacks such as:</p>
  
  <ul>
  <li>Using a huge type (a struct of a few dozens uint64): this would be a waste of memory and potentially slow if I only have a few objects (having to compare thousands of bits when I only have 8 objects, for example).</li>
  <li>Using dynamic arrays: I think dynamic allocation could prove expensive, although I have not given it too much thought. Also, I do not know if iterating through two arrays AND-ing each entrance would be as fast as AND-ing an object of the same size, but I suspect not.</li>
  </ul>
  
  <p>Is there an efficient solution to this problem? I'd be happy with another alternative to this way of checking 'compatibility' if it proves faster.</p>