《STL系列》之vector原理及實現

最近忙得蛋疼，但還是想寫點屬于自己的東西。也不知道寫點啥，最后決定試著自己實現STL中常用的幾個集合，一來加深自己對STL的理解，二來看看自己是否有這個能力實現。實現目標就是：1能和STL兼容；2最大化的實現STL中的接口并保持一致。即將STL中的集合換成我寫的也能用。這篇博客介紹的是vector的原理及實現。

先把vector的大致實現說一下，后面會給出完整的源碼。

新增元素：Vector通過一個連續的數組存放元素，如果集合已滿，在新增數據的時候，就要分配一塊更大的內存，將原來的數據復制過來，釋放之前的內存，在插入新增的元素。插入新的數據分在最后插入push_back和通過迭代器在任何位置插入，這里說一下通過迭代器插入，通過迭代器與第一個元素的距離知道要插入的位置，即int index=iter-begin()。這個元素后面的所有元素都向后移動一個位置，在空出來的位置上存入新增的元素。

        void insert(const_iterator iter,const T& t )
        {  
            int index=iter-begin();
            if (index<size_)
            {
                if (size_==capacity_)
                {
                    int capa=calculateCapacity();
                    newCapacity(capa);
                }
                memmove(buf+index+1,buf+index,(size_-index)*sizeof(T)); 
                buf[index]=t;
                size_++;
            } 
        }

刪除元素：刪除和新增差不多，也分兩種，刪除最后一個元素pop_back和通過迭代器刪除任意一個元素erase(iter)。通過迭代器刪除還是先找到要刪除元素的位置，即int index=iter-begin();這個位置后面的每個元素都想前移動一個元素的位置。同時我們知道erase不釋放內存只初始化成默認值。

刪除全部元素clear：只是循環調用了erase，所以刪除全部元素的時候，不釋放內存。內存是在析構函數中釋放的。

        iterator erase(const_iterator iter)
        {
            int index=iter-begin(); 
            if (index<size_ && size_>0)
            {
                memmove(buf+index ,buf+index+1,(size_-index)*sizeof(T)); 
                buf[--size_]=T();
            } 
            return iterator(iter); 
        }

迭代器iteraotr是STL的一個重要組成部分,通過iterator可以很方便的存儲集合中的元素.STL為每個集合都寫了一個迭代器, 迭代器其實是對一個指針的包裝,實現一些常用的方法,如++,--,!=,==,*,->等, 通過這些方法可以找到當前元素或是別的元素. vector是STL集合中比較特殊的一個,因為vector中的每個元素都是連續的,所以在自己實現vector的時候可以用指針代替,如typedef T* iterator;typedef const T* const_iterator，如果STL中的函數能方便的操作自己寫的集合，實現的迭代器最好繼承std::iterator<std::forward_iterator_tag,T>。我實現vector的迭代器大概是這個樣子：

template<typename T>

class viterator:public std::iterator<std::forward_iterator_tag,T>{}

后面會給出完整的代碼，std::iterator<std::forward_iterator_tag,T>的源碼如下：

template<class _Category,
    class _Ty,
    class _Diff = ptrdiff_t,
    class _Pointer = _Ty *,
    class _Reference = _Ty&>
    struct iterator
    {    // base type for all iterator classes
           typedef _Category iterator_category;
           typedef _Ty value_type;
           typedef _Diff difference_type;
           typedef _Diff distance_type;    // retained
           typedef _Pointer pointer;
           typedef _Reference reference;
    };

Iterator其中沒有任何成員，只是定義了一組類型，所以繼承它并不會讓你的struct變大，這組類型是STL的內部契約，STL中的函數假設每個迭代器都定義了這些類型，所以只要你的迭代器定義了這些類型，就可以和STL函數集合一起使用。

我的vector實現源碼如下：

#ifndef _CVECTOR_H_
#define _CVECTOR_H_

namespace cth
{
    class NoCopy
    {
    public: 
        inline NoCopy(){}
        NoCopy(const NoCopy&);
        NoCopy& operator=(const NoCopy&); 
    };

    template<typename T>
    class viterator:public std::iterator<std::forward_iterator_tag,T>
    {
    public: 
        viterator()
        {
            t=NULL;
        }
        viterator(T* t_)
        {
            t=t_;
        }
        viterator(const viterator& other)
        {
            t=other.t;
        }
        viterator& operator=(const viterator& other)
        {
            t=other.t;
            return *this;
        }

        viterator& operator++()
        {
            t++;
            return *this;
        } 
        viterator operator++(int)
        {
            viterator iter=*this;
            t++;
            return iter;
        } 
        viterator operator+(int count)
        {
            viterator iter=*this;
            iter.t+=count;
            return iter;
        } 
        viterator& operator--()
        {
            t--;
            return *this;
        } 
        viterator operator--(int)
        {
            viterator iter=*this;
            t--;
            return iter;
        } 
        viterator operator-(int count)
        {
            viterator iter=*this;
            iter.t-=count;
            return iter;
        }

