相关疑难解决方法(0)

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

// 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 限制，特别是考虑查询位图的性能方面（插入性能并不重要）。