c++ - 在 C++ 复杂性和实现中选择位 vector

Question

我正在实现矩阵约简算法，我是一名数学专业的学生。显然我已经在互联网上搜索和阅读但没有找到我正在寻找的东西(我在最后列出了我找到的东西和我读过的论文。)

问题的快速概述:

• 位 vector b 的长度为固定长度 N。

• b 在每一步都发生变化(可能仅在几个索引处(大多数情况下)或在相当多的索引处(从 1/10 到 1/3))，这仅占 ~10%个案)。

• 我已经有了一个稀疏实现，现在我想使用位 vector 的一些智能实现对其进行编码。

  //initialize to 0 
  b=bitvector(0, n=N)
  
  for i in 1 to N
      {some operations on the bitvector b}
      get I= { j | b[j] == 1 }
      {save I}
  

我需要的是:

• 快速设置 b[i]=1 或 =0(可能是 O(1))
• 快速获取每一步的索引集I(绝对不超过O(logN)，最好是O(1))
• 允许它的 C++ 库
• 论文/文档

有什么会很好:

• 一种快速获得“最低的”的方法(最后一个索引设置为1，即select(rank(b))，如果两个操作都很快(O(1)))

我不需要的是:

• 节省空间
• 压缩数据

我一直在使用 Simon Gog 等人的库 Sdsl 2.0。 ( https://github.com/simongog/sdsl-lite ) 但选择结构

bit_vector::select_1_type

初始化的成本为 O(n)，每个查询的成本为 O(1)，但不会“跟随”b 中的变化(对吗？？我还没有找到任何关于它的非常具体的信息)，这意味着它需要在修改后的每一步都被初始化。

我读过的论文有:“位图上的快速、小型、简单排序/选择”(G. Navarro 和 E. Providel)和“实用熵压缩排序/选择字典”(D. OkanoharaK. Sadakane)，我将不胜感激任何指向 C++ 可靠实现的链接(如果结构满足我的要求)

我在 stackexchange 上找到的关于类似主题但没有帮助的内容:

• Dynamic bit vector in C/C++

• Bit vector and bitset

抱歉这个冗长的问题，我希望我解释了我需要什么以及我找到它的决心。我仍然对与 bitvectors 相关的各种事情感到困惑，这绝对不是我的专业领域，因此不胜感激。

提前致谢。

Answer 1

结构描述here是我所知道的最接近您想要的属性的东西。

具体来说:

• 初始化是常数时间
• 设置/清除条目为常数时间
• 成员资格测试是固定时间
• 检索条目集的条目数为 O(N)(假设您不需要对它们进行排序 - 实际上最终是按插入顺序遍历它们；您不会比 O( N) 总的来说，如果你需要为接下来发生的一切走过所有的路，当然)