位图法通过字节数组模拟位级存储实现高效整数去重，适用于已知且适中范围的场景；计算字节数为(max_value+7)/8，用vector构建，通过位运算set_bit(i)标记出现状态。
如果您需要在内存受限的环境中对大量整数进行去重操作，位图法是一种极为高效的空间优化方案。以下是实现基于位图的高效数据排重算法的具体步骤：
一、使用 std::vector 构建动态位图
该方法通过字节数组模拟位级存储，每个 bit 表示一个整数是否出现过，适用于已知数据范围且范围适中的场景。位图总长度由最大可能值决定，以字节为单位向上取整。
1、计算所需字节数：size_in_bytes = (max_value + 7) / 8。
2、声明 vector
3、定义宏或内联函数 set_bit(i)：bitmap[i / 8] |= (1U
4、定义宏或内联函数 test_bit(i)：return bitmap[i / 8] & (1U
5、遍历输入数组，对每个合法整数 x（0 ≤ x ≤ max_value），调用 set_bit(x) 标记。
6、再次遍历位图，对每个 i 满足 test_bit(i) 为真，则将 i 加入结果集合。
二、采用 std::bitset 实现编译期确定大小的位图
当数据范围 N 在编译期已知且不超百万量级时，std::bitset 提供零开销抽象和自动边界检查，支持直接按位操作与迭代器遍历，避免手动位运算错误。
1、声明 bitset
2、对每个输入整数 x，若 0 ≤ x
3、使用 for (size_t i = 0; i
4、如需节省空间并仅保留存在值，可同步维护 std::vector
三、分段位图处理超大整数范围（如 [0, 2³²)）
面对 32 位甚至 64 位全范围整数，单一块位图内存不可行。此方案将值域划分为固定大小的桶（例如每桶 65536 个数），按需分配位图，显著降低常驻内存占用。
1、定义桶大小 BUCKET_SIZE = 1U
2、使用 std::unordered_map
3、对每个输入值 x，计算桶索引 bucket_id = x / BUCKET_SIZE，位偏移 pos = x % BUCKET_SIZE。
4、若 bucket_map 中无 bucket_id 键，则插入 vector
5、在对应桶的 vector 中执行 set_bit(pos)。
6、遍历 bucket_map，对每个桶内满足 test_bit(j) 的 j，构造原始值 x = bucket_id * BUCKET_SIZE + j 并收集。
四、内存映射文件支持超大规模位图（TB 级去重）
当去重数据规模远超物理内存，可借助操作系统内存映射机制，将位图 backed by 文件，实现“看似在内存操作，实则按需换页”的效果，规避 OOM 风险。
1、创建指定大小的稀疏文件（如 Linux 下用 ftruncate 或 Windows 下 SetFileValidData）。
2、调用 mmap（POSIX）或 CreateFileMapping/MapViewOfFile（Windows）将文件映射至进程地址空间。
3、将映射起始地址 reinterpret_cast 为 uint8_t*，作为位图基址。
4、实现与方法一相同的 set_bit 和 test_bit 宏，但操作目标为映射内存而非堆内存。
5、所有位操作实时写入文件，程序退出前调用 munmap 或 UnmapViewOfFile，并确保 fsync。
注意：该方式要求文件系统支持稀疏文件且磁盘空间充足；随机访问性能依赖于 OS 页面缓存效率。
五、使用 roaring bitmap 库替代手写位图
Roaring Bitmap 是一种现代压缩位图结构，在高基数稀疏数据下比朴素位图节省 90% 以上内存，同时保持高性能 AND/OR/XOR 运算能力，适合生产环境部署。
1、从 GitHub 获取 roaring C++ 库并编译安装，或通过 vcpkg/conan 引入依赖。
2、包含头文件 #include "roaring/roaring.hh"。
3、声明 roaring::Roaring rb；
4、对每个输入整数 x，调用 rb.add(x)；重复添加自动去重。
5、调用 rb.to_array() 获取去重后数组，或使用 rb.forEach([](uint32_t x) { /* 处理 x */ }) 流式消费。
注意：roaring::Roaring 默认仅支持 uint32_t；如需 int32_t 负数支持，须先做无符号偏移映射。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
