The DynamicBitset class represents a set of bits. The size of the DynamicBitset can be set at runtime via constructor or Resize method.
It supports bitwise operations with behaviour equivalent to builtin unsigned integral types. The DynamicBitset class provides ability to manipulate with bits via overloaded operator[] and At, Test member functions. It also supports iterators with proxy class for bit manipulation.
The main problem that DynamicBitset class is trying to solve is to represent a subset of finite set. For example, you can use it to represent the visited nodes in graph using BFS, DFS.
The DynamicBitset class designed to provide fast bit manipulations and space-efficient memory storage.
Important
To build tests and/or benchmarks you need to have:
- C/C++ compiler;
- CMake;
- google test package;
- google benchmark package.
The building process is configured with two options.
| Option | Supported values | Default value |
|---|---|---|
| BUILD_TESTS | ON/OFF | ON |
| BUILD_BENCHMARKS | ON/OFF | OFF |
Warning
Building the project with presets requires CMake version greater than or equal to 3.19.
The project offers the build with CMakePresets support for configuration and building process.
Supported presets can be listed with commands:
cmake --list-presets=configure
cmake --list-presets=buildWith your chosen configuration and build preset finally execute this commands:
cmake --preset <preset-type> [-D <project-options>]
cmake --build --preset <preset-type>All build artifacts and executables will be in build/<preset-type> folder.
Warning
Building the project with workflows requires CMake version greater than or equal to 3.25.
On newer CMake you can just use the single command to configure and build the project.
First of all, check the supported workflows with: cmake --list-presets=workflow
Choose your appropriate workflow and execute this command: cmake --workflow --preset <workflow-preset>
Warning
Workflows do not accept any configuration parameters and you can not pass -D<name>:<type>=<value>.
If you are going to build the benchmarks or provide additional configuration then use CMakePresets build or Regular build.
If your CMake does not support workflows or presets then you can build the project as usual.
Execute commands below with your options (if any will be specified, e.g. -DCMAKE_LINKER_TYPE=<linker-type>):
cmake [-D <project-options>] -DCMAKE_BUILD_TYPE=Release -S . -B ./build
cmake --build ./buildCaution
This class was optimized and tested for machines with Little-Endian byte ordering.
Tests are written using gtest framework and located in <build-dir>/test/bin folder with executable name test.
Run the tests with ctest to see if all working correctly: ctest --test-dir <build-dir>/test.
Benchmarks are written using google benchmark framework and located in <build-dir>/benchmark/bin directory.
All possible benchmarks to built locates in subdirectories:
- bits (bits::DynamicBitset);
- boost (boost::dynamic_bitset);
- std (std::vector<bool>).
You can run all the benchmarks available for each container by running the executable in <build-dir>/benchmark/bin/<namespace>.
Also you can provide regular expression to filter the benchmarks as with usual google benchmark executable.
To see the certain benchmarks run: ./<build-dir>/benchmark/bin/<container>/benchmark --benchmark_filter=<regex>.
Tip
Benchmarks can be filtered by testing operations, container names or even by block types.
Filtering benchmarks by block types only available for bits::DynamicBitset and boost::dynamic_bitset.
General benchmark name: [(const )<container>::<operation>].
General benchmark name example: [const bits::DynamicBitset<unsigned>::PushBack()].
Example use: --benchmark_filter='(<unsigned ?(char|short|long( long)?)?>)?::(push_back|PushBack){1}\(\)'.
List of available benchmark names
| Benchmark | Name (operation) |
|---|---|
| Default constructor | vector() dynamic_bitset() DynamicBitset() |
| Copy constructor | vector(const vector&) dynamic_bitset(const dynamic_bitset&) DynamicBitset(const DynamicBitset&) |
| Move constructor | vector(vector&&) dynamic_bitset(dynamic_bitset&&) DynamicBitset(DynamicBitset&&) |
| Copy assignment operator | operator=(const vector&) operator=(const dynamic_bitset&) operator=(const DynamicBitset&) |
| Move assignment operator | operator=(vector&&) operator=(dynamic_bitset&&) operator=(DynamicBitset&&) |
| Push back | push_back() (vector/dynamic_bitset) PushBack() (DynamicBitset) |
| Pop back | pop_back() (vector/dynamic_bitset) PopBack() (DynamicBitset) |
| Subscript operator | operator[] |
| At method | at() (vector/dynamic_bitset) At() (DynamicBitset) |
| Test method | test() (dynamic_bitset) Test() (DynamicBitset) |
| Set method | set() (dynamic_bitset) Set() (DynamicBitset) |
| Reset method | reset() (dynamic_bitset) Reset() (DynamicBitset) |
| Flip method | flip() (vector/dynamic_bitset) Flip() (DynamicBitset) |
| Swap method | swap() (vector/dynamic_bitset) Swap() (DynamicBitset) |
| All method | all() (dynamic_bitset) All() (DynamicBitset) |
| Any method | any() (dynamic_bitset) Any() (DynamicBitset) |
| None method | none() (dynamic_bitset) None() (DynamicBitset) |
| Front method | front() (vector) Front() (DynamicBitset) |
| Back method | back() (vector) Back() (DynamicBitset) |
| Count method | count() (dynamic_bitset) Count() (DynamicBitset) |
| Empty method | empty() (vector/dynamic_bitset) Empty() (DynamicBitset) |
| Size method | size() (vector/dynamic_bitset) Size() (DynamicBitset) |
| Capacity method | capacity() (vector/dynamic_bitset) Capacity() (DynamicBitset) |