《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); 
        }