在std :: bitset中迭代真位的有效方法？

Question

有没有一种方法可以迭代(可能是巨大的)设置为true的位数std::bitset是线性的？我想防止必须检查bitset中的每个位置.迭代应该连续返回设置为true的每个位的索引.

Answer 1

标准位向量不支持在真位上进行有效迭代 - 运行时始终为O(n),其中n是总位数,不依赖于k.然而,称为van Emde Boas Tree的特殊结构支持对时间比特O(k lg lg n)进行迭代,其中n是比特数,k是真比特数.

作为一点无耻的自我推销,我在我的个人网站上实现了一个vEB树.如果我在这里做广告不合适,请告诉我,我会把它删掉.

Answer 2

为了使其成为线性，您需要一个链接列表/数组/索引集设置为 true。保留这样的二级索引不是 std::bitset 所需的性能/存储权衡的一部分，并且考虑到如果没有您的特定要求，它会给每个人带来不利，因此实现无法提供此功能。您可以考虑自己用这样的容器补充您的位集，或者使用 boost 的多索引容器库。