        int operator-(const viterator& other)
        { 
            return t-other.t;
        } 
        int operator-(const viterator& other)const
        { 
            return t-other.t;
        }

        T& operator*()
        {
            return *t;
        } 
        const T& operator*() const
        {
            return *t;
        }

        T* operator->()
        {
            return t;
        }
        const T* operator->() const
        {
            return t;
        }

        inline bool operator!=(const viterator& other)
        {
            return t!=other.t;
        }
        inline bool operator!=(const viterator& other)const
        {
            return t!=other.t;
        }

        inline bool operator==(const viterator& other)
        {
            return t==other.t;
        }
        inline bool operator==(const viterator& other)const
        {
            return t==other.t;
        }

        inline bool operator<(const viterator& other)
        {
            return t<other.t;
        }
        inline bool operator<(const viterator& other)const
        {
            return t<other.t;
        }

        inline bool operator<=(const viterator& other)
        {
            return t<=other.t;
        }
        inline bool operator<=(const viterator& other)const
        {
            return t<=other.t;
        }

        inline bool operator>(const viterator& other)
        {
            return t>other.t;
        }
        inline bool operator>(const viterator& other)const
        {
            return t>other.t;
        }

        inline bool operator>=(const viterator& other)
        {
            return t>=other.t;
        } 
        inline bool operator>=(const viterator& other)const
        {
            return t>=other.t;
        } 
    private: 
        T* t;
    };


    template<typename T>
    class cvector:public NoCopy
    {
    public: 
        typedef viterator<T> iterator;//viterator<T>就是對一個指針的包裝，所以完全可以用T*代替viterator <T>
        typedef const viterator<T> const_iterator;

        //typedef T* iterator;
        //typedef const T* const_iterator;
        cvector()
        {
            initData(0);
        } 
        cvector(int capa,const T& val=T())
        { 
            initData(capa);
            newCapacity(capacity_);
            for (int i=0;i<size_;i++) 
                buf[i]=val; 
        } 
        cvector(const_iterator first,const_iterator last)
        {  
            initData(last-first);
            newCapacity(capacity_);
            iterator iter=iterator(first); 
            int index=0;
            while(iter!=last)
                buf[index++]=*iter++;
        }

        ~cvector()
        {
            if (buf)
            {
                delete[] buf;
                buf=NULL;
            }
            size_=capacity_=0;
        }
        void clear()
        {
            if (buf)
                erase(begin(),end());
        }

        void push_back(const T& t)
        {
            if (size_==capacity_)
            {
                int capa=calculateCapacity();
                newCapacity(capa);
            }
            buf[size_++]=t;
        }
        void pop_back()
        { 
            if (!empty())
                erase(end() - 1); 
        }

        int insert(const_iterator iter,const T& t )
        {  
            int index=iter-begin();
            if (index<=size_)
            {
                if (size_==capacity_)
                {
                    int capa=calculateCapacity();
                    newCapacity(capa);
                }
                memmove(buf+index+1,buf+index,(size_-index)*sizeof(T)); 
                buf[index]=t;
                size_++;
            } 
            return index;
        }
        iterator erase(const_iterator iter)
        {
            int index=iter-begin(); 
            if (index<size_ && size_>0)
            {
                memmove(buf+index ,buf+index+1,(size_-index)*sizeof(T)); 
                buf[--size_]=T();
            } 
            return iterator(iter); 
        }

        iterator erase(const_iterator first,const_iterator last)
        { 
            iterator first_=iterator(first);
            iterator last_=iterator(last); 
            while(first_<=last_--) 
                erase(first_);  
            return iterator(first_);
        }

        T& front()
        { 
            assert(size_>0);
            return buf[0];
        }
        T& back()
        { 
            assert(size_>0);
            return buf[size_-1];
        }
        T& at(int index)
        { 
            assert(size_>0);
            return buf[index];
        }
        T& operator[](int index)
        { 
            assert(size_>0 && index>=0 && index<size_);
            return buf[index];
        }

        bool empty() const
        {
            return size_==0; 
        }
        int size() const
        {
            return size_;
        }
        int capacity() const
        {
            return capacity_;
        }

        iterator begin()
        {  
            return iterator(&buf[0]); 
        } 
        iterator end()
        {  
            return iterator(&buf[size_]); 
        }

    private: 
        void newCapacity(int capa)
        { 
            capacity_=capa;
            T* newBuf=new T[capacity_];
            if (buf)
            {
                memcpy(newBuf,buf,size_*sizeof(T)); 
                delete [] buf;
            } 
            buf=newBuf;
        }

        inline int calculateCapacity()
        {
            return capacity_*3/2+1 ;
        }

        inline void initData(int capa)
        {
            buf=NULL;
            size_=capacity_=capa>0?capa:0;
        }
        int size_; 
        int capacity_ ;
        T* buf; 
    };



    struct Point
    {
        Point(int x_=0,int y_=0):x(x_),y(y_){}
        int x,y;
    };

