6

我需要存储一个动态的位数组。
vector<bool> 上的 C++ 参考页有以下信息：

存储不一定是bool值数组，但库实现可以优化存储，以便每个值都存储在单个位中。

如何确保我使用的程序vector<bool>确实将位存储在向量而不是布尔值（字节）中？

4

6 回答 6

6

不要试图那样做。相反，使用boost::dynamic_bitsetwhich 清楚地表明你真正想要什么。优化实际上为错误创造了许多可能性，vector<bool>例如在使用迭代器时（因为它通常返回一个代理对象）。

于 2013-01-14T21:19:32.663 回答
2

好吧，您总是可以查看编译器附带的头文件。由于 STL 容器几乎完全是模板类，因此实现的大部分（如果不是全部）部分将在标题中可见。

也许在调试器中查看vector对象也会有所帮助。

注意：您还应该知道，vector<bool>与此同时，C++ 社区对此颇为不满，并且这种优化是针对大小而不是速度的：

https://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=98

于 2013-01-14T21:19:32.963 回答
1

这里根本没有什么可以检查的。标准要求专门vector<bool>存储位而不是更大的对象。§23.2.5：“为了优化空间分配，提供了一个专门用于 bool 元素的向量：”。

我想从某种角度来看，您所引用的内容至少是正确的。由于基本上没有人可以证明编译器的一致性，而且基本上没有编译器甚至尝试满足所有一致性要求，因此编译器也可以选择忽略此要求。

不过，我不知道有任何编译器这样做——如果有人这样做，我猜它可能是众所周知的。有时关于取消vector<bool>专业化的讨论非常激烈，所以如果有人有现实生活中的例子说明这让事情变得更好（或更糟），我怀疑我们会听说过它。

编辑：在 C++11 中，要求std::vector<bool>已移至 §23.3.7。更重要的是，措辞已更改，以指定将每个bool都存储为单个位而不是bool值的连续分配的打包表示现在只是一个建议。

至少在国际海事组织，这几乎没有什么真正的区别。据我所知，所有实际实现仍然使用打包表示，因此即使打包存储在理论上不再得到保证，但无论如何它都会在实践中发生。

于 2013-01-15T04:55:51.570 回答
1

可以在编译时通过检查 的非常量版本的返回类型来检查这一点vector<bool>::operator[]： 将其值存储为位的实现将必须返回代理引用类而不是bool&.

于 2013-01-15T00:24:04.787 回答
0

这个程序证明了这一点。

#include <vector>
#include <iostream>

template <typename T>
void showSize() {
    std::vector<T> myvec;
    size_t capacity = myvec.capacity();
    std::cout << "capacity: " << myvec.capacity() << std::endl;
    std::cout << "size: " << myvec.size() << std::endl;
    while (myvec.capacity() < 1024) {
        while (myvec.capacity() == capacity) {
            myvec.push_back(T());
        }
        capacity = myvec.capacity();
        std::cout << "capacity: " << myvec.capacity() << std::endl;
        std::cout << "size: " << myvec.size() << std::endl;
    }

}

int main(int, char**) {
    std::cout << std::endl << std::endl;
    std::cout << "*********************" << std::endl << std::endl;
    std::cout << "Booleans: " << std::endl << std::endl;
    showSize<bool>();
    std::cout << std::endl << std::endl;
    std::cout << "*********************" << std::endl << std::endl;
    std::cout << "Chars: " << std::endl << std::endl;
    showSize<char>();
}

输出：

*********************

Booleans: 

capacity: 0
size: 0
capacity: 64
size: 1
capacity: 128
size: 65
capacity: 256
size: 129
capacity: 512
size: 257
capacity: 1024
size: 513


*********************

Chars: 

capacity: 0
size: 0
capacity: 1
size: 1
capacity: 2
size: 2
capacity: 4
size: 3
capacity: 8
size: 5
capacity: 16
size: 9
capacity: 32
size: 17
capacity: 64
size: 33
capacity: 128
size: 65
capacity: 256
size: 129
capacity: 512
size: 257
capacity: 1024
size: 513

所以关键是 bool 的容量一次增加 64 个条目（int 或我的机器的大小）。这暗示它一次只保留 8 个字节。

于 2013-01-14T22:17:33.720 回答
-1

创建一个巨大的vector<bool>并查看程序的内存使用情况。

或者只是查看源代码 - 您可以查看vector标题。

于 2013-01-14T21:16:01.873 回答