当前位置： 文江博客 话题详情

为什么不是vector＆lt; bool＆gt; STL容器？

发布于 2025-01-21 20:06:34 字数 807 浏览 0 评论 0 原文

斯科特·迈耶斯（Scott Meyers）书的第18项有效的STL：改善您对标准模板库的使用的50种特定方法表示避免 vector＆lt; bool＆gt; ，因为它不是STL容器和它并没有真正容纳 bool s。

以下代码：

vector <bool> v; 
bool *pb =&v[0];

不会编译，违反了STL容器的要求。

错误：

cannot convert 'std::vector<bool>::reference* {aka std::_Bit_reference*}' to 'bool*' in initialization

vector＆lt; t＆gt; :: operator [] 返回类型应该为 t＆amp; ，但是为什么这是 vector＆lt; bool＆gt; < thy类型。 /代码>？

vector＆lt; bool＆gt; 真正由什么组成？

该项目进一步说：

deque<bool> v; // is a STL container and it really contains bools

可以用作 vector＆lt; bool＆gt; 的替代方案吗？

有人可以解释一下吗？

原文

Item 18 of Scott Meyers's book Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library says to avoid vector <bool> as it's not an STL container and it doesn't really hold bools.

The following code:

vector <bool> v; 
bool *pb =&v[0];

will not compile, violating a requirement of STL containers.

Error:

cannot convert 'std::vector<bool>::reference* {aka std::_Bit_reference*}' to 'bool*' in initialization

vector<T>::operator [] return type is supposed to be T&, but why is it a special case for vector<bool>?

What does vector<bool> really consist of?

The Item further says:

deque<bool> v; // is a STL container and it really contains bools

Can this be used as an alternative to vector<bool>?

Can anyone please explain this?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（6）

一城柳絮吹成雪 2025-01-28 20:06:35

出于空间优化的原因，C ++标准（回到C ++ 98）明确呼叫 vector＆lt; bool＆gt; 作为一个特殊的标准容器，其中每个Bool仅使用一个位置而不是一个空间字节作为正常的bool将（实现一种“动态bitset”）。为了换取此优化，它无法提供普通标准容器的所有功能和接口。

在这种情况下，由于您无法在字节中稍微删除一些地址，因此 operator [] 之类的东西无法返回 bool＆amp; ，而是返回允许操纵特定位的代理对象。由于此代理对象不是 bool＆amp; ，因此您无法将其地址分配给 bool*，就像您在此类操作员上呼叫的结果一样“ 容器。反过来，这意味着 bool *pb =＆amp; v [0]; 不是有效的代码。

另一方面， Deque 没有任何这样的专业化，因此每个Bool都会采用一个字节，您可以从 operator [] 中获取值的地址。

最后，请注意，MS标准库实现（可以说）是最佳的，因为它使用小块的大小进行Deques，这意味着将Deque用作替代品并不总是正确的答案。

For space-optimization reasons, the C++ standard (as far back as C++98) explicitly calls out vector<bool> as a special standard container where each bool uses only one bit of space rather than one byte as a normal bool would (implementing a kind of "dynamic bitset"). In exchange for this optimization it doesn't offer all the capabilities and interface of a normal standard container.

In this case, since you can't take the address of a bit within a byte, things such as operator[] can't return a bool& but instead return a proxy object that allows to manipulate the particular bit in question. Since this proxy object is not a bool&, you can't assign its address to a bool* like you could with the result of such an operator call on a "normal" container. In turn this means that bool *pb =&v[0]; isn't valid code.

On the other hand deque doesn't have any such specialization called out so each bool takes a byte and you can take the address of the value return from operator[].

Finally note that the MS standard library implementation is (arguably) suboptimal in that it uses a small chunk size for deques, which means that using deque as a substitute isn't always the right answer.

回复 原文
清风疏影 2025-01-28 20:06:35

问题在于 vector＆lt; bool＆gt; 返回a 代理参考对象而不是真实的参考，因此C ++ 98样式代码 bool * p =＆amp; V [0]; 不会编译。但是，如果运营商＆amp; 也可以使现代C ++ 11具有 auto p =＆amp; v [0]; 也可以进行编译。 stackoverflow.com/q/14061694/819272"> < retrongurns代理指针对象 。霍华德·辛南特（Howard Hinnant使用此类代理参考和指针时进行改进。

斯科特·迈耶斯（Scott Meyers）在关于代理类。您可以走很长的路要走几乎模仿内置类型：对于任何给定的类型 t ，一对代理（例如 reference_proxy＆lt; t＆lt; t＆gt; 可以使 iterator_proxy＆lt; t＆gt; ）在某种意义上保持一致，因为 reference_proxy＆lt; t＆gt; :: protor＆amp;（）operator＆amp;（）和 iterator_proxy_proxy＆lt; *（）是彼此的反向。

