c++怎么实现一个简单的位图（Bitmap）_c++位图结构与应用示例

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

c++怎么实现一个简单的位图（Bitmap）_c++位图结构与应用示例

2025-11-01

浏览次数：次

返回列表

位图用比特表示整数存在状态，节省内存。通过vector或bitset实现，支持set、clear、get操作，适用于去重排序小整数，如输出2 3 5 7 8；std::bitset适合固定大小场景，手动实现更灵活，广泛用于系统级设计。

c++怎么实现一个简单的位图（bitmap）_c++位图结构与应用示例

在C++中，位图（Bitmap）是一种高效的数据结构，用于表示一组布尔状态，通常用来标记某个整数是否出现过。它的核心思想是用一个比特（bit）来表示一个元素的存在与否，从而极大节省内存空间。

位图的基本原理

假设我们要处理的整数范围是 0 到 N-1，那么可以用 N 个比特来表示这些整数的状态：0 表示未出现，1 表示已出现。由于一个字节有8位，我们可以使用 unsigned char 或 std::vector 来存储这些比特。

更高效的做法是使用 std::vector 或 std::bitset，通过位操作直接访问特定位置的比特。

手动实现简单的位图类

下面是一个基于 vector 的简单位图实现：

#include <iostream>
#include <vector>

class Bitmap {
private:
    std::vector<char> 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 < 0 || i >= size) return;
        int byteIndex = i / 8;
        int bitIndex = i % 8;
        bits[byteIndex] |= (1 << bitIndex);
    }

    // 清除某一位为 0
    void clear(int i) {
        if (i < 0 || i >= size) return;
        int byteIndex = i / 8;
        int bitIndex = i % 8;
        bits[byteIndex] &= ~(1 << bitIndex);
    }

    // 检查某一位是否为 1
    bool get(int i) {
        if (i < 0 || i >= size) return false;
        int byteIndex = i / 8;
        int bitIndex = i % 8;
        return (bits[byteIndex] & (1 << bitIndex)) != 0;
    }
};

使用示例：去重与排序小整数

位图常用于对非负整数进行快速去重和排序。比如我们有一组数据，想输出不重复且有序的结果：

NameGPT

免费的名称生成器，AI驱动在线生成企业名称及Logo

119 查看详情 NameGPT

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 <bitset>
#include <iostream>

int main() {
    std::bitset<100> 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++位图结构与应用示例的详细内容，更多请关注其它相关文章！

# 是一个 # 人才网站全年推广方案 # 海口怎么优化关键词排名 # 正规网站优化大概费用 # 灌阳关键词排名加盟 # 响应式网站建设营销推广 # 铜仁港网站建设 # 深圳独立网站优化有用吗 # 乳山seo关键词排名优化软件 # 江宁区企业网站推广服务 # seo专职好做吗 # 是一种 # 更灵活 # 字节 # 正确处理 # 如何用 # 如何处理 # 重写 # 适用于 # 有什么 # 数据结构 # 标准库 # stream # ios # c++ # ai