Dynamic Bitsets in GCC

Revision en15, by bitset, 2024-05-13 23:41:38

Hello sirs, you might know that Boost has a dynamically sized bitset class, but did you know that GCC also has one? Turns out it's included in the tr2 folder. You can simply include the <tr2/dynamic_bitset> header, and use it as std::tr2::dynamic_bitset. Yes, it works on Codeforces.

Here's a code example to count triangles in a graph (abc258_g):

Code

In some problems, we might not be able to use a constant sized bitset. For example, on 1856E2 - ПерестановДерево (сложная версия). Here's a submission where we replaced neal's custom_bitset template with using custom_bitset = tr2::dynamic_bitset<>;, and got accepted with little performance difference (260853192, original 217308610).

The implementation of the bitset seems identical to a version of Boost's dynamic bitset, so you can read the docs here. You can view the source here.

Comparing to std::bitset, here are some notable things I saw:

  • They include more set operations, such as set difference and checking if a bitset is a subset of another bitset.
  • They include lexicographical comparisons between bitsets.
  • You can append single bits, as well as whole blocks (i.e. integers)
  • You can also resize it like a vector. (For some reason there's no pop_back though...)
  • Find first and find next are also supported, without weird function names like std::bitset. Unfortunately, there's still no find previous :(
  • You can specify the word type and allocator as template arguments.

Of course, it also has all the normal std::bitset functionality. However, I'm not sure how fast this is compared to std::bitset; you can let me know in the comments. Interestingly, it seems to be using 64 bit integers on Codeforces.

If you enjoyed this blog, please make sure to like and subscribe for more bitset content.

Thanks qmk for helping with the blog.

Tags bitset, gcc, boost

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en22 English bitset 2024-06-12 19:17:27 150 Tiny change: 'gain when it's on Codef' -> 'gain when the fix is on Codef'
en21 English bitset 2024-06-08 23:19:49 50 (published)
en20 English bitset 2024-06-08 23:19:28 11
en19 English bitset 2024-06-08 23:12:35 272 Tiny change: '1157481). \n\nI'll keep ' -> '1157481). I'll keep ' (saved to drafts)
en18 English bitset 2024-05-13 23:50:33 0 (published)
en17 English bitset 2024-05-13 23:45:34 3 Tiny change: 'ames like std::bits' -> 'ames like in std::bits'
en16 English bitset 2024-05-13 23:42:07 1 Tiny change: 'difference and check' -> 'difference, and check'
en15 English bitset 2024-05-13 23:41:38 1 Tiny change: 'difference, and check' -> 'difference and check'
en14 English bitset 2024-05-13 23:39:11 7 Tiny change: 's all the std::bits' -> 's all the normal std::bits'
en13 English bitset 2024-05-13 23:37:23 17
en12 English bitset 2024-05-13 23:35:34 18
en11 English bitset 2024-05-13 23:31:33 14 Tiny change: 'mentation seems ide' -> 'mentation of the bitset seems ide'
en10 English bitset 2024-05-13 23:30:22 9 Tiny change: ' to use a max sized bit' -> ' to use a constant sized bit'
en9 English bitset 2024-05-13 23:29:46 21 Tiny change: 'er>\n\nIn problems with test cases, we migh' -> 'er>\n\nIn some problems, we migh'
en8 English bitset 2024-05-13 23:26:19 59 Tiny change: '] content.' -> '] content.\n\nThanks [user:qmk] for helping with the blog.'
en7 English bitset 2024-05-13 23:19:28 395 Tiny change: '260853192]).\n\n\nT' -> '260853192], original [submission:217308610]).\n\n\nT'
en6 English bitset 2024-05-13 23:04:10 751 Tiny change: 'main() {\n cin.tie(0)' -> 'main() {\n cin.tie(0)'
en5 English bitset 2024-05-13 22:52:28 71
en4 English bitset 2024-05-13 22:39:57 278 Tiny change: 's I saw:\n- They i' -> 's I saw:\n\n- They i'
en3 English bitset 2024-05-13 22:30:54 54
en2 English bitset 2024-05-13 22:28:59 325
en1 English bitset 2024-05-13 22:24:34 908 Initial revision (saved to drafts)