但是，在某个时候，需要将代理对象映射回行为，就像 t*或 t＆amp; 。对于迭代器代理，可以过载运算符 - ＆gt;（）并访问模板 t 的接口而无需重新实现所有功能。但是，对于参考代理，您需要超载运算符。（），并且在当前C ++中不允许使用（尽管Sebastian Redl 在BOOSTCON 2013上呈现了这样的建议 ）。您可以像参考代理中的 .get（）成员一样使详细的工作围绕，或在参考中实现所有 t 的界面（这就是什么为 vector＆lt; bool＆gt; :: bit_reference ），但这要么会丢失内置语法，要么介绍没有用于类型转换的内置语义的用户定义的转换（您最多可以具有一个用户 - 定义的转换每个参数）。

tl; dr ：no vector＆lt; bool＆gt; 不是容器用C ++ 11（自动）靠近C ++ 98。

The problems is that vector<bool> returns a proxy reference object instead of a true reference, so that C++98 style code bool * p = &v[0]; won't compile. However, modern C++11 with auto p = &v[0]; can be made to compile if operator& also returns a proxy pointer object. Howard Hinnant has written a blog post detailing the algorithmic improvements when using such proxy references and pointers.

Scott Meyers has a long Item 30 in More Effective C++ about proxy classes. 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<T> and iterator_proxy<T>) can be made mutually consistent in the sense that reference_proxy<T>::operator&() and iterator_proxy<T>::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<bool>::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).

TL;DR: no vector<bool> is not a container because the Standard requires a real reference, but it can be made to behave almost like a container, at least much closer with C++11 (auto) than in C++98.

回复 原文
难理解 2025-01-28 20:06:35

vector＆lt; bool＆gt; 仅使用一个位以进行value（而不是8个bool []阵列，以压缩形式包含布尔值。不可能返回C ++中的一些引用，因此有一种特殊的辅助类型“ BIT Reference”，它为您提供了一个内存中某个位置的接口，并允许您使用标准运算符和铸件。

vector<bool> contains boolean values in compressed form using only one bit for value (and not 8 how bool[] arrays do). It is not possible to return a reference to a bit in c++, so there is a special helper type, "bit reference", which provides you a interface to some bit in memory and allows you to use standard operators and casts.

回复 原文
所谓喜欢 2025-01-28 20:06:35

许多人认为 vector＆lt; bool＆gt; 专业化是一个错误。

在论文中“ noreferrer”> +17“
有一个建议
重新考虑矢量部分专业。

有一个悠久的历史
std ::向量不满足容器要求，in
特别是，其迭代器不满足随机的要求
访问迭代器。以前贬低该容器的尝试是
拒绝C ++ 11，

拒绝的原因之一是尚不清楚它将
是指贬低模板的特定专业化。那
可以用仔细的措辞来解决。更大的问题是
（包装）向量的专业化提供了重要的
标准图书馆的客户真正寻求的优化，但
不再可用。我们不太可能
贬低标准的这一部分，直到更换设施为
提出的和接受，例如 n2050 。不幸的是，没有这样的
目前正在向图书馆进化提供的修订建议
工作组。

Many consider the vector<bool> specialization to be a mistake.

In a paper "Deprecating Vestigial Library Parts in C++17"
There is a proposal to
Reconsider vector Partial Specialization.

There has been a long history of the bool partial specialization of
std::vector not satisfying the container requirements, and in
particular, its iterators not satisfying the requirements of a random
access iterator. A previous attempt to deprecate this container was
rejected for C++11, N2204.

One of the reasons for rejection is that it is not clear what it would
mean to deprecate a particular specialization of a template. That
could be addressed with careful wording. The larger issue is that the
(packed) specialization of vector offers an important
optimization that clients of the standard library genuinely seek, but
would not longer be available. It is unlikely that we would be able to
deprecate this part of the standard until a replacement facility is
proposed and accepted, such as N2050. Unfortunately, there are no such
revised proposals currently being offered to the Library Evolution
Working Group.

回复 原文
紫南 2025-01-28 20:06:35

查看如何实现。 STL在模板上大大构建，因此标题确实包含了它们所做的代码。

例如，查看 stdc ++ 实现在这里。

即使不是STL符合的位向量，也很有趣的是 llvm :: bitvector 来自在这里。

llvm :: bitVector 的本质是一个嵌套类，称为参考和合适的操作员过载以使 bitvector 的行为与 vector相似有一些限制。下面的代码是一个简化的界面，以显示BitVector如何隐藏一个称为 Reference 的类，以使真实实现几乎像真实的Bool一样，而无需为每个值使用1个字节。

class BitVector {
public:
  class reference {
    reference &operator=(reference t);
    reference& operator=(bool t);
    operator bool() const;
  };
  reference operator[](unsigned Idx);
  bool operator[](unsigned Idx) const;      
};

此代码在这里具有不错的属性：

BitVector b(10, false); // size 10, default false
BitVector::reference &x = b[5]; // that's what really happens
bool y = b[5]; // implicitly converted to bool 
assert(b[5] == false); // converted to bool
assert(b[6] == b[7]); // bool operator==(const reference &, const reference &);
b[5] = true; // assignment on reference
assert(b[5] == true); // and actually it does work.

此代码实际上有缺陷，尝试运行：

