以一个简陋的自制 vector仿制品 来演示 特例是如何为存储 布尔值提供更高效的方案。

my_vector imitate vector : functions as follow:

declare the initial size of my_vector in the constructor.

increase the elements of my_vector by member function push_back().

read or write the elements of my_vector by overloading subscript operator “[ ]”.

在通常的计算机平台上，sizeof(bool) 的返回值为 1，即是 1 字节(byte) 。但布尔型只有两个值，true or false
.we can show it by only 1 bit . 1 bit can save 8 bool variables completely. It seems too much of a waste to occupy 1 byte. So we need a terse preservation method.

code as follows:

#include<stdexcept>
#include<iostream>
#include<cstdlib>

template <typename T>
class my_vector
{
    T *array;
    unsigned size;
    unsigned block_size;
public:
    my_vector(unsigned bsz):array((T*)malloc(sizeof(T)*bsz)),size(0),block_size(bsz)
    {}
    ~my_vector()
    {
        if(array)
            free(array);
    }
    
    void push_back(T const &elem)
    throw (std::runtime_error)
    {
        if(size==block_size)
        {
            block_size*=2;
            T* new_array=(T*)realloc(array,sizeof(T)*block_size);
            if(new_array!=NULL)
                array=new_array;
            else
            {
                free(array);
                array=NULL;
                throw std::runtime_error("Out of memory\n");
            }
        }
        array[size++]=elem;
        
    }
    T &operator[](unsigned i)
    {
        return array[i];
    }
    const T&operator [](unsigned i) const
    {
        return array[i];
    }
    unsigned get_mem_size() const
    {
        return block_size*sizeof(T);
    }
};


template<>
class my_vector<bool>
{
    int *array;
    unsigned size;
    unsigned block_size;
    const static unsigned seg_size;
public:
    my_vector(unsigned bsz=1):
    array((int *)malloc(sizeof(int)*bsz)),
    size(0),block_size(bsz)
    {
        
    }
    ~my_vector()
    {
        if(array)
            free(array);
    }
    
    void push_back(bool elem)
    throw (std::runtime_error)
        {
            if( size ==block_size*seg_size)
            {
                block_size*=2;
                int *new_array=(int *)realloc(array,sizeof(int)*block_size);
                if(new_array!=NULL)
                    array=new_array;
                else
                {
                    free(array);
                    array=NULL;
                    throw std::runtime_error("Out of memory.\n");
                }
            }
            set(size++,elem);
            
        }
    
    void set(unsigned i,bool elem)
    {
        if(elem)
            array[i/seg_size]|=(0x1<<(i%seg_size));
        else
            array[i/seg_size]&=~(0x1<<(i%seg_size));
    }
        bool operator[](unsigned i) const
        {
            return (array[i/seg_size]&(0x1<<(i%seg_size)))!=0;
        }
        unsigned get_mem_size() const
        {
            return block_size*sizeof(int);
    
        }
    
};
const unsigned my_vector<bool>::seg_size=sizeof(int)*8;


int main()
{
    my_vector<char> vi(2);
    my_vector<bool> vb(2);
    for(unsigned i=0;i<20;i++)
    {
        vi.push_back('a'+i);
        vb.push_back((i%4)==0);
    }
    
    using namespace std;
    cout<<"MemSize of my_vector<char> is "<<vi.get_mem_size()<<endl;
    cout<<"MemSize of my_vector<bool> is "<<vb.get_mem_size()<<endl;
    
    for(unsigned i=0;i<20;i++)
    {
        cout<<' '<<vi[i];
    }
    cout<<endl;
    for(unsigned i=0;i<20;i++)
        cout<<vb[i];
    cout<<endl;
}