在std :: bitset中迭代真实位的有效方式？ [英] Efficient way of iterating over true bits in std::bitset?

问题描述

有没有一种方式可以在位数中迭代（可能是巨大的） std :: bitset ，这是线性被设置为true ？我想防止不必检查位组中的每一个位置。迭代应该连续返回设置为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 Tree 的特殊结构支持在时间上的位迭代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, a special structure called a van Emde Boas Tree supports 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.

作为一个无耻的自我推广，我有一个我个人网站上的vEB树的实现。如果我不适合在这里做广告，请让我知道，我会把它放下。

As a bit of Shameless Self-Promotion, I have an implementation of a vEB-tree on my personal website. If it's inappropriate for me to advertise this here, please let me know and I'll take it down.

这篇关于在std :: bitset中迭代真实位的有效方式？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！