Need 2-dimensional Bitarray

[Ralf Schneider]

Hello,

I do need a bitarray like this: Bitarray Bit[1000,500].

Do someone knows a class that implements that?
I do only need direct access to the bits to set and get a bit.
I do not want to use BOOL because that need factor 8 memory consumption.

thx.

Ralf

[ProgramArtist]

Hello,

I do need a bitarray like this: Bitarray Bit[1000,500].

Do someone knows a class that implements that?
I do only need direct access to the bits to set and get a bit.
I do not want to use BOOL because that need factor 8 memory consumption.

thx.

Ralf

First: what you wrote is not c++.

A two dimensional array is either an array to an array or maybe declared as <type> arr_foo[n][m];.

Static sized bit array: http://www.sgi.com/tech/stl/bitset.html

Dynamic bit array: http://www.boost.org/doc/libs/1_49_0...ic_bitset.html

With regards
PA

[monarch_dodra]

If you do not need the second dimension bits in contiguous memory, then an "std::vector<std::bitset<500>> my_bits(1000)" should fit the bill.

If you need everything in contiguous memory, or would like to wrap everything inside a strong type, just do the good old wrapper approach:

#include <bitset>

template <size_t M, size_t N>
class bitset2D
{
public:
  //typedefs
  typedef typename std::bitset<M*N>::reference reference;

  //bitset::bitset
  //See http://www.cplusplus.com/reference/stl/bitset/bitset/
  bitset2D() : m_bits(){}

  //bitset operators
  //See http://www.cplusplus.com/reference/stl/bitset/operators/

  //Bit access
  bool operator()(size_t m, size_t n) const {return m_bits[m*N + n];}
  reference operator()(size_t m, size_t n) {return m_bits[m*N + n];}

  //Bit operations:
  bitset2D<M, N>& reset() {m_bits.reset(); return *this;}
  bitset2D<M, N>& reset(size_t m, size_t n) {m_bits.reset(m*N + n); return *this;}
  bitset2D<M, N>& flip() {m_bits.flip(); return *this;}
  bitset2D<M, N>& flip(size_t m, size_t n) {m_bits.flip(m*N + n); return *this;}
  bitset2D<M, N>& set() {m_bits.set(); return *this;}
  bitset2D<M, N>& set(size_t m, size_t n, bool val = true) {m_bits.set(m*N + n, val); return *this;}

  //Bitset operations:
  unsigned long to_ulong() const {return m_bits.to_ulong();}
  template <class charT, class traits, class Allocator>
  std::basic_string<charT,traits,Allocator> to_string() const {m_bits.to_string<charT, traits, Allocator>(); return *this;}
  unsigned long count() const {return m_bits.count();}
  unsigned long size() const {return m_bits.size();}
  unsigned long test(size_t m, size_t n) const {m_bits.test(m*N + n); return *this;}
  unsigned long any() const {return m_bits.any();}
  unsigned long none() const {return m_bits.none();}

private:
  std::bitset<M*N> m_bits;
};

This wraps most of bitset into a 2D class. I didn't do all the constructors, or any of the operators (because I'm not going to do everything myself).

Here is some example usage.

#include <iostream>
#include "bitset2D.h"

int main()
{
  bitset2D<1000,500> a;
  std::cout << a(1,1) << std::endl;
}

I used "a(1,1)" instead of "a[1][1]". Long story short, it is a mostly better approach. If you MUST have the a[1][1] syntax, then I recommend writing an operator[j] which returns a proxy object, itself having an operator[i] which just forwards back to (j, i). YOu can then move operator()(i, j) to protected, if you want.

[Ralf Schneider]

Hello and thx.

it looks rather complex.
I thought there will be an easier solution because I do not need all functions....

[D_Drmmr]

Hello and thx.

it looks rather complex.
I thought there will be an easier solution because I do not need all functions....

Then don't implement them. Just write a wrapper that has a getbit and setbit function.

[monarch_dodra]

it looks rather complex.
I thought there will be an easier solution because I do not need all functions....

Are you kidding me? You have an entire 2D bitset class, with all the requirements you ask for, in less than 30 lines of code, and it is "too complex"? How much simpler do you think it can get?

As for those "functions you don't need": Just don't use them. I already implemented them for you anyways. Just because you aren't going to use them now, doesn't mean you won't use them later, or somebody else reading this thread won't.

[superbonzo]

it looks rather complex.
I thought there will be an easier solution because I do not need all functions....

if you just need a "working" solution then any c-array with a bit of pointer arithmetic and bit-twiddling will do.

The problem is when you want to equip a bit set with the same rich interface of other STL containers, enabling the same well-proven usage patterns and algorithm support. More specifically, your goal should be to decouple as much as possible your data structure from the algorithm that will act on.

Unfortunately, this is impossible for single bits because objects in C++ have always size >=1 bytes; for this reason, any abstraction exposing a mutable bit sequence will either use 1-byte sized "bits" or return proxy references that in turn are unsuitable for generic algorithms.

So, if you really cannot afford the size overhead ( do you ? ) an alternative solution to proxy based pseudo containers could be to use any container you like ( array, std::vector, a matrix type from your preferred matrix library, etc... ) with each item made of a binary block: a char = 8 consecutive bits in 1D, a char[2] = a block of 4x4 bits in 2D, a char = a block of 2x2x2 bits in 3D ( or two 2D slices ) etc ...

in this way, an algorithm would split into two parts: one acting over the sequence ( using your preferred N-dimensional container interface ) and one acting over the fixed ( and finite ) elementary binary block.