stl源码剖析之vector

作者最近在学习c++,学习侯捷的stl源码剖析这本书,但是我觉得里面的内容有些古老并且生涩。比如说alloc,对于一些基础知识不太牢固的同学不是很友好(我建议先细读第二章前4小节,第一级分配器之后的内容可等基础足够再回头弥补),虽然这本书本就不是面对像菜鸟的c++程序员。然一些基础思想,编程方法,可以试着学习学习。 本人在学习c++prime的同时,也曾自己实现过vector等contain。

这是一个实现vector的详细代码,我自己也实现了一份于不同于侯捷老师的vector,有需要的可以留言。。 这里我贴出stl源码剖析里面的代码,并且加了一些注释总体来说说得过去。 我改了一些细节, 可以对照着书上的看。

我标注了我实现的顺序,可以借鉴借鉴。。


#ifndef vector_hpp

#define vector_hpp


#include<iostream>

#include<memory>

#include<algorithm>


template<typenameT>

classvector

{

public:

   /*        1            */

   typedefT                  value_type;            //声明T类型的别名

   typedefvalue_type*         pointer;               //声明T*类型的别名指针

    typedefvalue_type*         iterator;              //声明T*类型的别名迭代器iterator就是迭代器,粘合剂。         vector不需要定义迭代器

   typedefvalue_type&         reference;             //左值

   typedefsize_t              size_type;             //表示距离

   typedefptrdiff_t          difference_type;       //表示指针间的距离

    

   /*        3             */

   //若干构造函数 为了代码的可读性省略了几个微不足道的考虑,如想了解可参考书

   //default构造函数 拷贝构造函数 拷贝复制运算符必不可少

    vector():start(0),finish(0),end_of_storage(0) {  }

    vector(intn,constT& value)

    {

       fill_initialize(n, value);

    }

    

   /*        4             */

   voidfill_initialize(size_typen,constT& value)

    {

       start=allocate_and_fill(n, value);

       finish=start+ n;

       end_of_storage=finish;

    }

    

   /*        5             */

   //原本实现在private中。放至这里是便于程序更加易读性,故放在public

   iteratorallocate_and_fill(size_typen,constT& value)

    {

       iteratorresult =data_allocator.allocate(n);

       std::uninitialized_fill_n(result, n, value);

        

       returnresult;

    }

    

   /*        6             */

   iteratorbegin()

    {

       returnstart;

    }

   iteratorend()

    {

       returnfinish;

    }

   size_typesize()

    {

       returnsize_type(end() -begin());

    }

    

   constsize_typecapacity()const

    {

       returnsize_type(end_of_storage-begin());

    }

    

   constboolempty()const

    {

       returnbegin() ==end();

    }

   //还有frontback函数返回相应的值

   referencefront()                                  //注意是引用类型。下同

    {

       return*begin();

    }

   referenceback()

    {

       return*(end() -1);

    }

    

   /*        7             */

   //写完第六步的一些零零散散的配件下面进入正题push&pop

   voidpush_back(constT& x)

    {

       if(finish!=end_of_storage)

        {

          // iterator p = finish;

           data_allocator.construct(finish, x);

            ++finish;

          // finish = p;

      //     std::cout << x << std::endl;

        }

       else

           insert_aux(finish, x);                      //aux为辅助希腊语为增长-辅助的意思

    }

    

   voidpop_back()

    {

       //--finish;

       data_allocator.destroy(--finish);

        

    }

    

   iteratorearse(iteratorfirst,iteratorlast)

    {

       iteratori =std::copy(last,finish, first);

       autop = i;

       data_allocator.destroy(++p);

       finish=finish- (last - first);

        

       returnfinish;

    }

    

   iteratorearse(iteratorpos)

    {

       if(pos +1!=end())

           std::copy(pos +1,finish, pos);

        --finish;

       data_allocator.destroy(finish);

        

       returnpos;

    }

    

   voidclear()

    {

        earse(begin(),end());

    }

    

   /*

     

     

     */

    

   voidinsert(iteratorpos,size_typen,constT& x)

    {

       if(n !=0)                     //虽然n != 0在这里很微不足道,很渺小。但是依旧要重视

        {

           if(size_type(finish-end_of_storage) >= n)

            {

                T x_copy = x;

               constsize_typeelems_after =finish- pos;

               iteratorold_finish =finish;

                

               if(elems_after >= n)

                {

                   std::uninitialized_copy(finish- n,finish,finish);

                   finish+= n;

                   std::fill(pos, pos + n, x_copy);

                }

               else

                {

                   std::uninitialized_fill_n(finish, n - elems_after, x_copy);

                   finish+= n - elems_after;

                   std::uninitialized_copy(pos, old_finish,finish);

                   finish+= elems_after;

                   std::fill(pos, old_finish, x_copy);

                }

            }

           else

            {

               constsize_typeold_siez =size();

               constsize_typelen = old_siez +std::max(old_siez, n);

                

               iteratornew_start =data_allocator.allocate(len);

               iteratornew_finish =finish;

                

                new_finish =std::uninitialized_copy(start, pos, new_start);

                new_finish =std::uninitialized_fill_n(new_finish, n, x);

                new_finish =std::uninitialized_copy(pos,finish, new_finish);

                

               start= new_start;

               finish= new_finish;

               end_of_storage= new_start + len;

            }

        }

    }

    

    

    

    

    

    

    

    

private:

   /*        2             */

   iteratorstart;                                    //指向第一个的迭代器指针

   iteratorfinish;                                   //指向第一个空闲没有实参的迭代器指针

   iteratorend_of_storage;                           //指向尾后迭代器的迭代器指针

   std::allocator<int> data_allocator;

    

    

   /*        8             */

   //接下来考虑动态数组内存不够的情况

   voidinsert_aux(iteratorposition,constT& x)                 //position :安置;放在适当位置

    {

//

        const size_typeold_size =size();                         //旧的动态数组的大小

       constsize_typelen = old_size !=02* old_size :1;    //如果old_size不为0 * 2否则大小为1

        

       iteratornew_start =data_allocator.allocate(len);     //新建一块动态数组是原来的两倍

       iteratornew_finish = new_start;                       //指向同一个地址

        

        new_finish =std::uninitialized_copy(begin(), position, new_start);     //将原先的vector内的对象拷贝到新的vector

       data_allocator.construct(new_finish, x);         //为新的元素设置为x

        ++new_finish;

        

       //new_finish = uninitialized_copy(position, finish, new_finish);          //这一行跟push_back没有太大关系用途是在insert这个函数因为insert_aux的第一个参数不一定是end()

        

       start= new_start;

       finish= new_finish;

       end_of_storage= new_start + len;

    }

};






版权声明:本文为chaotuan1721原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。