我有一个vector<bool>
,我想把它归零。我需要尺寸保持不变。
正常的方法是遍历所有元素并重置它们。但是,vector<bool>
它是一个经过特别优化的容器,根据实现,每个元素可能只存储一位。有没有办法利用这一点来有效地清除整个事情?
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
因此,对于 VC++,最快的方法可能是您最初认为最幼稚的方法——分配给每个单独项目的循环。使用 g++,结果只是有点不同:
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 ms 的速度差异并不是真正可重复的)。
值得一提的是,尽管这部分测试使用 g++ 显示得更快,但总体时间彼此相差不到 1%(VC++ 为 4.944 秒,g++ 为 4.915 秒)。
尝试
v.assign(v.size(), false);
看看这个链接: http ://www.cplusplus.com/reference/vector/vector/assign/
或以下
std::fill(v.begin(), v.end(), 0)
你运气不好。 std::vector<bool>
至少基于我对 cppreference 的阅读,显然甚至不保证连续内存或随机访问迭代器(甚至向前?!)的专业化——解码标准将是下一步。
所以编写实现特定的代码,祈祷并使用一些标准的归零技术,或者不使用类型。我投票3。
收到的智慧是这是一个错误,可能会被弃用。如果可能,请使用不同的容器。绝对不要乱搞内部胆量,或者依赖它的包装。检查您的std
库中是否有动态位集,或者滚动您自己的包装器std::vector<unsigned char>
。
使用std::vector<bool>::assign
为此目的提供的方法。如果实现特定于bool
,那么assign
很可能也适当地实现。
我最近遇到了这个作为性能问题。我没有尝试在网上寻找答案,但确实发现使用 g++ O3 (Debian 4.7.2-5) 4.7.2 对构造函数进行赋值要快 10 倍。我发现这个问题是因为我想避免额外的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>
。只需非常了解位向量表示即可。
如果您能够切换vector<bool>
到自定义位向量表示,那么您可以使用专为快速清除操作而设计的表示,并获得一些潜在的相当显着的加速(尽管并非没有权衡)。
诀窍是对每个位向量条目使用整数和一个“滚动阈值”值,该值确定哪些条目实际上随后评估为真。
然后,您可以通过仅增加单个阈值来清除位向量,而无需触及其余数据(直到阈值溢出)。
可以在此处找到有关此内容的更完整的文章和一些示例代码。
似乎还没有提到一个不错的选择:
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>
,reset
在 aboost::dynamic_bitset
上也可以编译成 a memset
,而你可能不会用std::vector<bool>
. 例如,请参阅https://godbolt.org/z/aqSGCi