CODEWITHSUNDEEP
c++
Johan S
Johan S

Reputation: 3591

Custom implementation of a bool vector with bit representation - how to implement operator[]

Disclaimer - this is a school assignment, however the problem is still interesting I hope!

I have implemented a custom class called Vector<bool>, which stores the bool entries as bits in an array of numbers.

Everything has gone fine except for implementing this:

bool& operator[](std::size_t index) {
    validate_bounds(index);
    ???
}

The const implementation is quite straight forward, just reading out the value. Here however I can't really understand what to do, and the course is a specialization course on C++ so I'm guessing I should do some type-deffing or something. The data is represented by an array of type unsigned int and should be dynamic (e.g. push_back(bool value) should be implemented).

Upvotes: 0

Views: 121

Answers (2)

Johan S
Johan S

Reputation: 3591

I solved this implementing a proxy class:

class BoolVectorProxy {
public:
explicit BoolVectorProxy(unsigned int& reference, unsigned char index) {
  this->reference = &reference;
  this->index = index;
}

void operator=(const bool v) {
  if (v) *reference |= 1 << index;
  else *reference &= ~(1 << index);
}

operator bool() const {
    return (*reference >> index) & 1;
}

private:
    unsigned int* reference;
    unsigned char index;
};

And inside the main class:

BoolVectorProxy operator[](std::size_t index) {
    validate_bound(index);
    return BoolVectorProxy(array[index / BLOCK_CAPACITY], index % BLOCK_CAPACITY);
}

I also use Catch as a testing library, the code passes this test:

TEST_CASE("access and assignment with brackets", "[Vector]") {
    Vector<bool> a(10);
    a[0] = true;
    a[0] = false;
    REQUIRE(!a[0]);

    a[1] = true;
    REQUIRE(a[1]);

    const Vector<bool> &b = a;
    REQUIRE(!b[0]);
    REQUIRE(b[1]);

    a[0] = true;
    REQUIRE(a[0]);
    REQUIRE(b[0]);
    REQUIRE(b.size() == 10);

    REQUIRE_THROWS(a[-1]);
    REQUIRE_THROWS(a[10]);
    REQUIRE_THROWS(b[-1]);
    REQUIRE_THROWS(b[10]);
}

If anyone finds any issues or improvements that can be made, please comment, thanks!

Upvotes: 1

Cobrand
Cobrand

Reputation: 133

Basically implementing operator[] is the same as implementing const operator[] as you might expect, it's just that one is writable (lvalue) and the other is read only (rvalue).

I think you've got a understanding of the problem : you can convert an unsigned int into a bool using bitwise operations, and you can also say "if the nth bool is modified in X, do a bitwise operation with X and it's done !". But this operator means : I want a lvalue of the bool so I can modify it whenever I want and have an impact on the integer associated. It means that you want a reference of a bool, or in your case a reference of a single bit, so you can modify that bit on the fly. Unfortunately you can't reference a single bit, the smallest you can do is a whole byte (with char), so you would have to take a chunk of at least 7 other booleans with you. That's not what you want.

That being said, I understand that it might be for your assignment, but converting bools into multiple unsigned int is more like useless C optimization to me. You would be better with having a single array of bools (C-style), and doing the memory handling manually, because that is almost what you are doing. Plus with that method, you would actually be able to reference one single boolean (and be able to modify it) without touching the others. Is it mandatory that you have to use an array of unsigned int for this assignment ?

Upvotes: 0

Related Questions