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

Question

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

我读过 bool 可以节省 1/0（或 true/false），但这也是 8 位 storage.So 如果我可以将值存储在一位。

我没有选择多维存储，而是选择将矩阵存储在一维矩阵中，并通过 matrix[row*N + column] 访问元素，其中 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,...}

我选择了无符号字符来存储 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

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

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

Answer 1

这正是 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> is a possibly space-efficient specialization of std::vector for the type bool.

The manner in which std::vector<bool> is made space efficient (as well as whether it is optimized at all) is implementation defined. One potential optimization involves coalescing vector elements such that each element occupies a single bit instead of sizeof(bool) bytes.

std::vector<bool> behaves similarly to std::vector, but in order to be space efficient, it:

Does not necessarily store its elements as a contiguous array.

Exposes class std::vector<bool>::reference as a method of accessing individual bits. In particular, objects of this class are returned by operator[] by value.

Does not use std::allocator_traits::construct to construct bit values.

Does not guarantee that different elements in the same container can be modified concurrently by different threads.

std::vector<bool> 的专业化是否是个好主意是一个讨论得很多的问题。参见例如 Why isn't vector<bool> a STL container?。不过，差异主要体现在通用代码中，有时必须添加特殊情况，因为 std::vector<bool> 在细节上与其他 std::vector 不同。

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

Is it possible to store (0,1)-matrix with single bits rather than bool?

c++

bit-manipulation

bitmap

sparse-matrix