# 一些关于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.

[经这篇文章测试](http://www.cnblogs.com/wpcockroach/p/3179572.html)，按操作次数计时，`std::vector<bool>`的访问效率相比标准`std::vector<T>`，速度慢了大约40倍。当然，空间也节省了`sizeof<T>`倍，这个就看取舍了。

然而没有一个内存连续排列的`bool`容器，有时候毕竟还是不方便。我在做的这个工程恰好已经用到了[thrust](https://thrust.github.io/)，一个类似`std`但支持异构并行的模板库（可以看作是`std`的并行复刻版），其内部实现中没有对`bool`特殊关照，直接拿来用就解决了问题。当然如果工程中本来不引用`thrust`，自然就没必要加这么一个大号依赖了，各显神通咯。