一些关于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 of sizeof(bool) bytes.
• std::vector<bool> behaves similarly to std::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 by operator[] 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，自然就没必要加这么一个大号依赖了，各显神通咯。