CODEWITHSUNDEEP
c++bitset
Vovik
Vovik

Reputation: 121

Good library for bitsets or bitarrays

Hallo all, I'm looking for some good library, that works with bitsets or bitarrays. Anybody knows something better (or not worse in all cases) then boost::dynamic_bitset? No matter if the library is open source or commercial.

In my project it is a common task to store and work with large bit masks, that contain less number of ones. So they could be compressed well in memory.

Upvotes: 5

Views: 2408

Answers (3)

rniekisch
rniekisch

Reputation: 71

There are several implementations of compressed bitvectors available. They usually feature a run length encoding together with and/or/xor/not operations which work on the compressed form.

So the benefits are:

  • smaller space usage (for sparse bitsets, as in your use case)
  • very fast bit operations (because they work on words and are far more cpu cache friendly)

and on the downside:

  • slower bit access (iteration required to find a bit at a specific position)

Some implementations i am aware of (there are others i am sure):

Fastbit Is in fact a database using a bitvector index. The compressed bitvector class can be used directly (without the indexing)

Lemur bitmapindex Another implementation of the EWAH encoding introduced by Fastbit

Compressed bitvector by koen.vandamme Never tried it...but only two headers and a cpp file. So not much effort to give it a try.

Bitmagic Full blown package implementing several compressed bitvectors including hardware support (sse2, ...)


Hope this helps,

Roland

Upvotes: 7

Vatsan
Vatsan

Reputation: 1173

If all you are looking for is space optimization, then std::vector provides a vector specialization that's optimized for space.

http://www.cplusplus.com/reference/stl/vector/

and C++ standard 23.2.5

No idea if this is better than boost:dynamic_bitset, but it's worth investigating if you haven't already looked into it.

Upvotes: 0

Schedler
Schedler

Reputation: 1413

How about MiniSAT libraries?

http://minisat.se/

I recall this having a simple implementation for bit arrays.

Upvotes: 0

Related Questions