Jer*_*fin 25
这里有很多取决于你正在使用多少布尔值.
bitset和vector<bool>通常都使用压缩表示,其中布尔值仅存储为单个位.
一方面,这会以位操作的形式强加一些开销以访问单个值.
另一方面,这也意味着更多的布尔人将适合您的缓存.
如果你使用了很多布尔(例如,实施了一个Eratosthenes的筛子),那么在缓存中安装更多的布林将几乎总是获得净收益.内存使用的减少将比比特操作失败更多.
反对的大多数论点std::vector<bool>都回到了它不是标准容器的事实(即,它不符合容器的要求).IMO,这主要是一个期望的问题 - 因为它说vector,很多人都认为它是一个容器(其他类型的载体),并且它们经常对vector<bool>不是容器的事实做出负面反应.
如果你以一种真正需要它为容器的方式使用向量,那么你可能想要使用其他组合 - deque<bool>或者vector<char>可以正常工作.在你做这件事之前先想想 - 有很多(糟糕的,IMO)的建议,vector<bool>一般应该避免,很少或根本没有解释为什么应该避免它,或者在什么情况下它会对你产生真正的影响.
是的,有些情况下其他东西会更好.如果您处于其中一种情况,使用其他东西显然是个好主意.但是,请确保您首先处于其中一种情况.任何告诉你(例如)"Herb说你应该使用vector<char>"而没有对所涉及的权衡进行大量解释的人都不应该被信任.
让我们举一个真实的例子.由于评论中提到过,让我们考虑一下Eratosthenes的筛选:
#include <vector>
#include <iostream>
#include <iterator>
#include <chrono>
unsigned long primes = 0;
template <class bool_t>
unsigned long sieve(unsigned max) {
std::vector<bool_t> sieve(max, false);
sieve[0] = sieve[1] = true;
for (int i = 2; i < max; i++) {
if (!sieve[i]) {
++primes;
for (int temp = 2 * i; temp < max; temp += i)
sieve[temp] = true;
}
}
return primes;
}
// Warning: auto return type will fail with older compilers
// Fine with g++ 5.1 and VC++ 2015 though.
//
template <class F>
auto timer(F f, int max) {
auto start = std::chrono::high_resolution_clock::now();
primes += f(max);
auto stop = std::chrono::high_resolution_clock::now();
return stop - start;
}
int main() {
using namespace std::chrono;
unsigned number = 100000000;
auto using_bool = timer(sieve<bool>, number);
auto using_char = timer(sieve<char>, number);
std::cout << "ignore: " << primes << "\n";
std::cout << "Time using bool: " << duration_cast<milliseconds>(using_bool).count() << "\n";
std::cout << "Time using char: " << duration_cast<milliseconds>(using_char).count() << "\n";
}
我们已经使用了一个足够大的数组,我们可以预期它的很大一部分会占用主内存.我也有点痛苦,以确保在一次调用和另一次调用之间唯一改变的是使用vector<char>vs vector<bool>..这是一些结果.首先使用VC++ 2015:
ignore: 34568730
Time using bool: 2623
Time using char: 3108
...然后使用g ++ 5.1的时间:
ignore: 34568730
Time using bool: 2359
Time using char: 3116
显然,vector<bool>两种情况下的胜利 - 使用VC++约为15%,使用gcc约为30%.另请注意,在这种情况下,我选择的尺寸显示vector<char>在非常有利的光线下.如果,例如,我减少number从100000000到10000000时,时间差变得太大更大:
ignore: 3987474
Time using bool: 72
Time using char: 249
虽然我还没有做很多工作来确认,但我想在这种情况下,使用的版本vector<bool>节省了足够的空间,使得数组完全适合缓存,而且vector<char>足够大以溢出缓存,并且涉及大量的主存储器访问.
Age*_*ien 12
您通常应该避免,std::vector<bool>因为它不是标准容器.它是一个打包版本,所以它打破了一些通常给出的有价值的保证vector.一个有效的替代方案是使用std::vector<char>Herb Sutter推荐的方法.
您可以在他的GotW中阅读有关该主题的更多信息.
更新:
正如已经指出的那样,vector<bool>可以使用良好的效果,因为打包表示可以改善大型数据集的局部性.根据具体情况,它可能是最快的选择.不过,我仍然不是默认,因为它打破了许多所确立的承诺推荐它std::vector和包装是速度/内存权衡这可能是在速度和内存是有益的.
如果您选择使用它,我会在针对vector<char>您的应用进行测量之后这样做.即便如此,我还是建议使用a typedef来通过一个名称来引用它,而这个名称似乎并不能保证它不能保留.