logo标签列表

如何将vector<bool>清零？

c++vector
30

我有一个vector<bool>，想将它清零，但需要保持大小不变。

通常的方法是遍历所有元素并重置它们。然而，vector<bool>是一个特别优化的容器，根据实现方式，每个元素可能只存储一位(bit)。是否有一种方法可以利用这一点来高效地清空整个向量？

bitset, 固定长度的变体，具有set函数。那么vector<bool>是否有类似的功能呢？

5
使用std::fill函数，将容器v的所有元素设置为0。 - Kakalokia
3
这是OP隐含提到的一种常规方式，可能并没有利用在操作中设置8位。 - masoud
1
你计时了吗？也许像std::fill这样的算法在你的标准库实现中是专门为std::vector<bool>优化的。 - Björn Pollex
2
一个好的方法也是不要使用vector<bool>，因为它可以说是有问题的。 - Bartek Banachewicz
2
尽管 std::vector<bool> 存在不幸的问题，但最初添加它的原因正是为了解决这样的问题。那么，“不要使用它”并不是一个合适的评论。 - MSalters
显示剩余4条评论
8个回答
25

到目前为止，已经发布的回答中似乎有很多猜测，但很少有事实，因此进行一些测试可能会是值得的。

#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秒）。

两个平台之间的相对差异令人惊讶。只有 fill 在两次测试中都出现在更快的组中。我认为这里的重点是 vector<bool> 不可靠。 - Adam
2
“不可靠”意味着它不能正常工作。但实际上，它可以在任何地方工作，并且您似乎可以依赖其高效的内存实现。唯一不能保证的是速度。 - MSalters
@MSalters：除了它在某些方面不是完全符合向量（STL容器）的规范之外...然而，对于简洁地总结大多数人需要知道的内容，我给予+1。 - DarthGizka
21
2
"Try" 和 "may work"；两种猜测放在一句话里；不是很高质量的答案。特别是在 C++ 中，这样的回答可能是不可移植的，甚至是危险的。 - Sebastian Mach
9
@phresnel，当我说“try”时，我的意思是我相信这段代码能够正常工作。对于第二段代码，我不是很确定，但并没有做出应该被投反对票的事情 :) - Kakalokia
1
请注意，gcc实现的assign实际上执行了std::fill操作。详情请参见http://gcc.gnu.org/git/?p=gcc.git;a=blob_plain;f=libstdc%2B%2B-v3/include/bits/stl_bvector.h;hb=HEAD。 - log0
1
@log0 我不是100%确定，但我认为assign中的std::fill是针对容器单词而不是单个位。因此，这可能是一种优化的方式，至少对于GCC来说是这样。Jerry的VC测试是相反的。 - Adam
10

你运气不太好。 std::vector<bool> 是一种特化类型，据我阅读cppreference所得，它甚至不能保证连续的内存或随机访问迭代器（甚至不支持前向迭代器？！）-- 解码标准将是下一步。

因此，编写实现特定的代码，祈祷并使用某些标准的清零技术，或者不使用该类型。我投票选第三个选项。

有人认为这是一个错误，可能会被废弃。如果可能的话，请使用其他容器。绝对不要擅自更改其内部结构或依赖于其打包方式。检查您的std库中是否有动态位集，或者在std::vector<unsigned char>周围编写自己的包装器。

1
这并没有直接回答问题，但你的选择3可能是正确的前进道路。使用一个从一开始就为此目的而设计的容器执行相同的操作。 @TemplateRex的链接展示了正确（和错误）使用位向量的优点：http://isocpp.org/blog/2012/11/on-vectorbool - Adam
8

最近我遇到了这个性能问题。我没有尝试在网上寻找答案，但是发现使用构造函数的赋值比使用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>的专业知识；只需要非常清楚地了解位向量表示即可。

谢谢解决方案。有人能告诉我为什么“assign”比循环快这么多吗？内部必须循环设置值，对吧？ - Wikunia
7
使用std::vector<bool>::assign方法来完成此操作。如果实现是针对bool的，那么assign方法很可能也会被适当地实现。
5
如果你能从vector<bool>转换到自定义位向量表示，那么你可以使用专为快速清除操作设计的表示，并获得一些可能相当显着的加速（虽然不是没有权衡）。技巧在于每个位向量条目使用整数和单个“滚动阈值”值，该值确定哪些条目实际上会评估为true。因此，你只需增加单个阈值，而不触及其余数据（直到阈值溢出），就可以清除位向量。关于这方面的更完整写作和一些示例代码，请查看此处。
4

看起来有一个不错的选项还没有被提到：

auto size = v.size();
v.resize(0);
v.resize(size);

STL实现者应该选择最有效的清零方法，所以我们甚至不需要知道具体是哪种方法。这也适用于真正的向量（考虑模板），而不仅仅是std::vector<bool>这样的怪物。

在循环中可以使用重用的缓冲区来获得微小的优势（例如筛子等），在其中只需将大小调整为当前回合所需的大小，而不是原始大小。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接