The Specialized bool Vector

std::vector

std::bitset can pack 8 boolean values into a single byte. std::vector<bool> offers similar space optimization while maintaining vector functionality.

The special std::vector implementation

std::vector<bool> uses a specialized implementation (called class template specialization) that may compress multiple boolean values into individual bits, similar to std::bitset. Unlike std::bitset designed for bit manipulation, std::vector<bool> focuses on space-efficient boolean storage without extensive bit operation support.

Basic usage

For most operations, std::vector<bool> works like a normal vector:

#include <iostream>
#include <vector>

int main()
{
    std::vector<bool> flags { true, false, true, true, false };

    for (bool flag : flags)
        std::cout << flag << ' ';
    std::cout << '\n';

    flags[2] = false;  // Modify element

    for (bool flag : flags)
        std::cout << flag << ' ';
    std::cout << '\n';

    return 0;
}

Output:

1 0 1 1 0
1 0 0 1 0

Performance and memory trade-offs

std::vector<bool> involves significant trade-offs:

Memory overhead: On a 64-bit system, std::vector<bool> has approximately 40 bytes of overhead. You won't save memory unless storing many boolean values.

Performance variability: Highly implementation-dependent. Well-optimized versions can be faster than alternatives; poorly optimized ones will be slower.

Container non-conformance: Most critically, std::vector<bool> is NOT a true container:

• Not required to be contiguous in memory
• Doesn't hold actual bool values (holds bits)
• Doesn't meet C++'s container requirements

Incompatibility with generic code

Code working with other types may fail with std::vector<bool>:

template <typename T>
void process(std::vector<T>& vec)
{
    T& first = vec[0];  // Get reference to first element
    // Use first...
}

This works for all types EXCEPT bool, because std::vector<bool> can't return true references to individual bits.

The consensus: avoid std::vector

The modern C++ community generally advises against std::vector<bool>. The space savings rarely justify the incompatibility problems. It's enabled by default with no way to disable it, and calls exist to deprecate it.

Recommended alternatives

Use these instead:

For compile-time sized bit collections: Use constexpr std::bitset

• Works when size is known at compile-time
• Suitable for moderate bit counts (under 64k)
• Provides bit manipulation operations

For runtime Boolean collections: Use std::vector<char>

• Behaves like a proper container
• Works with all generic code
• Wastes some memory but avoids compatibility issues

For dynamic bitsets: Use third-party implementations like boost::dynamic_bitset

• Provides bit manipulation operations
• Doesn't pretend to be a standard container
• More honest about capabilities

Example with alternatives

Instead of:

std::vector<bool> settings { true, false, true, false };  // Avoid

Use:

#include <bitset>
#include <vector>

// Option 1: Fixed size
constexpr std::bitset<4> settings1 { 0b1010 };

// Option 2: Variable size, proper container behavior
std::vector<char> settings2 { 1, 0, 1, 0 };

The memory overhead of std::vector<char> is usually acceptable for the gained reliability and compatibility.

Summary

Class template specialization: std::vector<bool> uses a specialized implementation that may pack multiple boolean values into individual bits for space efficiency. Unlike std::bitset which focuses on bit manipulation, std::vector<bool> prioritizes space-efficient boolean storage.

Container non-conformance: std::vector<bool> is not a true standard container. It's not required to be contiguous in memory, doesn't hold actual bool values, and can't return true references to individual bits. This makes it incompatible with generic code expecting standard container behavior.

Performance trade-offs: Memory overhead of approximately 40 bytes means you need many boolean values before seeing space savings. Performance varies significantly by implementation, and container non-conformance can break generic algorithms.

Incompatibility issues: Code working with other std::vector types may fail with std::vector<bool> because it can't return references to individual bits. This breaks generic functions that assume T& references work for all vector types.

Recommended alternatives: For compile-time sized collections, use constexpr std::bitset. For runtime boolean collections, use std::vector<char> which behaves like a proper container. For dynamic bitsets with bit manipulation, use third-party libraries like boost::dynamic_bitset.

Community consensus: Modern C++ developers generally avoid std::vector<bool> because space savings rarely justify compatibility problems. It's enabled by default with no way to disable it, and there are ongoing calls to deprecate it.

The lesson here is clear: specialized implementations that violate expected behavior patterns cause more problems than they solve, especially when better alternatives exist.