c++模版编程构造栈和向量vector

ゝ一世哀愁。 2022-04-18 01:33 184阅读 0赞

### c++模版编程构造栈和向量vector ###

*   *  向量
     *  栈

## 向量 ##

//使用 声明通例
    template <typename T>
    class my_vector{
        T* my_array;
        unsigned size;
        unsigned  block_size;
    
    public:
        my_vector(unsigned bsz):my_array((T*)malloc(sizeof(T)*bsz)),size(0),block_size(bsz){}
    
        ~my_vector(){
            if(my_array)
                free(my_array);
        }
    
        void push_back(T const & elem) throw (std::runtime_error){
            if (size == block_size){
                //已经有的空间已经用完，需要重新分配空间
                block_size *=2;
                T*new_array=(T*)realloc(my_array,block_size* sizeof(T));
                if(new_array != NULL){
                    my_array=new_array;
                }else{
                    //申请空间失败，内存耗尽
                    free(my_array);
                    my_array=NULL;
                    throw std::runtime_error("out of memory");
                }
    
            }
            my_array[size++]=elem;
        }
    
        T&operator[](unsigned i){
            return my_array[i];
        }
    
        const T &operator[](unsigned  i) const {
            return  my_array[i];
        }
    
        //告诉占用了多少内存
        unsigned get_mem_size()const{
            return block_size*sizeof(T);
        }
    
    
    };
    //声明my_vector的特例
    
    template <>
    class my_vector<bool>{
        int * array;
        unsigned size;
        unsigned block_size;
    
        //一个段（segment)即是一个整数值，段的大小极为一个整数值所能容纳的作答的布尔值
        // =sizeof(int)*8
        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,block_size* sizeof(int));
                if(new_array!=NULL){
                    array=new_array;
                }else{
                    free(array);
                    array=NULL;
                    throw std::runtime_error("Out of memory");
                }
            }
    
            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;

## 栈 ##

// 文件名：stack.hpp
        #include <stdexcept>
        template<typename T> class my_stack;   //前置栈类模板声明
        template<typename T>
        class list_node
        {
            T value;
            list_node ＊next;
            // 私有构造函数，只能由其友类构造
            list_node(T const &v, list_node ＊n) :
                value(v), next(n) {}
            // 友类必须是类模板my_stack的实例
            friend class my_stack<T>;
        };
        template<typename T=int>
        class my_stack {
            typedef list_node<T> node_type;
            node_type ＊head;
            // my_stack不可复制构造，也不可赋值
            my_stack operator=(my_stack const &) {}
            my_stack(my_stack const &s) {}
        public:
            // 构造与析构
            my_stack() : head(0) {}
            ～my_stack() {while (!empty()) pop();}
            // 在类模板内实现的成员函数模板
            bool empty() const {return head == 0;}
            T const& top() const throw (std::runtime_error) {
                if (empty())
                      throw std::runtime_error("stack is empty.");
                return head->value;
            }
    void push(T const &v) {head = new node_type(v, head);}
        // 成员函数声明，将在类模板外实现
        void pop();
    };
    // 在类模板外实现的成员函数模板
    template<typename T>
    void my_stack<T>::pop()
    {
        if (head) {
            node_type ＊tmp = head;
            head = head->next;
            delete tmp;
        }
    }