Search/scan for elements in unordered, non-unique sparse vector
- See also
- bm::sparse_vector<>::const_iterator
-
bm::sparse_vector<>::back_insert_iterator
-
bm::sparse_vector_scanner
#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <random>
#include <stdexcept>
using namespace std;
static
{
{
vect[i] = v;
bv_null[i] = true;
*bi = v;
if (i % 64 == 0)
{
bi.add_null(5);
i += 5;
}
}
}
static
unsigned value,
{
for (size_t i = 0; i < vect.size(); ++i)
{
if (vect[i] == value)
}
bv_res &= bv_null;
}
inline
{
cout <<
"( count = " << bv.
count() <<
")" <<
": [";
cout << *en << ", ";
cout << "]" << endl;
}
{
try
{
{
}
std::vector<unsigned> vect;
{
}
unsigned search_repeats = 500;
std::vector<unsigned> search_vect;
{
search_vect.reserve(search_repeats);
for (unsigned i = 0; i < search_repeats;)
{
{
search_vect.push_back(idx);
bv_tmp[idx] = 1;
++i;
}
}
}
{
for (unsigned i = 0; i < search_repeats; ++i)
{
unsigned vs = search_vect[i];
}
}
{
scanner.
find_eq(sv, search_vect.begin(), search_vect.end(), bv_res2);
}
{
std::cerr << "2. Search result mismatch!" << std::endl;
}
{
for (; it != it_end; ++it)
{
unsigned v = *it;
if (bv_search.test(v))
{
}
}
}
{
std::cerr << "3. Search result mismatch!" << std::endl;
}
}
catch(std::exception& ex)
{
std::cerr << ex.what() << std::endl;
return 1;
}
return 0;
}
static void generate_test_set(std::vector< unsigned > &vect, bm::bvector<> &bv_null, sparse_vector_u32 &sv)
void invert(const SV &sv, typename SV::bvector_type &bv_out)
invert search result ("EQ" to "not EQ")
Algorithms for sparse_vector<>
friend back_insert_iterator
bool valid() const
Checks if iterator is still valid. Analog of != 0 comparison for pointers.
size_type count() const
population cout (count of ON bits)
sparse vector with runtime compression using bit transposition method
Utility class to collect performance measurements and statistics.
bvector< Alloc > & reset()
Clears every bit in the bitvector.
bm::chrono_taker::duration_map_type timing_map
void set_bit_no_check(size_type n)
Set bit without checking preconditions (size, etc)
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
Constant iterator designed to enumerate "ON" bits.
algorithms for sparse_vector scan/seach
int compare(const bvector< Alloc > &bvect) const
Lexicographical comparison with a bitvector.
void print_bvector(const bm::bvector<> &bv)
@ use_null
support "non-assigned" or "NULL" logic
static void vector_search(const std::vector< unsigned > &vect, const bm::bvector<> &bv_null, unsigned value, bm::bvector<> &bv_res)
bool test(size_type n) const
returns true if bit n is set and false is bit n is 0.
const_iterator end() const
Provide const iterator access to the end
void init()
Explicit post-construction initialization.
Timing utilities for benchmarking (internal)
bm::sparse_vector< bm::id_t, bm::bvector<> > sparse_vector_u32
@ BM_GAP
GAP compression is ON.
const_iterator begin() const
Provide const iterator access to container content
std::mt19937 gen(rand_dev())
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
std::uniform_int_distribution rand_dis(1, value_max)
std::map< std::string, statistics > duration_map_type
test name to duration map
back_insert_iterator get_back_inserter()
Provide back insert iterator Back insert iterator implements buffered insertion, which is faster,...
static void print_duration_map(const duration_map_type &dmap, format fmt=ct_time)
std::random_device rand_dev
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
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