2 dimensional bitset and square bracket operator

Question

For a personal project I need to use a 2D bitset. Conducted a lot of googling and found a really great post with very useful code, https://forums.codeguru.com/showthread.php?522711-Need-2-dimensional-Bitarray. Take a look at the answer by monarch_dodra.

At the end of if there is a following statement

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.

I can't figure out what the author is talking about? How do I implement this proxy object? I would appreciate any help with it.

Since you can't return a pointer or reference to an individual bit, you would have to return an object pointing at the byte in which the bit is and also an index that tells _which_ bit it is "pointing" at. You'd also need to implement operators to make it _act_ like it's "the real thing". For ease in implementing this and also for performance, I suggest `operator()(size_t, size_t)` just like the author of the post did. — Ted Lyngmo, Apr 16 '21 at 21:59
There is no `operator[][]` in C++. If you want such behaviour in a `Matrix`, you need to implement `operator[]` which returns some other class (say, `Row` or `Column`), which also has overloaded `operator[]`. This `Row` is a proxy. — Yksisarvinen, Apr 16 '21 at 22:01
My suggestion is note the level of scorn being heaped on the `[i][j]` notation and the extra work it causes and avoid it. Where possible, stick to the call operator and use `(i,j)`. — user4581301, Apr 16 '21 at 22:01

score 1 · Answer 1 · 2021-06-17T15:07:23.763

Imagine a class Matrix that looked like this:

template<int rows, int columns, class T>
class Matrix {

    template <int r, class T>
    class Columns{
        T _rows[r];
    public:
        T operator[](int index) {
            return _rows[index];
        }
    };

    Columns<rows, T> _Matrix_Columns[columns];

    public:

    Columns<rows, T> operator[](int index) {
        return _Matrix_Columns[index];
    }
};

And a person using this Matrix like this:

int main() {
    Matrix<5, 5, char> M;
    char ch = M[1][1]; 
}

The code in main() could actually be written as:

int main() {
    Matrix<5, 5, char> M;
    char ch = M.operator[](1).operator[](1);
}

The Matrix operator[] returns the proxy object Column, which has it's own operator[], which returns our char.

Note: The Matrix is for educational purposes, it doesn't actually work.

score 1 · Answer 2 · answered Apr 16 '21 at 23:07

How do I implement this proxy object?

You construct the proxy object with custom semantics (usually overloaded operators) and return it from operator[] of the parent object. Below I present an example, with even two proxy objects - first operator[] returns a Bitset::Byte, then Bitset::Byte::operator[] returns Bitset::Bit. The cool think is, Bitset::Bit has special operator= that allows to "just set" it's value.

#include <iostream>
#include <cstddef>
#include <climits>
#include <array>
#include <cassert>
#include <iomanip>

template<size_t N>
struct Bitset {
    std::array<unsigned char, N> mem{};
    struct Bit {
        unsigned char& byte;
        unsigned mask;
        Bit(unsigned char &byte, unsigned idx) :
            byte(byte), mask(1 << idx) {}
        operator unsigned () {
            return (byte & mask) ? 1 : 0;
        }
        Bit& operator=(unsigned v) {
            if (v) {
                byte |= mask;
            } else {
                byte &= mask;
            }
            return *this;
        }
    };
    struct Byte {
        unsigned char& byte;
        Bit operator[](unsigned idx) {
            return {byte, idx};
        }
        operator unsigned () {
            return byte;
        }
    };
    Byte operator[](unsigned idx) {
        return { mem.at(idx) };
    }
};


int main() {
    Bitset<20> a;
    std::cout << "a[1][3] = " << a[1][3] << "\n";
    // let's set 2nd byte 4th bit
    a[1][3] = 1; // yay!
    std::cout << "a[1] = 0x" << std::hex << std::setw(2) << std::setfill('0') <<  a[1] << "\n";
    std::cout << "a[1][3] = " << a[1][3] << "\n";
}

which outputs:

a[1][3] = 0
a[1] = 0x08
a[1][3] = 1

Doing a[1][3] = something is great and amazing functionality, it's clear and precise. But it's way more writing then just providing a function in parent object:

#include <iostream>
#include <cstddef>
#include <climits>
#include <array>
#include <cassert>
#include <iomanip>

template<size_t N>
struct Bitset {
    std::array<unsigned char, N> mem{};
    unsigned char& operator()(size_t n) {
        return mem.at(n);
    }
    void set(size_t n, size_t idx, unsigned v) {
        if (v) {
            mem.at(n) |= 1 << idx;
        } else {
            mem.at(n) &= 1 << idx;
        }
    }
    unsigned operator()(size_t n, size_t idx) {
        return (mem.at(n) & 1 << idx) ? 1 : 0;
    }
};


int main() {
    Bitset<20> a;
    std::cout << "a[1][3] = " << a(1, 3) << "\n";\
    // let's set 2nd byte 4th bit
    // a(1, 3) = 1; // ugh, not possible
    a.set(1, 3, 1);
    std::cout << "a[1] = 0x" << std::hex << std::setw(2) << std::setfill('0') << (unsigned)a(1) << "\n";
    std::cout << "a[1][3] = " << a(1, 3) << "\n";
}

2 dimensional bitset and square bracket operator

2 Answers2