标准非STL容器 : bitset

朱雀 2022-08-05 07:27 170阅读 0赞

**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部分实现源码

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  template<size\_t \_Nb>
2.  class bitset : private \_Base\_bitset<\_\_BITSET\_WORDS(\_Nb)>
3.  \{
4.  private:
5.  typedef \_Base\_bitset<\_\_BITSET\_WORDS(\_Nb)> \_Base;
6.  typedef unsigned long \_WordT;
7.  
8.  private:
9.  void \_M\_do\_sanitize() \{
10. \_Sanitize<\_Nb%\_\_BITS\_PER\_WORD>::\_M\_do\_sanitize(this\->\_M\_hiword());
11. \}
12. .....
13. \}

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  \#define \_\_BITS\_PER\_WORD (CHAR\_BIT\*sizeof(unsigned long))
2.  \#define \_\_BITSET\_WORDS(\_\_n) \\
3.  ((\_\_n) < 1 ? 1 : ((\_\_n) + \_\_BITS\_PER\_WORD - 1)/\_\_BITS\_PER\_WORD)

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  template<size\_t \_Nw>
2.  struct \_Base\_bitset \{
3.  typedef unsigned long \_WordT;
4.  
5.  \_WordT \_M\_w\[\_Nw\]; // 0 is the least significant word.
6.  
7.  \_Base\_bitset( void ) \{ \_M\_do\_reset(); \}
8.  \_Base\_bitset(unsigned long \_\_val) \{
9.  \_M\_do\_reset();
10. \_M\_w\[0\] = \_\_val;
11. \}
12. 
13. static size\_t \_S\_whichword( size\_t \_\_pos )
14. \{ return \_\_pos / \_\_BITS\_PER\_WORD; \}
15. static size\_t \_S\_whichbyte( size\_t \_\_pos )
16. \{ return (\_\_pos % \_\_BITS\_PER\_WORD) / CHAR\_BIT; \}
17. static size\_t \_S\_whichbit( size\_t \_\_pos )
18. \{ return \_\_pos % \_\_BITS\_PER\_WORD; \}
19. static \_WordT \_S\_maskbit( size\_t \_\_pos )
20. \{ return (static\_cast<\_WordT>(1)) << \_S\_whichbit(\_\_pos); \}
21. 
22. \_WordT& \_M\_getword(size\_t \_\_pos) \{ return \_M\_w\[\_S\_whichword(\_\_pos)\]; \}
23. \_WordT \_M\_getword(size\_t \_\_pos) const \{ return \_M\_w\[\_S\_whichword(\_\_pos)\]; \}
24. 
25. \_WordT& \_M\_hiword() \{ return \_M\_w\[\_Nw - 1\]; \}
26. \_WordT \_M\_hiword() const \{ return \_M\_w\[\_Nw - 1\]; \}
27. 
28. void \_M\_do\_and(const \_Base\_bitset<\_Nw>& \_\_x) \{
29. for ( size\_t \_\_i = 0; \_\_i < \_Nw; \_\_i++ ) \{
30. \_M\_w\[\_\_i\] &= \_\_x.\_M\_w\[\_\_i\];
31. \}
32. \}
33. 
34. void \_M\_do\_or(const \_Base\_bitset<\_Nw>& \_\_x) \{
35. for ( size\_t \_\_i = 0; \_\_i < \_Nw; \_\_i++ ) \{
36. \_M\_w\[\_\_i\] |= \_\_x.\_M\_w\[\_\_i\];
37. \}
38. \}
39. 
40. void \_M\_do\_xor(const \_Base\_bitset<\_Nw>& \_\_x) \{
41. for ( size\_t \_\_i = 0; \_\_i < \_Nw; \_\_i++ ) \{
42. \_M\_w\[\_\_i\] ^= \_\_x.\_M\_w\[\_\_i\];
43. \}
44. \}

节选上述代码，可以得到：  
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）

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  void fun()
2.  \{
3.  const int n = 800000000;
4.  
5.  bitset<n> a;
6.  cout << a.size() << endl;
7.  \}
8.  int main(int argc, char\*\* argv)
9.  \{
10. fun();
11. 
12. return 0;
13. \}

大内存分配可以分配在堆中，如下：

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  const int n = 800000000;
2.  
3.  bitset<n> \*a = new(std::nothrow) bitset<n>;
4.  
5.  if(a)
6.  \{
7.  cout << a->size() << endl;
8.  delete a;
9.  a = NULL;
10. \}

**4. vector<bool>及deque<bool>**  
bitset高效，但是size必须在编译器确定，不支持插入和删除。因此，一个可能的替代品是vector<bool>和deque<bool>  
两者的区别：  
vector<bool>不是一个STL容器，并且不容纳bool（like bitse底层t机制）  
deque<bool>是一个STL容器，它保存真正的bool值  
分别运行

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  deque<bool> a;
2.  a\[0\] = 0;
3.  bool\* b = &a\[0\];
4.  cout << \*b << endl;

和

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  vector<bool> a;
2.  a\[0\] = 0;
3.  bool\* b = &a\[0\];
4.  cout << \*b << endl;

将会发现：  
使用deque<bool>正确，而是用vector<bool>会报错：“cannot convert \`std::\_Bit\_reference\*' to \`bool\*' in initialization“  
  
但是，deque简直是在践踏内存。  
**使用deque<bool>**

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  int main(int argc, char\*\* argv)
2.  \{
3.  deque<bool> a(10000000000);
4.  sleep(100);
5.  return 0;
6.  \}

内存使用：  
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>**

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  int main(int argc, char\*\* argv)
2.  \{
3.  vector<bool> a(10000000000);
4.  sleep(100);
5.  return 0;
6.  \}

内存使用：  
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**

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  int main(int argc, char\*\* argv)
2.  \{
3.  const unsigned long int n = 10000000000;
4.  bitset<n> \*a = new(std::nothrow) bitset<n>;
5.  sleep(100);
6.  
7.  return 0;
8.  \}

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>则是9990M**  
  
**5. 总结**  
在需要对位集合进行操作的时候，如何操作集合大小比较固定，优先选择高效的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:

**\[cpp\]** [ view plain][view plain] [copy][view plain]

1.  class vector<bool>::reference \{
2.  friend class vector;
3.  reference(); // no public constructor
4.  public:
5.  ~reference();
6.  operator bool () const; // convert to bool
7.  reference& operator= ( const bool x ); // assign from bool
8.  reference& operator= ( const reference& x ); // assign from bit
9.  void flip(); // flip bit value.
10. \}

[view plain]: http://blog.csdn.net/yfkiss/article/details/6998231#

发表评论取消回复

表情：

评论列表（有 0 条评论，170人围观）

还没有评论，来说两句吧...

相关阅读

相关【C++ STL 容器】——bitset

概念 bitset可以看做是二进制位的容器，并提供了位的相关操作函数。常用函数构造赋值函数 bitset(); b

「爱情、让人受尽委屈。」/ 2023年01月23日 15:58/ 0 赞/ 184 阅读

相关 C++学习笔记（五）标准模板库STL之容器

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5

末蓝、/ 2023年01月04日 14:54/ 0 赞/ 154 阅读

相关 stl标准模板库_C ++标准模板库（STL）–简介

![254de206d929750ae35c4a20faeb979d.png][] stl标准模板库 In this tutorial you will learn abo

待我称王封你为后i/ 2022年12月08日 04:47/ 0 赞/ 255 阅读

相关 C++语法基础--标准库类型--bitset

1.bitset \定义原型： template< std::size\_t N > class bitset; \构造函数原型： bits

偏执的太偏执、/ 2022年10月02日 04:57/ 0 赞/ 236 阅读

相关 STL_Bitset

1.构造 <span style="font-family:Microsoft YaHei;font-size:24px;">std::bitset<16>

女爷i/ 2022年09月23日 04:52/ 0 赞/ 134 阅读

相关对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法，从链表到队列，从向量到堆栈，对hash到二叉树，从搜索到排序，从增加到删除......可以说，如果你理解了STL，你会发现你已不用拘泥于

╰半夏微凉°/ 2022年08月26日 08:12/ 0 赞/ 212 阅读

相关非标准的散列容器（未完成）

c++标准在现有版本中没有散列容器，以后肯定会有。所以现有的散列容器都是非标准的这些非标准散列容器非常容易获得，他们甚至有事实上的标准名字：hash\_set、hash\_

深碍√TFBOYSˉ_/ 2022年08月10日 09:27/ 0 赞/ 127 阅读

相关标准非STL容器 : bitset

1. 概念什么是“标准非STL容器”？标准非STL容器是指“可以认为它们是容器，但是他们并不满足STL容器的所有要求”。前文提到的容器适配器stack、queue及pri

朱雀/ 2022年08月05日 07:27/ 0 赞/ 171 阅读

相关标准模板库（STL）

标准模板库（STL）以矢量vector为例，如下程序是begin()、end()、push\_back、pop\_back()、erase()、insert()、sor

我不是女神ヾ/ 2022年06月08日 05:38/ 0 赞/ 294 阅读

相关 C/C++编程：标准库bitset

作用：提供了一种抽象方法来操作位的集合若在编译时 bitset 的大小未知，则可使用 [std::vector<bool>][std_vector_bool] 或 [boo

刺骨的言语ヽ痛彻心扉/ 2022年05月19日 10:44/ 0 赞/ 345 阅读