C++詳細講解模擬實現(xiàn)位圖和布隆過濾器的方法
位圖
引論
四十億個無符號整數(shù)，現(xiàn)在給你一個無符號整數(shù)，判斷這個數(shù)是否在這四十億個數(shù)中。
路人甲：簡單，快排+二分。
可是存儲這四十億個整數(shù)需要多少空間？
簡單算一下，1G=1024M=1024 * 1024KB=1024 * 1024 * 1024Byte，也就是說1G大概也就是十億個字節(jié)。
四十億個整數(shù)多大？40億 * 4==160億個字節(jié)，換算一下也就是16G。
我電腦內(nèi)存也就十六個G，還不加上別的應用，顯然內(nèi)存超限了。
所以快排+二分是不可取的，那有沒有別的法子呢？
所以也就有了下面要講的位圖。
概念
位圖是什么？
根據(jù)上面的模型我們可以發(fā)現(xiàn)，之前要用四個字節(jié)存儲一個數(shù)字，現(xiàn)在只需一個比特位，當然我們不是存儲具體數(shù)值，而是存儲數(shù)字的狀態(tài)。
因為一個比特位只有兩種狀態(tài)，所以我們存儲的是該數(shù)字是否存在（數(shù)字存在對應位為1，否則為0）
解決引論
上面發(fā)現(xiàn)本來需要4個字節(jié)存儲，現(xiàn)在只需要1位去存儲，一下子就縮小了32倍，所以原本需要16G內(nèi)存存儲的數(shù)據(jù)只需要0.5G。顯然這個內(nèi)存我們是開的起的。
那該怎么判斷這個數(shù)字是否存在呢？將這個數(shù)字/8得到它在第幾個字節(jié)，將這個數(shù)字%8即可得到他在這個數(shù)字在第幾位。
比如10，就在第一個字節(jié)的第二位。（都是從0開始計數(shù)）
總結(jié)一下應該怎么解決引論提出的問題？開一個能存儲42億位的位圖，查找時算出待查找數(shù)的位置，如果這個位置為1則表示存在，否則就不存在。
位圖也是一種哈希思想的運用
位圖的模擬實現(xiàn)
鋪墊
從上面可以看出，位圖的實現(xiàn)主要在于把某一位置為0和把某一位置為1。
如何把某一位置為1？
把那個位置 |1
|是按位或運算符
如何把某一位置為0？
把那個位置 &0
&是按位與運算符
所以我們在實現(xiàn)時只需要算出那個位置再進行位操作即可。
結(jié)構(gòu)
構(gòu)造函數(shù)
BitSet()
{
_bits.resize(N / 8 + 1);//開這么多個字節(jié),+1是怕有余數(shù)
}
比如開10個位就要開兩個字節(jié)。
因為采用的是vector,所以所有的char都會被默認置為0。char類型的默認值就是0，空字符。
比如底層實現(xiàn)時resize第二個參數(shù)默認值給成T()，T為模板，當用char去實例化時，那默認值就是char()了，也就是ASCII碼為0的字符。
存儲
vector<char>_bits;
用vector存的。
set,reset,test
test作用：檢查這一位是0還是1，是1返回true，否則返回false
bool test(size_t x)
{
size_t integer = x / 8;//第幾個字節(jié)
size_t rem = x % 8;//字節(jié)的第幾個位置
return ((_bits[integer] >> rem) & 1) ? true : false;
}
set作用：把某一個位置置為1
void set(size_t x)//第x位置為1
{
if (!test(x))//如果這一位是0，置為1的話++
{
_cnt++;
}
size_t integer = x / 8;//第幾個字節(jié)
size_t rem = x % 8;//字節(jié)的第幾個位置
_bits[integer] |= (1 << rem);
}
reset作用：把某一個位置置為0
void reset(size_t x)//第x位置為0
{
if (test(x))//如果這一位是1，置為0的話--
{
_cnt--;
}
size_t integer = x / 8;//第幾個字節(jié)
size_t rem = x % 8;//字節(jié)的第幾個位置
_bits[integer] &= (~(1 << rem));
}
flip,size,count
flip：翻轉(zhuǎn)，0變?yōu)?,1變?yōu)?
void flip(size_t x)//翻轉(zhuǎn)
{
if (test(x))//1
{
reset(x);
}
else//0
{
set(x);
}
}
size：位圖有多少位
size_t size() const
{
return N;//模板參數(shù)
}
count：位圖里有多少個1
size_t count()
{
return _cnt;
}
any,none,all
any：位圖里有沒有1，有1返回true，否則返回false
bool any()
{
if (_cnt)
{
return true;
}
return false;
}
none：與any相反
bool none()
{
return !any();
}
all：全為1返回true，否則返回false
bool all()
{
if (_cnt == N)
{
return true;
}
else
{
return false;
}
}
重載流運算符
重載流運算符必須在BitSet里面加上一個函數(shù)聲明
template<size_t T> friend ostream& operator<<(ostream& out, const BitSet<T>& bs);
這里會出現(xiàn)的一個問題是，因為類已經(jīng)有了一個模板參數(shù)，所以很容易寫成
friend ostream& operator<<(ostream& out, const BitSet<N>& bs);
導致運行時報鏈接錯誤。
原因講解：目錄-解決方法
簡單解釋一下，因為這是一個聲明，所以編譯到這里時只當這是個友元函數(shù)的聲明，并不會把函數(shù)里的模板N參數(shù)實例化，只有調(diào)用流運算符時才會去實例化，這就出現(xiàn)了二次編譯（第一次編譯只實例化了BitSet類，即類BitSet模板參數(shù)N被確定下來）
但因為友元函數(shù)只是聲明并沒有實例化，即第二種寫法的N并沒有被確定下來，到調(diào)用這個函數(shù)的時候要對N進行編譯，但是不知道這個N具體是什么，因為N是一個模板參數(shù)被第一次實例化確定下來后就沒了，編譯器往上找也找不到，導致有函數(shù)聲明但是找不到具體函數(shù)，從而發(fā)生了鏈接錯誤。解決就是寫成第一種，第二次編譯時看到了上面有一個模板聲明就知道T是個模板參數(shù)，調(diào)用時第一次被確定的N傳給現(xiàn)在的T，所以就能正確運行。
ostream& operator<<(ostream& out, const BitSet<T>& bs)
{
//從后往前是低位到高位，庫里面是這樣的
int len = bs.size() / 8 ;
char tmp;
tmp = bs._bits[len];
for (int i = bs.size() % 8 - 1; i >= 0; i--)
{
if ((tmp >> i) & 1)
{
cout << '1';
}
else
{
cout << '0';
}
}
for (int i = len-1; i >=0; i--)
{
tmp = bs._bits[i];
for (int j = 7; j >=0; j--)
{
if ((tmp >> j) & 1)
{
cout << '1';
}
else
{
cout << '0';
}
}
}
//從前往后是低位到高位（人看起來合適）
//for (int i=0;i<len;i++)
//{
// tmp = bs._bits[i];
// for (int i =0;i<8;i++)
// {
// if ((tmp >> i) & 1)
// {
// cout << '1';
// }
// else
// {
// cout << '0';
// }
// }
//}
//tmp = bs._bits[len];
//for (int i = 0; i < bs.size() % 8; i++)
//{
// if ((tmp >> i) & 1)
// {
// cout << '1';
// }
// else
// {
// cout << '0';
// }
//}
return out;
}比如有十個位，把第一位置為1，那打印出來就是0000000010
是從右往左數(shù)的，庫里的打印是這樣的，注釋掉的那部分代碼會打印0100000000
實際我們操作內(nèi)存實現(xiàn)的存儲是00000010 00000000
測試
void test_bitset()
{
BitSet<10> bits;
bits.set(1);
bits.set(9);
cout << bits.count() << endl;
bits.reset(1);
cout << bits.count() << endl;
cout << bits << endl;
/*cout << bits.none() << endl;
bits.set(4);
cout << bits.none() << endl;
cout << bits.any() << endl;
cout << bits.all() << endl;*/
/*bits.set(4);
cout << bits.test(4) << endl;
bits.flip(4);
cout << bits.test(4) << endl;
bits.flip(4);
cout << bits.test(4) << endl;*/
/*bits<0xffffffff>bits;
cout << endl;*/
}位圖簡單應用
100億個整數(shù)，找到只出現(xiàn)一次的數(shù)。
100億個整數(shù)不代表要開一百億位大小的空間，有些可能重復了幾次，所以開int大小的即可。
整兩個位圖代表兩位， 00 01 10 11， 第一個位圖代表第一位，第二個位圖表示第二位 ，初始狀態(tài)都是00，插入一個數(shù)后將其置為01， 再來就置為10 ，再去遍歷整個位圖得到只出現(xiàn)一次的數(shù)的集合。
template<size_t N>
class FindOnceVal
{
public:
void set(size_t x)
{
bool flag1 = _bs1.test(x);//得到第一位
bool flag2 = _bs2.test(x);//得到第二位
if (flag1 == false && flag2 == false)//00->01
{
_bs2.set(x);
}
else if (flag1 == false && flag2 == true)//01->10
{
_bs1.set(x);
_bs2.reset(x);
}
//10->11...不用再處理了
}
bool check(size_t x)
{
if (!_bs1.test(x) && _bs2.test(x))//01
{
return true;
}
return false;
}
void print()
{
for (size_t i = 0; i < N; i++)
{
if (check(i))
{
printf("%d\n",i);
}
}
}
private:
BitSet<N>_bs1;
BitSet<N>_bs2;
};
void TestFindOnceVal()
{
int a[] = { 1, 20, 30, 43, 5, 4, 1, 43, 43, 7, 9, 7, 7, 0 };
FindOnceVal<100> fov;
for (auto e : a)
{
fov.set(e);
}
fov.print();
}給兩個文件，分別有100億個整數(shù)，我們只有1G內(nèi)存，如何找到兩個文件交集？
兩個位圖，分別去映射兩個文件，再去遍歷比對即可。比如兩個位圖的同一個位置都為1說明整個數(shù)就在交集里面
給一個超過100G大小的log file, log中存著IP地址, 設計算法找到出現(xiàn)次數(shù)最多的IP地址？ 我們只有1G內(nèi)存，如何找到top K的IP？
哈希切割，運用哈希算法將IP分類（切割），比如把IP轉(zhuǎn)成字符串，再映射成整形，這就是一種哈希算法，100G給分成100個文件，即100個小類，每一個文件去計數(shù)，比如就用map<string,int> 然后記錄下最大的，再將map清空。
第二個文件出來的最大次數(shù)再與第一個得到的最大次數(shù)進行比較記錄下出現(xiàn)最大次數(shù)的ip和次數(shù)，如此循環(huán)遍歷完 100個文件即可。 如果要topK 建一個小堆即可
如果出現(xiàn)切分后一個文件還是過大，那換一種哈希算法再進行切割
位圖的優(yōu)勢就在于可以大大節(jié)省空間！
位圖代碼匯總
#pragma once
#include <vector>
#include <string>
#include <iostream>
using namespace std;
namespace ck
{
template<size_t N>//N個數(shù)
class BitSet
{
public:
BitSet()
{
_bits.resize(N / 8 + 1);//開這么多個字節(jié)
}
void set(size_t x)//第x位置為1
{
if (!test(x))//如果這一位是0，置為1的話++
{
_cnt++;
}
size_t integer = x / 8;//第幾個字節(jié)
size_t rem = x % 8;//字節(jié)的第幾個位置
_bits[integer] |= (1 << rem);
}
void reset(size_t x)//第x位置為0
{
if (test(x))//如果這一位是1，置為0的話--
{
_cnt--;
}
size_t integer = x / 8;//第幾個字節(jié)
size_t rem = x % 8;//字節(jié)的第幾個位置
_bits[integer] &= (~(1 << rem));
}
bool test(size_t x)
{
size_t integer = x / 8;//第幾個字節(jié)
size_t rem = x % 8;//字節(jié)的第幾個位置
return ((_bits[integer] >> rem) & 1) ? true : false;
}
void flip(size_t x)//翻轉(zhuǎn)
{
if (test(x))//1
{
reset(x);
}
else//0
{
set(x);
}
}
size_t size() const
{
return N;//模板參數(shù)
}
size_t count()
{
return _cnt;
}
bool any()
{
if (_cnt)
{
return true;
}
return false;
}
bool none()
{
return !any();
}
bool all()
{
if (_cnt == N)
{
return true;
}
else
{
return false;
}
}
template<size_t T>
friend ostream& operator<<(ostream& out, const BitSet<T>& bs);
private:
vector<char>_bits;
size_t _cnt = 0;//被設置為1的個數(shù)
};
template<size_t T>//模板參數(shù)不能取名為N
ostream& operator<<(ostream& out, const BitSet<T>& bs)
{
//從后往前是低位到高位，庫里面是這樣的
int len = bs.size() / 8 ;
char tmp;
tmp = bs._bits[len];
for (int i = bs.size() % 8 - 1; i >= 0; i--)
{
if ((tmp >> i) & 1)
{
cout << '1';
}
else
{
cout << '0';
}
}
for (int i = len-1; i >=0; i--)
{
tmp = bs._bits[i];
for (int j = 7; j >=0; j--)
{
if ((tmp >> j) & 1)
{
cout << '1';
}
else
{
cout << '0';
}
}
}
//從前往后是低位到高位（人看起來合適）
//for (int i=0;i<len;i++)
//{
// tmp = bs._bits[i];
// for (int i =0;i<8;i++)
// {
// if ((tmp >> i) & 1)
// {
// cout << '1';
// }
// else
// {
// cout << '0';
// }
// }
//}
//tmp = bs._bits[len];
//for (int i = 0; i < bs.size() % 8; i++)
//{
// if ((tmp >> i) & 1)
// {
// cout << '1';
// }
// else
// {
// cout << '0';
// }
//}
return out;
}
void test_bitset()
{
BitSet<10> bits;
bits.set(1);
bits.set(9);
cout << bits.count() << endl;
bits.reset(1);
cout << bits.count() << endl;
cout << bits << endl;
/*cout << bits.none() << endl;
bits.set(4);
cout << bits.none() << endl;
cout << bits.any() << endl;
cout << bits.all() << endl;*/
/*bits.set(4);
cout << bits.test(4) << endl;
bits.flip(4);
cout << bits.test(4) << endl;
bits.flip(4);
cout << bits.test(4) << endl;*/
/*bits<0xffffffff>bits;
cout << endl;*/
}
/*1. 給定100億個整數(shù)，設計算法找到只出現(xiàn)一次的整數(shù)？
100億個整數(shù)不代表要開一百億位大小的空間，有些可能重復了幾次，所以開int大小的即可。
整兩個位圖 00 01 10 11 第一個位圖代表第一位 第二個位圖表示第二位 初始狀態(tài)都是00 來了一個數(shù)后將其置為01 再來就置為10 再去遍歷
*/
template<size_t N>
class FindOnceVal
{
public:
void set(size_t x)
{
bool flag1 = _bs1.test(x);
bool flag2 = _bs2.test(x);
if (flag1 == false && flag2 == false)//00->01
{
_bs2.set(x);
}
else if (flag1 == false && flag2 == true)//01->10
{
_bs1.set(x);
_bs2.reset(x);
}
//10->11...不用再處理了
}
bool check(size_t x)
{
if (!_bs1.test(x) && _bs2.test(x))//01
{
return true;
}
return false;
}
void print()
{
for (size_t i = 0; i < N; i++)
{
if (check(i))
{
printf("%d\n",i);
}
}
}
private:
BitSet<N>_bs1;
BitSet<N>_bs2;
};
void TestFindOnceVal()
{
int a[] = { 1, 20, 30, 43, 5, 4, 1, 43, 43, 7, 9, 7, 7, 0 };
FindOnceVal<100> fov;
for (auto e : a)
{
fov.set(e);
}
fov.print();
}
/*位圖應用變形：1個文件有100億個int，1G內(nèi)存，設計算法找到出現(xiàn)次數(shù)不超過2次的所有整數(shù) 在第一題的基礎上稍作改動即可*/
/*給兩個文件，分別有100億個整數(shù)，我們只有1G內(nèi)存，如何找到兩個文件交集？
兩個位圖，分別去映射兩個文件，再去遍歷即可
*/
/*給一個超過100G大小的log file, log中存著IP地址, 設計算法找到出現(xiàn)次數(shù)最多的IP地址？ 與上題條件相同，
如何找到top K的IP？*/
/*哈希切割 運用哈希算法將IP分類（切割），比如把IP轉(zhuǎn)成字符串，再映射成整形，這就是一種哈希算法 100G給分成100個文件，即100個小類，
每一個文件去計數(shù)，比如就用map<string,int> 然后記錄下最大的，再將map清空
第二個文件出來的最大次數(shù)再與第一個得到的最大次數(shù)進行比較
如果要topK 建一個小堆即可 如果出現(xiàn)一個文件還是過大，那換一種哈希算法在進行切割
*/
}布隆過濾器
前提是已經(jīng)實現(xiàn)了位圖
引論
存在一億個ip，給一個ip,快速判斷這個ip在不在這一億個ip中
之前哈希切割能不能做？之前是切成小文件，但是其實歸根到底都只記錄了出現(xiàn)次數(shù)最多的，并沒有記錄所有人的狀態(tài)。
那我們可不可以通過位圖來做，把IP映射到位圖的一個位置，再去判斷這個IP是否在位圖中。聽起來可行，但是顯然會出現(xiàn)映射上的沖突，即兩個不同的IP映射到了同一個位置，這就導致了誤判。那有沒有更好的法子？
一個叫布隆的人發(fā)現(xiàn)消除沖突是不可能的，但是可以減緩沖突，他是怎么減緩沖突的呢？
之前一個ip映射一個位置，現(xiàn)在我去映射多個位置，比如映射三個，只有三個位置全部對上，那才說明這個ip存在，當然這也可能存在誤判，但誤判概率已經(jīng)減小很多了。這就是布隆過濾器
要點
- 布隆過濾器沒有消除沖突，但是減緩了沖突。
- 布隆過濾器判斷數(shù)據(jù)是否存在時是可能誤判的，但是在判斷數(shù)據(jù)不存在時一定準確
- 在一些允許誤判的情境下大大提高了判斷的效率。
一個經(jīng)典的場景就是取名，我們在一個軟件內(nèi)注冊一個用戶，用戶輸入一個名稱檢查是否重復，誤判的情景：用戶輸入一個名字，這個名字事實上不存在，但是被誤判為存在，那這個代價很小啊，大不了讓用戶換一個名字輸入不就行了。如果為了得到一個準確的結(jié)果，可以在判斷存在后去對服務器發(fā)送一個請求去檢查這個名字是否存在（一般能不涉及服務器就不去涉及了）。
- 布隆過濾器可以刪除嗎？
理論上是可以的，但是不建議，比如兩個元素，每個元素映射三個位置，三個位置里有兩個位置相同，那刪除一個ip，即刪除三個位置肯定會影響到另一個，所以就不好刪除。
但也不是不能刪除，硬要刪除也是可以的，現(xiàn)在一個ip映射三個位置，每個位置都是1個比特位，只能表示兩種狀態(tài)，可以把每種狀態(tài)設置為8個位，也就是一個字節(jié)，就可以表示256種狀態(tài)，可以用來計數(shù)實現(xiàn)刪除。但是問題在開位圖的原因就是為了節(jié)省空間，現(xiàn)在一個狀態(tài)一個字節(jié)與初衷相違背了，可謂是殺敵一千自損八百。因此不建議刪除
代碼實現(xiàn)
這個比較簡單，復用位圖即可，比如一個ip映射三個位置，也就是用來三個哈希函數(shù)而已。
哈希函數(shù)都是貼網(wǎng)上的代碼，處理string的哈希效率比較好的有BKDR哈希等等。實現(xiàn)的布隆過濾器默認的哈希函數(shù)是處理string的
#include "BitSet_.h"http://復用位圖
namespace ck
{
struct HashFunc1
{
//BKDR Hash
size_t operator()(const string& str)
{
size_t seed = 131; // 31 131 1313 13131 131313 etc..
size_t hash = 0;
for (size_t i = 0; i < str.length(); i++)
{
hash = (hash * seed) + str[i];
}
return hash;
}
};
struct HashFunc2
{
//FNV Hash
size_t operator()(const string& str)
{
size_t fnv_prime = 0x811C9DC5;
size_t hash = 0;
for (std::size_t i = 0; i < str.length(); i++)
{
hash *= fnv_prime;
hash ^= str[i];
}
return hash;
}
};
struct HashFunc3
{
//APH Hash
size_t operator()(const string& str)
{
unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8);
unsigned int ThreeQuarters = (unsigned int)((BitsInUnsignedInt * 3) / 4);
unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8);
unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
unsigned int hash = 0;
unsigned int test = 0;
for (std::size_t i = 0; i < str.length(); i++)
{
hash = (hash << OneEighth) + str[i];
if ((test = hash & HighBits) != 0)
{
hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
}
}
return hash;
}
};
template<size_t N, class K=string ,class Hash1 = HashFunc1, class Hash2 = HashFunc2, class Hash3 = HashFunc3>
class BloomFilter
{
public:
void set(const K& key)
{
size_t x1 = Hash1()(key)%len;
size_t x2 = Hash2()(key) % len;
size_t x3 = Hash3()(key) % len;
_bs.set(x1);
_bs.set(x2);
_bs.set(x3);
}
bool test(const K& key)
{
//不用一次性算出所有的值
size_t x1 = Hash1()(key) % len;
if (!_bs.test(x1))
{
return false;
}
size_t x2 = Hash2()(key) % len;
if (!_bs.test(x2))
{
return false;
}
size_t x3 = Hash2()(key) % len;
if (!_bs.test(x3))
{
return false;
}
return true;//三個位置全都存在才能說明存在
}
private:
BitSet<6*N>_bs;
size_t len = 6 * N;//位圖的大小可以決定過濾器的效率（越大哈希沖突概率越小，誤判概率越低）
};效率
效率指的就是誤判的概率。
多搞幾個哈希函數(shù)，或者把位圖開大一點都能提高降低誤判的可能性。
網(wǎng)上有很多大佬探究了位圖大小開多少合適，比如位圖要存儲N個數(shù)，那開多大可以讓性能還可以的同時也不用開過多的空間，結(jié)果是4。有N個數(shù)就開4N左右，當然和存儲的具體數(shù)據(jù)有關。比如我上面就開了6N。
解決方法
1. 直接把定義和實現(xiàn)都寫在類中
2. 如下：
#include <iostream>
using namespace std;
template <class T>
class Compleax
{
template <class S> //注意這里是S,和上面的T的名字不一樣
friend ostream & operator<< (ostream &out, Compleax <S>&c);
public:
Compleax(T a, T b);
void PrintCom()
{
cout<<"a:"<<a<<" b:"<<b<<endl;
}
private:
T a;
T b;
};
template <class T>
Compleax<T> :: Compleax(T a, T b)
{
this->a = a;
this->b = b;
}
template <class T>
ostream &operator << (ostream &out, Compleax<T> &c)
{
out<<c.a<<" "<<c.b<<endl;
return out;
}
int main()
{
Compleax<int> c(2, 3);
c.PrintCom();
cout<<c<<endl;
return 0;
}3. 如下：
#include <iostream>
using namespace std;
//1.需要先聲明類模板
template <class T>
class Compleax;
//2.再聲明友元函數(shù)
template <class T>
ostream & operator<< (ostream &out, Compleax<T> &c);
template <class T>
class Compleax
{
//3.類中定義友元函數(shù)，注意需要加上<>
friend ostream & operator<< <T>(ostream &out, Compleax &c);
public:
Compleax(T a, T b);
void PrintCom()
{
cout<<"a:"<<a<<" b:"<<b<<endl;
}
private:
T a;
T b;
};
template <class T>
Compleax<T> :: Compleax(T a, T b)
{
this->a = a;
this->b = b;
}
template <class T>
ostream &operator << (ostream &out, Compleax<T> &c)
{
out<<c.a<<" "<<c.b<<endl;
return out;
}
int main()
{
Compleax<int> c(2, 3);
c.PrintCom();
cout<<c<<endl;
return 0;
}這樣即可解決錯誤提示為無法解析的外部符之類的問題。下面來說明一下為什么會有這樣的現(xiàn)象發(fā)生。
其實在模板機制的內(nèi)部，編譯器做的工作和沒有模板機制時我們做的功能大同小異。在使用了函數(shù)模板的代碼中。編譯器其實進行了二次編譯，第一次是在聲明函數(shù)模板時，會檢查你的函數(shù)模板的語法有沒有錯誤，然后編譯你的函數(shù)頭，之后代碼中使用模板時，就會把函數(shù)模板的代碼根據(jù)變量類型來編譯后并實例化，完成二次編譯。
出現(xiàn)這種問題的原因就是，兩次編譯的函數(shù)頭不一樣，因為友元函數(shù)并不屬于類的成員函數(shù)，所以需要單獨聲明此友元函數(shù)是函數(shù)模板，如果沒有聲明，但是后面在實現(xiàn)的時候又使用了template <class T>，就會導致錯誤的發(fā)生。所以需要額外使用template <class S>聲明。
加上<T>的目的是告訴編譯器當前函數(shù)需要使用函數(shù)模板并且參數(shù)類型使用當前模板類的參數(shù)類型。
到此這篇關于C++詳細講解模擬實現(xiàn)位圖和布隆過濾器的方法的文章就介紹到這了,更多相關C++模擬位圖內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++實現(xiàn)將輸入復制到輸出的方法,實例分析了C++字符串轉(zhuǎn)換及輸入輸出操作的相關技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
今天小編就為大家分享一篇關于C++標準模板庫vector的常用操作，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
C通過運行時堆棧支持遞歸函數(shù)的實現(xiàn)。遞歸函數(shù)就是直接或間接調(diào)用自身的函數(shù)2013-07-07
本篇文章是對C語言中段錯誤的問題進行了詳細的分析介紹，需要的朋友參考下2013-05-05
今天小編就為大家分享一篇C語言實現(xiàn)將字符和數(shù)字串到一起，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
這篇文章主要為大家詳細介紹了C語言實現(xiàn)五子棋人人對戰(zhàn)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-12-12
本文主要介紹了Qt實現(xiàn)線程與定時器的方法，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
這篇文章主要為大家詳細介紹了C語言實現(xiàn)導航功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
C語言中的strcpy函數(shù)，是一種C語言的標準庫函數(shù)，它用于對字符串進行復制。本章帶你了解它的使用并模擬實現(xiàn)它2022-05-05
這篇文章主要介紹了C語言 動態(tài)分配數(shù)組案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08