Tutorial: Internal access to vector bool

Revision en3, by z4120, 2020-01-08 18:52:26

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English z4120 2020-01-08 18:52:26 10
en2 English z4120 2020-01-08 18:50:46 3
en1 English z4120 2020-01-08 18:49:42 2716 Initial revision (published)