16.12 — std::vector

In this lesson, you'll learn about std::vector, a specialized version of std::vector that has unique characteristics and behaviors. You'll understand why it exists, how it differs from regular vectors, and when you should (or shouldn't) use it.

What makes std::vector special?

std::vector is a template specialization that behaves differently from other std::vector types. Instead of storing bool values directly, it uses a space-efficient representation where each bool takes only 1 bit of storage rather than 1 byte.

Memory efficiency comparison

#include <vector>
#include <iostream>

int main()
{
    std::vector<bool> boolVector(100, true);
    std::vector<char> charVector(100, 1); // Using char to simulate regular bool storage
    std::vector<int> intVector(100, 1);
    
    std::cout << "Memory usage comparison for 100 elements:" << std::endl;
    std::cout << "std::vector<bool>: " << sizeof(boolVector) + boolVector.capacity() / 8 
              << " bytes (estimated)" << std::endl;
    std::cout << "std::vector<char>: " << sizeof(charVector) + charVector.capacity() 
              << " bytes" << std::endl;
    std::cout << "std::vector<int>: " << sizeof(intVector) + intVector.capacity() * 4 
              << " bytes" << std::endl;
    
    return 0;
}

Output (example):

Memory usage comparison for 100 elements:
std::vector<bool>: 36 bytes (estimated)
std::vector<char>: 124 bytes
std::vector<int>: 424 bytes

The reference proxy problem

The most important difference is that std::vector doesn't return actual bool references. Instead, it returns proxy objects:

#include <vector>
#include <iostream>

int main()
{
    std::vector<bool> boolVec = {true, false, true, false};
    std::vector<int> intVec = {1, 0, 1, 0};
    
    // This works fine with regular vectors
    int& intRef = intVec[0];  // Real reference
    intRef = 5;               // Modifies the original
    std::cout << "intVec[0] = " << intVec[0] << std::endl;
    
    // This creates a proxy, not a real reference
    auto boolRef = boolVec[0]; // This is NOT bool&, it's a proxy object
    
    // Check the actual types
    std::cout << "Type of intVec[0]: " << typeid(intVec[0]).name() << std::endl;
    std::cout << "Type of boolVec[0]: " << typeid(boolVec[0]).name() << std::endl;
    
    // The proxy can be used like a bool
    boolRef = false; // This works, but it's different from a real reference
    std::cout << "boolVec[0] = " << boolVec[0] << std::endl;
    
    return 0;
}

Output:

intVec[0] = 5
Type of intVec[0]: i
Type of boolVec[0]: NSt3__114__bit_referenceINS_6vectorIbNS_9allocatorIbEEEEEE
boolVec[0] = 0

Problems caused by the proxy

#include <vector>
#include <iostream>

void takeBoolReference(bool& b)
{
    std::cout << "Received bool reference: " << b << std::endl;
    b = !b; // Flip the bool
}

void takeBoolValue(bool b)
{
    std::cout << "Received bool value: " << b << std::endl;
}

int main()
{
    std::vector<bool> boolVec = {true, false, true};
    
    // This works - implicit conversion to bool
    takeBoolValue(boolVec[0]);
    
    // ❌ This won't compile - proxy can't bind to bool&
    // takeBoolReference(boolVec[0]); // Compilation error!
    
    // Workaround: create a temporary bool
    bool temp = boolVec[0];
    takeBoolReference(temp);
    boolVec[0] = temp; // Update the vector if needed
    
    std::cout << "After flip: " << boolVec[0] << std::endl;
    
    return 0;
}

Output:

Received bool value: 1
Received bool reference: 1
After flip: 0

Basic operations with std::vector

Despite the proxy issue, most basic operations work as expected:

#include <vector>
#include <iostream>

int main()
{
    // Construction and initialization
    std::vector<bool> flags;
    std::vector<bool> switches(5, true);
    std::vector<bool> options = {true, false, true, false, true};
    
    std::cout << "Basic operations:" << std::endl;
    
    // Size and capacity
    std::cout << "Options size: " << options.size() << std::endl;
    std::cout << "Options capacity: " << options.capacity() << std::endl;
    
    // Adding elements
    flags.push_back(true);
    flags.push_back(false);
    flags.push_back(true);
    
    std::cout << "Flags: ";
    for (bool flag : flags) // Range-based for loop works
    {
        std::cout << flag << " ";
    }
    std::cout << std::endl;
    
    // Accessing elements
    std::cout << "First option: " << options[0] << std::endl;
    std::cout << "Last option: " << options.back() << std::endl;
    
    // Modifying elements
    options[0] = false;
    options.back() = false;
    
    std::cout << "Modified options: ";
    for (std::size_t i = 0; i < options.size(); ++i)
    {
        std::cout << options[i] << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Output:

Basic operations:
Options size: 5
Options capacity: 64
Flags: 1 0 1 
First option: 1
Last option: 1
Modified options: 0 0 1 0 0 

Special member functions of std::vector

std::vector provides some additional member functions for bit manipulation:

flip() function

#include <vector>
#include <iostream>

int main()
{
    std::vector<bool> bits = {true, false, true, false};
    
    std::cout << "Original: ";
    for (bool bit : bits)
    {
        std::cout << bit << " ";
    }
    std::cout << std::endl;
    
    // Flip all bits
    bits.flip();
    
    std::cout << "After flip(): ";
    for (bool bit : bits)
    {
        std::cout << bit << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Output:

Original: 1 0 1 0 
After flip(): 0 1 0 1 

Individual element flipping

#include <vector>
#include <iostream>

int main()
{
    std::vector<bool> status = {true, true, false, false};
    
    std::cout << "Before flipping individual elements:" << std::endl;
    for (std::size_t i = 0; i < status.size(); ++i)
    {
        std::cout << "status[" << i << "] = " << status[i] << std::endl;
    }
    
    // Flip individual elements using the proxy's flip method
    status[0].flip();
    status[2].flip();
    
    std::cout << "\nAfter flipping elements 0 and 2:" << std::endl;
    for (std::size_t i = 0; i < status.size(); ++i)
    {
        std::cout << "status[" << i << "] = " << status[i] << std::endl;
    }
    
    return 0;
}

Output:

Before flipping individual elements:
status[0] = 1
status[1] = 1
status[2] = 0
status[3] = 0

After flipping elements 0 and 2:
status[0] = 0
status[1] = 1
status[2] = 1
status[3] = 0

Practical applications

Application 1: Bit flags and options

#include <vector>
#include <iostream>
#include <string>

class FeatureManager
{
private:
    std::vector<bool> features;
    std::vector<std::string> featureNames;
    
public:
    void addFeature(const std::string& name, bool enabled = false)
    {
        featureNames.push_back(name);
        features.push_back(enabled);
    }
    
    void enableFeature(std::size_t index)
    {
        if (index < features.size())
        {
            features[index] = true;
        }
    }
    
    void disableFeature(std::size_t index)
    {
        if (index < features.size())
        {
            features[index] = false;
        }
    }
    
    void toggleFeature(std::size_t index)
    {
        if (index < features.size())
        {
            features[index].flip();
        }
    }
    
    void displayStatus() const
    {
        std::cout << "Feature Status:" << std::endl;
        for (std::size_t i = 0; i < features.size(); ++i)
        {
            std::cout << "  " << featureNames[i] << ": " 
                      << (features[i] ? "ON" : "OFF") << std::endl;
        }
        std::cout << std::endl;
    }
    
    std::size_t getFeatureCount() const { return features.size(); }
};

int main()
{
    FeatureManager manager;
    
    manager.addFeature("Dark Mode", false);
    manager.addFeature("Auto Save", true);
    manager.addFeature("Spell Check", true);
    manager.addFeature("Grammar Check", false);
    
    manager.displayStatus();
    
    // Toggle some features
    manager.toggleFeature(0); // Enable Dark Mode
    manager.toggleFeature(2); // Disable Spell Check
    
    std::cout << "After toggling Dark Mode and Spell Check:" << std::endl;
    manager.displayStatus();
    
    return 0;
}

Output:

Feature Status:
  Dark Mode: OFF
  Auto Save: ON
  Spell Check: ON
  Grammar Check: OFF

After toggling Dark Mode and Spell Check:
Feature Status:
  Dark Mode: ON
  Auto Save: ON
  Spell Check: OFF
  Grammar Check: OFF

Application 2: Sieve of Eratosthenes

#include <vector>
#include <iostream>

std::vector<int> sieveOfEratosthenes(int limit)
{
    // Create a vector of booleans, initially all true
    std::vector<bool> isPrime(limit + 1, true);
    isPrime[0] = isPrime[1] = false; // 0 and 1 are not prime
    
    for (int i = 2; i * i <= limit; ++i)
    {
        if (isPrime[i])
        {
            // Mark multiples of i as not prime
            for (int j = i * i; j <= limit; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
    
    // Collect prime numbers
    std::vector<int> primes;
    for (int i = 2; i <= limit; ++i)
    {
        if (isPrime[i])
        {
            primes.push_back(i);
        }
    }
    
    return primes;
}

int main()
{
    int limit = 100;
    auto primes = sieveOfEratosthenes(limit);
    
    std::cout << "Prime numbers up to " << limit << ":" << std::endl;
    for (std::size_t i = 0; i < primes.size(); ++i)
    {
        std::cout << primes[i];
        if (i < primes.size() - 1) std::cout << ", ";
        if ((i + 1) % 10 == 0) std::cout << std::endl; // New line every 10 primes
    }
    std::cout << std::endl;
    std::cout << "Found " << primes.size() << " primes." << std::endl;
    
    return 0;
}

Output:

Prime numbers up to 100:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
73, 79, 83, 89, 97
Found 25 primes.

When to avoid std::vector

Use alternatives when you need real references

#include <vector>
#include <bitset>
#include <iostream>

// Problem scenario: need to pass bool by reference
void flipBool(bool& b)
{
    b = !b;
}

int main()
{
    std::cout << "Comparison of alternatives:" << std::endl;
    
    // ❌ std::vector<bool> - can't pass elements by reference
    std::vector<bool> boolVec = {true, false, true};
    
    // Workaround for std::vector<bool>
    bool temp = boolVec[0];
    flipBool(temp);
    boolVec[0] = temp;
    std::cout << "vector<bool> after workaround: " << boolVec[0] << std::endl;
    
    // ✅ std::vector<char> - real references work
    std::vector<char> charVec = {1, 0, 1};
    bool charAsBool = charVec[0];
    flipBool(charAsBool);
    charVec[0] = charAsBool;
    std::cout << "vector<char> alternative: " << static_cast<bool>(charVec[0]) << std::endl;
    
    // ✅ std::bitset - for fixed-size bit arrays
    std::bitset<8> bitsetFlags("10101010");
    std::cout << "bitset alternative: " << bitsetFlags << std::endl;
    bitsetFlags.flip(0);
    std::cout << "bitset after flip: " << bitsetFlags << std::endl;
    
    return 0;
}

Output:

Comparison of alternatives:
vector<bool> after workaround: 0
vector<char> alternative: 0
bitset alternative: 10101010
bitset after flip: 10101011

Alternatives to std::vector

When to use each alternative

#include <vector>
#include <bitset>
#include <iostream>

int main()
{
    std::cout << "Choosing the right container for boolean data:" << std::endl;
    
    // std::vector<bool> - space-efficient, dynamic size
    std::vector<bool> dynamicFlags;
    for (int i = 0; i < 100; ++i)
    {
        dynamicFlags.push_back(i % 2 == 0);
    }
    std::cout << "vector<bool> - Dynamic size, space efficient" << std::endl;
    
    // std::vector<char> - real references, slightly more memory
    std::vector<char> flagsAsChar = {1, 0, 1, 0, 1};
    char& realRef = flagsAsChar[0]; // Real reference
    realRef = 0;
    std::cout << "vector<char> - Real references, more memory" << std::endl;
    
    // std::bitset - fixed size, rich interface
    std::bitset<8> fixedFlags("11001010");
    fixedFlags.flip();
    fixedFlags.set(0, true);
    std::cout << "bitset - Fixed size: " << fixedFlags << std::endl;
    
    // Choose based on needs:
    std::cout << "\nChoose based on your needs:" << std::endl;
    std::cout << "- std::vector<bool>: Dynamic, space-efficient, proxy references" << std::endl;
    std::cout << "- std::vector<char>: Dynamic, real references, more memory" << std::endl;
    std::cout << "- std::bitset: Fixed size, rich interface, very efficient" << std::endl;
    
    return 0;
}

Output:

Choosing the right container for boolean data:
vector<bool> - Dynamic size, space efficient
vector<char> - Real references, more memory
bitset - Fixed size: 00110101

Choose based on your needs:
- std::vector<bool>: Dynamic, space-efficient, proxy references
- std::vector<char>: Dynamic, real references, more memory
- std::bitset: Fixed size, rich interface, very efficient

Best practices

1. Be aware of the proxy behavior

// ❌ Don't assume you get real bool references
// bool& ref = boolVec[0]; // Won't compile

// ✅ Use auto for the proxy or convert to bool
auto proxy = boolVec[0]; // Works with proxy
bool value = boolVec[0]; // Converts to bool

2. Use range-based for loops when possible

std::vector<bool> flags = {true, false, true};

// ✅ Good - works naturally
for (bool flag : flags)
{
    std::cout << flag << " ";
}

3. Consider alternatives when you need real references

// If you frequently need to pass elements by reference
std::vector<char> boolAsChar; // Consider this instead
std::bitset<N> fixedBits;     // Or this for fixed-size

Summary

std::vector is a specialized container with unique characteristics:

Advantages:

• Space-efficient: Uses 1 bit per bool instead of 1 byte
• Provides flip() functionality for all elements
• Most standard operations work as expected

Disadvantages:

• Doesn't provide real bool references (uses proxy objects)
• Can't pass elements directly to functions expecting bool&
• May have surprising behavior in generic code

When to use std::vector:

• Space efficiency is important
• You need dynamic sizing
• You don't need to pass elements by reference
• You can work with the proxy behavior

When to use alternatives:

• std::vector: Need real references, don't mind extra memory
• std::bitset<N>: Fixed size, rich bit manipulation interface
• Custom bit vector: Full control over behavior and interface

Key takeaway: std::vector is useful for space-efficient storage of large numbers of boolean values, but be prepared to handle its unique proxy behavior.

In the next lesson, you'll get a comprehensive summary of everything you've learned about std::vector.

Quiz

1. How does std::vector differ from std::vector in terms of memory usage?
2. What is a proxy reference and why does std::vector use them?
3. What special member function does std::vector provide that other vectors don't?
4. When might you choose std::vector over std::vector?
5. What alternatives exist to std::vector for storing boolean data?

Practice exercises

Try these exercises to practice working with std::vector:

1. Bit manipulation utility: Create a class that wraps std::vector and provides safe methods for common operations, handling the proxy reference issues transparently.

2. Boolean matrix: Implement a 2D boolean matrix using std::vector as the underlying storage. Provide methods for setting, getting, and flipping individual bits.

3. Feature comparison: Write a program that compares the memory usage and performance of std::vector, std::vector, and std::bitset for storing and manipulating large amounts of boolean data.

4. Bitwise operations: Implement functions that perform bitwise AND, OR, and XOR operations between two std::vector objects of the same size.