青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆-91  評論-137  文章-0  trackbacks-0
首先是vector的定義
        template <typename T>
        class vector
        {
        };

讓我們先來看看vector中的一些別名
        public:
            typedef T         value_type;
            typedef T*        pointer;
            typedef T&        reference;
            typedef const T&  const_reference;
            typedef size_t    size_type;
            typedef ptrdiff_t difference_type;
            typedef const T* const_iterator;
            typedef reverse_iterator<const_iterator, value_type, size_type, difference_type> const_reverse_iterator;
            typedef T* iterator;
            typedef reverse_iterator<iterator, value_type, size_type, difference_type> reverse_iterator;
由上可見,正如上一篇所說,vector的迭代器是由原生的指針來實現的。

下面是其內部的成員變量
        protected:
            typedef vector<T>    self;
            typedef allocator<T> Alloc;

            iterator start;
            iterator finish;
            iterator end_of_element;
start:指向vector的起始地址
finish:指向最后一個元素的后一個元素的地址
end_of_element:指向已申請內存塊的結束位置(finish總是小于或等于end_of_element)

在STL中從begin到end總是以一個前閉后開的形式來表示的,形如[begin,end),這樣做的好處是可以使代碼寫的更簡潔:
        template <typename Iterator, typename T>
        Iterator find(Iterator first, Iterator last, const T& value)
        {
            while(first != last && *first != value) ++first;
            return first;
        }

下面來看看vector中最基本的構造函數和析構函數
            vector() : start(0), finish(0), end_of_element(0)
            {
            }

            ~vector()
            {
                destruct(start, end_of_element);
                if (start != 0) Alloc::deallocate(start, end_of_element - start);
            }
這里將其中的3個成員變量都填充為0。
上一篇所說,在STL中是將內存分配與對象初始化分開的,同樣對象析構與內存釋放也是被分開的。

然后是其begin和end方法,用來獲取第一個元素和最后一個元素的后一個元素的迭代器。
            inline iterator begin()
            {
                return start;
            }

            inline const_iterator begin()const
            {
                return start;
            }

            inline iterator end()
            {
                return finish;
            }

            inline const_iterator end()const
            {
                return finish;
            }

front和back分別被用來獲取第一個元素和最后一個元素
            inline reference front()
            {
                return *begin();
            }

            inline const_reference front()const
            {
                return *begin();
            }

            inline reference back()
            {
                return *(end() - 1);
            }

            inline const_reference back()const
            {
                return *(end() - 1);
            }

empty、size、capacity分別被用來判別容器是否為空、容器內元素的個數和容器的大小
            inline bool empty()const
            {
                return begin() == end();
            }

            inline const size_type size()const
            {
                return size_type(end() - begin());
            }

            inline const size_type capacity()const
            {
                return size_type(end_of_element - begin());
            }

由于在vector的頭部插入元素會使所有元素后移,應此它被設計為單向的,只能由尾部插入或移除數據
            void push_back(const T& x)
            {
                if (end_of_element != finish)
                {
                    construct(&*finish, x);
                    ++finish;
                }
                else
                {
                    insert_aux(end(), x);
                }
            }

            inline void pop_back()
            {
                --finish;
                destruct<T>(finish, has_destruct(*finish));
            }
當然從頭部移除數據也并非不可以,可以使用erase方法來移除頭部的數據,erase方法將會在后面的部分作出說明。

我們先來看一下insert_aux這個方法,在插入元素時幾乎都使用到了這個方法。
            void insert_aux(const iterator position, const T& x)
            {
                if(finish != end_of_element)
                {
                    construct(&*finish, *(finish - 1));
                    T x_copy = x;
                    copy_backward(position, finish - 1, finish);
                    *position = x_copy;
                    ++finish;
                }
                else
                {
                    const size_type old_size = size();
                    const size_type new_size = old_size == 0 ? 2 : old_size * 2;
                    iterator tmp = Alloc::allocate(new_size);
                    uninitialized_copy(begin(), position, tmp);
                    iterator new_position = tmp + (position - begin());
                    construct(&*new_position, x);
                    uninitialized_copy(position, end(), new_position + 1);
                    destruct(begin(), end());
                    Alloc::deallocate(begin(), old_size);
                    end_of_element = tmp + new_size;
                    finish = tmp + old_size + 1;
                    start = tmp;
                }
            }
在容器還有足夠的空間時,首先將從position位置到finish位置的元素整體后移一個位置,最后將要被插入的元素寫入到原position的位置同時改變finish指針的值。
若空間不足時,首先根據原有空間的大小的一倍來申請內存,然后將元素從原有位置的begin到position拷貝到新申請的內存中,然后在新申請內存的指定位置插入要插入的元素值,最后將余下的部分也拷貝過來。然后將原有元素析構掉并把內存釋放掉。