std::for_each(&b[5], &b[6], some_func); // address of reference not an iterator

由于 servert（（（＆amp; b [5] - ＆amp; b [3]））==（5-3） ）; 将失败（在 llvm :: BitVector 中）

这是非常简单的LLVM版本。 std :: vector＆lt; bool＆gt; 还在其中工作了。
因此，呼叫（auto i = b.begin（），e = b.end（）; i！= e; ++ i）将起作用。还有 std :: vector＆lt; bool＆gt; :: const_iterator 。

但是，在 std :: vector＆lt; bool＆gt; 中仍然存在局限性，这使得在某些情况下的行为不同。

Look at how it is implemented. the STL builds vastly on templates and therefore the headers do contain the code they do.

for instance look at the stdc++ implementation here.

also interesting even though not an stl conforming bit vector is the llvm::BitVector from here.

the essence of the llvm::BitVector is a nested class called reference and suitable operator overloading to make the BitVector behaves similar to vector with some limitations. The code below is a simplified interface to show how BitVector hides a class called reference to make the real implementation almost behave like a real array of bool without using 1 byte for each value.

class BitVector {
public:
  class reference {
    reference &operator=(reference t);
    reference& operator=(bool t);
    operator bool() const;
  };
  reference operator[](unsigned Idx);
  bool operator[](unsigned Idx) const;      
};

this code here has the nice properties:

BitVector b(10, false); // size 10, default false
BitVector::reference &x = b[5]; // that's what really happens
bool y = b[5]; // implicitly converted to bool 
assert(b[5] == false); // converted to bool
assert(b[6] == b[7]); // bool operator==(const reference &, const reference &);
b[5] = true; // assignment on reference
assert(b[5] == true); // and actually it does work.

This code actually has a flaw, try to run:

std::for_each(&b[5], &b[6], some_func); // address of reference not an iterator

will not work because assert( (&b[5] - &b[3]) == (5 - 3) ); will fail (within llvm::BitVector)

this is the very simple llvm version. std::vector<bool> has also working iterators in it.
thus the call for(auto i = b.begin(), e = b.end(); i != e; ++i) will work. and also std::vector<bool>::const_iterator.

However there are still limitations in std::vector<bool> that makes it behave differently in some cases.

回复 原文
玩物 2025-01-28 20:06:35

这来自 http://www.cplusplus.com/reference com/reference/reference/reference/vector/vector/Vector-bool-vector-bool /

bool的向量这是向量的专门版本，该版本已被使用
对于类型bool的元素并为空间进行优化。

它的行为与矢量的无专业版本一样
以下更改：

  • 存储不一定是布尔值的数组，但是库实现可以优化存储
    存储在一个位中。
  • 元素不是使用分配器对象构造的，但是它们的值直接设置在内部存储中的适当位。
  • 成员功能翻转和成员交换的新签名。
  • 一种特殊的成员类型，参考，一个类，可以访问容器内部存储中的单个位，并带有一个接口

    模拟布尔参考。相反，成员类型const_reference是
    普通的布尔。

  • 容器使用的指针和迭代器类型不一定是指针，也不是符合迭代剂，尽管它们
    应模拟他们的大多数预期行为。

这些更改为此专业化提供了一个古怪的界面，
优化内存优化而不是处理（可能会适合或不适合
您的需求）。无论如何，不​​可能实例化
BOOL的向量非专业模板。解决方法
避免使用其他类型（char，unsigned char）或
容器（例如Deque）使用包装纸类型或进一步专业
特定的分配器类型。

bitset是一个为固定尺寸提供类似功能的类
位阵列。

This comes from http://www.cplusplus.com/reference/vector/vector-bool/

Vector of bool This is a specialized version of vector, which is used
for elements of type bool and optimizes for space.

It behaves like the unspecialized version of vector, with the
following changes:

  • The storage is not necessarily an array of bool values, but the library implementation may optimize storage so that each value is
    stored in a single bit.
  • Elements are not constructed using the allocator object, but their value is directly set on the proper bit in the internal storage.
  • Member function flip and a new signature for member swap.
  • A special member type, reference, a class that accesses individual bits in the container's internal storage with an interface that
    emulates a bool reference. Conversely, member type const_reference is
    a plain bool.
  • The pointer and iterator types used by the container are not necessarily neither pointers nor conforming iterators, although they
    shall simulate most of their expected behavior.

These changes provide a quirky interface to this specialization and
favor memory optimization over processing (which may or may not suit
your needs). In any case, it is not possible to instantiate the
unspecialized template of vector for bool directly. Workarounds to
avoid this range from using a different type (char, unsigned char) or
container (like deque) to use wrapper types or further specialize for
specific allocator types.

bitset is a class that provides a similar functionality for fixed-size
arrays of bits.

回复 原文
~没有更多了~

关于作者

你曾走过我的故事

暂无简介

文章
评论
910 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

饮湿

文章 0 评论 0

明月

文章 0 评论 0

02

文章 0 评论 0

hs1283

文章 0 评论 0

风向决定发型

文章 0 评论 0

落花浅忆

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文