- This sample implements a compact integer list using
SmartBitmap
.
- For example, a list or
std::set
can be used to create a set of IDs. The downsides of this approach include the relatively large memory footprint and the need for active memory management.
- Bit vectors can be used to store the data more compactly if the maximum ID value is known.
SmartBitmap
allows the addition of a small amount of data to a bit vector to count or search data efficiently.
class ItemList {
public:
static const size_t NUM_ITEM = 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(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;
for (int i = 0; i < 200; ++i) L.Set(i * 5);
L.Set(501);
return true;
}
NLIB_MAINFUNC