Author: Daisuke Okanohara ([email protected])

Libarary of a collection of direct accessible vectors.

dag_vector

dag_vector is a direct accessible gamma code vector. dag_vector stores positive integers space-efficiently, and supports push_back() and fast random access.

comp_vector

comp_vector is a compressed vector for arbitrary objects. In comp_vector, each distinct object is assigned a unique positive value, and this value is stored by dag_vector. The object should support comparator (bool operator< (const object& ) const). If the frequency distribution of elements is skewed, comp_vector efficiently stores objects.

sparse_set

sparse_set is a space-efficient set for positive integers [0, 1, ...].

usage : dag_vector

include <dag/dag_vector.hpp>

dag::dag_vector dv;

// you can use dag_vector as vector // the working space is same as the gamma code. For an positive integer x, it requires 2log2(x+1) - 1 bits // For example, "0" requires 1 bits, "7" requires 5 bits, and 100 requires 13 bits.

dv.push_back(7); dv.push_back(1); dv.push_back(100); dv.push_back(0); dv.push_back(1000000000);

// All operations are const except push_back(); // To lookup dv[i], it requires O(log dv[i]) time.

assert(dv[0] == 7); assert(dv[1] == 1); assert(dv[2] == 100); assert(dv[3] == 0); assert(dv[4] == 1000000000);

// dag_vector supports prefix_sum() operation // dv.prefix_sum(i) returns dv[0] + dv[1] + ... + dv[i-1] in O(log max_val) time // where max_val = max(dv[0], dv[1], ...dv[i-1])

assert(dv.prefix_sum(0) == 0); assert(dv.prefix_sum(1) == 7); assert(dv.prefix_sum(2) == 8); assert(dv.prefix_sum(3) == 108); assert(dv.prefix_sum(4) == 108); assert(dv.prefix_sum(5) == 1000000108);

usage : comp_vector

include <dag/comp_vector.hpp>

dag::comp_vector cv;

cv.push_back(string("hoge")); cv.push_back(string("fuga")); cv.push_back(string("hoge")); cv.push_back(string("hoge")); cv.push_back(string("fuga"));

assert(cv[0] == "hoge"); assert(cv[1] == "fuga"); assert(cv[2] == "hoge"); assert(cv[3] == "hoge"); assert(cv[4] == "fuga");

Acknowledgement

I use criterion.h (https://github.com/tanakh/criterion) for performance test. Thanks tanakh.