迭代std :: bitset中真实位的有效方法?

沃梦达教程 C/C++实例代码

2022-10-18

Efficient way of iterating over true bits in std::bitset?(迭代std :: bitset中真实位的有效方法?)

本文介绍了迭代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.

这篇关于迭代std :: bitset中真实位的有效方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！