C++如何實(shí)現(xiàn)BitMap數(shù)據(jù)結(jié)構(gòu)
分治，分布式。BitMap(位圖)及其升級(jí)版bloom filter是處理海量數(shù)據(jù)常用的方法，這里先介紹BitMap概念及其c++實(shí)現(xiàn)。
一、BitMap位圖
該數(shù)據(jù)結(jié)構(gòu)描述了一個(gè)有限定義域內(nèi)的稠密集合，其中的每一個(gè)元素最多出現(xiàn)一次并且沒(méi)有其他任何數(shù)據(jù)與該元素相關(guān)聯(lián)。
即使這些條件沒(méi)有完全滿(mǎn)足（例如，存在重復(fù)元素或額外的數(shù)據(jù)），也可以用有限定義域內(nèi)的鍵作為一個(gè)表項(xiàng)更復(fù)雜的表格索引。
所謂的Bit-map就是用一個(gè)bit位來(lái)標(biāo)記某個(gè)元素對(duì)應(yīng)的Value， 而Key即是該元素。
由于采用了Bit為單位來(lái)存儲(chǔ)數(shù)據(jù)，因此在存儲(chǔ)空間方面，可以大大節(jié)省。
例如假設(shè)我們要對(duì)0-7內(nèi)的5個(gè)元素(4,7,2,5,3)排序（這里假設(shè)這些元素沒(méi)有重復(fù)）。
那么我們就可以采用Bit-map的方法來(lái)達(dá)到排序的目的。
要表示8個(gè)數(shù)，我們就只需要8個(gè)Bit（1Bytes），首先我們開(kāi)辟1Byte的空間，將這些空間的所有Bit位都置為0，
如下圖：
遍歷第一個(gè)元素4，則在第4為標(biāo)1：
以此來(lái)推，遍歷完所有后結(jié)構(gòu)：
我們現(xiàn)在遍歷一遍Bit區(qū)域，將該位是bit 1的位的編號(hào)輸出（2，3，4，5，7），這樣就達(dá)到了排序的目的。
二、C++實(shí)現(xiàn)
我們可以用一個(gè)unsigned int類(lèi)型的數(shù)組或者向量來(lái)表示位圖，假設(shè)我們定義vector<unsigned int> a，則 第i位可表示為a[i/32]的i%32位（其中，32*N+r = i，r為i%32，也就是i/32的余數(shù)）。
由于計(jì)算機(jī)對(duì)位的操作比乘除法更有效率，這里計(jì)算i/32可以用位移操作：i>>5；計(jì)算i%32可以用1&31。
若是一個(gè)char數(shù)組str，則str的第i位為i/8(i>>3)地址塊的第i%8(i&7)位.下面以char為例說(shuō)明，int類(lèi)比可知。
#include<iostream>
#include<string>
#include<stdlib.h>
using namespace std;
class BitMap{
private:
char *bitmap;
int gsize;
public:
BitMap(){
gsize=(10000>>3)+1;//default 10000
bitmap= new char[gsize];
memset(bitmap,0,sizeof(bitmap));
}
BitMap(int n){
gsize=(n>>3)+1;
bitmap=new char[gsize];
memset(bitmap,0,sizeof(bitmap));
}
~BitMap(){delete []bitmap;}
int get(int x){
int cur=x>>3;
int red=x&7;
if(cur>gsize)return -1;
return (bitmap[cur]&=1>>red);
}
bool set(int x){
int cur=x>>3;//獲取元素位置,除8得到哪個(gè)元素，x/2^3得到那一個(gè)byte
int red=x&(7);//邏輯與，獲取進(jìn)準(zhǔn)位置,x&7==x%8.該Byte里第幾個(gè)
if(cur>gsize)return 0;
bitmap[cur]|=1>>red;//賦值，1向右移動(dòng)red位，|表示該位賦值1
return 1;
}
};以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
基于C++ bitset常用函數(shù)及運(yùn)算符(詳解)
下面小編就為大家?guī)?lái)一篇基于C++ bitset常用函數(shù)及運(yùn)算符(詳解)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-11-11
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法時(shí)間空間復(fù)雜度基礎(chǔ)實(shí)踐
這篇文章主要為大家介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法中時(shí)間空間復(fù)雜度的基礎(chǔ)實(shí)踐，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步2022-02-02
strcat函數(shù)與strncat函數(shù)的深入分析
本篇文章是對(duì)strcat函數(shù)與strncat函數(shù)進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
VC中CWinThread類(lèi)以及和createthread API的區(qū)別分析
這篇文章主要介紹了VC中CWinThread類(lèi)以及和createthread API的區(qū)別分析,較為詳細(xì)的講述了CWinThread類(lèi)的原理,并以實(shí)例形式對(duì)AfxBeginThread函數(shù)的內(nèi)部實(shí)現(xiàn)進(jìn)行了解釋說(shuō)明,需要的朋友可以參考下2014-10-10
使用順序存儲(chǔ)結(jié)構(gòu)的線性存儲(chǔ)結(jié)構(gòu)的表為線性順序表。本文將分別利用C語(yǔ)言和C++實(shí)現(xiàn)線性順序表，文中示例代碼講解詳細(xì)，需要的可以參考一下2022-05-05
在C++中關(guān)于友元函數(shù)的進(jìn)一步理解
今天小編就為大家分享一篇關(guān)于在C++中關(guān)于友元函數(shù)的進(jìn)一步理解，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2018-12-12
C語(yǔ)言中sizeof函數(shù)踩過(guò)的坑總結(jié)
sizeof是C語(yǔ)言的一種單目操作符，如C語(yǔ)言的其他操作符++、--等。它并不是函數(shù)。sizeof操作符以字節(jié)形式給出了其操作數(shù)的存儲(chǔ)大小。操作數(shù)可以是一個(gè)表達(dá)式或括在括號(hào)內(nèi)的類(lèi)型名。操作數(shù)的存儲(chǔ)大小由操作數(shù)的類(lèi)型決定2022-04-04
大家好，本篇文章主要講的是C語(yǔ)言之選擇分支語(yǔ)句詳解，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話(huà)記得收藏一下，方便下次瀏覽2021-12-12
c語(yǔ)言實(shí)現(xiàn)http下載器的方法
這篇文章主要介紹了c語(yǔ)言實(shí)現(xiàn)http下載器的相關(guān)知識(shí)，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了C語(yǔ)言如何改變字體顏色，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-10-10