C++位图简明介绍与实现
何时使用位图?
给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。【腾讯】
- 遍历,时间复杂度O(N)
- 排序(O(NlogN)),利用二分查找: logN
上述两种方法都不是很好,因此有了位图的用武之地
位图(表示一个数在不在)
数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0代表不存在。比如:
用位图解决上述问题需要的空间为:
因此位图需要开42亿9千万个比特即500M的空间:
位图的简单实现(C++库中有:bitset)
#include<iostream>
#include<vector>
using namespace std;
namespace cola
{
template<size_t N>
class bitset
{
public:
bitset()
{
//假设为7:7/8 = 0或10:10/8 = 1,因此最后加一个1防止空间不够用
_bits.resize(N / 8 + 1, 0);//初始化为全0
}
//将数据存入位图
void set(size_t x)
{
//计算x会放到第几个字节
size_t i = x / 8;
//计算x会放到第几位
size_t j = x % 8;
//存入位图中(位图置为1)
_bits[i] |= (1 << j);
}
//将数据从位图中移除
void reset(size_t x)
{
//计算在第几个字节
size_t i = x / 8;
//计算第几位
size_t j = x % 8;
//将数据移除(位图置为0)
_bits[i] &= ~(1 << j);
}
//查看数据是否存在(位图是否为1)
bool test
数九天有一个秘密: 我是108期的,互关一下。
猿奋~: 写的很详细,容易理解,对没有使用过智能指针的新手很友好,作者用心了
小虚竹: 大佬牛逼,一起加油!作者构思巧,善于选点展开,行文跌宕起伏,耐人寻味。
码咔吧咔: std::vector<MEDIA_CLIENT> media_client_list;博主这段是啥含义呀