c++ - 如何在文件中节省空间地存储和检索 std::vector<int> 值

Question

我有一个std::vector<int>它由值 -1,0,1 组成。对这些值进行一些初始操作后，我最终得到一个 vector ，其中 -1 值可以省略。 如何以有效的方式在空间(更重要)和时间上将所需的 0,1 值存储在文件中。

似乎有3个推荐选项std::vector<bool> , std::bitset和boost::dynamic_bitset但在这种情况下哪个是最好的。 我可以循环遍历 vector 和 if value!=-1将其添加到 vector<bool>然后存储它，但这是最好的方法吗？该 vector 有大约 100 万个元素(操作后)。

// Initialize temp_array of size n(obtained in runtime) with value -1
std::vector<int> temp_array(n, -1);
// Do some manipulation on the temp array
// Now temp array has values containing -1,0,1 of which all occurrences of -1 can be removed without worrying about the index
std::vector<bool>final_array;
for (const auto &i : temp_array)
    {
      if (i != -1)
      {
        final_array.push_back(i);
      }
    }
// How to store and retrieve this in the most space efficient way

编辑: 有关该问题的更多背景细节。空间效率是必须的，因为我正在存储邻接矩阵的压缩格式(执行一些自定义压缩)。每个节点最多可以有一百万个边(有时甚至更多)，并且大约有 1000 万个这样的节点(处理大型图)。目的是将该图的压缩形式完全加载到内存中并支持基本查询，而无需解压缩并支持流边缘(例如实时日志图有 4,847,571 个节点)。

Answer 1

如果空间效率是一个大问题，并且您拥有的只是 0 和 1，那么您可以考虑存储二进制字符串的游程长度编码。

请参阅，https://en.wikipedia.org/wiki/Run-length_encoding

最坏的情况是 0 和 1 交替出现。

代码应该相对简单，涉及单个传递 vector 。