為何不使用reallocate?
reallocate的本意并不是在原有內存的位置增加或減少內存,reallocate首先會試圖在原有的內存位置增加或減少內存,若失敗則會重新申請一塊新的內存并把原有的數據拷貝過去,這種操作本質上等價于重新申請一塊內存,應此這里使用的是allocate而并非reallocate。

然后讓我們來看一下insert和erase方法
            inline iterator insert(iterator position, const T& x)
            {
                const size_type pos = position - begin();
                if(finish != end_of_element && position == end())
                {
                    construct(&*finish, x);
                    ++finish;
                }
                else insert_aux(position, x);
                return begin() + pos;
            }

            iterator erase(iterator position)
            {
                destruct(position, has_destruct(*position));
                if (position + 1 != end())
                {
                    copy(position + 1, end(), position);
                }
                --finish;
                return position;
            }
若是要在最后插入一個元素且容器的剩余空間還足夠的話,直接將元素插入到finish的位置,并將finish指針后移一位即可。若容器空間不夠或不是插在最后一個的位置,則調用insert_aux重新分配內存或插入。
刪除時首先析構掉原有元素,若被刪元素不是最后一個元素,則將后面的所有元素拷貝過來,最后將finish指針前移一個位置。

最后讓我們來看一下其中重載的運算符
            self& operator=(const self& x)
            {
                if(&x == thisreturn *this;
                size_type const other_size = x.size();
                if(other_size > capacity())
                {
                    destruct(start, finish);
                    Alloc::deallocate(start, capacity());
                    start = Alloc::allocate(other_size);
                    finish = uninitialized_copy(x.begin(), x.end(), start);
                    end_of_element = start + other_size;
                }
                else
                {
                    finish = uninitialized_copy(x.begin(), x.end(), start);
                }
                return *this;
            }

            inline reference operator[](size_type n)
            {
                return *(begin() + n);
            }

            inline value_type at(size_type n)
            {
                return *(begin() + n);
            }
由于vector內部用的是原生的指針,應此這些運算符的使用方式和原生指針的并無差異。值得注意的是在做賦值操作時會產生內存的重新分配與拷貝操作。

至此,vector的講解已完成,完整的代碼請到http://qlanguage.codeplex.com下載
posted on 2012-06-17 17:08 lwch 閱讀(3591) 評論(3)  編輯 收藏 引用 所屬分類: STL

評論:
# re: 山寨STL實現之vector[未登錄] 2012-06-18 11:22 | 路人甲
“迭代器”比較麻煩,得做到自己版本的vector的迭代器能拿到std中使用。
  回復  更多評論
  
# re: 山寨STL實現之vector 2012-06-26 00:58 | 朱峰everettjf
學習,
自己最近看了STL源碼剖析,總是在看,卻未想自己實現一個。
  回復  更多評論
  
# re: 山寨STL實現之vector 2012-06-26 09:42 | lwch
@朱峰everettjf
程序還是要靠多寫才行~  回復  更多評論
  
# re: 山寨STL實現之vector 2012-06-30 21:28 | beibei
博主,我剛好也在做這個,但在實現含有兩個迭代器的構造函數時,出了問題:
template<class In>
Vec(In b, In e) {
start=alloc.allocate( e-b );
finish=end_of_element=std::uninitialized_copy( b, e, data );
}
在最后一行出現了error C2665。  回復  更多評論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美久久久久久久| 欧美日韩精品久久久| 狠狠色狠狠色综合| 久久精品国产欧美激情| 欧美一区激情| 亚洲韩日在线| 夜夜嗨av色一区二区不卡| 国产精品另类一区| 久久伊人精品天天| 欧美成人免费观看| 亚洲欧美在线一区| 久久九九免费| 一区二区三区国产在线| 亚洲欧美影院| 亚洲欧洲在线视频| 亚洲永久精品大片| 亚洲精品一区二| 亚洲一区二区三区涩| 亚洲国产欧美日韩精品| 日韩亚洲一区二区| 狠狠久久亚洲欧美| 一本色道久久综合精品竹菊| 国产综合18久久久久久| 亚洲免费黄色| 在线播放中文字幕一区| 正在播放欧美一区| 91久久精品美女| 午夜久久一区| 99av国产精品欲麻豆| 欧美在线一区二区三区| 亚洲视频综合在线| 免费黄网站欧美| 欧美在线一二三| 欧美日韩国产在线| 欧美激情精品久久久六区热门 | 久久久蜜臀国产一区二区| 亚洲视频福利| 玖玖视频精品| 久久久久久久网站| 欧美视频网址| 亚洲黄网站在线观看| 国产视频一区欧美| 亚洲一本视频| 在线视频免费在线观看一区二区| 久久久噜噜噜久久| 午夜精品美女久久久久av福利| 欧美成人性生活| 蘑菇福利视频一区播放| 国产一区二区丝袜高跟鞋图片 | 久久人人97超碰精品888| 国产精品盗摄一区二区三区| 亚洲精品中文在线| 亚洲免费观看| 欧美高清成人| 亚洲国产欧美一区| 亚洲国产一区在线| 麻豆freexxxx性91精品| 欧美激情二区三区| 欧美激情中文字幕一区二区| 黄色成人在线网址| 久久久久久久综合| 久久一区中文字幕| 亚洲风情亚aⅴ在线发布| 久久精品久久综合| 女人天堂亚洲aⅴ在线观看| 在线观看视频免费一区二区三区 | 亚洲第一视频| 亚洲欧洲在线视频| 欧美精彩视频一区二区三区| 亚洲国内自拍| 亚洲一区三区电影在线观看| 欧美日韩一区在线视频| 在线一区二区视频| 欧美一区二区三区在线播放| 国产日韩精品视频一区二区三区| 欧美一区二区三区免费观看视频| 久久精品视频99| 亚洲大胆女人| 欧美精品高清视频| 亚洲视频一起| 久久一区二区三区四区五区| 亚洲黄色小视频| 欧美三区在线观看| 性欧美大战久久久久久久久| 久久亚洲一区二区| 99热在这里有精品免费| 国产精品v日韩精品| 欧美一级在线视频| 亚洲韩国日本中文字幕| 亚洲欧美伊人| 亚洲高清在线观看一区| 欧美日韩精品久久久| 欧美专区日韩专区| 最新国产の精品合集bt伙计| 亚洲欧美日韩精品久久亚洲区 | 久久国产精品久久久久久| 黑人一区二区三区四区五区| 欧美精品123区| 欧美伊久线香蕉线新在线| 亚洲国产毛片完整版| 性欧美超级视频| 亚洲日韩视频| 国产视频在线一区二区| 欧美精品麻豆| 久久精品亚洲精品| 一区二区欧美精品| 欧美成人一区二区| 欧美在线看片a免费观看| 亚洲精品视频啊美女在线直播| 国产伦精品一区二区三区| 欧美成人高清| 久久国产精品免费一区| 在线一区二区三区四区五区| 亚洲大胆人体在线| 久久婷婷成人综合色| 亚洲欧美在线看| 99视频+国产日韩欧美| 狠狠干综合网| 国产视频一区二区三区在线观看| 欧美日韩国产免费| 美女在线一区二区| 久久精品人人做人人爽电影蜜月 | 久久色在线播放| 亚洲欧美在线观看| 在线中文字幕日韩| 亚洲美女区一区| 亚洲国产另类 国产精品国产免费| 国产精品一卡二卡| 国产精品草草| 欧美精品日韩综合在线| 免费观看一级特黄欧美大片| 久久久久国色av免费观看性色| 亚洲欧美国产日韩中文字幕| 一个色综合导航| a91a精品视频在线观看| 亚洲毛片av| 国产日韩视频| 国产欧美日韩一区二区三区在线观看| 欧美成人69av| 欧美第十八页| 欧美精品18videos性欧美| 久久综合九色综合网站| 久热re这里精品视频在线6| 久久久青草青青国产亚洲免观| 久久久国产精品一区二区中文| 久久爱www.| 老司机午夜精品| 欧美成年人视频网站| 欧美精品videossex性护士| 欧美成人a视频| 欧美日韩在线精品| 国产精品毛片| 国产亚洲一区二区三区在线播放| 国产自产在线视频一区| 亚洲国产精品一区二区尤物区| 亚洲国产欧美一区二区三区同亚洲| 亚洲第一精品夜夜躁人人躁| 亚洲精品久久久蜜桃| 亚洲图片欧洲图片日韩av| 香蕉av福利精品导航| 久久精品国产亚洲高清剧情介绍| 久久夜色精品国产欧美乱| 欧美大片免费观看| 亚洲毛片网站| 香港久久久电影| 老司机一区二区三区| 欧美日韩亚洲网| 国产日产欧美精品| 亚洲国产一区二区视频| 亚洲在线不卡| 久久综合一区二区| 亚洲精品日产精品乱码不卡| 亚洲自拍偷拍一区| 久久九九国产精品怡红院| 欧美日韩精品是欧美日韩精品| 欧美性猛片xxxx免费看久爱| 影音先锋久久| 亚洲一区二区三区精品动漫| 久久免费视频在线观看| 欧美福利电影在线观看| 亚洲视频一起| 欧美成人在线免费视频| 国产日韩欧美二区| 日韩视频永久免费观看| 久久久999| 艳妇臀荡乳欲伦亚洲一区| 久久亚洲综合| 国产日韩欧美在线看| 日韩一区二区精品| 老司机精品导航| 亚洲免费在线电影| 欧美日韩精品二区第二页| 亚洲成人在线视频播放| 午夜一级在线看亚洲| 亚洲第一免费播放区| 欧美在线影院| 国产日韩av高清| 亚洲视频福利| 亚洲精品国产精品国产自| 久久另类ts人妖一区二区 |