### z4120's blog

By z4120, history, 3 years ago,

Note: All of the information in this blog relies on implementation-defined behavior. Do not use this in production code. In Codeforces contests, it's usually preferred to simply use hand-implemented bitset, because you've infinite time before the contest; or bitset (however bitset is printed differently from vector<bool> in GDB, and it doesn't work if you need dynamic size).

It's mentioned in a previous comment that bitset internal can be accessed by casting it to int32_t*. What about vector<bool>?

Method 1: cast its content to uint32_t* (or uint64_t*), but it'll only work when _GLIBCXX_DEBUG is not defined.

	vector<bool> a {1,0,0,1,0,1};
cout << * (uint32_t*&&) a << '\n';
cout << * (uint32_t*&&) a.begin() << '\n';


Both prints 41.

Method 2: Access _M_p and _M_offset members of the iterators.

In normal mode it works fine, but in debug mode it will throw this error

error: ‘std::__cxx1998::_Bit_type* std::__cxx1998::_Bit_iterator_base::_M_p’ is inaccessible within this context


In this case, just cast it to the base. If you want something that works with both lvalue and rvalue, you can use

#ifdef _GLIBCXX_DEBUG
__cxx1998::_Bit_iterator_base& PP(auto& x){ return (__cxx1998::_Bit_iterator_base&) x; }
__cxx1998::_Bit_iterator_base&& PP(auto&& x){ return (__cxx1998::_Bit_iterator_base&&) x; }
#else
template<class T>
auto&& /* decltype(auto) ? */ PP(T&& x){ return std::forward<T>(x); }
#endif


(any way to simplify the template?)

#define private public may work, but I don't recommend using it.

Sample code: computing bitwise AND of two vectors:

	vector<bool> a {1,1,0,1,0,1};
vector<bool> b {0,1,1,1,1,0};
transform(
PP(a.begin())._M_p,
PP(a.end())._M_p + (PP(a.end())._M_offset != 0),
PP(b.begin())._M_p,
PP(a.begin())._M_p,
[](auto x, auto y){ return x&y; });
for(int x : a) cout << x;


Don't forget + (T(a.end())._M_offset != 0) when necessary.

Find the first set bit:

	vector<bool> a(100);
a[52] = 1;

auto iter = begin(a);
PP(iter)._M_p = find_if(PP(iter)._M_p, PP(end(a))._M_p, [](auto x){ return x; });
iter = find(iter, end(a), 1);
cout << iter - begin(a) << '\n';


Note: While it's possible to change unused bits like this

	vector<bool> a {1,1,0,1,0,1};
*PP(a.begin())._M_p = 0b111111111;
a.resize(7);
for(int x : a) cout << x;


and it would still work fine, I'm not sure if it's always the case. It would simplify the implementation of some algorithm.

• +60