BitMagic C++ Library: APIs

February 11, 2018



Root of BitMagic API, implements bm::bvector<>. Iterators, methods and functions implementing container and main set algebraic operations. Very often, this is sufficiently enough to start working with bit sets.


Classes and methods to transform bit-vector into a compact BLOB, ready for I/O or network transfer. Tools to restore/deserialize bit-vector. Methods to perform logical operations between bit-vector and its compact, serialized BLOB.

bmalgo.h bmalho_impl.h

Algorithms with bit vectors to build various similarity/distance metrics and components of complex metrics efficiently, without producing intermediate temporary bit vectors. Logical operations between bit vectors and arrays (or STL iterators).


bm::random_subset<> - template utility to do random sampling of bit-vectors.


bm::sparse_vector<> - template container for bit-transposed arrays. Each bit plain represented as compressed bit-vector, implements a form of in-memory compression for primitive integer types.


Algorithms based on sparse vector. Dynamic range clipping, set-algebra on plains, etc.


Serialization and de-serialization of sparse vector into compact and portable BLOB.


Bit-vector container its iterators, serialization and algorithms.


Name Description Links Examples
bm::bvector<> container Main container for inverted lists representation. Depending on settings it can store lists of integers or bit-vectors. More sample1.cpp sample2.cpp sample3.cpp
bm::bvector<>::reference Accessor to use regular C++/STL operator conventions to assign container content More sample1.cpp sample9.cpp
bm::combine_*() operations Set Alebra algorithms for interoprability between arrays and bit vectors More sample7.cpp
bm::bvector<>::enumerator Constant iterator to traverse inverted list without explicit conversion into unpacked list of integers More sample5.cpp sample8.cpp
bm::bvector<>::counted_enumerator Constant iterator to traverse inverted list without explicit conversion into unpacked list of integers. It offers extra functinality of keeping a running sum of all ON bits it traversed from position 0 to current. More sample11.cpp
bm::bvector<>::insert_iterator insert iterator to feed inverted list into bit-vector More sample8.cpp
Serialization Utilities and algorithms to compress and serialize bit-vector for database storage or network transfer More sample4.cpp
Allocator API to re-define standard bvector<> alocator type to create special pool allocation strategy, thread local mamory pools, collect bit-vector related memory activity statistics, etc. More sample6.cpp
Bit counting Various methods and techniques to do bit counting for the whole bit-vector, ranges, via accelerated structures or iterations. Performance benchmarking for different methods. Details sample11.cpp
Setting bits Various methods and techniques to set bits in bit-vectors, ranges of bits, bits flipping/swapping, load bits from a set of ints, extraction of bits. Performance benchmarking for different methods. sample12.cpp
Logical operations on serialized bit-vectors Example on how to perform logical operations on bit-vecor BLOBs without necessarily materializing them into a random-access bit-vector. sample14.cpp

Algorithms for bm::bvector<>

Name Description Links Examples
Distances Algorithms optimized for computing binary distances for clusterization of multi-dimentional binary spaces. More sample9.cpp
Random sub-set Algorithm binary subset randomization. More sample10.cpp
Miscelleneous Algorithms for combining(OR, XOR, SUB, AND) bvector<> with STL-compatible iterators. Count number of intervals in bit-vector, etc. More

Sparse Vector

Name Description Links Examples
bm::sparse_vector<> container Store array of integers using compact bit-transposed implementation and the arsenal of compression methods provided by bm::bvector<> More svsample01.cpp svsample02.cpp svsample03.cpp
Serialization Algorithms to compress and serialize bm::sparse_vector<> for storage or network transfer More svsample02.cpp
Algorithms Algorithms on bit-transposed sparse vectror. Dynamic range clipping. More

Advanced techniques

Name Description Links Examples
Memory consumption / sparse sets Comparison of different methods of handling of sparse sets. Memory and performance benchmarks. Described techniques can be used for in-memory acceleration of ER JOIN operations. More xsample01.cpp