我有一个vector<bool>
,想将它清零,但需要保持大小不变。
通常的方法是遍历所有元素并重置它们。然而,vector<bool>
是一个特别优化的容器,根据实现方式,每个元素可能只存储一位(bit)。是否有一种方法可以利用这一点来高效地清空整个向量?
bitset
, 固定长度的变体,具有set
函数。那么vector<bool>
是否有类似的功能呢?
到目前为止,已经发布的回答中似乎有很多猜测,但很少有事实,因此进行一些测试可能会是值得的。
#include <vector>
#include <iostream>
#include <time.h>
int seed(std::vector<bool> &b) {
srand(1);
for (int i = 0; i < b.size(); i++)
b[i] = ((rand() & 1) != 0);
int count = 0;
for (int i = 0; i < b.size(); i++)
if (b[i])
++count;
return count;
}
int main() {
std::vector<bool> bools(1024 * 1024 * 32);
int count1= seed(bools);
clock_t start = clock();
bools.assign(bools.size(), false);
double using_assign = double(clock() - start) / CLOCKS_PER_SEC;
int count2 = seed(bools);
start = clock();
for (int i = 0; i < bools.size(); i++)
bools[i] = false;
double using_loop = double(clock() - start) / CLOCKS_PER_SEC;
int count3 = seed(bools);
start = clock();
size_t size = bools.size();
bools.clear();
bools.resize(size);
double using_clear = double(clock() - start) / CLOCKS_PER_SEC;
int count4 = seed(bools);
start = clock();
std::fill(bools.begin(), bools.end(), false);
double using_fill = double(clock() - start) / CLOCKS_PER_SEC;
std::cout << "Time using assign: " << using_assign << "\n";
std::cout << "Time using loop: " << using_loop << "\n";
std::cout << "Time using clear: " << using_clear << "\n";
std::cout << "Time using fill: " << using_fill << "\n";
std::cout << "Ignore: " << count1 << "\t" << count2 << "\t" << count3 << "\t" << count4 << "\n";
}
这段代码创建了一个向量,设置其中一些随机选择的位,计算它们并清除它们(然后重复)。设置/计数/打印是为了确保即使进行激进的优化,编译器也不能/不会将我们的代码优化掉以清除向量。
我发现结果非常有趣。首先是使用VC++的结果:
Time using assign: 0.141
Time using loop: 0.068
Time using clear: 0.141
Time using fill: 0.087
Ignore: 16777216 16777216 16777216 16777216
Time using assign: 0.002
Time using loop: 0.08
Time using clear: 0.002
Time using fill: 0.001
Ignore: 16777216 16777216 16777216 16777216
在这里,循环是(远远)最慢的方法(其他方法基本上是相当的 - 1毫秒的速度差异并不真正可重复)。
值得一提的是,尽管测试的这部分在g ++中显示出了更快的速度,但总体时间相差不到1%(VC ++为4.944秒,g ++为4.915秒)。
fill
在两次测试中都出现在更快的组中。我认为这里的重点是 vector<bool>
不可靠。 - Adam尝试
v.assign(v.size(), false);
请查看此链接:http://www.cplusplus.com/reference/vector/vector/assign/
或者以下内容:
std::fill(v.begin(), v.end(), 0)
assign
中的std::fill
是针对容器单词而不是单个位。因此,这可能是一种优化的方式,至少对于GCC来说是这样。Jerry的VC测试是相反的。 - Adam你运气不太好。 std::vector<bool>
是一种特化类型,据我阅读cppreference所得,它甚至不能保证连续的内存或随机访问迭代器(甚至不支持前向迭代器?!)-- 解码标准将是下一步。
因此,编写实现特定的代码,祈祷并使用某些标准的清零技术,或者不使用该类型。我投票选第三个选项。
有人认为这是一个错误,可能会被废弃。如果可能的话,请使用其他容器。绝对不要擅自更改其内部结构或依赖于其打包方式。检查您的std
库中是否有动态位集,或者在std::vector<unsigned char>
周围编写自己的包装器。
最近我遇到了这个性能问题。我没有尝试在网上寻找答案,但是发现使用构造函数的赋值比使用malloc
快10倍,使用g++ O3 (Debian 4.7.2-5) 4.7.2。我发现这个问题是因为我想避免额外的malloc
。看起来赋值操作与构造函数一样被优化了,并且在我的基准测试中大约快两倍。
unsigned sz = v.size(); for (unsigned ii = 0; ii != sz; ++ii) v[ii] = false;
v = std::vector(sz, false); // 10x faster
v.assign(sz, false); > // 20x faster
因此,我不建议避免使用vector<bool>
的专业知识;只需要非常清楚地了解位向量表示即可。
std::vector<bool>::assign
方法来完成此操作。如果实现是针对bool
的,那么assign
方法很可能也会被适当地实现。vector<bool>
转换到自定义位向量表示,那么你可以使用专为快速清除操作设计的表示,并获得一些可能相当显着的加速(虽然不是没有权衡)。技巧在于每个位向量条目使用整数和单个“滚动阈值”值,该值确定哪些条目实际上会评估为true。因此,你只需增加单个阈值,而不触及其余数据(直到阈值溢出),就可以清除位向量。关于这方面的更完整写作和一些示例代码,请查看此处。看起来有一个不错的选项还没有被提到:
auto size = v.size();
v.resize(0);
v.resize(size);
STL实现者应该选择最有效的清零方法,所以我们甚至不需要知道具体是哪种方法。这也适用于真正的向量(考虑模板),而不仅仅是std::vector<bool>
这样的怪物。
在循环中可以使用重用的缓冲区来获得微小的优势(例如筛子等),在其中只需将大小调整为当前回合所需的大小,而不是原始大小。
作为 std::vector<bool>
的替代方案,可以尝试使用 boost::dynamic_bitset
(https://www.boost.org/doc/libs/1_72_0/libs/dynamic_bitset/dynamic_bitset.html)。通过调用 reset()
成员函数,您可以将所有元素都设置为 false。
与清除 std::vector<int>
类似,boost::dynamic_bitset
上的 reset
也可以编译成 memset
,而在 std::vector<bool>
上可能无法实现。例如,请参见 https://godbolt.org/z/aqSGCi
std::fill
这样的算法在你的标准库实现中是专门为std::vector<bool>
优化的。 - Björn Pollexvector<bool>
,因为它可以说是有问题的。 - Bartek Banachewiczstd::vector<bool>
存在不幸的问题,但最初添加它的原因正是为了解决这样的问题。那么,“不要使用它”并不是一个合适的评论。 - MSalters