1. 概念
什么是“标准非STL容器”?标准非STL容器是指“可以认为它们是容器,但是他们并不满足STL容器的所有要求”。前文提到的容器适配器stack、queue及priority_queue都是标准非STL容器的一部分。此外,valarray也是标准非STL容器。
bitset:一种
高效位集合操作容器。
2. API
bitset提供的api:
(constructor) Construct bitset (public member function)
operator[] Access bit (public member function)
set Set bits (public member function)
reset Reset bits (public member function )
flip Flip bits (public member function)
to_ulong Convert to unsigned long integer (public member function)
to_string Convert to string (public member function)
count Count bits set (public member function)
size Return size (public member function)
test Return bit value (public member function )
any Test if any bit is set (public member function)
none Test if no bit is set (public member function)
3. 源码剖析
SGI bitset部分实现源码
节选上述代码,可以得到:
1. bitset继承_Base_bitset,具体操作封装在_Base_bitset中
2. bitset 的size作为模板参数(非类型模板参数的一个要求是,编译器能在编译期就能把参数确定下来),因此,
bitset大小在编译期固定,不支持插入和删除元素
3. 各种位操作,
性能高
4._Base_bitset使unsigned long作为底层存储,
不支持指针、引用、迭代器
5. 使用_WordT _M_w[_Nw];分配内存,
因此在栈中定义bitset需要注意大小(和STL标准容器堆内存分配区别开)。
eg,下面的代码将栈溢出(测试机器栈内存10M)
大内存分配可以分配在堆中,如下:
4. vector<bool>及deque<bool>
bitset高效,但是size必须在编译器确定,不支持插入和删除。因此,一个可能的替代品是vector<bool>和deque<bool>
两者的区别:
vector<bool>不是一个STL容器,并且不容纳bool(like bitse底层t机制)
deque<bool>是一个STL容器,它保存真正的bool值
分别运行
和
将会发现:
使用deque<bool>正确,而是用vector<bool>会报错:“cannot convert `std::_Bit_reference*' to `bool*' in initialization“
但是,deque简直是在践踏内存。
使用deque<bool>内存使用:
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
23612 work 25 0
9990m 9.8g 720 S 0.0 65.0 0:39.35 test
使用vector<bool>内存使用:
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
23909 work 25 0
1198m 1.2g 716 S 0.0 7.8 0:01.31 test
使用bitset
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
24439 work 25 0
1198m 1.2g 712 S 30.7 7.8 0:00.92 test
10亿个bool,vector<bool>和bitset使用内存1198M,deque<bool>则是9990M5. 总结
在需要对位集合进行操作的时候,如何操作集合大小比较固定,优先选择高效的bitset;
如果需要动态增删元素,或者编译期间无法确定集合大小,则可以考虑vector<bool>,deque<bool>内存开销太大,基本上不考虑。
参考:
http://www.sgi.com/tech/stl/download.html
http://www.cplusplus.com/reference/stl/vector/
http://www.cplusplus.com/reference/stl/bitset/
扩展阅读:
Vector specialization: vector<bool>
The vector class template has a special template specialization for the bool type.
This specialization is provided to optimize for space allocation: In this template specialization, each element occupies only one bit (which is eight times less than the smallest type in C++:
char).
The references to elements of a
bool vector returned by the
vector members are not references to
bool objects, but a special member type which is a reference to a single bit, defined inside the
vector<bool> class specialization
as:
分享到:
相关推荐
6.7 其它STL容器 57 6.7.1 HashTable 59 6.7.2 引用计数 59 6.8 各种容器的运用时机 61 6.8.1 各种容器的使用时机 61 7 STL迭代器 64 7.1 迭代器头文件 64 7.2 迭代器类型 64 7.2.1 Input迭代器 64 7.2.2 Output迭代...
3、容器 3 4、迭代器 4 5、使用注意 4 一、stack 堆栈 5 成员函数: 5 实例程序: 5 二、queue 队列 6 成员函数: 6 实例程序: 6 三、Priority Queues 优先队列 7 成员函数: 7 实例程序: 7 四、Bitset位集合 9 ...
本实验主要练习容器link、队列、栈、优先队列、bitset的使用方法。 实验器材: VScode 实验内容: 一.回顾以上容器常用函数的使用方法。 二.练习课本第7章的例7.11-7.27。 三.实验报告应包含例7.14、7.18、7.21、...
求素数个数,比较不同方法,一个是用STL容器中的bitset容器,一个是低级位筛法
//STL 位集容器 #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> //复数类 #include <cstdio> #include <cstdlib> #...
C、传统 C++ #include <assert.h> //设定插入点 #include <ctype.h> //字符处理 #include <errno.h> //定义错误码 #include <float.h> //浮点数...#include <bitset> //STL 位集容器 #include #include <cerrno>
mlib:使用纯C语言(C99或C11)的通用容器和类型安全容器的库,用于容器的广泛收集(与C ++ STL比较)
#include <bitset> //STL 位集容器 #include #include #include #include #include <complex> //复数类 #include #include #include #include #include <deque> //STL 双端队列容器 #include <exception>...
20.1 标准模板库(STL)简介 20.1.1 容器简介 20.1.2 迭代器简介 20.1.3 算法简介 20.2 顺序容器 20.2.1 vector顺序容器 20.2.2 1ist顺序容器 20.2.3 deque顺序容器 20.3 关联容器 20.3.1 multiset...
20.1 标准模板库(STL)简介 20.1.1 容器简介 20.1.2 迭代器简介 20.1.3 算法简介 20.2 顺序容器 20.2.1 vector顺序容器 20.2.2 1ist顺序容器 20.2.3 deque顺序容器 20.3 关联容器 20.3.1 multiset...
|-- C++STL之Container(容器).pdf| |-- C++STL之Special Containers(特殊容器).pdf| |-- C++STL之String(字符串).pdf| |-- bitset.txt| `-- stl速成.doc|-- WC讲课资料| |-- 数学.pdf| |-- 计数.pdf| |-- 调试导论....