ProblemsMemory ManagementA reference to a single bit
IntermediateMemory Management

A reference to a single bit

Context

A million flags in bool[] is a megabyte; packed into bits it is 128 KB. std::vector<bool> does exactly this — and that is why its operator[] returns not bool& but a special proxy object. Now you write the same thing and find out how a[i] = true works when bit i has no address of its own.

Task

BitSet packs bits into bytes — eight times less memory than bool[]. The catch: operator[] cannot return bool&, a single bit has no address. Implement a proxy object: reading converts it to bool, writing sets the bit. The goal is for a[i] = true to just work.

Constraints

  • Storage stays packed (the byte array is given) — no bool arrays on the side
  • a[i] = true / a[i] = false sets the bit; reading a[i] in a bool context returns it
  • Assignments chain: a[0] = a[1] = true
  • The const overload of operator[] returns plain bool

Before you code

  • Why can operator[] not return bool& here?
  • What two things must the proxy remember to find its bit?
  • Why does std::vector<bool> surprise people in generic code?

Tests

  • #1Set and read individual bits
  • #2Assignments chain
  • #3A const BitSet can be read

Hints

Hint 1

The proxy needs a pointer to the byte and a mask of the bit inside it. Assignment ORs or ANDs the byte; reading ANDs and compares.

Hint 2

Two members make it behave like a reference: operator=(bool) for writes and operator bool() for reads. For chaining, operator= returns Ref&.

Editorbitset-proxy-reference.cpp
Results

Hit Submit (or ⌘/Ctrl + ↵) — test results will show up here.