迭代std :: bitset中真实位的有效方法?
有没有一种方法可以迭代(可能很大)std::bitset，它在 设置为 true 的位数中 线性/em>?我想避免检查位集中的每个位置.迭代应该连续返回每个设置为 true 的位的索引.
Is there a way of iterating over a (possibly huge) std::bitset that is linear in the number of bits that are set to true? I want to prevent having to check every single position in the bitset. The iteration should successively return the indices of each bit that is set to true.
推荐答案
标准位向量不支持对真实位的有效迭代 - 运行时间总是 O(n)，其中 n 是总位数，它没有对 k 的依赖.但是，也有专门的数据结构，例如 van Emde Boas 树 和 y-fast 尝试，支持位迭代在时间 O(k lg lg n) 中，n 是位数，k 是真实位数.
A standard bitvector does not support efficient iteration over true bits - the runtime is always O(n), where n is the number of total bits, which has no dependence on k. However, there are specialized data structures like van Emde Boas trees and y-fast tries, that support iteration over the bits in time O(k lg lg n), where n is the number of bits and k is the number of true bits.
相关文章