16

在考虑这个问题时，我开始怀疑std::copy()和/或std::fill是否专门（我的意思是优化）std::vector<bool>.

这是 C++ 标准所要求的，还是 C++ 标准库供应商常用的方法？

简单来说，不知道是不是下面的代码：

std::vector<bool> v(10, false);
std::fill(v.begin(), v.end(), true);

在任何方面都比这更好/不同：

std::vector<bool> v(10, false);
for (auto it = v.begin(); it != v.end(); ++it) *it = true;

非常严格 - 可以说：std::fill<std::vector<bool>::iterator>()进入内部表示std::vector<bool>并设置它们的整个字节而不是单个位？我认为交std::fill朋友std::vector<bool>对图书馆供应商来说不是一个大问题？

[更新]

std::vector<bool>下一个相关问题：如果还没有专门化，我（或其他任何人：）可以专门化这样的算法吗？这是 C++ 标准允许的吗？我知道这将是不可移植的 - 但仅适用于一个选定的标准 C++ 库？假设我（或其他任何人）找到了接触std::vector<bool>私处的方法。

4

4 回答 4

13

STD 是仅标头库，它随您的编译器一起提供。您可以自己查看这些标题。因为 GCC 的vector<bool> 执行是在stl_bvector.h. 对于其他编译器，它也可能是相同的文件。是的，有专门的fill（看附近__fill_bvector）。

于 2012-09-15T05:07:33.497 回答
4

标准中没有强制要求进行优化。如果可以应用优化，则假定这是一个“实施质量”问题。然而，大多数算法的渐近复杂度是有限的。

只要正确的程序按照标准要求运行，就可以进行优化。您询问的示例，即涉及使用迭代器 on 的标准算法的优化std::vector<bool>，几乎可以以实现认为合适的任何方式实现其目标，因为没有办法监控它们是如何实现的。这就是说，我非常怀疑. 上是否有任何标准库实现优化操作std::vector<bool>。大多数人似乎认为这种专业化一开始就令人憎恶，应该消失。

如果专业化涉及至少一种用户定义的类型，则仅允许用户创建库类型的专业化。我认为根本不允许用户在命名空间std中提供任何功能：没有任何需求，因为所有此类功能都将涉及用户定义的类型，因此可以在用户的​​命名空间中找到。std::vector<bool>表述方式不同：我认为您暂时无法优化算法。但是，您可能会考虑为开源实现贡献优化版本（例如libstdc++和libc++）。

于 2012-09-15T01:05:37.253 回答
1

它没有专门化，但您仍然可以使用它。（虽然很慢）

但这是我发现的一个技巧，它使用代理类std::fill启用。std::vector<bool>std::_Vbase

（警告：我仅针对 MSVC2013 对其进行了测试，因此它可能不适用于其他编译器。）

int num_bits = 100000;
std::vector<bool> bit_set(num_bits , true);

int bitsize_elem = sizeof(std::_Vbase) * 8; // 1byte = 8bits
    
int num_elems = static_cast<int>(std::ceil(num_bits / static_cast<double>(bitsize_elem)));

在这里，因为如果你使用一个元素的任何一个位，你就需要它的整个位，所以元素的数量必须向上取整。

使用这些信息，我们将构建一个指针向量，指向位下的原始元素。

std::vector<std::_Vbase*> elem_ptrs(num_elems, nullptr);

std::vector<bool>::iterator bitset_iter = bit_set.begin();
for (int i = 0; i < num_elems; ++i)
{
    std::_Vbase* elem_ptr = const_cast<std::_Vbase*>((*bitset_iter)._Myptr);
    elem_ptrs[i] = elem_ptr;
    std::advance(bitset_iter, bitsize_elem);
}

(*bitset_iter)._Myptr: 通过取消引用 的迭代器std::vector<bool>，您可以访问代理类reference及其成员_Myptr。

由于返回类型std::vector<bool>::iterator::operator*()是const std::_Vbase*， 因此将它的 constness 删除const_cast。

现在我们得到指向这些位下面的原始元素的指针std::_Vbase* elem_ptr。

elem_ptrs[i] = elem_ptr: 记录这个指针，...

std::advance(bitset_iter, bitsize_elem): ...并继续我们的旅程，通过跳跃前一个元素持有的位来寻找下一个元素。

std::fill(elem_ptrs[0], elem_ptrs[0] + num_elems, 0); // fill every bits "false"
std::fill(elem_ptrs[0], elem_ptrs[0] + num_elems, -1); // fill every bits "true"

现在，我们可以使用std::fill指针向量，而不是位向量。

也许有些人可能会在外部使用代理类感到不舒服，甚至删除它的常量。

但是，如果您不关心这一点并且想要快速的东西，这是最快的方法。

我在下面做了一些比较。（做了新项目，没有改变配置，发布，x64）

int it_max = 10; // do it 10 times ...
int num_bits = std::numeric_limits<int>::max(); // 2147483647

std::vector<bool> bit_set(num_bits, true);
for (int it_count = 0; it_count < it_max; ++it_count)
{
    std::fill(elem_ptrs[0], elem_ptrs[0] + num_elems, 0);
} // Elapse Time : 0.397sec

for (int it_count = 0; it_count < it_max; ++it_count)
{
    std::fill(bit_set.begin(), bit_set.end(), false);
} // Elapse Time : 18.734sec

for (int it_count = 0; it_count < it_max; ++it_count)
{
    for (int i = 0; i < num_bits; ++i)
    {
        bit_set[i] = false;
    }
} // Elapse Time : 21.498sec

for (int it_count = 0; it_count < it_max; ++it_count)
{
    bit_set.assign(num_bits, false);
} // Elapse Time : 21.779sec

for (int it_count = 0; it_count < it_max; ++it_count)
{
    bit_set.swap(std::vector<bool>(num_bits, false)); // You can not use elem_ptrs anymore
} // Elapse Time : 1.3sec

有一个警告。当您swap()将原始向量与另一个向量结合时，指针向量就变得无用了！

于 2020-09-26T07:59:53.457 回答
0

23.2.5 C++ 国际标准中的类向量告诉我们

为了优化空间分配，提供了一个专门针对 bool 元素的向量：

之后提供 bitset 特化。就标准而言vector<bool>，供应商需要使用位集来实现它以优化空间。优化空间是有代价的，因为不优化速度。

如果一本书是在所有紧密装订在容器中的图书馆书籍之间，那么从图书馆取一本书比找到一本书更容易......

以你的例子为例，你正试图从头到尾做一个std::fill或std::copy。但情况并非总是如此，有时它不仅仅是简单地映射到整个字节。所以，这在速度优化方面有点问题。对于必须将每一位更改为 1 的情况很容易，这只是将字节更改为 0xF，但这里不是这种情况；如果您只更改字节的某些位，则会变得更加困难。然后你需要实际计算字节是什么；这不是一件小事*，或者至少不是当前硬件上的原子操作。

这是过早的优化故事，它在空间方面很好，但在性能方面却很糟糕。

有一张"is a multiple of 8 bits"支票值得开销吗？我对此表示怀疑。

* 我们这里说的是多位，对于只有一位的情况，你当然可以做位操作。

于 2012-09-15T01:00:22.663 回答