    bool operator<(const Point& p1,const Point& p2)
    {
        if(p1.x<p2.x)
        {
            return true;
        }else if(p1.x>p2.x)
        {
            return false;
        }
        return p1.y<p2.y;
    }

    void cvectorTest()
    {
        cvector<Point> vect;
        for (int i=0;i<10;i++)
        {
            Point p(i,i); 
            vect.push_back(p);
        }

        cvector<Point>::iterator iter=vect.begin(); 
        while (iter!=vect.end())
        {
            cout<< "[" << iter->x << " " << iter->y <<"], ";
            ++iter;
        }
        iter=vect.begin()+5; 
        vect.insert(iter,Point(55,55)); 
        iter=vect.end()-3; 
        vect.insert(iter,Point(77,77));
        cout<<endl<<endl<<"插入兩個元素后："<<endl;
        iter=vect.begin(); 
        while (iter!=vect.end())
        {
            cout<< "[" << iter->x << " " << iter->y <<"], ";
            ++iter;
        }
        std::sort(vect.begin(),vect.end());
        cout<<endl<<endl<<"排序后："<<endl;
        iter=vect.begin(); 
        while (iter!=vect.end())
        {
            cout<< "[" << iter->x << " " << iter->y <<"], ";
            ++iter;
        }
        vect.erase(vect.begin()+10);
        vect.erase(vect.begin()+10);
        cout<<endl<<endl<<"刪除之前新增的兩個元素"<<endl;
        iter=vect.begin(); 
        while (iter!=vect.end())
        {
            cout<< "[" << iter->x << " " << iter->y <<"], ";
            ++iter;
        }
        vect.clear();
        cout<<endl<<endl<<"執行clear之后"<<endl;
        cout<<"size="<<vect.size()<<",capacity="<<vect.capacity();

        cvector<Point> vect1;
        for (int i=10;i<20;i++)
        {
            Point p(i,i); 
            vect1.push_back(p);
        }
        cout<<endl<<endl<<"從別的cvector復制數據:"<<endl;

        cvector<Point> vect2(vect1.begin(),vect1.end());
        vect2.pop_back();
        vect2.pop_back();
        for(int i=0;i<vect2.size();i++)
        {
            cout<<"["<<vect2[i].x<<","<<vect2[i].y<<"], ";
        }

        cout<<endl; 
    }

}

#endif

View Code

實例代碼級運行結果如下：

    struct Point
    {
        Point(int x_=0,int y_=0):x(x_),y(y_){}
        int x,y;
    };

    bool operator<(const Point& p1,const Point& p2)
    {
        if(p1.x<p2.x)
        {
            return true;
        }else if(p1.x>p2.x)
        {
            return false;
        }
        return p1.y<p2.y;
    }

    void cvectorTest()
    {
        cvector<Point> vect;
        for (int i=0;i<10;i++)
        {
            Point p(i,i); 
            vect.push_back(p);
        }

        cvector<Point>::iterator iter=vect.begin(); 
        while (iter!=vect.end())
        {
            cout<< "[" << iter->x << " " << iter->y <<"], ";
            ++iter;
        }
        iter=vect.begin()+5; 
        vect.insert(iter,Point(55,55)); 
        iter=vect.end()-3; 
        vect.insert(iter,Point(77,77));
        cout<<endl<<endl<<"插入兩個元素后："<<endl;
        iter=vect.begin(); 
        while (iter!=vect.end())
        {
            cout<< "[" << iter->x << " " << iter->y <<"], ";
            ++iter;
        }
        std::sort(vect.begin(),vect.end());
        cout<<endl<<endl<<"排序后："<<endl;
        iter=vect.begin(); 
        while (iter!=vect.end())
        {
            cout<< "[" << iter->x << " " << iter->y <<"], ";
            ++iter;
        }
        vect.erase(vect.begin()+10);
        vect.erase(vect.begin()+10);
        cout<<endl<<endl<<"刪除之前新增的兩個元素"<<endl;
        iter=vect.begin(); 
        while (iter!=vect.end())
        {
            cout<< "[" << iter->x << " " << iter->y <<"], ";
            ++iter;
        }
        vect.clear();
        cout<<endl<<endl<<"執行clear之后"<<endl;
        cout<<"size="<<vect.size()<<",capacity="<<vect.capacity();

        cvector<Point> vect1;
        for (int i=10;i<20;i++)
        {
            Point p(i,i); 
            vect1.push_back(p);
        }
        cout<<endl<<endl<<"從別的cvector復制數據:"<<endl;
         
        cvector<Point> vect2(vect1.begin(),vect1.end());
        vect2.pop_back();
        vect2.pop_back();
        for(int i=0;i<vect2.size();i++)
        {
            cout<<"["<<vect2[i].x<<","<<vect2[i].y<<"], ";
        }
         
        cout<<endl; 
    }

之后還會有list，set，map等的實現，敬請期待......

posted @ 2014-05-19 21:06 古文觀芷閱讀(44340) 評論(4) 收藏舉報

刷新頁面返回頂部

《STL系列》之vector原理及實現

公告