位图用比特表示整数存在状态，节省内存。通过vector或bitset实现，支持set、clear、get操作，适用于去重排序小整数，如输出2 3 5 7 8；std::bitset适合固定大小场景，手动实现更灵活，广泛用于系统级设计。
在C++中，位图（Bitmap）是一种高效的数据结构，用于表示一组布尔状态，通常用来标记某个整数是否出现过。它的核心思想是用一个比特（bit）来表示一个元素的存在与否，从而极大节省内存空间。
位图的基本原理
假设我们要处理的整数范围是 0 到 N-1，那么可以用 N 个比特来表示这些整数的状态：0 表示未出现，1 表示已出现。由于一个字节有8位，我们可以使用 unsigned char 或 std::vector 来存储这些比特。
更高效的做法是使用 std::vector 或 std::bitset，通过位操作直接访问特定位置的比特。
手动实现简单的位图类
下面是一个基于 vector 的简单位图实现：
#include #include class Bitmap {private: std::vector bits; int size;public: // 构造函数，指定最大数值范围 Bitmap(int n) : size(n) { bits.resize((n + 7) / 8, 0); // 每个 char 8 bit，向上取整 } // 设置某一位为 1 void set(int i) { if (i = size) return; int byteIndex = i / 8; int bitIndex = i % 8; bits[byteIndex] |= (1 << bitIndex); } // 清除某一位为 0 void clear(int i) { if (i = size) return; int byteIndex = i / 8; int bitIndex = i % 8; bits[byteIndex] &= ~(1 << bitIndex); } // 检查某一位是否为 1 bool get(int i) { if (i = size) return false; int byteIndex = i / 8; int bitIndex = i % 8; return (bits[byteIndex] & (1 << bitIndex)) != 0; }};
使用示例：去重与排序小整数
位图常用于对非负整数进行快速去重和排序。比如我们有一组数据，想输出不重复且有序的结果：
立即学习“C++免费学习笔记（深入）”；
int main() { Bitmap bm(100); // 支持 0~99 int nums[] = {5, 2, 7, 5, 3, 2, 8, 7}; int n = sizeof(nums) / sizeof(nums[0]); // 插入所有数字（自动去重） for (int i = 0; i < n; ++i) { bm.set(nums[i]); } // 按顺序输出存在的数字 std::cout << "Unique sorted numbers: "; for (int i = 0; i < 100; ++i) { if (bm.get(i)) { std::cout << i << " "; } } std::cout << std::endl; return 0;}
输出结果：
Unique sorted numbers: 2 3 5 7 8
标准库替代方案：std::bitset
如果大小在编译期已知，可以直接使用 std::bitset，它更安全且接口简洁：
#include #include int main() { std::bitset bs; // 固定大小为100 bs.set(5); bs.set(2); bs.set(7); bs.set(5); // 重复设置无影响 for (int i = 0; i < 100; ++i) { if (bs.test(i)) { std::cout << i << " "; } } std::cout << std::endl; return 0;}
基本上就这些。自己实现的 Bitmap 更灵活，可动态扩展；而 std::bitset 更适合固定场景，写起来更简单。实际应用中，位图广泛用于布隆过滤器、内存页管理、文件系统索引等底层系统设计中。注意它只适用于整数且范围不太大的情况，超出后要考虑 Roaring Bitmap 等优化结构。
以上就是c++++怎么实现一个简单的位图（Bitmap）_c++位图结构与应用示例的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1481990.html
微信扫一扫 
支付宝扫一扫 
