一些关于std::vector<bool>的问题
前天写程序需要用到一个可变长度的bool
数组,于是很自然地写上std::vector<bool>
。后面由于要多线程访问,就用std::vector<bool>::data()
方法转了个指针出来,然后gcc
就跟我翻脸了……
各种尝试查错的过程就不说了,反正最后结果挺尴尬的:std::vector<bool>
这丫的就不是个(纯种的)容器啊!它虽然看起来像,不涉及内存结构的时候用起来也像,但是内部实现并不是往vector
里面放一些bool
。
std::vector<bool>
is a space-efficient specialization of std::vector for the type bool.- The manner in which
std::vector<bool>
is made space efficient (as well as whether it is optimized at all) is implementation defined. One potential optimization involves coalescing vector elements such that each element occupies a single bit instead ofsizeof(bool)
bytes. std::vector<bool>
behaves similarly tostd::vector
, but in order to be space efficient, it:- Does not necessarily store its elements as a contiguous array (so
&v[0] + n != &v[n]
) - Exposes class
std::vector<bool>::reference
as a method of accessing individual bits. In particular, objects of this class are returned byoperator[]
by value. - Does not use
std::allocator_traits::construct
to construct bit values. - Does not guarantee that different elements in the same container can be modified concurrently by different threads.
经这篇文章测试,按操作次数计时,std::vector<bool>
的访问效率相比标准std::vector<T>
,速度慢了大约40倍。当然,空间也节省了sizeof<T>
倍,这个就看取舍了。
然而没有一个内存连续排列的bool
容器,有时候毕竟还是不方便。我在做的这个工程恰好已经用到了thrust,一个类似std
但支持异构并行的模板库(可以看作是std
的并行复刻版),其内部实现中没有对bool
特殊关照,直接拿来用就解决了问题。当然如果工程中本来不引用thrust
,自然就没必要加这么一个大号依赖了,各显神通咯。