所谓位向量就是由一些二进制位组成的向量。位向量可以用很少的内存来存储Boolean变量。

BitVector.h

#pragma once
#include <cstddef>
class BitVector
{
public:
    typedef bool BitValType;
    static const BitValType TRUE = true;
    static const BitValType FALSE = false;
    BitVector();
    BitVector(size_t size, bool init_fill = true);
    BitVector(const BitVector& rhs);
    ~BitVector();
    void resize(size_t size);
    const BitValType& get(size_t index) const;
    bool set(size_t index, const BitValType& val);
    BitVector& operator=(const BitVector& rhs);
private:
    size_t size_;
    int* data_;
};

BitVector.cpp

#include "bitVector.h"
#include <algorithm>
#include <stdexcept>



BitVector::BitVector()
    :BitVector(0)
{}

BitVector::BitVector(size_t size, bool init_fill)
{
    size_t n = size / sizeof(int);
    this->data_ = new int[n];
    if (init_fill)
    {
        for (size_t i = 0; i < n; i++)
        {
            this->data_[i] = 0;
        }
    }
    this->size_ = size;
}

BitVector::BitVector(const BitVector & rhs)
    :BitVector(rhs.size_, false)
{
    std::copy(rhs.data_, rhs.data_ + rhs.size_, this->data_);
}

BitVector::~BitVector()
{
    delete[] this->data_;
}

void BitVector::resize(size_t newSize)
{
    size_t oldsize = this->size_;
    size_t oldn = oldsize / sizeof(int);
    size_t n = newSize / sizeof(int);
    int *oldp = this->data_;
    int *p = new int[n];
    for (size_t i = 0; i < n && i < oldn; i++)
    {
        p[i] = oldp[i];
    }
    delete[] oldp;
    this->data_ = p;
    this->size_ = newSize;
};

const BitVector::BitValType& BitVector::get(size_t index) const
{
    if (index < 0 || index > this->size_)
    {
        throw std::out_of_range("BitVector::get() parameter index");
        // return BitVector::FALSE;
    }
    size_t i = index / (sizeof(int) * 8);
    size_t n = index % (sizeof(int) * 8);
    if (((this->data_[i] & (1U << (n - 1)))) != 0)
    {
        return BitVector::TRUE;
    }
    else
    {
        return BitVector::FALSE;
    }
   
}

bool BitVector::set(size_t index, const BitValType & val)
{
    if (index < 0 || index > this->size_)
    {
        throw std::out_of_range("BitVector::set() parameter index");
        // return false;
    }
    size_t i = index / (sizeof(int) * 8);
    size_t n = index % (sizeof(int) * 8);
    if (val == BitVector::TRUE)
    {
        this->data_[i] |= (1U << (n - 1));
    }
    else
    {
        this->data_[i] &= ~(1U << (n - 1));
    }
    return true;
}

BitVector& BitVector::operator=(const BitVector & rhs)
{
    delete[] this->data_;
    this->data_ = new int[rhs.size_ / sizeof(int)];
    std::copy(rhs.data_, rhs.data_ + rhs.size_, this->data_);
    this->size_ = rhs.size_;
    return *this;
}

泛型模板实现（可以指定使用何种数据类型存储，默认为int）

#pragma once
#include <cstddef>

template <typename T = int>
class BitVector
{
public:
    typedef typename bool BitValType;
    static const BitValType TRUE = true;
    static const BitValType FALSE = false;
    BitVector();
    BitVector(size_t size, bool init = true);
    BitVector(const BitVector<T>& rhs);
    ~BitVector();
    void resize(size_t size);
    const BitValType& get(size_t index) const;
    bool set(size_t index, const BitValType& val);
    BitVector<T>& operator=(const BitVector<T>& rhs);
private:
    size_t size_;
    T* data_;
};

#include <algorithm>
#include <stdexcept>

template <typename T>
BitVector<T>::BitVector()
    :BitVector<T>(0)
{}

template <typename T>
BitVector<T>::BitVector(size_t size, bool init)
{
    size_t n = size / sizeof(T);
    this->data_ = new T[n];
    if (init_fill)
    {
        for (size_t i = 0; i < n; i++)
        {
            this->data_[i] = 0;
        }
    }
    this->size_ = size;
}

template <typename T>
BitVector<T>::BitVector(const BitVector & rhs)
    :BitVector<T>(rhs.size_, false)
{
    std::copy(rhs.data_, rhs.data_ + rhs.size_, this->data_);
}

template <typename T>
BitVector<T>::~BitVector()
{
    delete[] this->data_;
}

template <typename T>
void BitVector<T>::resize(size_t newSize)
{
    size_t oldsize = this->size_;
    size_t oldn = oldsize / sizeof(T);
    size_t n = newSize / sizeof(T);
    T *oldp = this->data_;
    T *p = new T[n];
    for (size_t i = 0; i < n && i < oldn; i++)
    {
        p[i] = oldp[i];
    }
    delete[] oldp;
    this->data_ = p;
    this->size_ = newSize;
};

template <typename T>
const typename BitVector<T>::BitValType& BitVector<T>::get(size_t index) const
{
    if (index < 0 || index > this->size_)
    {
        throw std::out_of_range("BitVector::get() parameter index");
        // return BitVector::FALSE;
    }
    size_t i = index / (sizeof(T) * 8);
    size_t n = index % (sizeof(T) * 8);
    if (((this->data_[i] & (1U << (n - 1)))) != 0)
    {
        return BitVector::TRUE;
    }
    else
    {
        return BitVector::FALSE;
    }

}

template <typename T>
bool BitVector<T>::set(size_t index, const BitValType & val)
{
    if (index < 0 || index > this->size_)
    {
        throw std::out_of_range("BitVector::set() parameter index");
        // return false;
    }
    size_t i = index / (sizeof(T) * 8);
    size_t n = index % (sizeof(T) * 8);
    if (val == BitVector<T>::TRUE)
    {
        this->data_[i] = this->data_[i] | (1U << (n - 1));
    }
    else
    {
        this->data_[i] = this->data_[i] & ~(1U << (n - 1));
    }
    return true;
}

template <typename T>
BitVector<T>& BitVector<T>::operator=(const BitVector<T> & rhs)
{
    delete[] this->data_;
    this->data_ = new T[rhs.size_ / sizeof(T)];
    std::copy(rhs.data_, rhs.data_ + rhs.size_, this->data_);
    this->size_ = rhs.size_;
    return *this;
}

UPDATE1

经过评论提醒：C语言的结构体位域也可以实现类似功能。

UPDATE2

C++的STL容器vector定义了特化vector，其就是用此方法实现的空间压缩，直接使用vector即可，无需自行实现。