C++自定义Bitset置位索引迭代的零开销抽象实现方案咨询

这问题太典型了——想要像方式一那样用简洁的范围for循环遍历Bitset的置位比特，又不想为了这份简洁付出vector堆分配的性能代价，自定义迭代器就是完美的解决方案！它能让你拥有方式一的语法优雅，同时保持方式二的零额外开销。

核心思路：自定义迭代器 #

我们要给Bitset类实现一个符合C++迭代器规范的自定义迭代器，这样就能直接用范围for循环遍历置位比特的索引，全程没有堆分配，性能和手动遍历完全一致。

完整实现代码 #

#include <cstdint>
#include <iterator> // 用于迭代器相关的类型定义
#include <iostream>

constexpr size_t BITS = 64;

struct Bitset {
    uint64_t* data_;
    size_t chunks_;

    // 自定义迭代器类
    class Iterator {
    public:
        // 迭代器类型定义，满足C++迭代器要求
        using iterator_category = std::forward_iterator_tag;
        using value_type = int;
        using difference_type = std::ptrdiff_t;
        using pointer = const value_type*;
        using reference = const value_type&;

        // 构造函数：初始化迭代器状态
        Iterator(const Bitset* bitset, size_t chunk_idx)
            : bitset_(bitset), chunk_idx_(chunk_idx), current_chunk_(0) {
            // 跳过全0的块，找到第一个有置位比特的块
            skip_empty_chunks();
            // 如果当前块有效，初始化current_chunk_为块的值
            if (chunk_idx_ < bitset_->chunks_) {
                current_chunk_ = bitset_->data_[chunk_idx_];
            }
        }

        // 解引用：返回当前置位比特的索引
        value_type operator*() const {
            return static_cast<int>(chunk_idx_ * BITS + __builtin_ctzll(current_chunk_));
        }

        // 前置++：移动到下一个置位比特
        Iterator& operator++() {
            // 清除当前置位的比特
            current_chunk_ &= current_chunk_ - 1;
            // 如果当前块还有置位比特，直接返回
            if (current_chunk_ != 0) {
                return *this;
            }
            // 否则移动到下一个块，跳过空块
            ++chunk_idx_;
            skip_empty_chunks();
            // 更新当前块的值
            if (chunk_idx_ < bitset_->chunks_) {
                current_chunk_ = bitset_->data_[chunk_idx_];
            } else {
                current_chunk_ = 0;
            }
            return *this;
        }

        // 后置++（可选，满足迭代器规范）
        Iterator operator++(int) {
            Iterator temp = *this;
            ++(*this);
            return temp;
        }

        // 相等比较
        bool operator==(const Iterator& other) const {
            // 当块索引超出范围，或者两个迭代器的块索引和当前块都相同时，视为相等
            return (chunk_idx_ == other.chunk_idx_) && (current_chunk_ == other.current_chunk_);
        }

        // 不等比较
        bool operator!=(const Iterator& other) const {
            return !(*this == other);
        }

    private:
        const Bitset* bitset_;
        size_t chunk_idx_;
        uint64_t current_chunk_;

        // 辅助函数：跳过所有全0的块
        void skip_empty_chunks() {
            while (chunk_idx_ < bitset_->chunks_ && bitset_->data_[chunk_idx_] == 0) {
                ++chunk_idx_;
            }
        }
    };

    // 返回起始迭代器
    Iterator begin() const {
        return Iterator(this, 0);
    }

    // 返回结束迭代器
    Iterator end() const {
        return Iterator(this, chunks_);
    }
};

// 现在的遍历代码和方式一一样简洁，但没有任何堆分配！
void Iterate(const Bitset& bitset) {
    for (int b : bitset) {
        std::cout << "bit: " << b << std::endl;
    }
}

为什么这个方案完美？ #

• 代码简洁性：和方式一一样，用for (int b : bitset)就能完成遍历，语法直观，不需要重复写嵌套循环逻辑。
• 零性能开销：迭代器是栈上分配的对象，遍历过程中没有任何堆内存分配，和方式二的手动遍历效率完全一致——甚至因为迭代器的逻辑被封装，更容易优化。
• 复用性强：遍历逻辑只在迭代器里实现一次，所有需要遍历Bitset置位比特的地方都可以直接用范围for，避免代码冗余。
• 符合C++规范：迭代器满足C++标准库的迭代器要求，还可以和标准库算法配合使用（比如std::count、std::for_each等）。

额外优化点 #

如果你的Bitset可能有大量全0的块，skip_empty_chunks()函数能帮你快速跳过这些块，进一步提升遍历效率——这是手动遍历容易遗漏的优化点。

内容的提问来源于stack exchange，提问作者Laakeri