随笔-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 阅读(3519) 评论(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。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理