SmartBitmap
を用いてコンパクトな整数リストを実装するサンプルです。
- 例えば、何らかのIDの集合を持ちたい場合、リストや
std::set
の利用が考えられますが、それらは比較的メモリを消費することと動的なメモリ管理を要するという欠点があります。
- ここでIDの最大値が分かっていれば、ビットベクトルを用いることでとてもコンパクトにデータを格納することができます。
SmartBitmap
はビットベクトルに対して少量のデータを付加することでデータの数え上げや検索を効率よく行うことができるようにしています。
class ItemList {
public:
static const size_t kNumItem = 1024;
int GetNextItem(uint32_t n) const {
return bitmap_.
Select1(bitmap_.Rank1(n));
}
int GetPrevItem(uint32_t n) const {
unsigned int r = bitmap_.Rank1(n);
if (r == 0) return -1;
return bitmap_.Select1(r - 1);
}
size_t GetNumItems() const { return bitmap_.Rank1(kNumItem); }
bool Find(uint32_t n) const { return bitmap_.Has(n); }
int FindNth(uint32_t nth) const { return bitmap_.Select1(nth); }
void Set(uint32_t n) { bitmap_.Set(n); }
void Unset(uint32_t n) { bitmap_.Unset(n); }
private:
SmartBitmap<kNumItem> bitmap_;
};
bool SampleMain(int, char**) {
ItemList item_list;
for (int i = 0; i < 200; ++i) item_list.Set(i * 5);
nlib_printf(
"50th value is %d\n", item_list.FindNth(50 - 1));
nlib_printf(
"next(500) is %d\n", item_list.GetNextItem(500));
item_list.Set(501);
nlib_printf(
"next(500) is %d\n", item_list.GetNextItem(500));
return true;
}
NLIB_MAINFUNC