12

众所周知，它std::vector<bool>不满足标准的容器要求，主要是因为打包表示阻止T* x = &v[i]返回指向布尔值的指针。

我的问题是：当reference_proxy 重载address-of以返回pointer_proxy时，这可以补救/缓解吗？operator&

在大多数实现中，指针代理可以包含与 reference_proxy 相同的数据，即指向打包数据的指针和用于隔离块内指向的特定位的掩码。然后，pointer_proxy 的间接生成将产生 reference_proxy。本质上，这两个代理都是“胖”指针，但是与基于磁盘的代理容器相比，它们仍然相当轻量级。

而不是T* x = &v[0]一个人可以这样做auto x = &v[0]，并且使用xlikeif(*x)没有问题。我也希望能够写for(auto b: v) { /* ... */ }

问题：这种多代理方法是否适用于 STL 的算法？还是某些算法真的依赖于x需要成为真实的需求bool*？或者是否有太多连续的用户定义转换需要阻止它工作？在尝试完全完成上述实现草图之前，我想知道任何此类障碍。

更新（基于@HowardHinnant 的回答和关于 comp.std.c++的古老讨论）

您几乎可以模仿内置类型：对于任何给定的类型 T，可以使一对代理（例如 reference_proxy 和 iterator_proxy）相互一致，即 reference_proxy::operator&() 和 iterator_proxy::operator* () 互为逆。

但是，在某些时候需要将代理对象映射回其行为类似于 T* 或 T&。对于迭代器代理，可以重载 operator->() 并访问模板 T 的接口，而无需重新实现所有功能。但是，对于参考代理，您需要重载 operator.()，这在当前的 C++ 中是不允许的（尽管Sebastian Redl 在 BoostCon 2013 上提出了这样的提议）。您可以在引用代理中进行详细的解决方法，例如 .get() 成员，或者在引用中实现所有 T 的接口（这是对 vector::bit_reference 所做的），但这会丢失内置语法或引入没有用于类型转换的内置语义的用户定义的转换（每个参数最多可以有一个用户定义的转换）。

4

2 回答 2

7

我的问题是：当reference_proxy 重载地址操作符& 以返回pointer_proxy 时，这可以补救/缓解吗？

libc++实际上就是这样做的。

#include <vector>
#include <cassert>

int main()
{
    std::vector<bool> v(1);
    std::vector<bool>::pointer pb = &v[0];
    assert(*pb == false);
    *pb = true;
    assert(v[0] == true);
    std::vector<bool>::const_pointer cbp = pb;
    assert(*cbp == true);
    v[0] = false;
    assert(*cbp == false);
}

const_pointer它甚至延伸到const_reference模仿相同类型的vector<int>. 这是 libc++ 的不符合标准的扩展。但这使得编写可能被实例化的通用代码vector<bool>更有可能编译和正确运行。

问题：这种多代理方法是否适用于 STL 的算法？还是某些算法真的依赖于 x 必须是真正的 bool* 的要求？或者是否有太多连续的用户定义转换需要阻止它工作？

所有 libc++ 的算法都适用于vector<bool>. 其中一些表现相当壮观。特别是一种算法必须进行特殊处理，但遗憾的是该标准并未强制要求：

#include <vector>
#include <cassert>

int main()
{
    std::vector<bool> v(1);
    bool b = true;
    assert(v[0] == false);
    assert(b == true);
    std::swap(b, v[0]);
    assert(v[0] == true);
    assert(b == false);
}

这很容易实现。只需确保swap适用于bool和的任何组合vector<bool>::reference。但我不知道除了 libc++ 是否有任何实现可以做到这一点，而且它不是 C++11 强制要求的。

位数组是一种奇妙的数据结构。但不幸的是，它在 C++ 标准中的规定很差。libc++ 已经有些违法了，以证明这可能是一个非常有用和高性能的数据结构。希望未来的 C++ 标准可以朝这个方向迁移，以使 C++ 程序员受益。

于 2013-02-26T01:49:40.247 回答
1

我首先要说的是，它实际上将更多地取决于每个单独的 STL 实现的细节，因为它不正式符合标准要求 *reference_type 是 T* 的左值。因此，关于潜在的实施问题：

任何一段代码都显式依赖于容器的指针是真实 的主要原因bool*是算法是否使用指针算法，在这种情况下指针类型的大小变得相关。指针算法虽然会绕过迭代器接口，从而破坏了整个 STL 逐个迭代器容器设计的主要目的。std::vector<> 本身在 C++11 中保证是连续的，这允许优化 STL 算法和编译器 for(:) 的特化，两者都可以在内部使用指针算术。如果您的类型不是从 std::vector 派生的，那么这应该不是问题；一切都应该只假设迭代器方法。

然而！ STL 代码可能仍然使用指针，但不是为了指针算术，而是为了其他目的。在这种情况下，问题是C++ 语法。例如，引用您自己的问题：

而不是T* x = &v[0]一个可以做auto x = &v[0]

STL 中的任何模板化代码也必须做同样的事情……而且在这一点上，STL 实现似乎完全不可能广泛使用auto. 可能还有其他情况是 STL 尝试执行巧妙的 r 值转换技巧，但最终失败，因为它不期望不匹配的引用类型。

关于for(auto b: v) { /* ... */ }：我认为没有理由不应该工作。我认为它生成的代码的效率远低于你可以在 15 分钟（或更短时间）内完成的相同版本。我只是在你提到内在函数后才提出来在 OP 中，这意味着对性能的一些考虑。您也无法使用内在函数来帮助它。内在函数无法以某种方式超越用于顺序遍历位数组的简单按位移位。大部分增加的开销将来自编译器生成代码以更新迭代器指针和掩码值，然后在下一次迭代时重新加载掩码值。它无法神奇地推断出您正在尝试做的事情并将其变成您的顺序移位操作。它至少可以通过将指针更新+写回阶段缓存到循环外的寄存器中来优化它，但老实说，根据我的经验，我会非常怀疑。

这是一种从头到尾遍历位的方法，只是为了比较（能够从位流中的任意点开始的版本需要一些额外的设置逻辑）：

uint64_t* pBitSet   = &v[-1];   // gets incremented on first iteration through loop.
uint64_t  curBitSet =  v[0];

for (int i=0; i<v.length(); ++i)  {
    if ((i % 64) == 0) {
       curBitSet = *(++pBitSet);
    }
    int bit = curBitSet & 1;
    curBitSet >>= 1;

    // do stuff based on 'bit' here.
}
于 2012-12-31T22:03:07.397 回答