c++ - 在 set 与 vector 与 vector 之间进行选择以用作位图(位集/位数组)

Question

给定一系列索引(标识符)，我想将每个索引映射到一个 bool 值，即:

// interface pseudocode
interface bitmap {
  bool identifier_is_set(unsigned int id_idx) const;
  void set_identifier(unsigned int id_idx, bool val) const;
};

这样我就可以设置和查询每个 ID(索引)是否已设置，您更喜欢用什么来实现它？

我认为这叫做位数组或位图或位集，如果我错了请纠正我。

假设最大标识符是预先确定的并且不大于 1e6 (1m)，可能更小 (10k - 100k)。(这意味着 sizeof(int)*maximum_id_idx 使用的大小很容易适合存入内存。)

目前我看到的可能的解决方案:

• std::set<size_t> - 根据需要向该集合添加或删除标识符。只要我们有稀疏位图，这就允许任意大的标识符。
• std::vector<bool> - 调整到适当的最大值，为每个 id_idx 存储 true 或 false。
• std::vector<char> - 同样的事情，但没有遭受怪异 std::vector<bool>问题。使用的内存少于 vector<int> .
• std::vector<int> - 使用 int作为 bool 标志，让容器使用机器的自然字大小。 (不知道这是否会有所作为。)

请回答您更喜欢哪种容器类型以及原因，考虑到上面引用的最大 id 限制，特别是考虑查询位图的性能方面(插入性能无关紧要).

注:vector的接口(interface)用法与 set没关系，因为它无论如何都会隐藏在它的包装类后面。

编辑:添加到关于 std::bitset 的讨论中:std::bitset 会将整个数组大小合并到对象中，即 sizeof(std::bitset<1m>) 的大小约为 1/8 兆字节，这构成了一个巨大的单个对象，并构成了一些你不能再放在堆栈上的东西(这可能相关也可能不相关)。

Answer 1

在不知道您运行此代码的平台和您的访问模式的情况下，很难说 vector<bool> 是否有效。会比 vector<char> 快(或 vector<int> )甚至 set<int>或 unordered_set<int> .

例如，如果您有一个极其稀疏的数组，则线性搜索 vector<int>只包含索引集的可能是最好的答案。 ( See Mike Abrash's article on optimizing Pixomatic for x86. )

另一方面，您的数组可能有点稀疏。有点稀疏是指集合元素的数量远大于 L1 或 L2。在这种情况下，更多底层细节以及您的实际访问模式开始发挥作用。

例如，在某些平台上，可变位移位非常昂贵。因此，如果您正在查询一组随机标识符，您执行此操作的频率越高，vector<char> 就越多或 vector<int>成为比 bitset<...> 更好的主意或 vector<bool> . (后两者使用移位来查找位。)另一方面，如果您按顺序迭代稀疏位 vector 并且只想设置位，则可以优化该迭代以消除变量移位的开销。

此时，您可能还想知道稀疏标识符的实际分布情况。如果它们聚集在一起，您需要知道最佳内存读取大小和一次读取一个字符之间的权衡。这将决定更频繁地访问缓存是否会抵消非 native 大小数据的读取。

如果标识符是分散的，您可以通过使用哈希集 (unordered_set<int>) 而不是位 vector 来获得显着的胜利。然而，这取决于负载。