dynamic_bitset 1.3.3
Simple Useful Libraries: C++17/20 header-only dynamic bitset
Loading...
Searching...
No Matches
dynamic_bitset.hpp
Go to the documentation of this file.
1//
2// Copyright (c) 2019 Maxime Pinard
3//
4// Distributed under the MIT license
5// See accompanying file LICENSE or copy at
6// https://opensource.org/licenses/MIT
7//
8#ifndef SUL_DYNAMIC_BITSET_HPP
9#define SUL_DYNAMIC_BITSET_HPP
10
16#define SUL_DYNAMIC_BITSET_VERSION_MAJOR 1
17
23#define SUL_DYNAMIC_BITSET_VERSION_MINOR 3
24
30#define SUL_DYNAMIC_BITSET_VERSION_PATCH 3
31
45
46#include <algorithm>
47#include <cassert>
48#include <cmath>
49#include <functional>
50#include <limits>
51#include <memory>
52#include <stdexcept>
53#include <string>
54#include <string_view>
55#include <type_traits>
56#include <vector>
57
58// define DYNAMIC_BITSET_CAN_USE_LIBPOPCNT
59#if !defined(DYNAMIC_BITSET_NO_LIBPOPCNT)
60// https://github.com/kimwalisch/libpopcnt
61# if __has_include(<libpopcnt.h>)
62# include <libpopcnt.h>
63# define DYNAMIC_BITSET_CAN_USE_LIBPOPCNT true
64# endif
65#endif
66#if !defined(DYNAMIC_BITSET_CAN_USE_LIBPOPCNT)
67# define DYNAMIC_BITSET_CAN_USE_LIBPOPCNT false
68#endif
69
70// define DYNAMIC_BITSET_CAN_USE_STD_BITOPS
71#if !defined(DYNAMIC_BITSET_NO_STD_BITOPS)
72// https://en.cppreference.com/w/cpp/header/bit
73# if __has_include(<bit>)
74# include <bit>
75# ifdef __cpp_lib_bitops
76# define DYNAMIC_BITSET_CAN_USE_STD_BITOPS true
77# endif
78# endif
79#endif
80#if !defined(DYNAMIC_BITSET_CAN_USE_STD_BITOPS)
81# define DYNAMIC_BITSET_CAN_USE_STD_BITOPS false
82#endif
83
84// define DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_POPCOUNT
85// define DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_CTZ
86// define DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN
87// define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD
88// define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD64
89#if !DYNAMIC_BITSET_CAN_USE_STD_BITOPS && !defined(DYNAMIC_BITSET_NO_COMPILER_BUILTIN)
90# if defined(__clang__)
91// https://clang.llvm.org/docs/LanguageExtensions.html#feature-checking-macros
92// https://clang.llvm.org/docs/LanguageExtensions.html#intrinsics-support-within-constant-expressions
93# ifdef __has_builtin
94# if __has_builtin(__builtin_popcount) && __has_builtin(__builtin_popcountl) \
95 && __has_builtin(__builtin_popcountll)
96# define DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_POPCOUNT true
97# endif
98# if __has_builtin(__builtin_ctz) && __has_builtin(__builtin_ctzl) && __has_builtin(__builtin_ctzll)
99# define DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_CTZ true
100# endif
101# endif
102# elif defined(__GNUC__) // also defined by clang
103// https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
104# define DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN true
105# elif defined(_MSC_VER)
106// https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanforward-bitscanforward64
107// __popcnt16, __popcnt, __popcnt64 not used because it require to check the hardware support at runtime
108// (https://docs.microsoft.com/fr-fr/cpp/intrinsics/popcnt16-popcnt-popcnt64?view=msvc-160#remarks)
109# if defined(_M_IX86) || defined(_M_ARM) || defined(_M_X64) || defined(_M_ARM64)
110# include <intrin.h>
111# pragma intrinsic(_BitScanForward)
112# define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD true
113# endif
114# if(defined(_M_X64) || defined(_M_ARM64)) \
115 && !defined(DYNAMIC_BITSET_NO_MSVC_BUILTIN_BITSCANFORWARD64) // for testing purposes
116# pragma intrinsic(_BitScanForward64)
117# define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD64 true
118# endif
119# endif
120#endif
121#if !defined(DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_POPCOUNT)
122# define DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_POPCOUNT false
123#endif
124#if !defined(DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_CTZ)
125# define DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_CTZ false
126#endif
127#if !defined(DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN)
128# define DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN false
129#endif
130#if !defined(DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD)
131# define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD false
132#endif
133#if !defined(DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD64)
134# define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD64 false
135#endif
136#if !defined(DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN)
137# define DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN false
138#endif
139
140#ifndef DYNAMIC_BITSET_NO_NAMESPACE
146namespace sul
147{
148#endif
149
169 template<typename Block = unsigned long long, typename Allocator = std::allocator<Block>>
170 class dynamic_bitset
171 {
172 static_assert(std::is_unsigned<Block>::value, "Block is not an unsigned integral type");
173
174 public:
180 typedef size_t size_type;
181
187 typedef Block block_type;
188
194 typedef Allocator allocator_type;
195
201 static constexpr size_type bits_per_block = std::numeric_limits<block_type>::digits;
202
208 static constexpr size_type npos = std::numeric_limits<size_type>::max();
209
220 class reference
221 {
222 public:
234 constexpr reference(dynamic_bitset<Block, Allocator>& bitset, size_type bit_pos);
235
241 constexpr reference(const reference&) noexcept = default;
242
248 constexpr reference(reference&&) noexcept = default;
249
255 ~reference() noexcept = default;
256
268 constexpr reference& operator=(bool v);
269
281 constexpr reference& operator=(const reference& rhs);
282
294 constexpr reference& operator=(reference&& rhs) noexcept;
295
308 constexpr reference& operator&=(bool v);
309
322 constexpr reference& operator|=(bool v);
323
336 constexpr reference& operator^=(bool v);
337
355 constexpr reference& operator-=(bool v);
356
366 [[nodiscard]] constexpr bool operator~() const;
367
375 [[nodiscard]] constexpr operator bool() const;
376
382 constexpr void operator&() = delete;
383
393 constexpr reference& set();
394
404 constexpr reference& reset();
405
415 constexpr reference& flip();
416
428 constexpr reference& assign(bool v);
429
430 private:
431 block_type& m_block;
432 block_type m_mask;
433 };
434
440 typedef bool const_reference;
441
447 constexpr dynamic_bitset(const dynamic_bitset<Block, Allocator>& other) = default;
448
454 constexpr dynamic_bitset(dynamic_bitset<Block, Allocator>&& other) noexcept = default;
455
461 constexpr dynamic_bitset<Block, Allocator>& operator=(const dynamic_bitset<Block, Allocator>& other) = default;
462
468 constexpr dynamic_bitset<Block, Allocator>&
469 operator=(dynamic_bitset<Block, Allocator>&& other) noexcept = default;
470
482 constexpr explicit dynamic_bitset(const allocator_type& allocator = allocator_type());
483
500 constexpr explicit dynamic_bitset(size_type nbits,
501 unsigned long long init_val = 0,
502 const allocator_type& allocator = allocator_type());
503
518 constexpr dynamic_bitset(std::initializer_list<block_type> init_vals,
519 const allocator_type& allocator = allocator_type());
520
546 template<typename _CharT, typename _Traits>
547 constexpr explicit dynamic_bitset(
548 std::basic_string_view<_CharT, _Traits> str,
549 typename std::basic_string_view<_CharT, _Traits>::size_type pos = 0,
550 typename std::basic_string_view<_CharT, _Traits>::size_type n = std::basic_string_view<_CharT, _Traits>::npos,
551 _CharT zero = _CharT('0'),
552 _CharT one = _CharT('1'),
553 const allocator_type& allocator = allocator_type());
554
581 template<typename _CharT, typename _Traits, typename _Alloc>
582 constexpr explicit dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc>& str,
583 typename std::basic_string<_CharT, _Traits, _Alloc>::size_type pos = 0,
584 typename std::basic_string<_CharT, _Traits, _Alloc>::size_type n =
585 std::basic_string<_CharT, _Traits, _Alloc>::npos,
586 _CharT zero = _CharT('0'),
587 _CharT one = _CharT('1'),
588 const allocator_type& allocator = allocator_type());
589
615 template<typename _CharT, typename _Traits = std::char_traits<_CharT>>
616 constexpr explicit dynamic_bitset(
617 const _CharT* str,
618 typename std::basic_string<_CharT>::size_type pos = 0,
619 typename std::basic_string<_CharT>::size_type n = std::basic_string<_CharT>::npos,
620 _CharT zero = _CharT('0'),
621 _CharT one = _CharT('1'),
622 const allocator_type& allocator = allocator_type());
623
629 ~dynamic_bitset() noexcept = default;
630
646 constexpr void resize(size_type nbits, bool value = false);
647
660 constexpr void clear();
661
674 constexpr void push_back(bool value);
675
686 constexpr void pop_back();
687
699 constexpr void append(block_type block);
700
712 constexpr void append(std::initializer_list<block_type> blocks);
713
729 template<typename BlockInputIterator>
730 constexpr void append(BlockInputIterator first, BlockInputIterator last);
731
748 constexpr dynamic_bitset<Block, Allocator>& operator&=(const dynamic_bitset<Block, Allocator>& rhs);
749
766 constexpr dynamic_bitset<Block, Allocator>& operator|=(const dynamic_bitset<Block, Allocator>& rhs);
767
784 constexpr dynamic_bitset<Block, Allocator>& operator^=(const dynamic_bitset<Block, Allocator>& rhs);
785
807 constexpr dynamic_bitset<Block, Allocator>& operator-=(const dynamic_bitset<Block, Allocator>& rhs);
808
822 constexpr dynamic_bitset<Block, Allocator>& operator<<=(size_type shift);
823
837 constexpr dynamic_bitset<Block, Allocator>& operator>>=(size_type shift);
838
857 [[nodiscard]] constexpr dynamic_bitset<Block, Allocator> operator<<(size_type shift) const;
858
877 [[nodiscard]] constexpr dynamic_bitset<Block, Allocator> operator>>(size_type shift) const;
878
894 [[nodiscard]] constexpr dynamic_bitset<Block, Allocator> operator~() const;
895
915 constexpr dynamic_bitset<Block, Allocator>& set(size_type pos, size_type len, bool value);
916
933 constexpr dynamic_bitset<Block, Allocator>& set(size_type pos, bool value = true);
934
944 constexpr dynamic_bitset<Block, Allocator>& set();
945
962 constexpr dynamic_bitset<Block, Allocator>& reset(size_type pos, size_type len);
963
979 constexpr dynamic_bitset<Block, Allocator>& reset(size_type pos);
980
990 constexpr dynamic_bitset<Block, Allocator>& reset();
991
1008 constexpr dynamic_bitset<Block, Allocator>& flip(size_type pos, size_type len);
1009
1025 constexpr dynamic_bitset<Block, Allocator>& flip(size_type pos);
1026
1036 constexpr dynamic_bitset<Block, Allocator>& flip();
1037
1053 [[nodiscard]] constexpr bool test(size_type pos) const;
1054
1072 [[nodiscard]] constexpr bool test_set(size_type pos, bool value = true);
1073
1087 [[nodiscard]] constexpr bool all() const;
1088
1102 [[nodiscard]] constexpr bool any() const;
1103
1117 [[nodiscard]] constexpr bool none() const;
1118
1130 [[nodiscard]] constexpr size_type count() const noexcept;
1131
1147 [[nodiscard]] constexpr reference operator[](size_type pos);
1148
1164 [[nodiscard]] constexpr const_reference operator[](size_type pos) const;
1165
1175 [[nodiscard]] constexpr size_type size() const noexcept;
1176
1186 [[nodiscard]] constexpr size_type num_blocks() const noexcept;
1187
1202 [[nodiscard]] constexpr bool empty() const noexcept;
1203
1214 [[nodiscard]] constexpr size_type capacity() const noexcept;
1215
1230 constexpr void reserve(size_type num_bits);
1231
1244 constexpr void shrink_to_fit();
1245
1274 [[nodiscard]] constexpr bool is_subset_of(const dynamic_bitset<Block, Allocator>& bitset) const;
1275
1304 [[nodiscard]] constexpr bool is_proper_subset_of(const dynamic_bitset<Block, Allocator>& bitset) const;
1305
1331 [[nodiscard]] constexpr bool intersects(const dynamic_bitset<Block, Allocator>& bitset) const;
1332
1346 [[nodiscard]] constexpr size_type find_first() const;
1347
1365 [[nodiscard]] constexpr size_type find_next(size_type prev) const;
1366
1378 constexpr void
1379 swap(dynamic_bitset<Block, Allocator>& other) noexcept(noexcept(std::swap(m_blocks, other.m_blocks)));
1380
1390 [[nodiscard]] constexpr allocator_type get_allocator() const;
1391
1414 template<typename _CharT = char,
1415 typename _Traits = std::char_traits<_CharT>,
1416 typename _Alloc = std::allocator<_CharT>>
1417 [[nodiscard]] constexpr std::basic_string<_CharT, _Traits, _Alloc> to_string(_CharT zero = _CharT('0'),
1418 _CharT one = _CharT('1')) const;
1419
1435 [[nodiscard]] constexpr unsigned long to_ulong() const;
1436
1452 [[nodiscard]] constexpr unsigned long long to_ullong() const;
1453
1481 template<typename Function, typename... Parameters>
1482 constexpr void iterate_bits_on(Function&& function, Parameters&&... parameters) const;
1483
1518 [[nodiscard]] constexpr block_type* data() noexcept;
1519
1554 [[nodiscard]] constexpr const block_type* data() const noexcept;
1555
1571 template<typename Block_, typename Allocator_>
1572 friend constexpr bool operator==(const dynamic_bitset<Block_, Allocator_>& lhs,
1573 const dynamic_bitset<Block_, Allocator_>& rhs);
1574
1621 template<typename Block_, typename Allocator_>
1622 friend constexpr bool operator<(const dynamic_bitset<Block_, Allocator_>& lhs,
1623 const dynamic_bitset<Block_, Allocator_>& rhs);
1624
1625 private:
1626 template<typename T>
1627 struct dependent_false : public std::false_type
1628 {
1629 };
1630
1631 std::vector<Block, Allocator> m_blocks;
1632 size_type m_bits_number;
1633
1634 static constexpr block_type zero_block = block_type(0);
1635 static constexpr block_type one_block = block_type(~zero_block);
1636 static constexpr size_type block_last_bit_index = bits_per_block - 1;
1637
1638 static constexpr size_type blocks_required(size_type nbits) noexcept;
1639
1640 static constexpr size_type block_index(size_type pos) noexcept;
1641 static constexpr size_type bit_index(size_type pos) noexcept;
1642
1643 static constexpr block_type bit_mask(size_type pos) noexcept;
1644 static constexpr block_type bit_mask(size_type first, size_type last) noexcept;
1645
1646 static constexpr void
1647 set_block_bits(block_type& block, size_type first, size_type last, bool val = true) noexcept;
1648 static constexpr void flip_block_bits(block_type& block, size_type first, size_type last) noexcept;
1649
1650 static constexpr size_type block_count(const block_type& block) noexcept;
1651 static constexpr size_type block_count(const block_type& block, size_type nbits) noexcept;
1652
1653 static constexpr size_type count_block_trailing_zero(const block_type& block) noexcept;
1654
1655 template<typename _CharT, typename _Traits>
1656 constexpr void init_from_string(std::basic_string_view<_CharT, _Traits> str,
1657 typename std::basic_string_view<_CharT, _Traits>::size_type pos,
1658 typename std::basic_string_view<_CharT, _Traits>::size_type n,
1659 _CharT zero,
1660 _CharT one);
1661
1662 constexpr block_type& get_block(size_type pos);
1663 constexpr const block_type& get_block(size_type pos) const;
1664 constexpr block_type& last_block();
1665 constexpr block_type last_block() const;
1666
1667 // used bits in the last block
1668 constexpr size_type extra_bits_number() const noexcept;
1669 // unused bits in the last block
1670 constexpr size_type unused_bits_number() const noexcept;
1671
1672 template<typename BinaryOperation>
1673 constexpr void apply(const dynamic_bitset<Block, Allocator>& other, BinaryOperation binary_op);
1674 template<typename UnaryOperation>
1675 constexpr void apply(UnaryOperation unary_op);
1676 constexpr void apply_left_shift(size_type shift);
1677 constexpr void apply_right_shift(size_type shift);
1678
1679 // reset unused bits to 0
1680 constexpr void sanitize();
1681
1682 // check functions used in asserts
1683 constexpr bool check_unused_bits() const noexcept;
1684 constexpr bool check_size() const noexcept;
1685 constexpr bool check_consistency() const noexcept;
1686 };
1687
1688 // Deduction guideline for expressions like "dynamic_bitset a(32);" with an integral type as parameter
1689 // to use the constructor with the initial size instead of the constructor with the allocator.
1690 template<typename integral_type, typename = std::enable_if_t<std::is_integral_v<integral_type>>>
1691 dynamic_bitset(integral_type) -> dynamic_bitset<>;
1692
1693 //=================================================================================================
1694 // dynamic_bitset external functions declarations
1695 //=================================================================================================
1696
1720 template<typename Block, typename Allocator>
1721 constexpr bool operator!=(const dynamic_bitset<Block, Allocator>& lhs, const dynamic_bitset<Block, Allocator>& rhs);
1722
1747 template<typename Block, typename Allocator>
1748 constexpr bool operator<=(const dynamic_bitset<Block, Allocator>& lhs, const dynamic_bitset<Block, Allocator>& rhs);
1749
1775 template<typename Block, typename Allocator>
1776 constexpr bool operator>(const dynamic_bitset<Block, Allocator>& lhs, const dynamic_bitset<Block, Allocator>& rhs);
1777
1803 template<typename Block, typename Allocator>
1804 constexpr bool operator>=(const dynamic_bitset<Block, Allocator>& lhs, const dynamic_bitset<Block, Allocator>& rhs);
1805
1835 template<typename Block, typename Allocator>
1836 constexpr dynamic_bitset<Block, Allocator> operator&(const dynamic_bitset<Block, Allocator>& lhs,
1837 const dynamic_bitset<Block, Allocator>& rhs);
1838
1868 template<typename Block, typename Allocator>
1869 constexpr dynamic_bitset<Block, Allocator> operator|(const dynamic_bitset<Block, Allocator>& lhs,
1870 const dynamic_bitset<Block, Allocator>& rhs);
1871
1901 template<typename Block, typename Allocator>
1902 constexpr dynamic_bitset<Block, Allocator> operator^(const dynamic_bitset<Block, Allocator>& lhs,
1903 const dynamic_bitset<Block, Allocator>& rhs);
1904
1934 template<typename Block, typename Allocator>
1935 constexpr dynamic_bitset<Block, Allocator> operator-(const dynamic_bitset<Block, Allocator>& lhs,
1936 const dynamic_bitset<Block, Allocator>& rhs);
1937
1963 template<typename _CharT, typename _Traits, typename Block, typename Allocator>
1964 constexpr std::basic_ostream<_CharT, _Traits>& operator<<(std::basic_ostream<_CharT, _Traits>& os,
1965 const dynamic_bitset<Block, Allocator>& bitset);
1966
1995 template<typename _CharT, typename _Traits, typename Block, typename Allocator>
1996 constexpr std::basic_istream<_CharT, _Traits>& operator>>(std::basic_istream<_CharT, _Traits>& is,
1997 dynamic_bitset<Block, Allocator>& bitset);
1998
2020 template<typename Block, typename Allocator>
2021 constexpr void swap(dynamic_bitset<Block, Allocator>& bitset1,
2022 dynamic_bitset<Block, Allocator>& bitset2) noexcept(noexcept(bitset1.swap(bitset2)));
2023
2024 //=================================================================================================
2025 // dynamic_bitset::reference functions implementations
2026 //=================================================================================================
2027
2028 template<typename Block, typename Allocator>
2029 constexpr dynamic_bitset<Block, Allocator>::reference::reference(dynamic_bitset<Block, Allocator>& bitset,
2030 size_type bit_pos)
2031 : m_block(bitset.get_block(bit_pos))
2032 , m_mask(dynamic_bitset<Block, Allocator>::bit_mask(bit_pos))
2033 {
2034 }
2035
2036 template<typename Block, typename Allocator>
2037 constexpr typename dynamic_bitset<Block, Allocator>::reference&
2038 dynamic_bitset<Block, Allocator>::reference::operator=(bool v)
2039 {
2040 assign(v);
2041 return *this;
2042 }
2043
2044 template<typename Block, typename Allocator>
2045 constexpr typename dynamic_bitset<Block, Allocator>::reference&
2046 dynamic_bitset<Block, Allocator>::reference::operator=(const dynamic_bitset<Block, Allocator>::reference& rhs)
2047 {
2048 assign(rhs);
2049 return *this;
2050 }
2051
2052 template<typename Block, typename Allocator>
2053 constexpr typename dynamic_bitset<Block, Allocator>::reference&
2054 dynamic_bitset<Block, Allocator>::reference::operator=(dynamic_bitset::reference&& rhs) noexcept
2055 {
2056 assign(rhs);
2057 return *this;
2058 }
2059
2060 template<typename Block, typename Allocator>
2061 constexpr typename dynamic_bitset<Block, Allocator>::reference&
2062 dynamic_bitset<Block, Allocator>::reference::operator&=(bool v)
2063 {
2064 if(!v)
2065 {
2066 reset();
2067 }
2068 return *this;
2069 }
2070
2071 template<typename Block, typename Allocator>
2072 constexpr typename dynamic_bitset<Block, Allocator>::reference&
2073 dynamic_bitset<Block, Allocator>::reference::operator|=(bool v)
2074 {
2075 if(v)
2076 {
2077 set();
2078 }
2079 return *this;
2080 }
2081
2082 template<typename Block, typename Allocator>
2083 constexpr typename dynamic_bitset<Block, Allocator>::reference&
2084 dynamic_bitset<Block, Allocator>::reference::operator^=(bool v)
2085 {
2086 if(v)
2087 {
2088 flip();
2089 }
2090 return *this;
2091 }
2092
2093 template<typename Block, typename Allocator>
2094 constexpr typename dynamic_bitset<Block, Allocator>::reference&
2095 dynamic_bitset<Block, Allocator>::reference::operator-=(bool v)
2096 {
2097 if(v)
2098 {
2099 reset();
2100 }
2101 return *this;
2102 }
2103
2104 template<typename Block, typename Allocator>
2105 constexpr bool dynamic_bitset<Block, Allocator>::reference::operator~() const
2106 {
2107 return (m_block & m_mask) == zero_block;
2108 }
2109
2110 template<typename Block, typename Allocator>
2111 constexpr dynamic_bitset<Block, Allocator>::reference::operator bool() const
2112 {
2113 return (m_block & m_mask) != zero_block;
2114 }
2115
2116 template<typename Block, typename Allocator>
2117 constexpr typename dynamic_bitset<Block, Allocator>::reference& dynamic_bitset<Block, Allocator>::reference::set()
2118 {
2119 m_block |= m_mask;
2120 return *this;
2121 }
2122
2123 template<typename Block, typename Allocator>
2124 constexpr typename dynamic_bitset<Block, Allocator>::reference& dynamic_bitset<Block, Allocator>::reference::reset()
2125 {
2126 m_block &= static_cast<block_type>(~m_mask);
2127 return *this;
2128 }
2129
2130 template<typename Block, typename Allocator>
2131 constexpr typename dynamic_bitset<Block, Allocator>::reference& dynamic_bitset<Block, Allocator>::reference::flip()
2132 {
2133 m_block ^= m_mask;
2134 return *this;
2135 }
2136
2137 template<typename Block, typename Allocator>
2138 constexpr typename dynamic_bitset<Block, Allocator>::reference&
2139 dynamic_bitset<Block, Allocator>::reference::assign(bool v)
2140 {
2141 if(v)
2142 {
2143 set();
2144 }
2145 else
2146 {
2147 reset();
2148 }
2149 return *this;
2150 }
2151
2152 //=================================================================================================
2153 // dynamic_bitset public functions implementations
2154 //=================================================================================================
2155
2156 template<typename Block, typename Allocator>
2157 constexpr dynamic_bitset<Block, Allocator>::dynamic_bitset(const allocator_type& allocator)
2158 : m_blocks(allocator)
2159 , m_bits_number(0)
2160 {
2161 }
2162
2163 template<typename Block, typename Allocator>
2164 constexpr dynamic_bitset<Block, Allocator>::dynamic_bitset(size_type nbits,
2165 unsigned long long init_val,
2166 const allocator_type& allocator)
2167 : m_blocks(blocks_required(nbits), allocator)
2168 , m_bits_number(nbits)
2169 {
2170 if(nbits == 0 || init_val == 0)
2171 {
2172 return;
2173 }
2174
2175 constexpr size_t ull_bits_number = std::numeric_limits<unsigned long long>::digits;
2176 constexpr size_t init_val_required_blocks = ull_bits_number / bits_per_block;
2177 if constexpr(init_val_required_blocks == 1)
2178 {
2179 m_blocks[0] = init_val;
2180 }
2181 else
2182 {
2183 const unsigned long long block_mask = static_cast<unsigned long long>(one_block);
2184 const size_t blocks_to_init = std::min(m_blocks.size(), init_val_required_blocks);
2185 for(size_t i = 0; i < blocks_to_init; ++i)
2186 {
2187 m_blocks[i] = block_type((init_val >> (i * bits_per_block) & block_mask));
2188 }
2189 }
2190 sanitize();
2191 }
2192
2193 template<typename Block, typename Allocator>
2194 constexpr dynamic_bitset<Block, Allocator>::dynamic_bitset(std::initializer_list<block_type> init_vals,
2195 const allocator_type& allocator)
2196 : m_blocks(allocator)
2197 , m_bits_number(0)
2198 {
2199 append(init_vals);
2200 }
2201
2202 template<typename Block, typename Allocator>
2203 template<typename _CharT, typename _Traits>
2204 constexpr dynamic_bitset<Block, Allocator>::dynamic_bitset(
2205 std::basic_string_view<_CharT, _Traits> str,
2206 typename std::basic_string_view<_CharT, _Traits>::size_type pos,
2207 typename std::basic_string_view<_CharT, _Traits>::size_type n,
2208 _CharT zero,
2209 _CharT one,
2210 const allocator_type& allocator)
2211 : m_blocks(allocator)
2212 , m_bits_number(0)
2213 {
2214 assert(pos < str.size());
2215 init_from_string(str, pos, n, zero, one);
2216 }
2217
2218 template<typename Block, typename Allocator>
2219 template<typename _CharT, typename _Traits, typename _Alloc>
2220 constexpr dynamic_bitset<Block, Allocator>::dynamic_bitset(
2221 const std::basic_string<_CharT, _Traits, _Alloc>& str,
2222 typename std::basic_string<_CharT, _Traits, _Alloc>::size_type pos,
2223 typename std::basic_string<_CharT, _Traits, _Alloc>::size_type n,
2224 _CharT zero,
2225 _CharT one,
2226 const allocator_type& allocator)
2227 : m_blocks(allocator)
2228 , m_bits_number(0)
2229 {
2230 assert(pos < str.size());
2231 init_from_string(std::basic_string_view<_CharT, _Traits>(str), pos, n, zero, one);
2232 }
2233
2234 template<typename Block, typename Allocator>
2235 template<typename _CharT, typename _Traits>
2236 constexpr dynamic_bitset<Block, Allocator>::dynamic_bitset(const _CharT* str,
2237 typename std::basic_string<_CharT>::size_type pos,
2238 typename std::basic_string<_CharT>::size_type n,
2239 _CharT zero,
2240 _CharT one,
2241 const allocator_type& allocator)
2242 : m_blocks(allocator)
2243 , m_bits_number(0)
2244 {
2245 init_from_string(std::basic_string_view<_CharT, _Traits>(str), pos, n, zero, one);
2246 }
2247
2248 template<typename Block, typename Allocator>
2249 constexpr void dynamic_bitset<Block, Allocator>::resize(size_type nbits, bool value)
2250 {
2251 if(nbits == m_bits_number)
2252 {
2253 return;
2254 }
2255
2256 const size_type old_num_blocks = num_blocks();
2257 const size_type new_num_blocks = blocks_required(nbits);
2258
2259 const block_type init_value = value ? one_block : zero_block;
2260 if(new_num_blocks != old_num_blocks)
2261 {
2262 m_blocks.resize(new_num_blocks, init_value);
2263 }
2264
2265 if(value && nbits > m_bits_number && old_num_blocks > 0)
2266 {
2267 // set value of the new bits in the old last block
2268 const size_type extra_bits = extra_bits_number();
2269 if(extra_bits > 0)
2270 {
2271 m_blocks[old_num_blocks - 1] |= static_cast<block_type>(init_value << extra_bits);
2272 }
2273 }
2274
2275 m_bits_number = nbits;
2276 sanitize();
2277 assert(check_consistency());
2278 }
2279
2280 template<typename Block, typename Allocator>
2281 constexpr void dynamic_bitset<Block, Allocator>::clear()
2282 {
2283 m_blocks.clear();
2284 m_bits_number = 0;
2285 }
2286
2287 template<typename Block, typename Allocator>
2288 constexpr void dynamic_bitset<Block, Allocator>::push_back(bool value)
2289 {
2290 const size_type new_last_bit = m_bits_number++;
2291 if(m_bits_number <= m_blocks.size() * bits_per_block)
2292 {
2293 if(value)
2294 {
2295 set(new_last_bit, value);
2296 }
2297 }
2298 else
2299 {
2300 m_blocks.push_back(block_type(value));
2301 }
2302 assert(operator[](new_last_bit) == value);
2303 assert(check_consistency());
2304 }
2305
2306 template<typename Block, typename Allocator>
2307 constexpr void dynamic_bitset<Block, Allocator>::pop_back()
2308 {
2309 if(empty())
2310 {
2311 return;
2312 }
2313
2314 --m_bits_number;
2315 if(m_blocks.size() > blocks_required(m_bits_number))
2316 {
2317 m_blocks.pop_back();
2318 // no extra bits: sanitize not required
2319 assert(extra_bits_number() == 0);
2320 }
2321 else
2322 {
2323 sanitize();
2324 }
2325 assert(check_consistency());
2326 }
2327
2328 template<typename Block, typename Allocator>
2329 constexpr void dynamic_bitset<Block, Allocator>::append(block_type block)
2330 {
2331 const size_type extra_bits = extra_bits_number();
2332 if(extra_bits == 0)
2333 {
2334 m_blocks.push_back(block);
2335 }
2336 else
2337 {
2338 last_block() |= static_cast<block_type>(block << extra_bits);
2339 m_blocks.push_back(block_type(block >> (bits_per_block - extra_bits)));
2340 }
2341
2342 m_bits_number += bits_per_block;
2343 assert(check_consistency());
2344 }
2345
2346 template<typename Block, typename Allocator>
2347 constexpr void dynamic_bitset<Block, Allocator>::append(std::initializer_list<block_type> blocks)
2348 {
2349 if(blocks.size() == 0)
2350 {
2351 return;
2352 }
2353
2354 append(std::cbegin(blocks), std::cend(blocks));
2355 }
2356
2357 template<typename Block, typename Allocator>
2358 template<typename BlockInputIterator>
2359 constexpr void dynamic_bitset<Block, Allocator>::append(BlockInputIterator first, BlockInputIterator last)
2360 {
2361 if(first == last)
2362 {
2363 return;
2364 }
2365
2366 // if random access iterators, std::distance complexity is constant
2367 if constexpr(std::is_same_v<typename std::iterator_traits<BlockInputIterator>::iterator_category,
2368 std::random_access_iterator_tag>)
2369 {
2370 assert(std::distance(first, last) > 0);
2371 m_blocks.reserve(m_blocks.size() + static_cast<size_type>(std::distance(first, last)));
2372 }
2373
2374 const size_type extra_bits = extra_bits_number();
2375 const size_type unused_bits = unused_bits_number();
2376 if(extra_bits == 0)
2377 {
2378 auto pos = m_blocks.insert(std::end(m_blocks), first, last);
2379 assert(std::distance(pos, std::end(m_blocks)) > 0);
2380 m_bits_number += static_cast<size_type>(std::distance(pos, std::end(m_blocks))) * bits_per_block;
2381 }
2382 else
2383 {
2384 last_block() |= static_cast<block_type>(*first << extra_bits);
2385 block_type block = block_type(*first >> unused_bits);
2386 ++first;
2387 while(first != last)
2388 {
2389 block |= static_cast<block_type>(*first << extra_bits);
2390 m_blocks.push_back(block);
2391 m_bits_number += bits_per_block;
2392 block = block_type(*first >> unused_bits);
2393 ++first;
2394 }
2395 m_blocks.push_back(block);
2396 m_bits_number += bits_per_block;
2397 }
2398
2399 assert(check_consistency());
2400 }
2401
2402 template<typename Block, typename Allocator>
2403 constexpr dynamic_bitset<Block, Allocator>&
2404 dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset<Block, Allocator>& rhs)
2405 {
2406 assert(size() == rhs.size());
2407 // apply(rhs, std::bit_and());
2408 for(size_type i = 0; i < m_blocks.size(); ++i)
2409 {
2410 m_blocks[i] &= rhs.m_blocks[i];
2411 }
2412 return *this;
2413 }
2414
2415 template<typename Block, typename Allocator>
2416 constexpr dynamic_bitset<Block, Allocator>&
2417 dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset<Block, Allocator>& rhs)
2418 {
2419 assert(size() == rhs.size());
2420 // apply(rhs, std::bit_or());
2421 for(size_type i = 0; i < m_blocks.size(); ++i)
2422 {
2423 m_blocks[i] |= rhs.m_blocks[i];
2424 }
2425 return *this;
2426 }
2427
2428 template<typename Block, typename Allocator>
2429 constexpr dynamic_bitset<Block, Allocator>&
2430 dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset<Block, Allocator>& rhs)
2431 {
2432 assert(size() == rhs.size());
2433 // apply(rhs, std::bit_xor());
2434 for(size_type i = 0; i < m_blocks.size(); ++i)
2435 {
2436 m_blocks[i] ^= rhs.m_blocks[i];
2437 }
2438 return *this;
2439 }
2440
2441 template<typename Block, typename Allocator>
2442 constexpr dynamic_bitset<Block, Allocator>&
2443 dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset<Block, Allocator>& rhs)
2444 {
2445 assert(size() == rhs.size());
2446 // apply(rhs, [](const block_type& x, const block_type& y) { return (x & ~y); });
2447 for(size_type i = 0; i < m_blocks.size(); ++i)
2448 {
2449 m_blocks[i] &= static_cast<block_type>(~rhs.m_blocks[i]);
2450 }
2451 return *this;
2452 }
2453
2454 template<typename Block, typename Allocator>
2455 constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::operator<<=(size_type shift)
2456 {
2457 if(shift != 0)
2458 {
2459 if(shift >= m_bits_number)
2460 {
2461 reset();
2462 }
2463 else
2464 {
2465 apply_left_shift(shift);
2466 sanitize(); // unused bits can have changed, reset them to 0
2467 }
2468 }
2469 return *this;
2470 }
2471
2472 template<typename Block, typename Allocator>
2473 constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::operator>>=(size_type shift)
2474 {
2475 if(shift != 0)
2476 {
2477 if(shift >= m_bits_number)
2478 {
2479 reset();
2480 }
2481 else
2482 {
2483 apply_right_shift(shift);
2484 }
2485 }
2486 return *this;
2487 }
2488
2489 template<typename Block, typename Allocator>
2494
2495 template<typename Block, typename Allocator>
2500
2501 template<typename Block, typename Allocator>
2502 constexpr dynamic_bitset<Block, Allocator> dynamic_bitset<Block, Allocator>::operator~() const
2503 {
2504 dynamic_bitset<Block, Allocator> bitset(*this);
2505 bitset.flip();
2506 return bitset;
2507 }
2508
2509 template<typename Block, typename Allocator>
2510 constexpr dynamic_bitset<Block, Allocator>&
2511 dynamic_bitset<Block, Allocator>::set(size_type pos, size_type len, bool value)
2512 {
2513 if(len == 0)
2514 {
2515 assert(pos <= size());
2516 return *this;
2517 }
2518 assert(pos < size());
2519 assert(pos + len - 1 < size());
2520
2521 const size_type first_block = block_index(pos);
2522 const size_type last_block = block_index(pos + len - 1);
2523 const size_type first_bit_index = bit_index(pos);
2524 const size_type last_bit_index = bit_index(pos + len - 1);
2525
2526 if(first_block == last_block)
2527 {
2528 set_block_bits(m_blocks[first_block], first_bit_index, last_bit_index, value);
2529 }
2530 else
2531 {
2532 size_type first_full_block = first_block;
2533 size_type last_full_block = last_block;
2534
2535 if(first_bit_index != 0)
2536 {
2537 ++first_full_block; // first block is not full
2538 set_block_bits(m_blocks[first_block], first_bit_index, block_last_bit_index, value);
2539 }
2540
2541 if(last_bit_index != block_last_bit_index)
2542 {
2543 --last_full_block; // last block is not full
2544 set_block_bits(m_blocks[last_block], 0, last_bit_index, value);
2545 }
2546
2547 const block_type full_block = value ? one_block : zero_block;
2548 for(size_type i = first_full_block; i <= last_full_block; ++i)
2549 {
2550 m_blocks[i] = full_block;
2551 }
2552 }
2553
2554 return *this;
2555 }
2556
2557 template<typename Block, typename Allocator>
2558 constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::set(size_type pos, bool value)
2559 {
2560 assert(pos < size());
2561
2562 if(value)
2563 {
2564 m_blocks[block_index(pos)] |= bit_mask(pos);
2565 }
2566 else
2567 {
2568 m_blocks[block_index(pos)] &= static_cast<block_type>(~bit_mask(pos));
2569 }
2570
2571 return *this;
2572 }
2573
2574 template<typename Block, typename Allocator>
2575 constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::set()
2576 {
2577 std::fill(std::begin(m_blocks), std::end(m_blocks), one_block);
2578 sanitize();
2579 return *this;
2580 }
2581
2582 template<typename Block, typename Allocator>
2583 constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::reset(size_type pos, size_type len)
2584 {
2585 return set(pos, len, false);
2586 }
2587
2588 template<typename Block, typename Allocator>
2589 constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::reset(size_type pos)
2590 {
2591 return set(pos, false);
2592 }
2593
2594 template<typename Block, typename Allocator>
2595 constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::reset()
2596 {
2597 std::fill(std::begin(m_blocks), std::end(m_blocks), zero_block);
2598 return *this;
2599 }
2600
2601 template<typename Block, typename Allocator>
2602 constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::flip(size_type pos, size_type len)
2603 {
2604 if(len == 0)
2605 {
2606 assert(pos <= size());
2607 return *this;
2608 }
2609 assert(pos < size());
2610 assert(pos + len - 1 < size());
2611
2612 const size_type first_block = block_index(pos);
2613 const size_type last_block = block_index(pos + len - 1);
2614 const size_type first_bit_index = bit_index(pos);
2615 const size_type last_bit_index = bit_index(pos + len - 1);
2616
2617 if(first_block == last_block)
2618 {
2619 flip_block_bits(m_blocks[first_block], first_bit_index, last_bit_index);
2620 }
2621 else
2622 {
2623 size_type first_full_block = first_block;
2624 size_type last_full_block = last_block;
2625
2626 if(first_bit_index != 0)
2627 {
2628 ++first_full_block; // first block is not full
2629 flip_block_bits(m_blocks[first_block], first_bit_index, block_last_bit_index);
2630 }
2631
2632 if(last_bit_index != block_last_bit_index)
2633 {
2634 --last_full_block; // last block is not full
2635 flip_block_bits(m_blocks[last_block], 0, last_bit_index);
2636 }
2637
2638 for(size_type i = first_full_block; i <= last_full_block; ++i)
2639 {
2640 m_blocks[i] = block_type(~m_blocks[i]);
2641 }
2642 }
2643
2644 return *this;
2645 }
2646
2647 template<typename Block, typename Allocator>
2648 constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::flip(size_type pos)
2649 {
2650 assert(pos < size());
2651 m_blocks[block_index(pos)] ^= bit_mask(pos);
2652 return *this;
2653 }
2654
2655 template<typename Block, typename Allocator>
2656 constexpr dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::flip()
2657 {
2658 std::transform(std::cbegin(m_blocks), std::cend(m_blocks), std::begin(m_blocks), std::bit_not<block_type>());
2659 sanitize();
2660 return *this;
2661 }
2662
2663 template<typename Block, typename Allocator>
2664 constexpr bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
2665 {
2666 assert(pos < size());
2667 return (m_blocks[block_index(pos)] & bit_mask(pos)) != zero_block;
2668 }
2669
2670 template<typename Block, typename Allocator>
2671 constexpr bool dynamic_bitset<Block, Allocator>::test_set(size_type pos, bool value)
2672 {
2673 bool const result = test(pos);
2674 if(result != value)
2675 {
2676 set(pos, value);
2677 }
2678 return result;
2679 }
2680
2681 template<typename Block, typename Allocator>
2682 constexpr bool dynamic_bitset<Block, Allocator>::all() const
2683 {
2684 if(empty())
2685 {
2686 return true;
2687 }
2688
2689 const block_type full_block = one_block;
2690 if(extra_bits_number() == 0)
2691 {
2692 for(const block_type& block: m_blocks)
2693 {
2694 if(block != full_block)
2695 {
2696 return false;
2697 }
2698 }
2699 }
2700 else
2701 {
2702 for(size_type i = 0; i < m_blocks.size() - 1; ++i)
2703 {
2704 if(m_blocks[i] != full_block)
2705 {
2706 return false;
2707 }
2708 }
2709 if(last_block() != (full_block >> unused_bits_number()))
2710 {
2711 return false;
2712 }
2713 }
2714 return true;
2715 }
2716
2717 template<typename Block, typename Allocator>
2718 constexpr bool dynamic_bitset<Block, Allocator>::any() const
2719 {
2720 for(const block_type& block: m_blocks)
2721 {
2722 if(block != zero_block)
2723 {
2724 return true;
2725 }
2726 }
2727 return false;
2728 }
2729
2730 template<typename Block, typename Allocator>
2731 constexpr bool dynamic_bitset<Block, Allocator>::none() const
2732 {
2733 return !any();
2734 }
2735
2736 template<typename Block, typename Allocator>
2737 constexpr typename dynamic_bitset<Block, Allocator>::size_type
2738 dynamic_bitset<Block, Allocator>::count() const noexcept
2739 {
2740 if(empty())
2741 {
2742 return 0;
2743 }
2744
2745#if DYNAMIC_BITSET_CAN_USE_LIBPOPCNT
2746 const size_type count = static_cast<size_type>(popcnt(m_blocks.data(), m_blocks.size() * sizeof(block_type)));
2747#else
2748 size_type count = 0;
2749
2750 // full blocks
2751 for(size_type i = 0; i < m_blocks.size() - 1; ++i)
2752 {
2753 count += block_count(m_blocks[i]);
2754 }
2755
2756 // last block
2757 const block_type& block = last_block();
2758 const size_type extra_bits = extra_bits_number();
2759 if(extra_bits == 0)
2760 {
2761 count += block_count(block);
2762 }
2763 else
2764 {
2765 count += block_count(block, extra_bits);
2766 }
2767#endif
2768 return count;
2769 }
2770
2771 template<typename Block, typename Allocator>
2772 constexpr typename dynamic_bitset<Block, Allocator>::reference
2773 dynamic_bitset<Block, Allocator>::operator[](size_type pos)
2774 {
2775 assert(pos < size());
2776 return dynamic_bitset<Block, Allocator>::reference(*this, pos);
2777 }
2778
2779 template<typename Block, typename Allocator>
2780 constexpr typename dynamic_bitset<Block, Allocator>::const_reference
2781 dynamic_bitset<Block, Allocator>::operator[](size_type pos) const
2782 {
2783 return test(pos);
2784 }
2785
2786 template<typename Block, typename Allocator>
2787 constexpr typename dynamic_bitset<Block, Allocator>::size_type
2788 dynamic_bitset<Block, Allocator>::size() const noexcept
2789 {
2790 return m_bits_number;
2791 }
2792
2793 template<typename Block, typename Allocator>
2794 constexpr typename dynamic_bitset<Block, Allocator>::size_type
2795 dynamic_bitset<Block, Allocator>::num_blocks() const noexcept
2796 {
2797 return m_blocks.size();
2798 }
2799
2800 template<typename Block, typename Allocator>
2801 constexpr bool dynamic_bitset<Block, Allocator>::empty() const noexcept
2802 {
2803 return size() == 0;
2804 }
2805
2806 template<typename Block, typename Allocator>
2807 constexpr typename dynamic_bitset<Block, Allocator>::size_type
2808 dynamic_bitset<Block, Allocator>::capacity() const noexcept
2809 {
2810 return m_blocks.capacity() * bits_per_block;
2811 }
2812
2813 template<typename Block, typename Allocator>
2814 constexpr void dynamic_bitset<Block, Allocator>::reserve(size_type num_bits)
2815 {
2816 m_blocks.reserve(blocks_required(num_bits));
2817 }
2818
2819 template<typename Block, typename Allocator>
2820 constexpr void dynamic_bitset<Block, Allocator>::shrink_to_fit()
2821 {
2822 m_blocks.shrink_to_fit();
2823 }
2824
2825 template<typename Block, typename Allocator>
2826 constexpr bool dynamic_bitset<Block, Allocator>::is_subset_of(const dynamic_bitset<Block, Allocator>& bitset) const
2827 {
2828 assert(size() == bitset.size());
2829 for(size_type i = 0; i < m_blocks.size(); ++i)
2830 {
2831 if((m_blocks[i] & ~bitset.m_blocks[i]) != zero_block)
2832 {
2833 return false;
2834 }
2835 }
2836 return true;
2837 }
2838
2839 template<typename Block, typename Allocator>
2840 constexpr bool
2841 dynamic_bitset<Block, Allocator>::is_proper_subset_of(const dynamic_bitset<Block, Allocator>& bitset) const
2842 {
2843 assert(size() == bitset.size());
2844 bool is_proper = false;
2845 for(size_type i = 0; i < m_blocks.size(); ++i)
2846 {
2847 const block_type& self_block = m_blocks[i];
2848 const block_type& other_block = bitset.m_blocks[i];
2849
2850 if((self_block & ~other_block) != zero_block)
2851 {
2852 return false;
2853 }
2854 if((~self_block & other_block) != zero_block)
2855 {
2856 is_proper = true;
2857 }
2858 }
2859 return is_proper;
2860 }
2861
2862 template<typename Block, typename Allocator>
2863 constexpr bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset<Block, Allocator>& bitset) const
2864 {
2865 const size_type min_blocks_number = std::min(m_blocks.size(), bitset.m_blocks.size());
2866 for(size_type i = 0; i < min_blocks_number; ++i)
2867 {
2868 if((m_blocks[i] & bitset.m_blocks[i]) != zero_block)
2869 {
2870 return true;
2871 }
2872 }
2873 return false;
2874 }
2875
2876 template<typename Block, typename Allocator>
2877 constexpr typename dynamic_bitset<Block, Allocator>::size_type dynamic_bitset<Block, Allocator>::find_first() const
2878 {
2879 for(size_type i = 0; i < m_blocks.size(); ++i)
2880 {
2881 if(m_blocks[i] != zero_block)
2882 {
2883 return i * bits_per_block + count_block_trailing_zero(m_blocks[i]);
2884 }
2885 }
2886 return npos;
2887 }
2888
2889 template<typename Block, typename Allocator>
2890 constexpr typename dynamic_bitset<Block, Allocator>::size_type
2891 dynamic_bitset<Block, Allocator>::find_next(size_type prev) const
2892 {
2893 if(empty() || prev >= (size() - 1))
2894 {
2895 return npos;
2896 }
2897
2898 const size_type first_bit = prev + 1;
2899 const size_type first_block = block_index(first_bit);
2900 const size_type first_bit_index = bit_index(first_bit);
2901 const block_type first_block_shifted = block_type(m_blocks[first_block] >> first_bit_index);
2902
2903 if(first_block_shifted != zero_block)
2904 {
2905 return first_bit + count_block_trailing_zero(first_block_shifted);
2906 }
2907 else
2908 {
2909 for(size_type i = first_block + 1; i < m_blocks.size(); ++i)
2910 {
2911 if(m_blocks[i] != zero_block)
2912 {
2913 return i * bits_per_block + count_block_trailing_zero(m_blocks[i]);
2914 }
2915 }
2916 }
2917 return npos;
2918 }
2919
2920 template<typename Block, typename Allocator>
2921 constexpr void dynamic_bitset<Block, Allocator>::swap(dynamic_bitset<Block, Allocator>& other) noexcept(
2922 noexcept(std::swap(m_blocks, other.m_blocks)))
2923 {
2924 std::swap(m_blocks, other.m_blocks);
2925 std::swap(m_bits_number, other.m_bits_number);
2926 }
2927
2928 template<typename Block, typename Allocator>
2929 constexpr typename dynamic_bitset<Block, Allocator>::allocator_type
2930 dynamic_bitset<Block, Allocator>::get_allocator() const
2931 {
2932 return m_blocks.get_allocator();
2933 }
2934
2935 template<typename Block, typename Allocator>
2936 template<typename _CharT, typename _Traits, typename _Alloc>
2937 constexpr std::basic_string<_CharT, _Traits, _Alloc> dynamic_bitset<Block, Allocator>::to_string(_CharT zero,
2938 _CharT one) const
2939 {
2940 const size_type len = size();
2941 std::basic_string<_CharT, _Traits, _Alloc> str(len, zero);
2942 for(size_type i_block = 0; i_block < m_blocks.size(); ++i_block)
2943 {
2944 if(m_blocks[i_block] == zero_block)
2945 {
2946 continue;
2947 }
2948 block_type mask = block_type(1);
2949 const size_type limit = i_block * bits_per_block < len ? len - i_block * bits_per_block : bits_per_block;
2950 for(size_type i_bit = 0; i_bit < limit; ++i_bit)
2951 {
2952 if((m_blocks[i_block] & mask) != zero_block)
2953 {
2954 _Traits::assign(str[len - (i_block * bits_per_block + i_bit + 1)], one);
2955 }
2956 // mask <<= 1; not used because it trigger -Wconversion
2957 // because of integral promotion for block_type smaller than int
2958 mask = static_cast<block_type>(mask << 1);
2959 }
2960 }
2961 return str;
2962 }
2963
2964 template<typename Block, typename Allocator>
2965 constexpr unsigned long dynamic_bitset<Block, Allocator>::to_ulong() const
2966 {
2967 if(m_bits_number == 0)
2968 {
2969 return 0;
2970 }
2971
2972 constexpr size_t ul_bits_number = std::numeric_limits<unsigned long>::digits;
2973 if(find_next(ul_bits_number - 1) != npos)
2974 {
2975 throw std::overflow_error("sul::dynamic_bitset::to_ulong");
2976 }
2977
2978 unsigned long result = 0;
2979 const size_type result_bits_number = std::min(ul_bits_number, m_bits_number);
2980 for(size_type i_block = 0; i_block <= block_index(result_bits_number - 1); ++i_block)
2981 {
2982 result |= (static_cast<unsigned long>(m_blocks[i_block]) << (i_block * bits_per_block));
2983 }
2984
2985 return result;
2986 }
2987
2988 template<typename Block, typename Allocator>
2989 constexpr unsigned long long dynamic_bitset<Block, Allocator>::to_ullong() const
2990 {
2991 if(m_bits_number == 0)
2992 {
2993 return 0;
2994 }
2995
2996 constexpr size_t ull_bits_number = std::numeric_limits<unsigned long long>::digits;
2997 if(find_next(ull_bits_number - 1) != npos)
2998 {
2999 throw std::overflow_error("sul::dynamic_bitset::to_ullong");
3000 }
3001
3002 unsigned long long result = 0;
3003 const size_type result_bits_number = std::min(ull_bits_number, m_bits_number);
3004 for(size_type i_block = 0; i_block <= block_index(result_bits_number - 1); ++i_block)
3005 {
3006 result |= (static_cast<unsigned long long>(m_blocks[i_block]) << (i_block * bits_per_block));
3007 }
3008
3009 return result;
3010 }
3011
3012 template<typename Block, typename Allocator>
3013 template<typename Function, typename... Parameters>
3014 constexpr void dynamic_bitset<Block, Allocator>::iterate_bits_on(Function&& function,
3015 Parameters&&... parameters) const
3016 {
3017 if constexpr(!std::is_invocable_v<Function, size_t, Parameters...>)
3018 {
3019 static_assert(dependent_false<Function>::value, "Function take invalid arguments");
3020 // function should take (size_t, parameters...) as arguments
3021 }
3022
3023 if constexpr(std::is_same_v<std::invoke_result_t<Function, size_t, Parameters...>, void>)
3024 {
3025 size_type i_bit = find_first();
3026 while(i_bit != npos)
3027 {
3028 std::invoke(std::forward<Function>(function), i_bit, std::forward<Parameters>(parameters)...);
3029 i_bit = find_next(i_bit);
3030 }
3031 }
3032 else if constexpr(std::is_convertible_v<std::invoke_result_t<Function, size_t, Parameters...>, bool>)
3033 {
3034 size_type i_bit = find_first();
3035 while(i_bit != npos)
3036 {
3037 if(!std::invoke(std::forward<Function>(function), i_bit, std::forward<Parameters>(parameters)...))
3038 {
3039 break;
3040 }
3041 i_bit = find_next(i_bit);
3042 }
3043 }
3044 else
3045 {
3046 static_assert(dependent_false<Function>::value, "Function have invalid return type");
3047 // return type should be void, or convertible to bool
3048 }
3049 }
3050
3051 template<typename Block, typename Allocator>
3052 constexpr typename dynamic_bitset<Block, Allocator>::block_type* dynamic_bitset<Block, Allocator>::data() noexcept
3053 {
3054 return m_blocks.data();
3055 }
3056
3057 template<typename Block, typename Allocator>
3058 constexpr const typename dynamic_bitset<Block, Allocator>::block_type*
3059 dynamic_bitset<Block, Allocator>::data() const noexcept
3060 {
3061 return m_blocks.data();
3062 }
3063
3064 template<typename Block_, typename Allocator_>
3065 [[nodiscard]] constexpr bool operator==(const dynamic_bitset<Block_, Allocator_>& lhs,
3066 const dynamic_bitset<Block_, Allocator_>& rhs)
3067 {
3068 return (lhs.m_bits_number == rhs.m_bits_number) && (lhs.m_blocks == rhs.m_blocks);
3069 }
3070
3071 template<typename Block_, typename Allocator_>
3072 [[nodiscard]] constexpr bool operator<(const dynamic_bitset<Block_, Allocator_>& lhs,
3073 const dynamic_bitset<Block_, Allocator_>& rhs)
3074 {
3075 using size_type = typename dynamic_bitset<Block_, Allocator_>::size_type;
3076 using block_type = typename dynamic_bitset<Block_, Allocator_>::block_type;
3077 const size_type lhs_size = lhs.size();
3078 const size_type rhs_size = rhs.size();
3079 const size_type lhs_blocks_size = lhs.m_blocks.size();
3080 const size_type rhs_blocks_size = rhs.m_blocks.size();
3081
3082 if(lhs_size == rhs_size)
3083 {
3084 // if comparison of two empty bitsets
3085 if(lhs_size == 0)
3086 {
3087 return false;
3088 }
3089
3090 for(size_type i = lhs_blocks_size - 1; i > 0; --i)
3091 {
3092 if(lhs.m_blocks[i] != rhs.m_blocks[i])
3093 {
3094 return lhs.m_blocks[i] < rhs.m_blocks[i];
3095 }
3096 }
3097 return lhs.m_blocks[0] < rhs.m_blocks[0];
3098 }
3099
3100 // empty bitset inferior to 0-only bitset
3101 if(lhs_size == 0)
3102 {
3103 return true;
3104 }
3105 if(rhs_size == 0)
3106 {
3107 return false;
3108 }
3109
3110 const bool rhs_longer = rhs_size > lhs_size;
3111 const dynamic_bitset<Block_, Allocator_>& longest_bitset = rhs_longer ? rhs : lhs;
3112 const size_type longest_blocks_size = std::max(lhs_blocks_size, rhs_blocks_size);
3113 const size_type shortest_blocks_size = std::min(lhs_blocks_size, rhs_blocks_size);
3114 for(size_type i = longest_blocks_size - 1; i >= shortest_blocks_size; --i)
3115 {
3116 if(longest_bitset.m_blocks[i] != block_type(0))
3117 {
3118 return rhs_longer;
3119 }
3120 }
3121
3122 for(size_type i = shortest_blocks_size - 1; i > 0; --i)
3123 {
3124 if(lhs.m_blocks[i] != rhs.m_blocks[i])
3125 {
3126 return lhs.m_blocks[i] < rhs.m_blocks[i];
3127 }
3128 }
3129 if(lhs.m_blocks[0] != rhs.m_blocks[0])
3130 {
3131 return lhs.m_blocks[0] < rhs.m_blocks[0];
3132 }
3133 return lhs_size < rhs_size;
3134 }
3135
3136 //=================================================================================================
3137 // dynamic_bitset private functions implementations
3138 //=================================================================================================
3139
3140 template<typename Block, typename Allocator>
3141 constexpr typename dynamic_bitset<Block, Allocator>::size_type
3142 dynamic_bitset<Block, Allocator>::blocks_required(size_type nbits) noexcept
3143 {
3144 return nbits / bits_per_block + static_cast<size_type>(nbits % bits_per_block > 0);
3145 }
3146
3147 template<typename Block, typename Allocator>
3148 constexpr typename dynamic_bitset<Block, Allocator>::size_type
3149 dynamic_bitset<Block, Allocator>::block_index(size_type pos) noexcept
3150 {
3151 return pos / bits_per_block;
3152 }
3153
3154 template<typename Block, typename Allocator>
3155 constexpr typename dynamic_bitset<Block, Allocator>::size_type
3156 dynamic_bitset<Block, Allocator>::bit_index(size_type pos) noexcept
3157 {
3158 return pos % bits_per_block;
3159 }
3160
3161 template<typename Block, typename Allocator>
3162 constexpr typename dynamic_bitset<Block, Allocator>::block_type
3163 dynamic_bitset<Block, Allocator>::bit_mask(size_type pos) noexcept
3164 {
3165 return block_type(block_type(1) << bit_index(pos));
3166 }
3167
3168 template<typename Block, typename Allocator>
3169 constexpr typename dynamic_bitset<Block, Allocator>::block_type
3170 dynamic_bitset<Block, Allocator>::bit_mask(size_type first, size_type last) noexcept
3171 {
3172 first = bit_index(first);
3173 last = bit_index(last);
3174 if(last == (block_last_bit_index))
3175 {
3176 return block_type(one_block << first);
3177 }
3178 else
3179 {
3180 return block_type(((block_type(1) << (last + 1)) - 1) ^ ((block_type(1) << first) - 1));
3181 }
3182 }
3183
3184 template<typename Block, typename Allocator>
3185 constexpr void dynamic_bitset<Block, Allocator>::set_block_bits(block_type& block,
3186 size_type first,
3187 size_type last,
3188 bool val) noexcept
3189 {
3190 if(val)
3191 {
3192 block |= bit_mask(first, last);
3193 }
3194 else
3195 {
3196 block &= static_cast<block_type>(~bit_mask(first, last));
3197 }
3198 }
3199
3200 template<typename Block, typename Allocator>
3201 constexpr void
3202 dynamic_bitset<Block, Allocator>::flip_block_bits(block_type& block, size_type first, size_type last) noexcept
3203 {
3204 block ^= bit_mask(first, last);
3205 }
3206
3207 template<typename Block, typename Allocator>
3208 constexpr typename dynamic_bitset<Block, Allocator>::size_type
3209 dynamic_bitset<Block, Allocator>::block_count(const block_type& block) noexcept
3210 {
3211#if DYNAMIC_BITSET_CAN_USE_STD_BITOPS
3212 return static_cast<size_type>(std::popcount(block));
3213#else
3214 if(block == zero_block)
3215 {
3216 return 0;
3217 }
3218
3219# if DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN || DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_POPCOUNT
3220 constexpr size_t u_bits_number = std::numeric_limits<unsigned>::digits;
3221 constexpr size_t ul_bits_number = std::numeric_limits<unsigned long>::digits;
3222 constexpr size_t ull_bits_number = std::numeric_limits<unsigned long long>::digits;
3223 if constexpr(bits_per_block <= u_bits_number)
3224 {
3225 return static_cast<size_type>(__builtin_popcount(static_cast<unsigned int>(block)));
3226 }
3227 else if constexpr(bits_per_block <= ul_bits_number)
3228 {
3229 return static_cast<size_type>(__builtin_popcountl(static_cast<unsigned long>(block)));
3230 }
3231 else if constexpr(bits_per_block <= ull_bits_number)
3232 {
3233 return static_cast<size_type>(__builtin_popcountll(static_cast<unsigned long long>(block)));
3234 }
3235# endif
3236
3237 size_type count = 0;
3238 block_type mask = 1;
3239 for(size_type bit_index = 0; bit_index < bits_per_block; ++bit_index)
3240 {
3241 count += static_cast<size_type>((block & mask) != zero_block);
3242 // mask <<= 1; not used because it trigger -Wconversion
3243 // because of integral promotion for block_type smaller than int
3244 mask = static_cast<block_type>(mask << 1);
3245 }
3246 return count;
3247#endif
3248 }
3249
3250 template<typename Block, typename Allocator>
3251 constexpr typename dynamic_bitset<Block, Allocator>::size_type
3252 dynamic_bitset<Block, Allocator>::block_count(const block_type& block, size_type nbits) noexcept
3253 {
3254 assert(nbits <= bits_per_block);
3255#if DYNAMIC_BITSET_CAN_USE_STD_BITOPS
3256 const block_type shifted_block = block_type(block << (bits_per_block - nbits));
3257 return static_cast<size_type>(std::popcount(shifted_block));
3258#else
3259 const block_type shifted_block = block_type(block << (bits_per_block - nbits));
3260 if(shifted_block == zero_block)
3261 {
3262 return 0;
3263 }
3264
3265# if DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN || DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_POPCOUNT
3266 constexpr size_t u_bits_number = std::numeric_limits<unsigned>::digits;
3267 constexpr size_t ul_bits_number = std::numeric_limits<unsigned long>::digits;
3268 constexpr size_t ull_bits_number = std::numeric_limits<unsigned long long>::digits;
3269 if constexpr(bits_per_block <= u_bits_number)
3270 {
3271 return static_cast<size_type>(__builtin_popcount(static_cast<unsigned int>(shifted_block)));
3272 }
3273 else if constexpr(bits_per_block <= ul_bits_number)
3274 {
3275 return static_cast<size_type>(__builtin_popcountl(static_cast<unsigned long>(shifted_block)));
3276 }
3277 else if constexpr(bits_per_block <= ull_bits_number)
3278 {
3279 return static_cast<size_type>(__builtin_popcountll(static_cast<unsigned long long>(shifted_block)));
3280 }
3281# endif
3282
3283 size_type count = 0;
3284 block_type mask = 1;
3285 for(size_type bit_index = 0; bit_index < nbits; ++bit_index)
3286 {
3287 count += static_cast<size_type>((block & mask) != zero_block);
3288 // mask <<= 1; not used because it trigger -Wconversion
3289 // because of integral promotion for block_type smaller than int
3290 mask = static_cast<block_type>(mask << 1);
3291 }
3292
3293 return count;
3294#endif
3295 }
3296
3297 template<typename Block, typename Allocator>
3298 constexpr typename dynamic_bitset<Block, Allocator>::size_type
3299 dynamic_bitset<Block, Allocator>::count_block_trailing_zero(const block_type& block) noexcept
3300 {
3301 assert(block != zero_block);
3302#if DYNAMIC_BITSET_CAN_USE_STD_BITOPS
3303 return static_cast<size_type>(std::countr_zero(block));
3304#else
3305# if DYNAMIC_BITSET_CAN_USE_GCC_BUILTIN || DYNAMIC_BITSET_CAN_USE_CLANG_BUILTIN_CTZ
3306 constexpr size_t u_bits_number = std::numeric_limits<unsigned>::digits;
3307 constexpr size_t ul_bits_number = std::numeric_limits<unsigned long>::digits;
3308 constexpr size_t ull_bits_number = std::numeric_limits<unsigned long long>::digits;
3309 if constexpr(bits_per_block <= u_bits_number)
3310 {
3311 return static_cast<size_type>(__builtin_ctz(static_cast<unsigned int>(block)));
3312 }
3313 else if constexpr(bits_per_block <= ul_bits_number)
3314 {
3315 return static_cast<size_type>(__builtin_ctzl(static_cast<unsigned long>(block)));
3316 }
3317 else if constexpr(bits_per_block <= ull_bits_number)
3318 {
3319 return static_cast<size_type>(__builtin_ctzll(static_cast<unsigned long long>(block)));
3320 }
3321
3322# elif DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD
3323 constexpr size_t ul_bits_number = std::numeric_limits<unsigned long>::digits;
3324 constexpr size_t ui64_bits_number = std::numeric_limits<unsigned __int64>::digits;
3325 if constexpr(bits_per_block <= ul_bits_number)
3326 {
3327 unsigned long index = std::numeric_limits<unsigned long>::max();
3328 _BitScanForward(&index, static_cast<unsigned long>(block));
3329 return static_cast<size_type>(index);
3330 }
3331 else if constexpr(bits_per_block <= ui64_bits_number)
3332 {
3333# if DYNAMIC_BITSET_CAN_USE_MSVC_BUILTIN_BITSCANFORWARD64
3334 unsigned long index = std::numeric_limits<unsigned long>::max();
3335 _BitScanForward64(&index, static_cast<unsigned __int64>(block));
3336 return static_cast<size_type>(index);
3337# else
3338 constexpr unsigned long max_ul = std::numeric_limits<unsigned long>::max();
3339 unsigned long low = block & max_ul;
3340 if(low != 0)
3341 {
3342 unsigned long index = std::numeric_limits<unsigned long>::max();
3343 _BitScanForward(&index, low);
3344 return static_cast<size_type>(index);
3345 }
3346 unsigned long high = block >> ul_bits_number;
3347 unsigned long index = std::numeric_limits<unsigned long>::max();
3348 _BitScanForward(&index, high);
3349 return static_cast<size_type>(ul_bits_number + index);
3350# endif
3351 }
3352# endif
3353
3354 block_type mask = block_type(1);
3355 for(size_type i = 0; i < bits_per_block; ++i)
3356 {
3357 if((block & mask) != zero_block)
3358 {
3359 return i;
3360 }
3361 // mask <<= 1; not used because it trigger -Wconversion
3362 // because of integral promotion for block_type smaller than int
3363 mask = static_cast<block_type>(mask << 1);
3364 }
3365 assert(false); // LCOV_EXCL_LINE: unreachable
3366 return npos; // LCOV_EXCL_LINE: unreachable
3367#endif
3368 }
3369
3370 template<typename Block, typename Allocator>
3371 template<typename _CharT, typename _Traits>
3372 constexpr void
3373 dynamic_bitset<Block, Allocator>::init_from_string(std::basic_string_view<_CharT, _Traits> str,
3374 typename std::basic_string_view<_CharT, _Traits>::size_type pos,
3375 typename std::basic_string_view<_CharT, _Traits>::size_type n,
3376 [[maybe_unused]] _CharT zero,
3377 _CharT one)
3378 {
3379 assert(pos < str.size());
3380
3381 const size_type size = std::min(n, str.size() - pos);
3382 m_bits_number = size;
3383
3384 m_blocks.clear();
3385 m_blocks.resize(blocks_required(size));
3386 for(size_t i = 0; i < size; ++i)
3387 {
3388 const _CharT c = str[(pos + size - 1) - i];
3389 assert(c == zero || c == one);
3390 if(c == one)
3391 {
3392 set(i);
3393 }
3394 }
3395 }
3396
3397 template<typename Block, typename Allocator>
3398 constexpr typename dynamic_bitset<Block, Allocator>::block_type&
3399 dynamic_bitset<Block, Allocator>::get_block(size_type pos)
3400 {
3401 return m_blocks[block_index(pos)];
3402 }
3403
3404 template<typename Block, typename Allocator>
3405 constexpr const typename dynamic_bitset<Block, Allocator>::block_type&
3406 dynamic_bitset<Block, Allocator>::get_block(size_type pos) const
3407 {
3408 return m_blocks[block_index(pos)];
3409 }
3410
3411 template<typename Block, typename Allocator>
3412 constexpr typename dynamic_bitset<Block, Allocator>::block_type& dynamic_bitset<Block, Allocator>::last_block()
3413 {
3414 return m_blocks[m_blocks.size() - 1];
3415 }
3416
3417 template<typename Block, typename Allocator>
3418 constexpr typename dynamic_bitset<Block, Allocator>::block_type dynamic_bitset<Block, Allocator>::last_block() const
3419 {
3420 return m_blocks[m_blocks.size() - 1];
3421 }
3422
3423 template<typename Block, typename Allocator>
3424 constexpr typename dynamic_bitset<Block, Allocator>::size_type
3425 dynamic_bitset<Block, Allocator>::extra_bits_number() const noexcept
3426 {
3427 return bit_index(m_bits_number);
3428 }
3429
3430 template<typename Block, typename Allocator>
3431 constexpr typename dynamic_bitset<Block, Allocator>::size_type
3432 dynamic_bitset<Block, Allocator>::unused_bits_number() const noexcept
3433 {
3434 return bits_per_block - extra_bits_number();
3435 }
3436
3437 template<typename Block, typename Allocator>
3438 template<typename BinaryOperation>
3439 constexpr void dynamic_bitset<Block, Allocator>::apply(const dynamic_bitset<Block, Allocator>& other,
3440 BinaryOperation binary_op)
3441 {
3442 assert(num_blocks() == other.num_blocks());
3443 std::transform(
3444 std::cbegin(m_blocks), std::cend(m_blocks), std::cbegin(other.m_blocks), std::begin(m_blocks), binary_op);
3445 }
3446
3447 template<typename Block, typename Allocator>
3448 template<typename UnaryOperation>
3449 constexpr void dynamic_bitset<Block, Allocator>::apply(UnaryOperation unary_op)
3450 {
3451 std::transform(std::cbegin(m_blocks), std::cend(m_blocks), std::begin(m_blocks), unary_op);
3452 }
3453
3454 template<typename Block, typename Allocator>
3455 constexpr void dynamic_bitset<Block, Allocator>::apply_left_shift(size_type shift)
3456 {
3457 assert(shift > 0);
3458 assert(shift < capacity());
3459
3460 const size_type blocks_shift = shift / bits_per_block;
3461 const size_type bits_offset = shift % bits_per_block;
3462
3463 if(bits_offset == 0)
3464 {
3465 for(size_type i = m_blocks.size() - 1; i >= blocks_shift; --i)
3466 {
3467 m_blocks[i] = m_blocks[i - blocks_shift];
3468 }
3469 }
3470 else
3471 {
3472 const size_type reverse_bits_offset = bits_per_block - bits_offset;
3473 for(size_type i = m_blocks.size() - 1; i > blocks_shift; --i)
3474 {
3475 m_blocks[i] = block_type((m_blocks[i - blocks_shift] << bits_offset)
3476 | block_type(m_blocks[i - blocks_shift - 1] >> reverse_bits_offset));
3477 }
3478 m_blocks[blocks_shift] = block_type(m_blocks[0] << bits_offset);
3479 }
3480
3481 // set bit that came at the right to 0 in unmodified blocks
3482 std::fill(std::begin(m_blocks),
3483 std::begin(m_blocks) + static_cast<typename decltype(m_blocks)::difference_type>(blocks_shift),
3484 zero_block);
3485 }
3486
3487 template<typename Block, typename Allocator>
3488 constexpr void dynamic_bitset<Block, Allocator>::apply_right_shift(size_type shift)
3489 {
3490 assert(shift > 0);
3491 assert(shift < capacity());
3492
3493 const size_type blocks_shift = shift / bits_per_block;
3494 const size_type bits_offset = shift % bits_per_block;
3495 const size_type last_block_to_shift = m_blocks.size() - blocks_shift - 1;
3496
3497 if(bits_offset == 0)
3498 {
3499 for(size_type i = 0; i <= last_block_to_shift; ++i)
3500 {
3501 m_blocks[i] = m_blocks[i + blocks_shift];
3502 }
3503 }
3504 else
3505 {
3506 const size_type reverse_bits_offset = bits_per_block - bits_offset;
3507 for(size_type i = 0; i < last_block_to_shift; ++i)
3508 {
3509 m_blocks[i] = block_type((m_blocks[i + blocks_shift] >> bits_offset)
3510 | block_type(m_blocks[i + blocks_shift + 1] << reverse_bits_offset));
3511 }
3512 m_blocks[last_block_to_shift] = block_type(m_blocks[m_blocks.size() - 1] >> bits_offset);
3513 }
3514
3515 // set bit that came at the left to 0 in unmodified blocks
3516 std::fill(std::begin(m_blocks)
3517 + static_cast<typename decltype(m_blocks)::difference_type>(last_block_to_shift + 1),
3518 std::end(m_blocks),
3519 zero_block);
3520 }
3521
3522 template<typename Block, typename Allocator>
3523 constexpr void dynamic_bitset<Block, Allocator>::sanitize()
3524 {
3525 size_type shift = m_bits_number % bits_per_block;
3526 if(shift > 0)
3527 {
3528 last_block() &= static_cast<block_type>(~(one_block << shift));
3529 }
3530 }
3531
3532 template<typename Block, typename Allocator>
3533 constexpr bool dynamic_bitset<Block, Allocator>::check_unused_bits() const noexcept
3534 {
3535 const size_type extra_bits = extra_bits_number();
3536 if(extra_bits > 0)
3537 {
3538 return (last_block() & (one_block << extra_bits)) == zero_block;
3539 }
3540 return true;
3541 }
3542
3543 template<typename Block, typename Allocator>
3544 constexpr bool dynamic_bitset<Block, Allocator>::check_size() const noexcept
3545 {
3546 return blocks_required(size()) == m_blocks.size();
3547 }
3548
3549 template<typename Block, typename Allocator>
3550 constexpr bool dynamic_bitset<Block, Allocator>::check_consistency() const noexcept
3551 {
3552 return check_unused_bits() && check_size();
3553 }
3554
3555 //=================================================================================================
3556 // dynamic_bitset external functions implementations
3557 //=================================================================================================
3558
3559 template<typename Block, typename Allocator>
3560 constexpr bool operator!=(const dynamic_bitset<Block, Allocator>& lhs, const dynamic_bitset<Block, Allocator>& rhs)
3561 {
3562 return !(lhs == rhs);
3563 }
3564
3565 template<typename Block, typename Allocator>
3566 constexpr bool operator<=(const dynamic_bitset<Block, Allocator>& lhs, const dynamic_bitset<Block, Allocator>& rhs)
3567 {
3568 return !(rhs < lhs);
3569 }
3570
3571 template<typename Block, typename Allocator>
3572 constexpr bool operator>(const dynamic_bitset<Block, Allocator>& lhs, const dynamic_bitset<Block, Allocator>& rhs)
3573 {
3574 return rhs < lhs;
3575 }
3576
3577 template<typename Block, typename Allocator>
3578 constexpr bool operator>=(const dynamic_bitset<Block, Allocator>& lhs, const dynamic_bitset<Block, Allocator>& rhs)
3579 {
3580 return !(lhs < rhs);
3581 }
3582
3583 template<typename Block, typename Allocator>
3584 constexpr dynamic_bitset<Block, Allocator> operator&(const dynamic_bitset<Block, Allocator>& lhs,
3585 const dynamic_bitset<Block, Allocator>& rhs)
3586 {
3587 dynamic_bitset<Block, Allocator> result(lhs);
3588 return result &= rhs;
3589 }
3590
3591 template<typename Block, typename Allocator>
3592 constexpr dynamic_bitset<Block, Allocator> operator|(const dynamic_bitset<Block, Allocator>& lhs,
3593 const dynamic_bitset<Block, Allocator>& rhs)
3594 {
3595 dynamic_bitset<Block, Allocator> result(lhs);
3596 return result |= rhs;
3597 }
3598
3599 template<typename Block, typename Allocator>
3600 constexpr dynamic_bitset<Block, Allocator> operator^(const dynamic_bitset<Block, Allocator>& lhs,
3601 const dynamic_bitset<Block, Allocator>& rhs)
3602 {
3603 dynamic_bitset<Block, Allocator> result(lhs);
3604 return result ^= rhs;
3605 }
3606
3607 template<typename Block, typename Allocator>
3608 constexpr dynamic_bitset<Block, Allocator> operator-(const dynamic_bitset<Block, Allocator>& lhs,
3609 const dynamic_bitset<Block, Allocator>& rhs)
3610 {
3611 dynamic_bitset<Block, Allocator> result(lhs);
3612 return result -= rhs;
3613 }
3614
3615 template<typename _CharT, typename _Traits, typename Block, typename Allocator>
3616 constexpr std::basic_ostream<_CharT, _Traits>& operator<<(std::basic_ostream<_CharT, _Traits>& os,
3617 const dynamic_bitset<Block, Allocator>& bitset)
3618 {
3619 // A better implementation is possible
3620 return os << bitset.template to_string<_CharT, _Traits>();
3621 }
3622
3623 template<typename _CharT, typename _Traits, typename Block, typename Allocator>
3624 constexpr std::basic_istream<_CharT, _Traits>& operator>>(std::basic_istream<_CharT, _Traits>& is,
3625 dynamic_bitset<Block, Allocator>& bitset)
3626 {
3627 // A better implementation is possible
3628 constexpr _CharT zero = _CharT('0');
3629 constexpr _CharT one = _CharT('1');
3630 typename std::basic_istream<_CharT, _Traits>::sentry s(is);
3631 if(!s)
3632 {
3633 return is;
3634 }
3635
3636 dynamic_bitset<Block, Allocator> reverse_bitset;
3637 _CharT val;
3638 is.get(val);
3639 while(is.good())
3640 {
3641 if(val == one)
3642 {
3643 reverse_bitset.push_back(true);
3644 }
3645 else if(val == zero)
3646 {
3647 reverse_bitset.push_back(false);
3648 }
3649 else
3650 {
3651 is.unget();
3652 break;
3653 }
3654 is.get(val);
3655 }
3656
3657 bitset.clear();
3658 if(!reverse_bitset.empty())
3659 {
3660 for(typename dynamic_bitset<Block, Allocator>::size_type i = reverse_bitset.size() - 1; i > 0; --i)
3661 {
3662 bitset.push_back(reverse_bitset.test(i));
3663 }
3664 bitset.push_back(reverse_bitset.test(0));
3665 }
3666
3667 return is;
3668 }
3669
3670 template<typename Block, typename Allocator>
3671 constexpr void swap(dynamic_bitset<Block, Allocator>& bitset1,
3672 dynamic_bitset<Block, Allocator>& bitset2) noexcept(noexcept(bitset1.swap(bitset2)))
3673 {
3674 bitset1.swap(bitset2);
3675 }
3676
3677#ifndef DYNAMIC_BITSET_NO_NAMESPACE
3678} // namespace sul
3679#endif
3680
3681#endif // SUL_DYNAMIC_BITSET_HPP
sul::dynamic_bitset::reference
Reference to a sul::dynamic_bitset bit.
Definition dynamic_bitset.hpp:221
sul::dynamic_bitset::reference::reset
constexpr reference & reset()
Reset the referenced bit to false.
Definition dynamic_bitset.hpp:2124
sul::dynamic_bitset::reference::operator-=
constexpr reference & operator-=(bool v)
Apply binary difference to the referenced bit and a value, and assign the result to the referenced bi...
Definition dynamic_bitset.hpp:2095
sul::dynamic_bitset::reference::assign
constexpr reference & assign(bool v)
Assign the value v to the referenced bit.
Definition dynamic_bitset.hpp:2139
sul::dynamic_bitset::reference::reference
constexpr reference(dynamic_bitset< Block, Allocator > &bitset, size_type bit_pos)
Constructs a reference to a bit from a sul::dynamic_bitset and a bit position.
Definition dynamic_bitset.hpp:2029
sul::dynamic_bitset::reference::operator|=
constexpr reference & operator|=(bool v)
Apply binary operator OR to the referenced bit and a value, and assign the result to the referenced b...
Definition dynamic_bitset.hpp:2073
sul::dynamic_bitset::reference::reference
constexpr reference(const reference &) noexcept=default
Copy constructor.
sul::dynamic_bitset::reference::reference
constexpr reference(reference &&) noexcept=default
Move constructor.
sul::dynamic_bitset::reference::operator&=
constexpr reference & operator&=(bool v)
Apply binary operator AND to the referenced bit and a value, and assign the result to the referenced ...
Definition dynamic_bitset.hpp:2062
sul::dynamic_bitset::reference::operator~
constexpr bool operator~() const
Return the result of applying unary NOT operator.
Definition dynamic_bitset.hpp:2105
sul::dynamic_bitset::reference::operator=
constexpr reference & operator=(bool v)
Assign a value to the referenced bit.
Definition dynamic_bitset.hpp:2038
sul::dynamic_bitset::reference::flip
constexpr reference & flip()
Flip the referenced bit.
Definition dynamic_bitset.hpp:2131
sul::dynamic_bitset::reference::set
constexpr reference & set()
Set the referenced bit to true.
Definition dynamic_bitset.hpp:2117
sul::dynamic_bitset::reference::operator^=
constexpr reference & operator^=(bool v)
Apply binary operator XOR to the referenced bit and a value, and assign the result to the referenced ...
Definition dynamic_bitset.hpp:2084
sul::dynamic_bitset
Dynamic bitset.
Definition dynamic_bitset.hpp:171
sul::dynamic_bitset::set
constexpr dynamic_bitset< Block, Allocator > & set(size_type pos, size_type len, bool value)
Set the bits of the range [pos, pos + len[ to value value.
Definition dynamic_bitset.hpp:2511
sul::dynamic_bitset::operator<<=
constexpr dynamic_bitset< Block, Allocator > & operator<<=(size_type shift)
Performs binary shift left of shift bits.
Definition dynamic_bitset.hpp:2455
sul::dynamic_bitset::size
constexpr size_type size() const noexcept
Give the number of bits of the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2788
sul::dynamic_bitset::operator^=
constexpr dynamic_bitset< Block, Allocator > & operator^=(const dynamic_bitset< Block, Allocator > &rhs)
Sets the bits to the result of binary XOR on corresponding pairs of bits of *this and rhs.
Definition dynamic_bitset.hpp:2430
sul::dynamic_bitset::push_back
constexpr void push_back(bool value)
Add a new bit with the value value at the end of the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2288
sul::dynamic_bitset::test_set
constexpr bool test_set(size_type pos, bool value=true)
Test the value of the bit at position pos and set it to true or value value.
Definition dynamic_bitset.hpp:2671
sul::dynamic_bitset::set
constexpr dynamic_bitset< Block, Allocator > & set()
Set all the bits of the sul::dynamic_bitset to true.
Definition dynamic_bitset.hpp:2575
sul::dynamic_bitset::swap
constexpr void swap(dynamic_bitset< Block, Allocator > &other) noexcept(noexcept(std::swap(m_blocks, other.m_blocks)))
Exchanges the bits of this sul::dynamic_bitset with those of other.
Definition dynamic_bitset.hpp:2921
sul::dynamic_bitset::iterate_bits_on
constexpr void iterate_bits_on(Function &&function, Parameters &&... parameters) const
Iterate on the sul::dynamic_bitset and call function with the position of the bits on.
Definition dynamic_bitset.hpp:3014
sul::dynamic_bitset::empty
constexpr bool empty() const noexcept
Checks if the sul::dynamic_bitset is empty.
Definition dynamic_bitset.hpp:2801
sul::dynamic_bitset::block_type
Block block_type
Same type as Block.
Definition dynamic_bitset.hpp:187
sul::dynamic_bitset::any
constexpr bool any() const
Checks if any bits are set to true.
Definition dynamic_bitset.hpp:2718
sul::dynamic_bitset::operator<<
constexpr dynamic_bitset< Block, Allocator > operator<<(size_type shift) const
Performs binary shift right of shift bits.
Definition dynamic_bitset.hpp:2490
sul::dynamic_bitset::clear
constexpr void clear()
Clears the sul::dynamic_bitset, resize it to 0.
Definition dynamic_bitset.hpp:2281
sul::dynamic_bitset::num_blocks
constexpr size_type num_blocks() const noexcept
Give the number of blocks used by the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2795
sul::dynamic_bitset::is_subset_of
constexpr bool is_subset_of(const dynamic_bitset< Block, Allocator > &bitset) const
Determines if this sul::dynamic_bitset is a subset of bitset.
Definition dynamic_bitset.hpp:2826
sul::dynamic_bitset::size_type
size_t size_type
Type used to represent the size of a sul::dynamic_bitset.
Definition dynamic_bitset.hpp:180
sul::dynamic_bitset::to_string
constexpr std::basic_string< _CharT, _Traits, _Alloc > to_string(_CharT zero=_CharT('0'), _CharT one=_CharT('1')) const
Generate a string representation of the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2937
sul::dynamic_bitset::all
constexpr bool all() const
Checks if all bits are set to true.
Definition dynamic_bitset.hpp:2682
sul::dynamic_bitset::reset
constexpr dynamic_bitset< Block, Allocator > & reset()
Reset all the bits of the sul::dynamic_bitset to false.
Definition dynamic_bitset.hpp:2595
sul::dynamic_bitset::operator&=
constexpr dynamic_bitset< Block, Allocator > & operator&=(const dynamic_bitset< Block, Allocator > &rhs)
Sets the bits to the result of binary AND on corresponding pairs of bits of *this and rhs.
Definition dynamic_bitset.hpp:2404
sul::dynamic_bitset::allocator_type
Allocator allocator_type
Same type as Allocator.
Definition dynamic_bitset.hpp:194
sul::dynamic_bitset::is_proper_subset_of
constexpr bool is_proper_subset_of(const dynamic_bitset< Block, Allocator > &bitset) const
Determines if this sul::dynamic_bitset is a proper subset of bitset.
Definition dynamic_bitset.hpp:2841
sul::dynamic_bitset::operator-=
constexpr dynamic_bitset< Block, Allocator > & operator-=(const dynamic_bitset< Block, Allocator > &rhs)
Sets the bits to the result of the binary difference between the bits of *this and rhs.
Definition dynamic_bitset.hpp:2443
sul::dynamic_bitset::count
constexpr size_type count() const noexcept
Count the number of bits set to true.
Definition dynamic_bitset.hpp:2738
sul::dynamic_bitset::dynamic_bitset
constexpr dynamic_bitset(const dynamic_bitset< Block, Allocator > &other)=default
Copy constructor.
sul::dynamic_bitset::capacity
constexpr size_type capacity() const noexcept
Give the number of bits that the sul::dynamic_bitset has currently allocated space for.
Definition dynamic_bitset.hpp:2808
sul::dynamic_bitset::operator|=
constexpr dynamic_bitset< Block, Allocator > & operator|=(const dynamic_bitset< Block, Allocator > &rhs)
Sets the bits to the result of binary OR on corresponding pairs of bits of *this and rhs.
Definition dynamic_bitset.hpp:2417
sul::dynamic_bitset::to_ulong
constexpr unsigned long to_ulong() const
Converts the contents of the bitset to an unsigned long integer.
Definition dynamic_bitset.hpp:2965
sul::dynamic_bitset::flip
constexpr dynamic_bitset< Block, Allocator > & flip()
Flip all the bits of the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2656
sul::dynamic_bitset::find_next
constexpr size_type find_next(size_type prev) const
Find the position of the first bit set in the range [prev + 1, size()[ of the sul::dynamic_bitset sta...
Definition dynamic_bitset.hpp:2891
sul::dynamic_bitset::test
constexpr bool test(size_type pos) const
Test the value of the bit at position pos.
Definition dynamic_bitset.hpp:2664
sul::dynamic_bitset::reserve
constexpr void reserve(size_type num_bits)
Increase the capacity of the sul::dynamic_bitset to a value that's greater or equal to num_bits.
Definition dynamic_bitset.hpp:2814
sul::dynamic_bitset::shrink_to_fit
constexpr void shrink_to_fit()
Requests the removal of unused capacity.
Definition dynamic_bitset.hpp:2820
sul::dynamic_bitset::none
constexpr bool none() const
Checks if none of the bits are set to true.
Definition dynamic_bitset.hpp:2731
sul::dynamic_bitset::find_first
constexpr size_type find_first() const
Find the position of the first bit set in the sul::dynamic_bitset starting from the least-significant...
Definition dynamic_bitset.hpp:2877
sul::dynamic_bitset::bits_per_block
static constexpr size_type bits_per_block
Number of bits that can be stored in a block.
Definition dynamic_bitset.hpp:201
sul::dynamic_bitset::intersects
constexpr bool intersects(const dynamic_bitset< Block, Allocator > &bitset) const
Determines if this sul::dynamic_bitset and bitset intersect.
Definition dynamic_bitset.hpp:2863
sul::dynamic_bitset::append
constexpr void append(block_type block)
Append a block of bits block at the end of the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2329
sul::dynamic_bitset::const_reference
bool const_reference
Const reference to a sul::dynamic_bitset bit, type bool.
Definition dynamic_bitset.hpp:440
sul::dynamic_bitset::get_allocator
constexpr allocator_type get_allocator() const
Gets the associated allocator.
Definition dynamic_bitset.hpp:2930
sul::dynamic_bitset::data
constexpr block_type * data() noexcept
Return a pointer to the underlying array serving as blocks storage.
Definition dynamic_bitset.hpp:3052
sul::dynamic_bitset::operator[]
constexpr reference operator[](size_type pos)
Accesses the bit at position pos.
Definition dynamic_bitset.hpp:2773
sul::dynamic_bitset::flip
constexpr dynamic_bitset< Block, Allocator > & flip(size_type pos, size_type len)
Flip the bits of the range [pos, pos + len[.
Definition dynamic_bitset.hpp:2602
sul::dynamic_bitset::npos
static constexpr size_type npos
Maximum value of size_type, returned for invalid positions.
Definition dynamic_bitset.hpp:208
sul::dynamic_bitset::pop_back
constexpr void pop_back()
Remove the last bit of the sul::dynamic_bitset.
Definition dynamic_bitset.hpp:2307
sul::dynamic_bitset::resize
constexpr void resize(size_type nbits, bool value=false)
Resize the sul::dynamic_bitset to contain nbits bits.
Definition dynamic_bitset.hpp:2249
sul::dynamic_bitset::operator~
constexpr dynamic_bitset< Block, Allocator > operator~() const
Performs a unary NOT on all bits.
Definition dynamic_bitset.hpp:2502
sul::dynamic_bitset::to_ullong
constexpr unsigned long long to_ullong() const
Converts the contents of the bitset to an unsigned long long integer.
Definition dynamic_bitset.hpp:2989
sul::dynamic_bitset::operator>>
constexpr dynamic_bitset< Block, Allocator > operator>>(size_type shift) const
Performs binary shift left of shift bits.
Definition dynamic_bitset.hpp:2496
sul::dynamic_bitset::reset
constexpr dynamic_bitset< Block, Allocator > & reset(size_type pos, size_type len)
Reset the bits of the range [pos, pos + len[ to false.
Definition dynamic_bitset.hpp:2583
sul::dynamic_bitset::operator>>=
constexpr dynamic_bitset< Block, Allocator > & operator>>=(size_type shift)
Performs binary shift right of shift bits.
Definition dynamic_bitset.hpp:2473
sul
Simple Useful Libraries.
Definition dynamic_bitset.hpp:147
sul::operator>=
constexpr bool operator>=(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Test if lhs is "greater than or equal to" rhs. The comparison of the two sul::dynamic_bitset is first...
Definition dynamic_bitset.hpp:3578
sul::operator<=
constexpr bool operator<=(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Test if lhs is "less than or equal to" rhs. The comparison of the two sul::dynamic_bitset is first on...
Definition dynamic_bitset.hpp:3566
sul::operator<
constexpr bool operator<(const dynamic_bitset< Block_, Allocator_ > &lhs, const dynamic_bitset< Block_, Allocator_ > &rhs)
Definition dynamic_bitset.hpp:3072
sul::operator>
constexpr bool operator>(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Test if lhs is "greater than" rhs. The comparison of the two sul::dynamic_bitset is first on numbers ...
Definition dynamic_bitset.hpp:3572
sul::operator>>
constexpr std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &is, dynamic_bitset< Block, Allocator > &bitset)
Extract a sul::dynamic_bitset from a character stream using its string representation.
Definition dynamic_bitset.hpp:3624
sul::operator|
constexpr dynamic_bitset< Block, Allocator > operator|(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Performs binary OR on corresponding pairs of bits of lhs and rhs.
Definition dynamic_bitset.hpp:3592
sul::operator&
constexpr dynamic_bitset< Block, Allocator > operator&(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Performs binary AND on corresponding pairs of bits of lhs and rhs.
Definition dynamic_bitset.hpp:3584
sul::operator-
constexpr dynamic_bitset< Block, Allocator > operator-(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Performs binary difference between bits of lhs and rhs.
Definition dynamic_bitset.hpp:3608
sul::operator^
constexpr dynamic_bitset< Block, Allocator > operator^(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Performs binary XOR on corresponding pairs of bits of lhs and rhs.
Definition dynamic_bitset.hpp:3600
sul::operator<<
constexpr std::basic_ostream< _CharT, _Traits > & operator<<(std::basic_ostream< _CharT, _Traits > &os, const dynamic_bitset< Block, Allocator > &bitset)
Insert a string representation of this sul::dynamic_bitset to a character stream.
Definition dynamic_bitset.hpp:3616
sul::operator==
constexpr bool operator==(const dynamic_bitset< Block_, Allocator_ > &lhs, const dynamic_bitset< Block_, Allocator_ > &rhs)
Definition dynamic_bitset.hpp:3065
sul::operator!=
constexpr bool operator!=(const dynamic_bitset< Block, Allocator > &lhs, const dynamic_bitset< Block, Allocator > &rhs)
Test if two sul::dynamic_bitset content are different.
Definition dynamic_bitset.hpp:3560
sul::swap
constexpr void swap(dynamic_bitset< Block, Allocator > &bitset1, dynamic_bitset< Block, Allocator > &bitset2) noexcept(noexcept(bitset1.swap(bitset2)))
Exchange the content of bitset1 and bitset2.
Definition dynamic_bitset.hpp:3671