std::fill、std::copy是否专门为std::vector<bool>进行了优化?

16

当我思考这个问题时,我开始思考是否std::copy()和/或std::fill已经专门为std::vector<bool>进行了优化。

C++标准是否要求这样做,或者这是C++ std库供应商的常见做法?

简单地说,我想知道以下代码是否可行:

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++标准中允许吗?我知道这将是非便携的,但只用于一个选择的std C++库?假设我(或任何其他人)找到了一种方法来访问std::vector<bool>的私有部分。

1
不是必需的,但是允许这样做。我不知道是否有任何供应商这样做了。 - R. Martinho Fernandes
1
大多数情况下,在标准库中专门化大多数东西是不安全的。但是,您可以在任何其他命名空间中创建一个“fill”函数,并将其针对“vector<bool>”进行优化。 - Mooing Duck
1
只是间接相关,但你可能对我一段时间前发布的这个这个问题/答案感兴趣。 - user541686
1
对于这个问题来说有点晚了,可以参考这篇文章:http://isocpp.org/blog/2012/11/on-vectorbool。这篇文章是使用libc++(http://libcxx.llvm.org)编写的。文章详细介绍了几个通用的std::algorithms,并展示了如果针对`vector<bool>`进行优化可以实现什么样的效果。 - Howard Hinnant
@HowardHinnant 谢谢,非常有趣。我不知道确切的数字,但预计会有类似的结果。这就是为什么我问这个问题的原因。 - PiotrNycz
4个回答

13

STD是一个仅包含头文件的库,它随您的编译器一起提供。您可以自己查看这些头文件。对于GCC的vector<bool>实现,可以在stl_bvector.h中找到。对于其他编译器,该文件可能也是相同的。是的,还有专门的fill函数(在__fill_bvector附近查找)。


4
优化并没有在标准中要求。如果应用了优化,则假定这是“实现质量”问题。但是,大多数算法的渐进复杂度受到限制。
只要正确的程序按照标准要求运行,就允许使用优化。您所询问的示例,即使用std :: vector<bool>上的迭代器的标准算法涉及优化,可以通过实现看到其目标的任何方法来实现,因为没有监视它们如何实现的方式。尽管如此,我非常怀疑是否有任何标准库实现会优化对std :: vector<bool>的操作。大多数人似乎认为,这种特殊化本质上是一种可憎的方式,应该消失。
只有涉及至少一个用户定义类型的特殊化库类型才允许用户创建。我认为用户根本不允许在命名空间std中提供任何函数:因为所有这些函数都将涉及用户定义的类型,并且因此会在用户的命名空间中找到。换句话说:我认为您在目前无法获得针对std :: vector<bool>进行优化的算法。不过,您可以考虑向开源实现(例如libstdc ++libc ++)贡献优化版本。

1

虽然没有专门的支持,但你仍然可以使用它(即使速度很慢)。

但是,我发现了一个小技巧,可以使用代理类std::_Vbase,让std::fillstd::vector<bool>上起作用。

(警告:我只测试过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*,因此请通过使用const_cast移除其常量性
现在我们得到了指向原始元素的指针,该元素作为这些位的基础,std::_Vbase* elem_ptrelem_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()将原始向量与另一个向量交换时,指针向量将变得无用!


0

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

为了优化空间分配,提供了专门用于布尔元素的向量特化:

之后提供了位集合的特化。这就是标准关于vector<bool>的全部内容,供应商需要使用位集合来实现它以优化空间。在这里,为了不优化速度而进行空间优化是有代价的。

从图书馆借一本书比在所有密集容器中夹杂在一起的书中找到一本书要容易得多....


拿你的例子来说,你正在尝试从开始到结束做一个std::fillstd::copy。但这并不总是如此,有时它并不仅仅映射到整个字节。因此,在速度优化方面存在一些问题。对于您需要将每个位更改为1的情况很容易,只需将字节更改为0xF即可,但在这种情况下并非如此;如果您只更改字节的某些位,则变得更加困难。然后,您需要实际计算字节将是什么;这不是一件微不足道的事情*,或者至少不是当前硬件上的原子操作。
这是过早优化的故事,在空间方面很好,但在性能方面很糟糕。
检查是否为"8位的倍数"值得开销吗?我怀疑。 * 我们在这里谈论多个位,如果只有一个位,您当然可以进行位操作。

坦白地说,我考虑了更复杂的情况,其中start和stop不等于begin()和end()。 - PiotrNycz

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