如何将矢量<bool>归零？

Question

我有一个vector<bool>,我想把它归零.我需要大小保持不变.

通常的方法是迭代所有元素并重置它们.但是,vector<bool>是一个特别优化的容器,根据实现,每个元素只能存储一位.有没有办法利用这个来有效地清除整个事物？

bitset,固定长度的变体,具有该set功能.是否vector<bool>有类似的东西？

Answer 1

似乎有很多猜测,但到目前为止已经发布的答案中的事实很少,所以也许值得做一些测试.

#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毫秒差异不是真正可重复的).

值得一提的是,尽管g ++ 的这部分测试表现得更快,但总体时间在1%之内(VC++为4.944秒,g ++为4.915秒).

Answer 2

尝试

v.assign(v.size(), false);

看看这个链接:http: //www.cplusplus.com/reference/vector/vector/assign/

或者以下

std::fill(v.begin(), v.end(), 0)

Answer 3

你运气不好. std::vector<bool>是一种显然甚至不保证连续内存或随机访问迭代器(甚至转发？!)的特化,至少基于我对cppreference的读取 - 解码标准将是下一步.

因此,编写实现特定的代码,祈祷并使用一些标准的归零技术,或不使用该类型.我投票3.

接受的智慧是,这是一个错误,可能会被弃用.如果可能,请使用其他容器.绝对不要乱用内部胆量,或依靠其包装.检查您的std库mayhap中是否有动态bitset ,或者滚动自己的包装器std::vector<unsigned char>.

Answer 4

使用std::vector<bool>::assign为此目的提供的方法.如果某个实现是特定的bool,则assign很可能也适当地实现.

Answer 5

我最近遇到了这个性能问题.我没有尝试在网上寻找答案,但确实发现使用构造函数的赋值使用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>; 只是非常了解位向量表示.

Answer 6

如果您能够切换vector<bool>到自定义位向量表示,那么您可以使用专门为快速清除操作而设计的表示,并获得一些可能非常显着的加速(尽管不是没有权衡).

诀窍是使用每位向量条目的整数和单个"滚动阈值"值,该值确定哪些条目实际上评估为真.

然后,您可以通过增加单个阈值来清除位向量,而不会触及其余数据(直到阈值​​溢出).

可以在此处找到有关此内容以及一些示例代码的更完整的内容.