Is there a convenient analog of std::bitset<> that's dynamically sizable at instantiation time, but avoids the extra allocation required by boost::dynamic_bitset<>
You can create dynamically sized bit sets easily in C by doing something like :
typedef struct { node_t node; block_t bits[0]; } node_bitset_t;
p = (node_bitset_t *)malloc( (sizeof(node_t) + sizeof(block_t)*blocks) * array_size);
You could do this using std::vector<std::bitset<bits>> only if you know bits at compile time. If you use std::vector<boost::dynamic_bitset<>>, then you'll see an extra allocator call. Is there a compromise that achieves the above C code's balance?
You might for-example have some custom allocator for the std::vector<...> that leaves some extra space after each boost::dynamic_bitset<> and allocates m_block there, although that'll probably still cost you the pointer for m_block.
dynamic_bitsetitself on the heap, which you needn't do most of the time. How does the C version avoid extra allocations for an array ofnode_bitset_t *?node_bitset_t *require zero size because they're simply the continuation of the struct that has size exactlysizeof(node_t). We allocate space for the arraybitsusing themallocand access it asbits[i]or whatever. There is only onemallocin the C version, ditto the compile time sizedstd::bitsetversion I'd assume, but theboost::dynamic_bitsetversion requiresarray_size+1newcalls. I think the stack isn't large enough for the data sets in question.