Boost.DynamicBitset

Each bit represents either the Boolean value true or false (1 or 0). To set a bit is to assign it 1. To clear or reset a bit is to assign it 0. To flip a bit is to change the value to 1 if it was 0 and to 0 if it was 1. Each bit has a non-negative position. A bitset x contains x.size() bits, with each bit assigned a unique position in the range [0, x.size()). The bit at position 0 is called the least significant bit and the bit at position size() - 1 is the most significant bit. When converting an instance of dynamic_bitset to or from an unsigned integer n, the bit at position i of the bitset has the same value as (n >> i) & 1.

Because of the proxy reference type, dynamic_bitset is not a Container and its iterators do not satisfy the requirements for a LegacyForwardIterator. This means that, formally, its iterators are not usable with many standard algorithms. In practice, algorithms such as std::reverse() and std::sort() generally work, because they only need to read, assign and swap the elements, and the proxy reference supports all of that (swapping is done by an unqualified call to swap()). Moreover, dynamic_bitset provides C++20 iterators, which can be used with ranges, including the algorithms which modify the elements, such as std::ranges::fill(), std::ranges::reverse() and std::ranges::sort().

Some people prefer the name "toggle" to "flip". The name "flip" was chosen because that is the name used in std::bitset. In fact, most of the function names for dynamic_bitset were chosen for this reason.

dynamic_bitset does not throw exceptions when a precondition is violated (as is done in std::bitset). Instead BOOST_ASSERT() is used. See the guidelines for Error and Exception Handling for the explanation. Note that, consistently with this, the documentation of the member functions doesn’t use the term "precondition" for conditions that cause an exception to be emitted (the C++ standard uses the term "requires" in such cases).

The functions which have a precondition (e.g., test() and operator[]) aren’t declared noexcept, even if they can’t throw: so, an assertion handler which throws (see BOOST_ENABLE_ASSERT_HANDLER) can report a violation, e.g. in a test. The functions which have no precondition and can’t throw, such as clear(), count(), find_first() and the comparison operators, are noexcept. The default constructor, the constructor from an allocator, the move operations and swap() are noexcept if the corresponding operations of the underlying container are.

In C++20 and later, all the functions of dynamic_bitset, including those of its iterators and of its reference class, are constexpr, except the stream inserter and extractor, and the support for hashing and for Boost.Serialization. A call to them can be a constant expression only if the underlying container supports constant evaluation. So, if the standard library supports constant evaluation of std::vector (i.e., if it defines __cpp_lib_constexpr_vector), a dynamic_bitset which uses the default underlying container can be created, modified and destroyed during constant evaluation:

The constructors from a std::basic_string and to_string() also need a standard library which supports constant evaluation of std::basic_string (__cpp_lib_constexpr_string). As with std::vector, any memory allocated during a constant evaluation must be deallocated before it ends: so, in general, a dynamic_bitset can’t be a constexpr variable. A call which throws an exception (e.g., at() with an invalid position) is not a constant expression, and neither is one which violates a precondition checked by BOOST_ASSERT(), if assertions are enabled. If AllocatorOrContainer is a user-supplied container, constant evaluation is possible if that container supports it, even if std::vector doesn’t; if it’s a user-supplied allocator, that allocator must support it too.

With libstdc++ in debug mode (i.e., if _GLIBCXX_DEBUG is defined), some of the functions can’t be used in constant expressions, at least as of GCC 15, because the checks which that mode adds to standard algorithms such as std::fill() aren’t constexpr.

dynamic_bitset can be serialized with Boost.Serialization (see also serialize_impl). To do so, include <boost/dynamic_bitset/serialization.hpp> and make the underlying buffer serializable, too. For the default buffer (a std::vector), this means including <boost/serialization/vector.hpp>:

<boost/dynamic_bitset/serialization.hpp> doesn’t include any Boost.Serialization header itself, so that this library doesn’t depend on Boost.Serialization. If the second template argument of dynamic_bitset is a container, the Boost.Serialization support for that container must be visible instead. Boost.Serialization doesn’t provide it for every container (e.g., it doesn’t provide it for boost::container::small_vector): in that case, you have to write it yourself.

An archive holds the size of the bitset followed by its blocks, so it must be loaded into a dynamic_bitset with the same Block type as the saved one (a mismatch is not always detected). In particular, text and XML archives are portable only between platforms where Block has the same width: for portable archives, use a fixed-width type such as std::uint32_t rather than the default unsigned long.

Loading checks that the archive holds a valid bitset, and throws std::invalid_argument if it doesn’t. If loading throws, for this or any other reason, the bitset being loaded keeps its previous value, unless the archive throws after reading all of the data of the bitset (e.g., because an XML end tag is missing): then, it holds the loaded value.

Because loading validates the archive, a non-empty dynamic_bitset can’t be transmitted as a Boost.MPI skeleton (with boost::mpi::skeleton()): the skeleton holds the number of blocks, but not the size of the bitset, so loading it on the receiving side throws std::invalid_argument.

We would like to thank the Boost community for putting in the time to review and accept this library. This library is much better than it ever would have been due to all the suggestions from Boost members. We especially thank Matt Marcus for taking on the task of review manager. Also, a special thanks goes to James Kanze for his invaluable help with the internationalization issues.