在 set<int>、vector<bool> 与 vector<boolean_t> 之间进行选择以用作位图（位集/位数组）

Question

给定一系列索引（标识符），我想将每个索引映射到一个布尔值，即：

// 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>- 使用 anint作为布尔标志来拥有使用机器自然字大小的容器。（不知道这是否会有所作为。）

请回答您更喜欢哪种容器类型以及原因，考虑到上面引用的最大 id 限制，特别是考虑查询位图的性能方面（插入性能并不重要）。

vector注意： vs.的接口使用set并不重要，因为无论如何它都会隐藏在它的包装类后面。

编辑：添加关于 std::bitset 的讨论：std::bitset 会将整个数组大小合并到对象中，即 sizeof(std::bitset<1m>) 的大小约为 1/8 MB ，这会产生一个巨大的单个对象，并且会产生一些您无法再放入堆栈中的东西（这可能相关，也可能不相关）。

Answer 1

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

例如，如果您有一个极其稀疏的数组，则vector<int>仅包含索引集的 a 的线性搜索可能是最佳答案。（请参阅 Mike Abrash 关于针对 x86 优化 Pixomatic 的文章。）

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

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

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

如果标识符分散，则使用哈希集 ( unordered_set<int>) 而不是位向量可能会取得重大胜利。但这取决于负载。