1

I am implementing a simple document indexer for information retrieval. Now I need to implement an incidence matrix, that should be able to be extended dynamically (not satisfied with just a static array or smth).

And to make boolean search possible I have to be able to perform bitwise operations on the rows of the matrix. However, I have not come up with a fast solution. The question is data structure for each row of the matrix.

If it were just a std::vector<bool>, is it possible to do FAST bitwise operations on it? Or is there any other data structure, like BitArray from C#, applicable in the situation?

Evg
  • 25,259
  • 5
  • 41
  • 83
Capy Maths
  • 79
  • 6
  • 1
    The `std::bitset` 'container' may be what you're looking for ... but I think we need more information, here. – Adrian Mole Feb 19 '23 at 20:12
  • 1
    How would I apply `std::bitset` to `std::vector`? Or how would I dynamically my incidence matrix? What way to store it? Bitset is not a dynamic container, so it surely cannot represent a row of a matrix. – Capy Maths Feb 19 '23 at 20:35

1 Answers1

1

If FAST is your goal, look into using largest int available on your system (likely - uint64_t) and do a simple bitwise operations on that. If your matrix is wider that 64 - use an std::array of those. Then check if your compiler generates SIMD instructions from your code. If not - consider using intrinsics https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#

Vlad Feinstein
  • 10,960
  • 1
  • 12
  • 27
  • But how do you suggest dynamic extending of `std::array` or `uint64_t`? The main goal is to avoid any kind of conversion to static things like you suggested and perform bitwise operations on dynamic containers, like C#-`BitArray`. The main goal is a C++ `BitArray` if that already exists. – Capy Maths Feb 19 '23 at 20:50
  • 1
    Obviously, if you don't know the width of your matrix - `std::array` won't work. Use `std::vector`. If you need other features of C#'s `BitArray` - you would need to implement it yourself. – Vlad Feinstein Feb 19 '23 at 21:20