Search/scan for elements in unordered, non-unique sparse vector

See also
Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
See the License for the specific language governing permissions and
limitations under the License.
For more information please visit:
/** \example svsample06.cpp
Search/scan for elements in unordered, non-unique sparse vector
\sa bm::sparse_vector<>::const_iterator
\sa bm::sparse_vector<>::back_insert_iterator
\sa bm::sparse_vector_scanner
/*! \file svsample06.cpp
\brief Example: sparse_vector<> scan search (non-ordered set functionality)
#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <random>
#include <stdexcept>
#include "bm.h"
#include "bmsparsevec.h"
#include "bmtimer.h"
#include "bmundef.h" /* clear the pre-proc defines from BM */
using namespace std;
// ----------------------------------------------------
// Global parameters and types
// ----------------------------------------------------
const unsigned value_max = 1250000; // range of variants of events [0..max]
const unsigned test_size = 250000000; // vector size to generate
// -------------------------------------------
// Random generator
// -------------------------------------------
std::random_device rand_dev;
std::mt19937 gen(rand_dev());
std::uniform_int_distribution<> rand_dis(1, value_max); // generate uniform numebrs for [1, vector_max]
// timing storage for benchmarking
// Function to generate test vector set with some NULL values stored as a
// separate bit-bector
void generate_test_set(std::vector<unsigned>& vect,
bm::bvector<>& bv_null,
// back insert iterator is faster than random element access for sparse vector
for (unsigned i = 0; i < test_size; ++i)
unsigned v = unsigned(rand_dis(gen));
vect[i] = v;
bv_null[i] = true; // not NULL(assigned) element
*bi = v; // push back an element to sparse vector
if (i % 64 == 0)
bi.add_null(5); // add 5 unassigned elements using back inserter
i += 5; // insert a small NULL plate (unassigned values)
} // for
// plain scan in std::vector<>, matching values are indexed
// in result bit-vector (subset projection)
// values are added, so multiple calls result in subset addition
void vector_search(const std::vector<unsigned>& vect,
const bm::bvector<>& bv_null,
unsigned value,
bm::bvector<>& bv_res)
bv_res.init(); // always use init() if set_bit_no_check()
for (size_t i = 0; i < vect.size(); ++i)
if (vect[i] == value)
} // for
bv_res &= bv_null; // correct results to only include non-NULL values
cout << "( count = " << bv.count() << ")" << ": [";
for (; en.valid(); ++en)
cout << *en << ", ";
cout << "]" << endl;
int main(void)
// First, lets run, simple (printable) search case
sv.set(2, 25);
sv.set(3, 35);
sv.set(7, 75);
sv.set(1000, 2000);
sv.set(256, 2001);
sv.set(77, 25);
bm::bvector<> bv_found; // search results vector
scanner.find_eq(sv, 25, bv_found); // seach for all values == 25
print_bvector(bv_found); // print results
scanner.invert(sv, bv_found); // invert search results to NOT EQ
print_bvector(bv_found); // print all != 25
std::vector<unsigned> vect;
bm::bvector<> bv_null;
bm::chrono_taker tt1("0. test set generate ", 1, &timing_map);
generate_test_set(vect, bv_null, sv);
unsigned search_repeats = 500;
// generate a search vector for benchmarking
std::vector<unsigned> search_vect;
bm::bvector<> bv_tmp;
for (unsigned i = 0; i < search_repeats;)
if (!bv_tmp.test(idx)) // check if number is unique
bv_tmp[idx] = 1;
// run benchmarks
bm::bvector<> bv_res1;
bm::bvector<> bv_res2;
bm::bvector<> bv_res3;
bm::chrono_taker tt1("1. std::vector<> scan ", search_repeats, &timing_map);
for (unsigned i = 0; i < search_repeats; ++i)
unsigned vs = search_vect[i];
vector_search(vect, bv_null, vs, bv_res1);
} // for
bm::chrono_taker tt1("2. sparse_vector<> scan ", search_repeats, &timing_map);
scanner.find_eq(sv, search_vect.begin(), search_vect.end(), bv_res2);
// check jus in case if results look correct
if ( != 0)
std::cerr << "2. Search result mismatch!" << std::endl;
bv_res3.init(); // always init before calling "set_bit_no_check()"
bm::chrono_taker tt1("3. sparse_vector<>::const_iterator search ", search_repeats, &timing_map);
// prepare a unique search set
bm::combine_or(bv_search, search_vect.begin(), search_vect.end());
for (; it != it_end; ++it)
unsigned v = *it;
if (bv_search.test(v))
} // for
// paranoiya check
if ( != 0)
std::cerr << "3. Search result mismatch!" << std::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.
Timing utilities for benchmarking (internal)
pre-processor un-defines to avoid global space pollution (internal)
Constant iterator designed to enumerate "ON" bits.
Definition: bm.h:602
bool valid() const BMNOEXCEPT
Checks if iterator is still valid.
Definition: bm.h:282
Bitvector Bit-vector container with runtime compression of bits.
Definition: bm.h:114
bool test(size_type n) const BMNOEXCEPT
returns true if bit n is set and false is bit n is 0.
Definition: bm.h:1477
size_type count() const BMNOEXCEPT
population count (count of ON bits)
Definition: bm.h:2262
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition: bm.h:1819
void init()
Explicit post-construction initialization.
Definition: bm.h:2191
bvector< Alloc > & reset()
Clears every bit in the bitvector.
Definition: bm.h:1242
int compare(const bvector< Alloc > &bvect) const BMNOEXCEPT
Lexicographical comparison with a bitvector.
Definition: bm.h:3238
void set_bit_no_check(size_type n)
Set bit without checking preconditions (size, etc)
Definition: bm.h:3644
Utility class to collect performance measurements and statistics.
Definition: bmtimer.h:40
static void print_duration_map(const duration_map_type &dmap, format fmt=ct_time)
Definition: bmtimer.h:146
std::map< std::string, statistics > duration_map_type
test name to duration map
Definition: bmtimer.h:65
algorithms for sparse_vector scan/search
void invert(const SV &sv, typename SV::bvector_type &bv_out)
invert search result ("EQ" to "not EQ")
void find_eq(const SV &sv, typename SV::value_type value, typename SV::bvector_type &bv_out)
find all sparse vector elements EQ to search value
succinct sparse vector with runtime compression using bit transposition method
Definition: bmsparsevec.h:82
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
Definition: bmsparsevec.h:1517
const_iterator end() const BMNOEXCEPT
Provide const iterator access to the end
Definition: bmsparsevec.h:483
back_insert_iterator get_back_inserter()
Provide back insert iterator Back insert iterator implements buffered insertion, which is faster,...
Definition: bmsparsevec.h:496
const_iterator begin() const BMNOEXCEPT
Provide const iterator access to container content
Definition: bmsparsevec.h:1959
@ use_null
support "non-assigned" or "NULL" logic
Definition: bmconst.h:215
GAP compression is ON.
Definition: bmconst.h:144
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1016
unsigned int id_t
Definition: bmconst.h:37
const unsigned test_size
Definition: svsample06.cpp:54
std::random_device rand_dev
Definition: svsample06.cpp:60
bm::sparse_vector< bm::id_t, bm::bvector<> > sparse_vector_u32
Definition: svsample06.cpp:46
static void vector_search(const std::vector< unsigned > &vect, const bm::bvector<> &bv_null, unsigned value, bm::bvector<> &bv_res)
Definition: svsample06.cpp:106
bm::chrono_taker::duration_map_type timing_map
Definition: svsample06.cpp:65
int main(void)
Definition: svsample06.cpp:133
void print_bvector(const bm::bvector<> &bv)
Definition: svsample06.cpp:122
std::mt19937 gen(rand_dev())
const unsigned value_max
Definition: svsample06.cpp:53
std::uniform_int_distribution rand_dis(1, value_max)
static void generate_test_set(std::vector< unsigned > &vect, bm::bvector<> &bv_null, sparse_vector_u32 &sv)
Definition: svsample06.cpp:73