Need 2-dimensional Bitarray
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: Need 2-dimensional Bitarray

  1. #1
    Join Date
    Jul 2001
    Posts
    293

    Need 2-dimensional Bitarray

    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

  2. #2
    Join Date
    May 2006
    Location
    Dresden, Germany
    Posts
    458

    Re: Need 2-dimensional Bitarray

    Quote Originally Posted by Ralf Schneider View Post
    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

  3. #3
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,290

    Re: Need 2-dimensional Bitarray

    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:

    Code:
    #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.
    Code:
    #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.
    Last edited by monarch_dodra; April 5th, 2012 at 04:48 AM. Reason: little errors
    Is your question related to IO?
    Read this C++ FAQ LITE article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  4. #4
    Join Date
    Jul 2001
    Posts
    293

    Re: Need 2-dimensional Bitarray

    Hello and thx.

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

  5. #5
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,012

    Re: Need 2-dimensional Bitarray

    Quote Originally Posted by Ralf Schneider View Post
    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.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  6. #6
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,290

    Re: Need 2-dimensional Bitarray

    Quote Originally Posted by Ralf Schneider View Post
    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.

    Is your question related to IO?
    Read this C++ FAQ LITE article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  7. #7
    Join Date
    Oct 2008
    Posts
    1,116

    Re: Need 2-dimensional Bitarray

    Quote Originally Posted by Ralf Schneider View Post
    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center