nlib
succinct/bitvector/bitvector.cpp
SmartBitmapを用いてコンパクトな整数リストを実装するサンプルです。
例えば、何らかのIDの集合を持ちたい場合、リストやstd::setの利用が考えられますが、それらは比較的メモリを消費することと動的なメモリ管理を要するという欠点があります。
ここでIDの最大値が分かっていれば、ビットベクトルを用いることでとてもコンパクトにデータを格納することができます。 SmartBitmapはビットベクトルに対して少量のデータを付加することでデータの数え上げや検索を効率よく行うことができるようにしています。
// Implements a list(set) of integers by SmartBitmap
class ItemList {
public:
static const size_t NUM_ITEM = 1024;
int GetNextItem(uint32_t n) const {
// Rank1(n) computes the count of '1' bits in [0, n].
// Select1(r) computes the index for the (r + 1)th '1' bit.
// you can compute the place of the net '1' bit.
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(NUM_ITEM); }
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<NUM_ITEM> bitmap_;
};
bool SampleMain(int, char**) {
ItemList L;
// Set 0, 5, 10, 15, 20, ....., 995
for (int i = 0; i < 200; ++i) L.Set(i * 5);
// The size of SmartBitmap<NUM_ITEM> would be about (NUM_ITEM * 1.4 / 8) bytes.
// It is smaller than array or list.
nlib_printf("sizeof NumList: %" PRIuS "\n", sizeof(L));
// Gets the count of the numbers 'L' has. The time complexity is O(1).
nlib_printf(" %" PRIuS "\n", L.GetNumItems());
// Retrieves the 50th smallest value. The time complexity is Log(NUM_ITEM).
nlib_printf("50th value is %d\n", L.FindNth(50 - 1));
// The next value of 500 is 505.
nlib_printf("next(500) is %d\n", L.GetNextItem(500));
// Inserts 501 into L. The time complexity is O(1).
L.Set(501);
nlib_printf("501 inserted\n");
// The next value of 500 is 505 now.
nlib_printf("next(500) is %d\n", L.GetNextItem(500));
return true;
}
NLIB_MAINFUNC