多个代理类是否构成一个STL防护位向量? [英] Could multiple proxy classes make up a STL-proof bitvector?
问题描述
这是知名的, std :: vector< bool> ;
不满足标准的容器要求,主要是因为打包表示阻止 T * x =& v [i]
一个bool。
我的问题是:当reference_proxy重载运算符&
返回一个pointer_proxy?
在大多数实现中,指针代理可以包含与reference_proxy相同的数据,即指向打包数据的指针mask来隔离指向的块内的特定位。 pointer_proxy的间接然后将产生reference_proxy。基本上两个代理都是胖指针,然而,与基于磁盘的代理容器相比,它们仍然相当轻。
而不是然后可以使用
auto x =& v [0]
,然后使用 x
像 if(* x)
没有问题。我也想为 auto(b:v){/ * ... * /}
问题:这样的多代理方法与STL的算法一起使用?或者一些算法真的依赖于 x
需要是一个真实的 bool *
的要求?或者是否需要太多连续的用户定义转换才能阻止这种转换?在尝试完全完成上述实现草图之前,我想知道任何此类障碍。
UPDATE (基于@HowardHinnant的回答和此关于comp.std.c ++的古代讨论)
你可以走很长的路,几乎模仿内置类型:对于任何给定类型T,在reference_proxy :: operator&()和iterator_proxy :: operator *()彼此相反的意义上,一对代理(例如,reference_proxy和iterator_proxy)可以相互一致。 / p>
然而,在某些时候,需要将代理对象映射回T *或T&T行为。对于迭代器代理,可以重载operator - >()并访问模板T的接口,而不需要重新实现所有的功能。然而,对于引用代理,你需要重载operator。(),这是不允许在当前C + +(虽然 Sebastian Redl在BoostCon 2013上提出了这样的建议)。你可以像引用代理中的.get()成员一样进行冗长的工作,或者在引用中实现T的所有接口(这是为vector :: bit_reference做的),但是这将丢失内置语法或者引入没有类型转换的内建语义的用户定义转换(每个参数最多只能有一个用户定义的转换)。
解决方案
我的问题是:当
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 $ c $以向量< int>
模拟相同类型的方式使用和 const_reference
。这是libc ++的不符合扩展名。但是它使得编写可能在向量< bool>
上实例化的通用代码更容易编译和正确运行。
< blockquote>
问题:这样的多代理方法与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
和向量< bool> :: reference
。但我不知道除了libc ++之外是否有任何实现这一点,并且它不是由C ++ 11强制。
一个位数组是一个精彩数据结构。但不幸的是,它在C ++标准中指定不好。 libc ++有点过时,以证明这可以是一个非常有用和高性能的数据结构。希望未来的C ++标准可以沿着这个方向向C ++程序员的利益转移。
It's well known that std::vector<bool>
does not satisfy the Standard's container requirements, mainly because the packed representation prevents T* x = &v[i]
from returning a pointer to a bool.
My question is: can this be remedied/mitigated when the reference_proxy overloads the address-of operator&
to return a pointer_proxy?
The pointer-proxy could contain the same data as the reference_proxy in most implementations, namely a pointer into the packed data and a mask to isolate the particular bit inside the block pointed to. Indirection of the pointer_proxy would then yield the reference_proxy. Essentially both proxies are "fat" pointers, which are, however, still rather light-weight compared to disk-based proxy containers.
Instead of T* x = &v[0]
one could then do auto x = &v[0]
, and use x
like if(*x)
without problems. I would also like to be able to write for(auto b: v) { /* ... */ }
Questions: would such a multi-proxy approach work with the STL's algorithms? Or do some algorithms really rely on the requirement that x
needs to be a real bool*
? Or are there too many consecutive user-defined conversions required that prevent this to work? I'd like to know any of such obstructions before trying to fully complete the above implementation sketch.
UPDATE (based on @HowardHinnant 's answer and this ancient discussion on comp.std.c++)
You can come a long way to almost mimic the builtin types: for any given type T, a pair of proxies (e.g. reference_proxy and iterator_proxy) can be made mutually consistent in the sense that reference_proxy::operator&() and iterator_proxy::operator*() are each other's inverse.
However, at some point one needs to map the proxy objects back to behave like T* or T&. For iterator proxies, one can overload operator->() and access the template T's interface without reimplementing all the functionality. However, for reference proxies, you would need to overload operator.(), and that is not allowed in current C++ (although Sebastian Redl presented such a proposal on BoostCon 2013). You can make a verbose work-around like a .get() member inside the reference proxy, or implement all of T's interface inside the reference (this is what is done for vector::bit_reference), but this will either lose the builtin syntax or introduce user-defined conversions that do not have builtin semantics for type conversions (you can have at most one user-defined conversion per argument).
解决方案
My question is: can this be remedied/mitigated when the
reference_proxy overloads the address-of operator& to return a
pointer_proxy?
libc++ actually does this.
#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);
}
It even extends to const_pointer
and const_reference
in ways that mimic the same types for vector<int>
. This is a non-conforming extension for libc++. But it makes writing generic code which might be instantiated on vector<bool>
far more likely to compile and behave correctly.
Questions: would such a multi-proxy approach work with the STL's
algorithms? Or do some algorithms really rely on the requirement that
x needs to be a real bool*? Or are there too many consecutive
user-defined conversions required that prevent this to work?
All of libc++'s algorithms work with vector<bool>
. Some of them with quite spectacular performance. One algorithm in particular must have special treatment which the standard unfortunately does not mandate:
#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);
}
This is very easy for the implementation to accomplish. One simply needs to make sure swap
works for any combination of bool
and vector<bool>::reference
. But I don't know if any implementation besides libc++ does this, and it is not mandated by C++11.
An array of bits is a wonderful data structure. But unfortunately it is poorly specified in the C++ standard. libc++ has gone somewhat outlaw to demonstrate that this can be a very useful and high performance data structure. The hope is that a future C++ standard may migrate in this direction to the benefit of the C++ programmer.
这篇关于多个代理类是否构成一个STL防护位向量?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文