请选择 进入手机版 | 继续访问电脑版

Vector源码的注释

[复制链接]
卓小兔 发表于 2021-1-2 19:43:34 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
vector

[code]#include#include#include#include//#include//思考:1.各个函数实现各个部门的功能,然后给出将各自的接口,只要该该函数是坚固的,即该思量的情况都有思量,即可以举行放心即函数调用使用其函数,来组合成一个大的功能//2.对于容器,其算头不算尾,(begin(),end)范围内的元素指的是begin元素到末端元素,end()指向了末端元素的下一个元素//迭代器能查抄边界是因为两个指针来完成的,即设计了两个指针来实现容器内是否有对象。using namespace std;namespace yhp//yhp名字空间域{        // 异常        class out_of_range//超出范围类        {        public:                out_of_range(char *ptr) :str(ptr) {}//构造函数                ~out_of_range() {}//析构函数                const char * what() const { return str; }//常方法        protected:                char *str;        };        // 填充和拷贝函数        template        void Swap(T &a, T &b)//交换传入的值,引用使得实在参的作用域扩大        {                T c = a; //如果是容器 =颠末了重载                a = b;                b = c;//可以交换任意两个数的内容,值交换值的内容,指针交换指针的指向,vector《范例》 即两个容器的内容        }        //         template         _FI uninitialized_fill_n(_FI first, Size n, const T& x)//初始化填充,对象对空间,将开辟的空间填充n个x值,reserve开辟的空间类似        {                for (; n--; ++first)                {                        new(&*first) T(x);//通过模板举行 范例推演后对 first指向的空间举行定向new(调用构造函数)                        // new (static_cast(&*first))    typename iterator_traits::value_type(x);                }                return first;//返回最后一个元素的下一个下标        }        // Mem = object;         template        _FI uninitialized_copy(_II first, _II last, _FI result)//初始化拷贝函数(对象到空间),带uninitialized都需要重定位        {                for (; first != last; ++result, ++first)//每次将first空间的对象 来构造result的空间                {                        *result = *first;//error的,只能作用于内存范例,其需要举行对象到空间 变动构造函数                        //new(&*result) _FI(*first);                        //new (static_cast(&*result))    typename iterator_traits::value_type(*first);                }                return result;//返回目标范围中最后一个元素的迭代器        }        // object = object;        template        _OutI copy(_II first, _II last, _OutI result)//拷贝函数(对象到对象)        {                for (; first != last; ++result, ++first)//说明result已经有对象了,resize开辟的空间类似                {                        *result = *first;                }                return result;        }        template         void fill(_FI first, _FI last, const T& val)//填充函数(对象到对象,直接赋值)        {                while (first != last)//resize开辟的空间类似,while循环需要注意条件是否会形成死循环                {                        *first = val;                        ++first;                }        }        template//模板有 _BI1 , _BI2 两种 需要至少两个参数推演        _BI2 copy_backward(_BI first, _BI last, _BI2 result)//向后拷贝 (对象到对象),0也是对象   如果其容量满了呢,不会重新分配空间吗,会发生异常        {                while (last != first)                {                        *(--result) = *(--last);//竟然是前置--,为什么?不对吧,噢末端迭代器指向的是该元素的下一个元素,所以直接传入指针就有问题,所谓算头不算尾                        //向后复制元素范围,将范围(first,last)中从末端开始的元素复制到result终止的范围中。                }                return result; //函数返回目标范围中第一个元素的迭代器。        }        template         _OutI reverse_copy(_BI first, _BI last, _OutI result)//逆反拷贝        {                while (first != last)                {                        --last;//为什么先--了,噢末端迭代器指向的是该元素的下一个元素                        *result = *last;//对象直接赋值                        ++result;                }                return result;//返回指向末端的迭代器        }        template         inline void construct(_T* p)//一个参数的构造函数        {                new (p) _T();//变动T的构造函数给p空间构造        }        template         inline void construct(_T1*p, const _T2& value)//模板构造函数        {                new (p) _T1(value); //变动T1的构造函数        }        template         inline void destroy(_Tp*  pointer)//析构函数,析构对象,空间还保存        {                pointer->~_Tp();        }        template         inline void destroy(_FI first, _FI last)//析构一个一连内存的对象        {                for (; first != last; ++first)                {                        destroy(&*first);                }        }        template        inline size_t distance(_RAI _F, _RAI _L)//盘算L-F两数之差 隔断由于L是指向该元素下一个元素的迭代器 相当于 l-f+1 即长度        {                return _L - _F;        }        //向量基类有两个目标。首先,它的申请空间函数和释放空间函数分配(但不初始化)存储。        //这使得异常安全更容易。        //其次,基类封装了SGI样式分配器和标准一致性分配器之间的所有差别        template         class Vector_base        {        public:                Vector_base() : _M_start(0), _M_finish(0), _M_end_of_storage(0) {} //不带参构造,M_start =M_finish=M_end_of_storage=0 ,且finish原来该指向末端元素的下一个元素,即三个指针相等时访问发生异常吧                Vector_base(size_t n) : _M_start(0), _M_finish(0), _M_end_of_storage(0)//带一个参数                 {                        _M_start = _M_allocate(n);//申请空间,m_start指向给空间的首所在                        _M_finish = _M_start;//finish没有指向末端元素的下一个元素说明该空间没有对象                        _M_end_of_storage = _M_start + n;//指向开辟空间的末端所在的下一个元素                }                ~Vector_base()//析构函数,将(_M_start, _M_end_of_storage - _M_star)这个区域内的元素析构掉                {                        _M_deallocate(_M_start, _M_end_of_storage - _M_start);//变动逐个析构                }        protected:                _Tp * _M_start;//指向开辟空间的首所在                _Tp* _M_finish;//指向末端元素的下一个元素,当start=finish说明该空间内没有对象(设计出头向对象?)                _Tp* _M_end_of_storage;指向开辟空间的末端所在的下一个元素                _Tp* _M_allocate(size_t n)//类内函数,查找在声明中用到的名字,包罗数据成员和函数成员声明中用到的参数范例,第二步才是函数成员体内的名字。所以没有像main函数里需要前面声明来给编译器                {                        return (_Tp*)malloc(sizeof(_Tp)*n);// 然后指向该申请n个TP范例巨细的空间的首所在                }                void _M_deallocate(_Tp* p, size_t n) //                 {                        free(p);//释放p所指向的空间,free会去读取malloc头部文件里所生存的                }        };        template         class vector : protected Vector_base//vector掩护继承Vector_base。。。 当一个类派生自掩护基类时,基类的公有和掩护成员将成为派生类的掩护成员。        {        private:                typedef Vector_base _Base;//父类        public:                typedef _Tp                                        value_type;//将value_type 当做_TP的范例                typedef value_type*                        pointer;//指针范例                typedef const value_type*        const_pointer;//常指针                typedef value_type*                        iterator;//迭代器,从typedef来看迭代器和指针一模一样啊                typedef const value_type*        const_iterator;//常性迭代器                typedef value_type&                        reference;//引用                typedef const value_type&        const_reference;//常性引用                typedef size_t                                size_type;//范例为size_type 无符号范例                typedef int                                        difference_type;//有符号范例        public:                // 迭代器                iterator begin() { return _M_start; }//这里迭代器的范例照旧和指针一样啊。。                const_iterator begin() const { return _M_start; }//只是返回范例使得 返回的值为const                iterator end() { return _M_finish; }//好吧 finish,对于容器的利用,使得该迭代器指向末端元素的下一个元素                const_iterator end() const { return _M_finish; }//只是返回范例使得 返回的值为const                //  容量                size_type size() const//返回元素个数                {                        return size_type(end() - begin());//所谓算头不算尾,由于end()得到的是末端元素的下一个元素,则实在类似n-1 +1-0                }                size_type max_size() const//返回堆上能容纳Tp元素的理论最大值                {                        return size_type(-1) / sizeof(_Tp); //由于size_type(-1) 转成无符号是该内存位数的最大的无符号数                }                size_type capacity() const//容量                {                        return size_type(_M_end_of_storage - begin());//不+1的原因,_M_end_of_storage指向末端元素的下一个元素                }                bool empty() const                {                        return begin() == end();//果然 没有对象就是 _M_finish=_M_start                }                // 元素访问                reference operator[](size_type n) { return *(begin() + n); }//重载[]运算符,[]与最近的标识符联合,即与对象联合  *(this->begin()+n)索引第N个数 返回该内存,且可修改                const_reference operator[](size_type n) const { return *(begin() + n); }//常方法   运行常对象调用   返回该值,只能当做右值                reference at(const size_type pos) //at检测边界,同[],引用数组的内存                {                        if ((size_type)(_M_finish - _M_start) = xlen)//当前元素个数大于即是需要赋值的元素个数,则只用析构对象                                {                                        iterator i = copy(x.begin(), x.end(), begin());//直接对对象覆盖?                                        destroy(i, _M_finish);//这个是对反面的数举行析构                                }                                else//x的元素大于元素个数而小于容器个数   需要确定三个数  当前元素个数  、当前容量  、 赋值对象的元素                                {                                        copy(x.begin(), x.begin() + size(), _M_start);//直接举行对象与对象的覆盖拷贝                                        uninitialized_copy(x.begin() + size(), x.end(), _M_finish);//对反面没有对象的数举行对象和空间的初始化拷贝                                }                                _M_finish = _M_start + xlen;//                        }                        return *this;//返回容器                }                void reserve(size_type n)//预留空间,if大于此时的空间需要重新申请空间                {                        if (capacity() < n) //如果当前容器小于预留的n,应该将end指针,不对,空间还需要开辟,所以需要重新更换容器                        {                                const size_type old_size = size();//元素个数                                iterator tmp = M_allocate_and_copy(n, _M_start, _M_finish);//申请n个空间,且将该空间举行对象和空间的拷贝                                destroy(_M_start, _M_finish);//析构原来的容器                                _M_deallocate(_M_start, _M_end_of_storage - _M_start);//释放原来容器的空间                                _M_start = tmp;//让当前容器指向当前新形成的空间                                _M_finish = tmp + old_size;//指向当前容器元素的最后一个元素的下一个元素                                _M_end_of_storage = _M_start + n;//指向当前容器最大容量的下一个元素                        }                }                void assign(size_type n, const _Tp& val)//清空原来的容器对象,然后添加n个val对象 如果n大于容器则重写当前容器的元素个数                {                        if (n > capacity())//大于容量                        {                                vector tmp(n, val);//构造函数开辟n个内存,且将空间填充成val对象                                tmp.swap(*this);//this当前容器,tmp新构造的容器。 容器的交换  传入的参数范例是vector 即                        }                        else if (n > size())//大于元素个数而小于容量                        {                                fill(begin(), end(), val);//重写元素对象                                _M_finish = uninitialized_fill_n(_M_finish, n - size(), val);//且还要继承举行对没有元素对象的空间举行重写                        }                        else//小于元素个数                        {                                erase(fill_n(begin(), n, val), end());//先举行对象填充 填充后将                        }                }                void push_back(const _Tp& x)//在末端添加数据                {                        if (_M_finish != _M_end_of_storage)//如果元素个数不大于容器                        {                                construct(_M_finish, x);//将M_finish指向的空间构造x对象                                ++_M_finish;//指向下一个元素                        }                        else//元素个数大于容量                        {                                _M_insert_aux(end(), x);//在end位置插入x对象,如果元素个数大于容量跟换容器继承插入                        }                }                void swap(vector& x)//容器之间交换对象                   {                        Swap(_M_start, x._M_start);                        Swap(_M_finish, x._M_finish);                        Swap(_M_end_of_storage, x._M_end_of_storage);                }                iterator insert(iterator position, const _Tp& x)//插入x 且pos刚好就是是插入点                {                        size_type n = position - begin();//首元素到pos范围内的元素个数                        if (_M_finish != _M_end_of_storage && position == end())//元素巨细不即是容器巨细且pos指向末端元素的下一个元素                        {                                construct(_M_finish, x);//直接push_back(x);                                ++_M_finish;                        }                        else//容量不敷或插入位置不在末端                        {                                _M_insert_aux(position, x);//变动该函数,将x插入进该容器的pos位,且该函数还会处置惩罚当元素个数大于容量的情况还能插入 M_insert_aux(position, x)插入                                //一般运用于插入的位置是插入前面,会将插入元素后的后移在插入                        }                        return begin() + n;//返回指向插入的位置的迭代器                }                void insert(iterator position, const_iterator first, const_iterator last)//重载插入,在pos位置该插入插入一个容器或数组的对象                 {                        if (first != last)//确保插入的容器是有对象的                        {                                //size_type n = 0;                                //distance(first, last, n);                                size_type n = last - first;//元素个数                                if (size_type(_M_end_of_storage - _M_finish) >= n)//容量能容纳参加的元素                                {                                        const size_type elems_after = _M_finish - position;//需要移动的元素个数                                        iterator old_finish = _M_finish;                                        if (elems_after > n)//移动的数能容纳添加的数                                        {                                                uninitialized_copy(_M_finish - n, _M_finish, _M_finish);//将_M_finish - n, _M_finish范围内的对象拷贝到 _M_finish反面                                                 _M_finish += n;                                                copy_backward(position, old_finish - n, old_finish);//后移覆盖  移动出能容纳放入容量元素的位置                                                copy(first, last, position);//将first, last范围内的对象从pos处开始拷贝                                        }                                        else//移动的空间(有对象)不敷直接放入                                        {                                                uninitialized_copy(first + elems_after, last, _M_finish);//先将不敷移动的元素添加到末端                                                _M_finish += n - elems_after;                                                uninitialized_copy(position, old_finish, _M_finish);//将pos反面的,到原来容器的末端的元素拷贝到此时容器的末端                                                _M_finish += elems_after;                                                copy(first, first + elems_after, position);//将需要参加的元素覆盖原来的对象 有对象了真贫苦啊                                        }                                }                                else//需要扩展容器                                {                                        const size_type old_size = size();                                        const size_type len = old_size + max(old_size, n);//新的容量巨细                                        iterator new_start = _M_allocate(len);                                        iterator new_finish = new_start;                                        //__STL_TRY                                         {                                                new_finish = uninitialized_copy(_M_start, position, new_start);//_M_start, position 初始化拷贝新容器                                                new_finish = uninitialized_copy(first, last, new_finish);//将插入元素放入容器                                                new_finish = uninitialized_copy(position, _M_finish, new_finish);//将原来容器pos后的对象放入此时容器的末端                                        }                                        //__STL_UNWIND((destroy(new_start,new_finish), _M_deallocate(new_start,len)));                                        destroy(_M_start, _M_finish);//析构_M_start, _M_finish容器内的对象                                        _M_deallocate(_M_start, _M_end_of_storage - _M_start);//释放容器空间                                        _M_start = new_start;//指向新的容器                                        _M_finish = new_finish;                                        _M_end_of_storage = new_start + len;                                }                        }                }                void insert(iterator pos, size_type n, const _Tp& x)//重载,只是多了一个参数   在pos位置插入n个x  和插入一个容器元素差不多                {                        if (n != 0)                        {                                if (size_type(_M_end_of_storage - _M_finish) >= n)                                {                                        _Tp x_copy = x;                                        const size_type elems_after = _M_finish - pos;                                        iterator old_finish = _M_finish;                                        if (elems_after > n)                                        {                                                uninitialized_copy(_M_finish - n, _M_finish, _M_finish);//扩展对象                                                 _M_finish += n;                                                copy_backward(pos, old_finish - n, old_finish);//后移n位                                                fill(pos, pos + n, x_copy);//直接填充                                        }                                        else//当后移对象不敷覆盖,需要先构建对象                                        {                                                uninitialized_fill_n(_M_finish, n - elems_after, x_copy);//将需要插入的对象的后部门先构造在此时对象的末端                                                _M_finish += n - elems_after;                                                uninitialized_copy(pos, old_finish, _M_finish);//将原来容器里的对象全初始化拷贝的末端                                                _M_finish += elems_after;                                                fill(pos, old_finish, x_copy);//将还需要插入的前部门直接填充(覆盖)                                        }                                }                                else//容量不敷                                {                                        const size_type old_size = size();                                        const size_type len = old_size + max(old_size, n);                                        iterator new_start = _M_allocate(len);                                        iterator new_finish = new_start;                                        //__STL_TRY                                         {                                                new_finish = uninitialized_copy(_M_start, pos, new_start);                                                new_finish = uninitialized_fill_n(new_finish, n, x);                                                new_finish = uninitialized_copy(pos, _M_finish, new_finish);                                        }                                        //__STL_UNWIND((destroy(new_start,new_finish),_M_deallocate(new_start,len)));                                        destroy(_M_start, _M_finish);                                        _M_deallocate(_M_start, _M_end_of_storage - _M_start);                                        _M_start = new_start;                                        _M_finish = new_finish;                                        _M_end_of_storage = new_start + len;                                }                        }                }                void pop_back()//将末端元素弹出                {                        --_M_finish;                        destroy(_M_finish);//举行析构,空间还没有释放                }                iterator erase(iterator position)//擦除pos下标的对象     传入的是迭代器范例                {                        if (position + 1 != end())//如果擦除下标不是最后一个元素                        {                                copy(position + 1, _M_finish, position);//postion作为拷贝的起始  左移                        }                        --_M_finish;//擦除下标是最后一个下标则类似pop_back();                        destroy(_M_finish);                        return position;                }                iterator erase(iterator first, iterator last)//擦除(first,last)范围内的对象                {                        iterator i = copy(last, _M_finish, first);//将(last,到fisrt)的元素对象拷贝到first,且i是当前元素的下一个元素                        destroy(i, _M_finish);//析构i到最后元素范围内的对象                        _M_finish = _M_finish - (last - first);//finish总是指向最后一个元素的下一个元素                        return first;                }                void resize(size_type new_size, const _Tp& x)//改变了容器的空间 根据new_size对容器巨细举行调治                {                        if (new_size < size())//当想将容器缩小,元素个数大于n   此处size和容量一样大                                erase(begin() + new_size, end());//擦除比n大的部门                        else                                insert(end(), new_size - size(), x);//要想将容器增大,扩容插入new_size-size个元素x                }                void resize(size_type new_size)//只将容器举行改变,若扩容了将其变动构造函数                {                        resize(new_size, _Tp());//对其变动默认构造函数                }                void clear()//清空所有对象                {                        erase(begin(), end());                }        protected:                static void _Xrange()                {                        throw out_of_range("invalid vector subscript");                }                iterator M_allocate_and_copy(size_type n, const_iterator first, const_iterator last)                {                        iterator __result = _M_allocate(n);//迭代器result指向开辟的n个空间                        //__STL_TRY                         {                                uninitialized_copy(first, last, __result);//对开辟的空间举行对象的拷贝                                return __result;//噢,调用初始化拷贝的result指针不会改变主调函数的result (值通报)                        }                        //__STL_UNWIND(M_deallocate(__result, n));                }                void _M_insert_aux(iterator position)//将pos位指定插入一个默认构造的对象  一般运用于插入的位置是插入前面,会将插入元素后的后移在插入                {                        if (_M_finish != _M_end_of_storage)元素个数不大于容量                        {                                construct(_M_finish, *(_M_finish - 1));//添加一个元素,且该元素是最后一个元素拷贝到                                ++_M_finish;                                copy_backward(position, _M_finish - 2, _M_finish - 1);//向后拷贝   将pos,到倒数第二个元素范围内的对象举行后移一位,即覆盖了最后一位对象                                *position = _Tp();//将pos位指定插入一个默认构造的对象                        }                        else                        {                                const size_type old_size = size(); //元素个数=容量了,需要更换容器                                //const size_type len = old_size != 0 ? 2 * old_size : 1;                                const size_type len = old_size <  4 ? old_size + 1 : (old_size + old_size / 2);//容量小于4则举行元素个数+1递增,如果大于=4则举行1.5倍元素个数递增                                iterator new_start = _M_allocate(len);//指向新容器                                iterator new_finish = new_start;//此时还没用元素                                __STL_TRY//捕捉异常吧                                {                                        new_finish = uninitialized_copy(_M_start, position, new_start);//返回指向末端元素的下一个元素  将原本的容器从起始元素到pos-1个元素拷贝到新的容器里                                construct(new_finish);//构造一个对象在末端元素反面                                ++new_finish;                                new_finish = uninitialized_copy(position, _M_finish, new_finish);//从旧容器pos到最后一个元素拷贝到新容器的反面                                }                                __STL_UNWIND((destroy(new_start, new_finish), _M_deallocate(new_start, len)));                                destroy(begin(), end());//先析构旧容器的对象                                _M_deallocate(_M_start, _M_end_of_storage - _M_start); //释放容器的容量                                _M_start = new_start;//替换容器                                _M_finish = new_finish;                                _M_end_of_storage = new_start + len;                        }                }                void _M_insert_aux(iterator pos, const _Tp& x)//将x插入进该容器的pos位,且该函数还会处置惩罚当元素个数大于容量的情况还能插入                {                        if (_M_finish != _M_end_of_storage)//元素个数不大于容量                        {                                construct(_M_finish, *(_M_finish - 1));//添加一个元素,且该元素是最后一个元素拷贝到                                ++_M_finish;                                _Tp x_copy = x;//应该需要加consrt的吧                                   copy_backward(pos, _M_finish - 2, _M_finish - 1);//向后拷贝   将(pos,到倒数第二个元素范围内的对象举行后移一位                                *pos = x_copy;//将x插入进该容器的pos位                        }                        else                        {                                const size_type old_size = size();                                //const size_type len = old_size != 0 ? 2 * old_size : 1;                                const size_type len = old_size <  4 ? old_size + 1 : (old_size + old_size / 2);                                iterator new_start = _M_allocate(len);                                iterator new_finish = new_start;                                //__STL_TRY                                 {                                        new_finish = uninitialized_copy(_M_start, pos, new_start);                                        construct(new_finish, x);                                        ++new_finish;                                        new_finish = uninitialized_copy(pos, _M_finish, new_finish);                                }                                //__STL_UNWIND((destroy(new_start,new_finish), _M_deallocate(new_start,len)));                                destroy(begin(), end());                                _M_deallocate(_M_start, _M_end_of_storage - _M_start);                                _M_start = new_start;                                _M_finish = new_finish;                                _M_end_of_storage = new_start + len;                        }                }        };        template         inline bool operator==(const vector& x, const vector& y)  //判定两个容器x y是否相同        {                return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());        }}int main(){        yhp::vector vec;//默认构造一个对象        int ar[] = { 12,23,34,45,56,67 };        vec.insert(vec.begin(), ar, ar + 4);//将数组ar[4]的元素插入容器中        for (int i = 0; i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )