std::bitset and the std::vector<bool> trap

A hundred million yes-or-no flags take 12.5 MB as bits and 100 MB as bytes, and with bits a single shift and or can update 64 of them at once. std::bitset<N> is a fixed-size array of N bits with the bitwise operators built in: set, clear and test one bit, count the 1s, and combine two bitsets with &, |, ^, ~, << and >>, each working on a whole machine word at a time. N is part of the type, fixed when the program is compiled.

std::vector<bool> is the run-time-sized alternative, and it is a trap. It packs its bits too, and because a bit has no address of its own, its operator[] returns a small proxy objectproxy object: An object returned in place of a reference, standing for an element that cannot be referred to directly, as std::vector<bool>::reference stands for one bit. It points into its container and is valid only while the container lives. More in “C++ auto, decltype and type aliases” instead of a bool&: bool& r = v[0]; does not compile, auto b = v[0]; keeps a link to the vector, and two threads that write different elements can race. You will step through both on Apple clang 21 and GCC 16, time the whole-word operations, and pick a container for each kind of flag.

A bitset<12> holds 12 seats, and its text puts seat 0 last

One row of 12 cinema seats makes a good bitset: bit i is seat i, and a 1 means the seat is booked.

// One row of 12 cinema seats as a std::bitset<12>: bit i is seat i, and 1 means booked.
#include <bit>
#include <bitset>
#include <print>
#include <stdexcept>

int main() {
    std::bitset<12> booked;          // all 12 bits start at 0
    booked.set(0);
    booked.set(3);
    booked.set(4);
    booked[7] = true;                // operator[] returns a proxy you can assign through
    std::println("booked:  {}  {} of {} seats", booked.to_string(), booked.count(), booked.size());

    const std::bitset<12> aisle("100000000001");   // the text runs from seat 11 down to seat 0
    const std::bitset<12> free_seats = ~booked;
    std::println("aisle:   {}  seat 0 is on the aisle: {}", aisle.to_string(), aisle.test(0));
    std::println("free:    {}", free_seats.to_string());
    std::println("free aisle seats: {}", (free_seats & aisle).count());
    std::println("first free seat: {}", std::countr_zero(free_seats.to_ullong()));   // only for N <= 64

    booked |= std::bitset<12>(0b0000'0110'0000);   // book seats 5 and 6 in one operation
    std::println("booked:  {}  any free: {}", booked.to_string(), !booked.all());

    try {
        [[maybe_unused]] bool taken = booked.test(12);   // test() checks the position and throws
    } catch (const std::out_of_range&) {
        std::println("test(12) threw std::out_of_range");
    }
}

Its session compiles the program with Apple clang and with GCC and then runs each build; lines after a $ are commands, the rest is their output. The track’s first lesson explains how to repeat a session on your own computer:

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra seats.cpp -o seats && ./seats
g++-16 -std=c++23 -Wall -Wextra seats.cpp -o seats && ./seats
""")

$ clang++ -std=c++23 -Wall -Wextra seats.cpp -o seats && ./seats
booked:  000010011001  4 of 12 seats
aisle:   100000000001  seat 0 is on the aisle: true
free:    111101100110
free aisle seats: 1
first free seat: 1
booked:  000011111001  any free: true
test(12) threw std::out_of_range
$ g++-16 -std=c++23 -Wall -Wextra seats.cpp -o seats && ./seats
booked:  000010011001  4 of 12 seats
aisle:   100000000001  seat 0 is on the aisle: true
free:    111101100110
free aisle seats: 1
first free seat: 1
booked:  000011111001  any free: true
test(12) threw std::out_of_range

The members do what their names say: set, reset and flip change one bit or, without an argument, all of them; test reads one; count counts the 1 bits; all, any and none answer the obvious questions about the whole set; size returns N. Step through the program’s operations on the seats, each bit string as to_string() prints it:

Four details explain the rest of the output:

• The text runs backwards. to_string() writes bit N - 1 first and bit 0 last, the way numbers are written, so seat 0 is the rightmost character. The string constructor reads the same way: in "100000000001" the last character is bit 0. The standard says so in the constructor’s wording: the last character of the string corresponds to bit position zero.
• test checks, [] does not. test(12) on a 12-bit set throws std::out_of_range. operator[] has a precondition instead: an index outside the set is undefined behaviour, and in C++26 a hardened precondition that a hardened library checks (P3471R4).
• Whole-set operations need the same N. free_seats & aisle combines two std::bitset<12>; a bitset<12> and a bitset<16> do not mix.
• There is no “find the first set bit”. For N up to 64, convert with to_ullong() and use std::countr_zero from <bit>, as the program does with the free seats. libstdc++ offers _Find_first() and _Find_next(), but they are extensions of that library, so code that uses them does not build with libc++.

operator[] on a non-const bitset returns std::bitset<N>::reference, a proxy object that knows its bitset and the bit’s position, which is how booked[7] = true can change a single bit. Keep that word, proxy, in mind: it is the whole story of std::vector<bool> below.

A flag costs a bit in a bitset or a vector<bool>, and a byte in a vector<char>

A bitset stores its bits in whole machine words, and std::vector<bool> packs its bits the same way, while a std::vector<char> spends a byte on every flag:

// The memory behind a hundred million flags, and the size of a few bitsets.
#include <bitset>
#include <cstddef>
#include <print>
#include <vector>

int main() {
    constexpr std::size_t n = 100'000'000;
    const std::vector<bool> packed(n);   // capacity() counts bits
    const std::vector<char> bytes(n);    // capacity() counts chars, one byte each
    std::println("vector<bool>: {:>11} bytes for {} flags", packed.capacity() / 8, packed.size());
    std::println("vector<char>: {:>11} bytes for {} flags", bytes.capacity(), bytes.size());
    std::println("bitset<n>:    {:>11} bytes, wherever it lives", sizeof(std::bitset<n>));
    std::println("sizeof bitset<1>: {}, <64>: {}, <65>: {}, <1000>: {}", sizeof(std::bitset<1>), sizeof(std::bitset<64>),
                 sizeof(std::bitset<65>), sizeof(std::bitset<1000>));
}

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra memory.cpp -o memory && ./memory
g++-16 -std=c++23 -Wall -Wextra memory.cpp -o memory && ./memory
# The stack limit of this shell, in kilobytes: a local bitset<100000000> would not fit
ulimit -s
""")

$ clang++ -std=c++23 -Wall -Wextra memory.cpp -o memory && ./memory
vector<bool>:    12500000 bytes for 100000000 flags
vector<char>:   100000000 bytes for 100000000 flags
bitset<n>:       12500000 bytes, wherever it lives
sizeof bitset<1>: 8, <64>: 8, <65>: 16, <1000>: 128
$ g++-16 -std=c++23 -Wall -Wextra memory.cpp -o memory && ./memory
vector<bool>:    12500000 bytes for 100000000 flags
vector<char>:   100000000 bytes for 100000000 flags
bitset<n>:       12500000 bytes, wherever it lives
sizeof bitset<1>: 8, <64>: 8, <65>: 16, <1000>: 128
# The stack limit of this shell, in kilobytes: a local bitset<100000000> would not fit
$ ulimit -s
8176

A hundred million flags take 12.5 MB as bits and 100 MB as bytes, eight times more, on both libraries. The sizes of the small bitsets show the other side: storage is a whole number of 64-bit words, so even std::bitset<1> takes 8 bytes, std::bitset<65> takes 16 and std::bitset<1000> takes 128. A bitset lives wherever you declare it, and a std::bitset<100000000> declared as a local variable needs 12.5 MB of stack, more than the 8,176 KB (about 8 MB) the shell’s ulimit -s allowed here, so the program would crash. Make large bitsets static, a global, or put them on the heap with std::make_unique<std::bitset<N>>(), as the exercise at the end does.

One shift and one or update 64 totals at a time

The bitset operators work on whole words, so one instruction updates 64 bits: this is bit parallelismbit parallelism: Working on many flags at once by packing them into machine words, so that one bitwise instruction, such as a shift or an or, updates 64 of them. reach |= reach << w updates every total of a subset-sum problem this way.. Problems that update a large set of flags in the same way at once can use it directly. A classic one is subset sum: given some weights, which totals can a subset of them make? Keep a bit for every total, starting with only total 0 set (the empty subset). For each weight w, every total t that is reachable makes t + w reachable too, and reach << w moves every reachable total w places up at once, so one line updates every total:

Step through the same two weights, 3 and 5, one operation at a time. The bits are written as to_string() writes them, total 8 first and total 0 last:

The program below answers the question for 1,000 weights between 1 and 150 and totals up to 100,000, once with a plain loop over std::vector<bool>, once with the same loop over std::vector<char>, and once with reach |= reach << w on a std::bitset<100001>. Each version runs five times, taking turns with the other two, and its fastest time is printed, so that other programs on the computer disturb the result less:

// Which totals can a subset of 1,000 weights reach? The same question answered three ways, timed: each way runs
// 5 times, taking turns with the others, and the fastest of its times is printed.
#include <bitset>
#include <chrono>
#include <cstddef>
#include <print>
#include <random>
#include <vector>

constexpr std::size_t max_total = 100'000;

template <class Flags>   // std::vector<bool> or std::vector<char>: one flag per total, updated one total at a time
std::size_t count_with_loop(const std::vector<int>& weights) {
    Flags reach(max_total + 1);
    reach[0] = true;
    for (int w : weights) {
        for (std::size_t t = max_total; t >= static_cast<std::size_t>(w); --t) {   // high to low: each weight used once
            if (reach[t - w]) reach[t] = true;
        }
    }
    std::size_t n = 0;
    for (std::size_t t = 0; t <= max_total; ++t) n += reach[t] ? 1 : 0;
    return n;
}

std::size_t count_with_bitset(const std::vector<int>& weights) {
    std::bitset<max_total + 1> reach;
    reach[0] = true;
    for (int w : weights) reach |= reach << w;   // every reachable total t also makes t + w reachable
    return reach.count();
}

struct Way {
    const char* name;
    std::size_t (*count)(const std::vector<int>&);
    double best_ms = 1e300;
    std::size_t reachable = 0;
};

int main() {
    std::mt19937 gen(42);
    std::vector<int> weights(1'000);
    for (int& w : weights) w = 1 + static_cast<int>(gen() % 150);   // weights 1 to 150

    Way ways[] = {{"vector<bool> loop", count_with_loop<std::vector<bool>>},
                  {"vector<char> loop", count_with_loop<std::vector<char>>},
                  {"bitset shifts", count_with_bitset}};
    for (int round = 0; round < 5; ++round) {   // the three take turns, so a busy moment hurts them all alike
        for (Way& w : ways) {
            const auto start = std::chrono::steady_clock::now();
            w.reachable = w.count(weights);
            const std::chrono::duration<double, std::milli> ms = std::chrono::steady_clock::now() - start;
            if (ms.count() < w.best_ms) w.best_ms = ms.count();
        }
    }
    for (const Way& w : ways) std::println("{:<18} {:>6} totals reachable {:9.2f} ms", w.name, w.reachable, w.best_ms);
}

from session import run

run("""
clang++ -std=c++23 -O2 -Wall -Wextra subset_sum.cpp -o subset_sum && ./subset_sum
g++-16 -std=c++23 -O2 -Wall -Wextra subset_sum.cpp -o subset_sum && ./subset_sum
""")

$ clang++ -std=c++23 -O2 -Wall -Wextra subset_sum.cpp -o subset_sum && ./subset_sum
vector<bool> loop   74695 totals reachable    143.57 ms
vector<char> loop   74695 totals reachable     60.77 ms
bitset shifts       74695 totals reachable      2.35 ms
$ g++-16 -std=c++23 -O2 -Wall -Wextra subset_sum.cpp -o subset_sum && ./subset_sum
vector<bool> loop   74695 totals reachable    151.17 ms
vector<char> loop   74695 totals reachable     62.14 ms
bitset shifts       74695 totals reachable      1.81 ms

All three find the same 74,695 reachable totals. In the recorded run the bitset needed about 2 ms with either compiler, while the loops needed tens to hundreds of milliseconds, the vector<bool> loop always the slowest: the bitset was at least twenty times faster than either loop, and usually far more. Your numbers will differ, but not the order. The loops do one step per weight and per total, about 100 million steps in all, while the bitset handles 64 totals per step: 1,563 words per weight, about 1.6 million word shifts and as many ors.

The vector<bool> loop is the slowest of the three because every access through its proxy has to find the word, build a maskmask: An integer with 1 bits exactly where an operation should act, such as 1u << 3 for bit 3. flags | mask sets those bits, flags & ~mask clears them, flags ^ mask flips them and flags & mask keeps only them. More in “C++ bitwise operators and the <bit> header” and test or set one bit. The bitset is ahead because the problem has the right shape, the same update for every total. A sieve of Eratosthenessieve of Eratosthenes: A way to find every prime up to n without dividing: for each number not yet crossed off, cross off its multiples from its square up. Up to ten million it makes 22,850,051 crossings, far fewer than trial division's divisions. More in “C++ practice set: loops, conditions and numbers”, which touches one bit at a time, has a different shape, and the exercise measures what that does to the ranking.

std::vector<bool> hands out proxies instead of references

The standard (section 24.3.12) declares a separate version of std::vector for bool, “to optimize space allocation”, and recommends a representation that packs the bits. Both libraries pack them, which is where the 12.5 MB above comes from. But a single bit has no address, so operator[] cannot return a bool&. It returns std::vector<bool>::reference, which the standard describes as a class that simulates a reference to a single bit: it converts to bool when read, and sets or clears its bit when assigned to. Most of the time the difference does not show. When it does, it surprises people:

// What std::vector<bool>'s operator[] really returns, and the surprise it causes with auto.
#include <print>
#include <type_traits>
#include <vector>

int main() {
    std::vector<char> chars(4);
    std::vector<bool> flags(4);

    auto c = chars[0];   // a char: a copy of the element
    auto b = flags[0];   // a std::vector<bool>::reference: a small object that points at the bit
    chars[0] = 1;
    flags[0] = true;
    std::println("the copy from vector<char> is still {}", static_cast<int>(c));
    std::println("the \"copy\" from vector<bool> is now {}", static_cast<bool>(b));

    std::println("flags[0] is a bool&: {}", std::is_same_v<decltype(flags[0]), bool&>);
    std::println("flags[0] is a vector<bool>::reference: {}",
                 std::is_same_v<decltype(flags[0]), std::vector<bool>::reference>);

    bool copy = flags[1];   // naming the type converts the proxy to a plain bool
    flags[1] = true;
    std::println("bool copy = flags[1] stayed {}", copy);

    std::println("flags:        {}", flags);
    flags.flip();                                  // two members that only vector<bool> has: flip() ...
    std::println("after flip(): {}", flags);
    std::vector<bool>::swap(flags[0], flags[3]);   // ... and a swap of two elements through their proxies
    std::println("after swap(): {}", flags);
}

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra proxy.cpp -o proxy && ./proxy
g++-16 -std=c++23 -Wall -Wextra proxy.cpp -o proxy && ./proxy
""")

$ clang++ -std=c++23 -Wall -Wextra proxy.cpp -o proxy && ./proxy
the copy from vector<char> is still 0
the "copy" from vector<bool> is now true
flags[0] is a bool&: false
flags[0] is a vector<bool>::reference: true
bool copy = flags[1] stayed false
flags:        [true, true, false, false]
after flip(): [false, false, true, true]
after swap(): [true, false, true, false]
$ g++-16 -std=c++23 -Wall -Wextra proxy.cpp -o proxy && ./proxy
the copy from vector<char> is still 0
the "copy" from vector<bool> is now true
flags[0] is a bool&: false
flags[0] is a vector<bool>::reference: true
bool copy = flags[1] stayed false
flags:        [true, true, false, false]
after flip(): [false, false, true, true]
after swap(): [true, false, true, false]

auto b = flags[0]; did not copy a bool: auto deduced the proxy type, and the proxy still points into the vector, so writing flags[0] = true changed what b reads. The same line with std::vector<char> made a real copy. Naming the type, bool copy = flags[1];, converts the proxy at once and gives an ordinary bool. Step through those lines and watch what each name refers to:

The last lines of the program show the two members that only vector<bool> has, flip() for every bit and a static swap for two elements.

Generic code is where the proxy really bites. A template written for std::vector<T> that takes a reference or a pointer to an element compiles for every T except bool:

// Three lines that compile for std::vector<char> and fail for std::vector<bool>.
#include <vector>

template <class T>
void three_lines(std::vector<T>& v) {
    T& first = v[0];          // a reference to an element
    T* p = &v[1];             // a pointer to an element
    for (T& x : v) x = T{};   // a loop that modifies every element
    (void)first;
    (void)p;
}

int main() {
    std::vector<char> chars(8);
    three_lines(chars);   // fine
    std::vector<bool> flags(8);
    three_lines(flags);   // each of the three lines is an error
}

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra proxy_errors.cpp -o proxy_errors 2>&1 | grep error:
g++-16 -std=c++23 -Wall -Wextra proxy_errors.cpp -o proxy_errors 2>&1 | grep error:
""")

$ clang++ -std=c++23 -Wall -Wextra proxy_errors.cpp -o proxy_errors 2>&1 | grep error:
proxy_errors.cpp:6:8: error: non-const lvalue reference to type 'bool' cannot bind to a temporary of type 'reference' (aka '__bit_reference<vector<bool, std::allocator<bool>>>')
proxy_errors.cpp:7:8: error: no viable conversion from '__bit_iterator<std::vector<bool, std::allocator<bool>>, false>' to 'bool *'
proxy_errors.cpp:8:13: error: non-const lvalue reference to type 'bool' cannot bind to a temporary of type 'reference' (aka 'std::__bit_reference<std::vector<bool>>')
$ g++-16 -std=c++23 -Wall -Wextra proxy_errors.cpp -o proxy_errors 2>&1 | grep error:
proxy_errors.cpp:6:17: error: cannot bind non-const lvalue reference of type 'bool&' to an rvalue of type 'bool'
proxy_errors.cpp:7:14: error: taking address of rvalue [-fpermissive]
proxy_errors.cpp:7:12: error: cannot convert 'std::vector<bool>::reference*' to 'bool*' in initialization
proxy_errors.cpp:8:5: error: cannot bind non-const lvalue reference of type 'bool&' to an rvalue of type 'bool'

Each compiler rejects the reference, the pointer and the loop that modifies through T&, and the messages name the proxy (__bit_reference in libc++) or say that the element is an rvaluervalue: An xvalue or a prvalue: an expression whose object may be moved from, because nobody will look at it again. An rvalue reference, T&&, binds only to rvalues. More in “C++ value categories, std::move and copy elision”, a temporary with no address. For the same reason vector<bool> has no data(), and for (auto& b : flags) does not compile, while for (auto&& b : flags) does, because auto&& can bind to the temporary proxy.

Two threads that set different flags of one word can lose a write

The last difference cannot be seen in a single-threaded test. Two threads may normally write two different elements of one container at the same time, but the standard makes one exception, vector<bool>: its note in section 24.2.3 says that for a vector<bool> y, y[0] = true can race with y[1] = true, a data raceTwo threads using the same memory location at the same time, at least one of them writing, without a lock or an atomic operation to order them. In C++ a data race is undefined behaviour.. Both bits live in the same word, and a processor cannot write a single bit: each write reads the word, changes one bit and writes the word back. Step through the unlucky timing:

Thread 2 wrote back a copy of the word that it had read before thread 1’s write, so flag 0 is clear again, and nothing reports it. The timing is rare, so a test can pass a thousand times and the bug still ships. A std::vector<char> does not have the problem: each flag is a byte of its own, a separate object, so the two writes never touch the same memory. A std::bitset has it too, because its set() and operator[] change one object that both threads share, and the library’s rule is that two threads calling non-const members of the same object race unless the class says otherwise.

Choose the container by what the flags must do

Four containers hold flags, and each fits a different need: the size known at compile time or only at run time, whole-set operations, real references, and threads that write different flags. Answer the questions for your own flags, and the table rules out what cannot work, with the reason:

In short: std::bitset<N> when N is known at compile time and you want whole-set operations; std::vector<char> (or std::vector<std::uint8_t>) when code needs real references, data() or threads that write different flags; std::vector<bool> for the least memory at a run-time size, used only through its own interface; and a std::vector<std::uint64_t> with your own index arithmetic when you need whole-word operations on a run-time size, as the bitwise operators lesson shows.

Practise: a sieve on three containers

The sieve of Eratosthenes finds the primes up to n by crossing out the multiples of each prime, starting at its square. Write it three times in sieve.cpp, with a std::vector<bool>, a std::vector<char> and a std::bitset<10000001> that marks the composite numbers, and return how many primes are left. Checks in main test all three for n = 1, 2, 10, 100 and 1,000,000 (78,498 primes); once they pass, the program times the three versions up to ten million (664,579 primes).

// Exercise: the sieve of Eratosthenes three times, on std::vector<bool>, std::vector<char> and std::bitset.
// Each function returns how many primes are <= n. Write the three bodies, then build with -O2 and run this file:
// every check must say "ok"; then the program times the three versions up to ten million.
#include <bitset>
#include <chrono>
#include <cstddef>
#include <format>
#include <memory>
#include <print>
#include <utility>
#include <vector>

std::size_t count_primes_vector_bool(std::size_t n) {
    (void)n;   // your code here: std::vector<bool> composite(n + 1)
    return 0;
}

std::size_t count_primes_vector_char(std::size_t n) {
    (void)n;   // your code here: std::vector<char> composite(n + 1)
    return 0;
}

constexpr std::size_t max_n = 10'000'000;

std::size_t count_primes_bitset(std::size_t n) {   // n <= max_n
    auto composite = std::make_unique<std::bitset<max_n + 1>>();   // 1.25 MB: on the heap, not the stack
    (void)n;   // your code here
    return 0;
}

int failures = 0;

void check(bool passed, const char* what) {
    std::println("{}  {}", passed ? "ok    " : "FAILED", what);
    if (!passed) ++failures;
}

template <class F>
void timed(const char* what, F count) {
    const auto start = std::chrono::steady_clock::now();
    const std::size_t primes = count(max_n);
    const std::chrono::duration<double, std::milli> ms = std::chrono::steady_clock::now() - start;
    std::println("{:<12} {} primes up to {} in {:.1f} ms", what, primes, max_n, ms.count());
}

int main() {
    for (auto [n, expected] : {std::pair<std::size_t, std::size_t>{1, 0}, {2, 1}, {10, 4}, {100, 25}, {1'000'000, 78'498}}) {
        const bool all_three = count_primes_vector_bool(n) == expected && count_primes_vector_char(n) == expected &&
                               count_primes_bitset(n) == expected;
        check(all_three, std::format("{} primes up to {}", expected, n).c_str());
    }
    std::println("{} of 5 checks failed", failures);
    if (failures != 0) return 1;
    timed("vector<bool>", count_primes_vector_bool);
    timed("vector<char>", count_primes_vector_char);
    timed("bitset", count_primes_bitset);
    return 0;
}

Before any function is written, the checks fail like this:

from session import run

run("""
clang++ -std=c++23 -O2 -Wall -Wextra sieve.cpp -o sieve && ./sieve
""")

$ clang++ -std=c++23 -O2 -Wall -Wextra sieve.cpp -o sieve && ./sieve
ok      0 primes up to 1
FAILED  1 primes up to 2
FAILED  4 primes up to 10
FAILED  25 primes up to 100
FAILED  78498 primes up to 1000000
4 of 5 checks failed
[exit status 1]

You are done when all five checks say ok and the three times are printed. First hint: one function template, template <class Flags> std::size_t sieve(Flags& composite, std::size_t n), can do the work for all three, because all three support composite[i] and composite[i] = true. Start crossing out at i * i and stop the outer loop once i * i > n. Then compare your three times with the subset sums above, and work out why the ranking changes when every operation touches a single bit.

When the five checks pass, try the questions on bit order, memory, whole-word operations, proxies and threads. They start with what you know least, and every wrong option says what it overlooks:

Interview questions

Fresher · What is the difference between std::bitset<N> and std::vector<bool>?

Both store flags as bits, but a std::bitset<N> has a size fixed at compile time and lives wherever it is declared, with no allocation, while a std::vector<bool> has a run-time size that can grow and keeps its bits on the heap. The bitset offers whole-set operations (&, |, ^, ~, shifts, count, all, any, none) and conversions to strings and integers. std::vector<bool> is a special version of std::vector whose operator[] returns a proxy object instead of bool&, so references, pointers to elements and data() do not work, auto copies the proxy rather than the value, and two threads writing different elements can race. Both index from bit 0, and for both an index outside the size in operator[] is undefined behaviour.

Interviewers often push on the edges of that answer next: an index one past the end, and a size that is not known when the program is compiled. Decide both:

The module’s bank holds two harder questions on these containers: worker threads that lose finished flags in a shared std::vector<bool>, and the subset-sum rewrite that ran about a hundred times faster:

Key takeaways

• std::bitset<N> holds N bits in whole 64-bit words, and to_string() and the string constructor put bit 0 last; test() throws std::out_of_range, while operator[] does not check.
• A hundred million flags take 12.5 MB as bits and 100 MB as bytes, and a large bitset belongs in static storage or on the heap, not on an 8 MB stack.
• Whole-word operations made the subset-sum computation more than twenty times faster than the best per-flag loop, because one shift and one or update 64 totals at once.
• std::vector<bool> packs bits too, but its operator[] returns a proxy: no bool&, no bool*, no data(), and auto keeps a link to the vector.
• Two threads that set different flags of a vector<bool> or a bitset can lose a write, because each write reads and writes back a whole word; a std::vector<char> gives every flag its own byte.