时间戳

首页 > 解决方案 > 是否可以用单个位而不是 bool 存储 (0,1) 矩阵？

c++ - 是否可以用单个位而不是 bool 存储 (0,1) 矩阵？

问题描述

我需要在有限的内存设备上存储相当大的（1M x 1M）方阵。矩阵仅由元素“1”和“0”组成。

我已经读过 bool 可以保存 1/0（或真/假），但这也是 8 位存储。所以如果我可以将值存储在一个位中，我可以存储 8 倍的大小。

我没有使用多维存储，而是选择将矩阵存储在单维矩阵中并通过matrix[row*N + column]where访问元素size = N * N

我在下面有一个表示可以更好地解释一些东西

+ = 1
o = 0

  0 1 2 3 4 5
0 + o + o o o
1 o + + + o +
2 o o + o + o
3 + o o o o o
4 o o + + o 1

is converted to std::vector<unsigned char> matrix = {1,0,1,0,0,0,...}

我选择了 unsigned char 来存储 1 和 0，并且在 c++ 中具有 8 位的最小大小我有以下代码作为起点：


 int each_row;
 int row_val;
  for (int row = 0; row < 8; row++) {
    for (int col = 0; col < 8; col++) {
      
      unsigned char val = matrix[row * N + col];
      each_row = each_row + to_string(val);
      
    }

    row_val = std::stoi(each_row, nullptr, 2); // to int

所以我的问题是如何将每行/列中的值存储在一个字符的单个位中以压缩数据？

val = 0b00000001 or 0b00000000现在我想利用所有位的每个值，如第一行和第二行组合存储为（由于大小小于 8）0b10100001

标签： c++bitmapbit-manipulationsparse-matrix

解决方案

这正是std::vector<bool>它的用途。

#include <vector>
#include <string>


int main()
{
  std::string each_row;
  int row_val;
  int N = 8;
  std::vector<bool> matrix(N*N);
  for (int row = 0; row < N; row++) {
    for (int col = 0; col < N; col++) {
      
      unsigned char val = matrix[row * N + col];
      each_row = each_row + std::to_string(val);
      
    }
    row_val = std::stoi(each_row, nullptr, 2); // to int
  }
}

从cppreference：

std::vector<bool>std::vector是type的一种可能节省空间的特化 bool。

提高空间效率的方式std::vector<bool>（以及是否完全优化）由实现定义。一种潜在的优化涉及合并向量元素，以便每个元素占用一个位而不是 sizeof(bool) 字节。

std::vector<bool>行为类似于std::vector，但为了节省空间，它：

  • 不一定将其元素存储为连续数组。
  • 将类公开std::vector<bool>::reference为访问单个位的方法。特别是，这个类的对象是 operator[]按值返回的。
  • 不std::allocator_traits::construct用于构造位值。
  • 不保证同一个容器中的不同元素可以被不同的线程同时修改。

专业化是否std::vector<bool>是一个好主意是一个备受讨论的问题。参见例如为什么 vector<bool> 不是 STL 容器？. 但是，差异主要体现在泛型代码中，有时必须添加特殊情况，因为它的细节std::vector<bool>与其他std::vectors 不同。

推荐阅读