vector<bool> 内部实现？

modoke

记得在哪看过C++存的时候做了特化，这种特化对存储的影响是怎样的？我还需要对他再做压缩编码来减少存储开销吗？

[ 本帖最后由 modoke 于 2009-12-21 20:28 编辑 ]

OwnWaterloo

http://www.cplusplus.com/reference/stl/vector/

页面最后部分

modoke

thx！ 可惜STL没有提供压缩方法， 还得自己写

OwnWaterloo

没有提供压缩方法是什么意思？

modoke

比如 分段长度压缩编码 之类的 对稀疏矩阵、向量的压缩

这是空间开销的要求，
另外在时间开销上，用vector<bool>来实现位图，会不会将位运算的“快速”的benifit 抹杀掉？

[ 本帖最后由 modoke 于 2009-12-21 20:55 编辑 ]

OwnWaterloo

vector<bool> 提供的类似于一种不存在的vector<bit> 。 稀疏矩阵肯定做不了了。
分段长度压缩编码和向量的压缩不懂……   不满足需要的话， 还是自己写吧

modoke

谢谢楼上的帮助，还有一个最重要的问题
在时间开销上，用vector<bool>来实现位图，会不会将位运算的“快速”的benifit 抹杀掉？
比如一个位向量有32位，那么我们用一个int来实现，为了求出两个位向量x，y的与，需要这样: int x; int y; int z = x&y;
还有位运算的左、右移等等，然而要用vector<bool>来实现，可能需要跌代32次，并且vector<bool>的机器实现上会不会由于要维护一些组织信息，结果导致本身就会比单纯的位运算慢很多？？
简而言之，我就是想问从时间开销上，vector<bool>和单纯的位运算差多少？

OwnWaterloo

固定大小的位图可以用bitset
http://www.cplusplus.com/reference/stl/bitset/

它的效率应该和用char,int, long实现位图是相同的。


vector<bool> 是可增长的， 它好像不支持位移操作。而且又不会暴露内部数据， 实现位移可能会有影响。
不过， 如果你需要的真的是可增长的位图， 用int*, long*去实现位移的话， 那些开销大的工作依然是逃不掉的。

boost好像有个dynamic_bitset。 不知道和vector<bool>有什么区别……

modoke

太棒了，我最需要你在8楼的回复，就要这个！非常感谢！！！

modoke

看过了微软的bitset的实现之后总结了一句，希望对苦于追求实现位图索引的速度的人有所帮助：别用容器了，自己用基础数据类型写吧！

[ 本帖最后由 modoke 于 2009-12-21 22:35 编辑 ]