Example of how to use bm::str_sparse_vector<> - succinct container for sorted bit-transposed collection of integers
#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <random>
#include <algorithm>
#include <stdexcept>
using namespace std;
static
{
const unsigned max_coll = 50000;
vec.resize(0);
for (unsigned i = 10; i < max_coll; i += rand() % 3)
{
vec.emplace_back(i);
}
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(vec.begin(), vec.end(), g);
}
static
{
for (const unsigned u : vec)
{
bool found = scanner.
bfind(sv, u, pos);
(void)found;
}
}
{
try
{
vector<unsigned> vec;
std::sort(vec.begin(), vec.end());
{
vector<unsigned>::const_iterator vit = vec.begin();
for (; it != it_end; ++it, ++vit)
{
unsigned u = *it;
if (*vit != u)
{
cerr << "Mismatch at:" << u << "!=" << *vit << endl;
return 1;
}
}
}
cout << "Sort validation Ok." << endl;
}
catch(std::exception& ex)
{
std::cerr << ex.what() << std::endl;
return 1;
}
return 0;
}
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
Algorithms for bm::sparse_vector.
pre-processor un-defines to avoid global space pollution (internal)
algorithms for sparse_vector scan/search
bool bfind(const SV &sv, const value_type val, size_type &pos)
binary search for position in the sorted sparse vector
succinct sparse vector with runtime compression using bit-slicing / transposition method
bvector_type::size_type size_type
const_iterator end() const BMNOEXCEPT
Provide const iterator access to the end
void insert(size_type idx, value_type v)
insert specified element into container
const_iterator begin() const BMNOEXCEPT
Provide const iterator access to container content
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename sparse_vector< Val, BV >::statistics *stat=0)
run memory optimization for all vector planes
static void insertion_sort(sparse_vector_u32 &sv, const vector< unsigned > &vec)
bm::sparse_vector< bm::id_t, bm::bvector<> > sparse_vector_u32
static void generate_set(vector< unsigned > &vec)