给定一系列索引（标识符），我想将每个索引映射到一个布尔值，即：
// 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作为布尔标志来拥有使用机器自然字大小的容器。 （不知道这是否会有所作为。）
请回答您更喜欢哪种容器类型以及原因，考虑到上面引用的最大 ID 限制，特别是考虑到表现的方面querying位图（插入性能并不重要）。
注：接口使用vector vs. set没关系，因为无论如何它都会隐藏在它的包装类后面。
编辑：添加关于 std::bitset 的讨论： std::bitset 将把整个数组大小合并到对象中，即 sizeof(std::bitset) 的大小约为 1/8 MB ，这会产生一个巨大的单个对象，并且会产生一些您无法再放入堆栈中的东西（这可能相关，也可能不相关）。
在不知道您运行此代码的平台和访问模式的情况下，很难说是否vector<bool>会比vector<char> (or vector<int>） 甚至set<int> or unordered_set<int>.
例如，如果您有一个极其稀疏的数组，则线性搜索vector<int>仅包含索引集可能是最好的答案。 （请参阅 Mike Abrash 关于针对 x86 优化 Pixomatic 的文章。)
另一方面，您可能有一个有点稀疏的数组。我所说的有点稀疏是指集合元素的数量远大于 L1 或 L2。在这种情况下，更多的低级细节以及您的实际访问模式开始发挥作用。
例如，在某些平台上，可变位移位非常昂贵。因此，如果您正在查询一组随机标识符，则执行此操作的频率越高，查询的次数就越多。vector<char> or vector<int>成为一个更好的主意bitset<...> or vector<bool>。 （后两者使用移位来查找位。）另一方面，如果您按顺序迭代稀疏位向量并且只需要位集，则可以优化该迭代以消除变量移位的开销。
此时，您可能还想知道稀疏标识符实际上是如何分布的。如果它们聚集在一起，您需要知道最佳内存读取大小和一次读取一个字符之间的权衡。这将决定更频繁地访问缓存是否会抵消非本机大小数据的读取。
如果标识符分散，您可以通过使用哈希集获得重大胜利（unordered_set<int>) 而不是位向量。但这取决于负载。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
