Vector底层实现

Vector底层实现

vector的三个私有成员
:_start   记录初始位置
                        , _finish 记录有效字符
                        , _endofstoage  记录容量大小
vector会存储的类型不同，所以要用模版来定类型 
typedef T* iterator;
iterator _start;
                iterator _finish;
                iterator _endofstoage;
也就是T*
 
构造函数的方法很多 可以用迭代器的范围来构造
//用迭代器构造的构造函数
传过来的是它的迭代器的类型 我们也用它的类型来接收 不比加* &
 三个属性先初始化
只要根据传过来的范围来push_back（）即可
push_back函数后面会实现

1.         //用迭代器构造的构造函数
2.         template <class InputIterator>
3.         vector(InputIterator first, InputIterator last)
4.             : _start(nullptr)
5.             , _finish(nullptr)
6.             , _endofstoage(nullptr)
7.         {
8.             while (first != last)
9.             {
10.                 push_back(*first);
11.                 ++first;
12.             }
13.         }

复制代码

 
构造是 也可以根据n分val来构造 所以这个功能也需要提供
传过来的是n个 用size_t接收 因为n必须是>=0的  而val是根据类型 所以用模版类型接受  
有些情况下 val会不传参  那么我们就会提供他的默认构造  （注意 在C++中，内置类型也是有默认构造的）
三个属性初始话
先用reserve函数创建n个空间
在分别push_back（）添加val

1.         //构造n个val的构造函数
2.         vector(size_t n, const T& val = T())
3.             : _start(nullptr)
4.             , _finish(nullptr)
5.             , _endofstoage(nullptr)
6.         {
7.             reserve(n);
8.             for (size_t i = 0; i < n; ++i)
9.             {
10.                 push_back(val);
11.             }
12.         }

复制代码

 
因为某些情况 第一个参数是int  第二个参数也是int 会调用到迭代器的函数 因为这两个类型更加适配，所以会出问题，所以需要再提供一个第一个参数为int的相同函数，来避免这种情况

1.     //构造n个val的构造函数
2.         //因为用int会调用到其他函数 所以为了区分 单独写出一个第一个为int
3.         vector(int n, const T& val = T())
4.             : _start(nullptr)
5.             , _finish(nullptr)
6.             , _endofstoage(nullptr)
7.         {
8.             reserve(n);
9.             for (int i = 0; i < n; ++i)
10.             {
11.                 push_back(val);
12.             }
13.         }

复制代码

 
swap函数
这个函数是用来给拷贝构造使用
交换类的三个属性成员

1.         //交换
2.         void swap(vector<T>& v)
3.         {
4.             std::swap(_start, v._start);
5.             std::swap(_finish, v._finish);
6.             std::swap(_endofstoage, v._endofstoage);
7.         }

复制代码

 
拷贝构造
拷贝的本质是把一个有数据的拷贝给一个无数据的，只需要用这个无数据的迭代器去调用迭代器构造，给一个临时tmp，最后再用这个无数据的与临时tmp交换  即可
因为传过来的是另一个vector 所以必须用vector 接收  C++传参是特别需要注意的，真的很容易乱

1.         //拷贝构造
2.         vector(const vector<T>& v)
3.             : _start(nullptr)
4.             , _finish(nullptr)
5.             , _endofstoage(nullptr)
6.         {
7.             vector<T> tmp(v.begin(), v.end());//复用用迭代器构造的构造函数
8.             swap(tmp);
9.         }

复制代码

 
赋值重载
v1=v2  是两个vector的数据赋值 所以它的返回值必须是vector  而传参数时 也必须是vector 
函数本质也是交换，所以直接调用swap  这里之所以能直接调用 而不影响到v2 是因为函数是用传值传参，它是不会影响到v2本体的，（现代写法）
返回时是返回本体 （*this）

1.     vector<T>& operator=(vector<T> v)//赋值重载   不用引用  现代写法
2.         {
3.             swap(v);//现代写法
4.             return *this;
5.         }

复制代码

 
析构函数
判断是否为空 当不为空时才需要析构  如果为空 去析构 会崩溃
把数据释放，并且它三个属性置空

1.     // 资源管理
2.         ~vector()
3.         {
4.             if (_start)
5.             {
6.                 delete[] _start;
7.                 _start = _finish = _endofstoage = nullptr;
8.             }
9.         }

复制代码

 
迭代器部分
vector的迭代器本质就是指针  根据传进来的类型  iterator就是这个类型的指针
并且迭代器分为const版本和非const版本 
所以需要提供两个版本

1.         //迭代器
2.         typedef T* iterator;
3.         typedef const T* const_iterator;

复制代码

 
注意 end返回的是你的实际有效字符 而不是你的的空间多大

1.         iterator begin()
2.         {
3.             return _start;
4.         }
6.         iterator end()
7.         {
8.             return _finish;
9.         }
11.         const_iterator begin() const
12.         {
13.             return _start;
14.         }
16.         const_iterator end() const
17.         {
18.             return _finish;
19.         }

复制代码

 
size 
你的有效字符 _finish  而_finish实际上是有效字符的下一个位置
所以需要减去初始的位置 得到它真正的有效字符

1.         size_t size() const
2.         {
3.             return _finish - _start;
4.         }

复制代码

 
capacity
计算的是vector的空间大小 也就是你的记录空间大小减去初始位置

1.         size_t capacity() const
2.         {
3.             return _endofstoage - _start;
4.         }

复制代码

 
【】重载
vector是支持随意访问的，所以【】的重载必不可少
返回的是vector里存储的类型  实际上就是模版类型  因为传出去也代表它需要改变 所以需要传引用

1.         T& operator[](size_t n)
2.         {
3.             assert(n < size());
4.             //return *(_start + n);
5.             return _start[n]; //这个也可以
6.         }

复制代码

 
【】重载 有些地方是需要提供const版本 不允许更改的版本

1.         const T& operator[](size_t n) const
2.         {
3.             assert(n < size());
4.             //return *(_start + n);
5.             return _start[n]; //这个也可以
6.         }

复制代码

 
reserve
扩容空间  但不初始化
这里需要注意扩容后的三个属性更新出现的问题  正常运行会崩溃。  问题的关键：开辟一个新空间时，他们三个的类型是指针！而不是下标，一个地址更新，去用以前的指针，去更改这个新的地址，是会崩溃的，而下标是固定位置，地址在怎么更新，下标的位置就是固定的。
 
我们需要记录原先的有效字符个数
正常比较和扩容，只是这里用memcpy函数时，出现嵌套情况时，会出现浅拷贝情况
需要用赋值 深拷贝
 
另外两个要更新时，要用预先存储好的数据来更新 详情看注释！

1.         void reserve(size_t n)
2.         {
3.             size_t sz = size();
4.             if (n > capacity())
5.             {
6.                 T* tmp = new T[n];
7.                 if (_start)  //如果_start为空时 就不需要拷贝数据了
8.                 {
9.                     //memcpy(tmp, _start, size() * sizeof(T));//把_start的数据拷贝到tmp  //这样做 在嵌套时，会发生浅拷贝
10.                     for (size_t i = 0; i < size(); i++)//正确做法是直接赋值  在vector<vector> 这种嵌套时 是深拷贝
11.                     {
12.                         tmp[i] = _start[i];
13.                     }
14.                     delete[] _start;
15.                 }
16.                 _start = tmp;//更新过后 _start就不再是nullptr
17.             }
18.             //_finish = _start + size();//×  结果为空 解引用无地址 赋值会崩溃 ==_start+(_finish-_start)  这里的_finsih最后是等于空  
19.             //而跳出函数后 _finish解引用再赋值会崩溃 因为空地址无法赋值
21.             _finish = _start + sz;//√ 结果为_start有地址。解引用能赋值   ==_start+0 ==  这里先让原先的_finish-_start==0  再+上0  因为_start已经更新过了 所以需要在开头记录_size的大小
22.             //而更新过的_start不是空 这时候在调用size _finish-_start就不是0了 而是其他值了
23.             _endofstoage = _start + n;
24.         }

复制代码

 
resize
扩容，但会初始化数据
要扩容的大小 大于实际 空间大小（不是实际字符大小！） 时，我们先开需要大小空间即可
如果n大于实际字符大小时
我们需要在实际字符的位置后开始不断添加val（要初始化的值）
如果n小于实际字符大小
那么就把实际字符大小改为  n个  即 初始值+n

1.         void resize(size_t n, T val = T())
2.         {
3.             if (n > capacity())
4.             {
5.                 reserve(n);
6.             }
8.             if (n > size())
9.             {
10.                 while (_finish < _start + n)
11.                 {
12.                     *_finish = val;
13.                     ++_finish;
14.                 }
15.             }
16.             else
17.             {
18.                 _finish = _start + n;
19.             }
20.         }

复制代码

 
push_back()
添加字符
只要需要添加字符的函数，基本是需要检查空间是否足够的
一种情况为 实际空间为0 还未扩容时 默认给它开4个空间，如果有空间，但满时，扩二倍即可（为什么扩容二倍？没什么！因为合适 或者1.5倍，扩容其他倍数要么太小，要么太大，1.5和2的倍数是适应性最好的）
扩容好后，或者空间足够时
直接在有效字符的位置添加字符 （为什么不先++？因为前面说过，实际字符的指针实际上是指向实际字符的后一位，所以你要添加，直接在实际字符指针添加即可）
最后添加好后，实际字符++ （这也是返回真实字符时，不直接返回_finish，而是返回_finish-_start
 
因为嵌套的作用，此函数在insert函数实现后，可以直接复用insert就可以了

1.         void push_back(const T& x)
2.         {
3.             /*if (_finish == _endofstoage)
4.             {
5.                 size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
6.                 reserve(newCapacity);
7.             }
9.             *_finish = x;
10.             ++_finish;*/
12.             insert(end(), x);
13.         }

复制代码

 
pop_back()
此函数只需要把实际字符--即可
先判断合法性，实际字符必须大于初始值
 
因为嵌套的作用，此函数在erase函数实现后，可以直接复用erase就可以了

1.         void pop_back()
2.         {
3.             /*        if (_finish > _start)
4.                     {
5.                         --_finish;
6.                     }*/
7.             erase(end() - 1);
8.         }

复制代码

 
insert
注意此函数会有迭代器失效问题！
通常此函数是不需要返回的，但因为迭代器失效问题，所以必须有返回值，因为返回的就是此指向此函数的指针 也就是T* 模版类型指针  所以用重命名的iterator即可  
pos是指向要插入的位置，这个函数都是用指针来指针，所以没办法使用下标，这也是它的失效的问题之一！
首先判断是否需要扩容
上面的reserve提到过，扩容后，_start的地址是会变的，而pos也是迭代器，它也是指向这个地址的指针，它不会跟着更新地址而变化。
所以这个pos它指向的位置，是原来_start的位置，而这个位置已经被释放了，所以再去使用这个pos时，是会崩溃的！ 
所以为了防止这种情况，我们需要先记录这个pos的位置，等待_start的地址更新好后，我们要根据原先这个存储好pos的位置，在去用_start的地址，去更新新的pos位置，并且pos的位置不变。
 
然后开始移动pos后的数据 给pos位置开出空间，能让val插入
最后在pos的位置插入val
再++实际空间
最后需要放回插入后的位置
那么我们在使用是，需要用迭代器去接收，才能防止迭代器的失效，因为原先的迭代器已经失效，需要根据这个返回值，来更新迭代器。

1.     while (it != v1.end())
2.     {
3.         if (*it % 2 == 0)
4.         {
5.             it = v1.insert(it, 100);//因为迭代器更新数据会失效 所以要用it接收 防止失效
6.             ++ it;//返回的是插入的位置 再次++会再次遇到原来的位置 所以插入后 要自增++一次
7.         }
8.         ++it;
9.     }

复制代码

 
erase
此函数存在迭代器失效的问题
正常删除即可
只是返回必须返回删除后的下一个值
使用这个函数时，也是需要迭代器用函数返回值接收，来更新迭代器

1.     while (it != v.end())
2.     {
3.         if ((*it) % 2 == 0)
4.         {
5.             it = v.erase(it);
6.         }
7.         else
8.         {
9.             ++it;
10.         }
12.     }

复制代码

 
clear
置空功能，只需要把有效字符置为初始值即可。

1.         //置空
2.         void clear()
3.         {
4.             _finish = _start;//把有效字符改为初始
5.         }

复制代码

 
 
接下来是源码

1. #pragma once#include#includeusing namespace std;namespace moxuan{    template    class vector    {    public:        //迭代器
2.         typedef T* iterator;
3.         typedef const T* const_iterator;        //默认无参构造        vector()            :_start(nullptr)            , _finish(nullptr)            , _endofstoage(nullptr)        {}        //用迭代器构造的构造函数
4.         template <class InputIterator>
5.         vector(InputIterator first, InputIterator last)
6.             : _start(nullptr)
7.             , _finish(nullptr)
8.             , _endofstoage(nullptr)
9.         {
10.             while (first != last)
11.             {
12.                 push_back(*first);
13.                 ++first;
14.             }
15.         }        //构造n个val的构造函数
16.         vector(size_t n, const T& val = T())
17.             : _start(nullptr)
18.             , _finish(nullptr)
19.             , _endofstoage(nullptr)
20.         {
21.             reserve(n);
22.             for (size_t i = 0; i < n; ++i)
23.             {
24.                 push_back(val);
25.             }
26.         }        //构造n个val的构造函数
27.         //因为用int会调用到其他函数 所以为了区分 单独写出一个第一个为int
28.         vector(int n, const T& val = T())
29.             : _start(nullptr)
30.             , _finish(nullptr)
31.             , _endofstoage(nullptr)
32.         {
33.             reserve(n);
34.             for (int i = 0; i < n; ++i)
35.             {
36.                 push_back(val);
37.             }
38.         }        //交换
39.         void swap(vector<T>& v)
40.         {
41.             std::swap(_start, v._start);
42.             std::swap(_finish, v._finish);
43.             std::swap(_endofstoage, v._endofstoage);
44.         }        //拷贝构造
45.         vector(const vector<T>& v)
46.             : _start(nullptr)
47.             , _finish(nullptr)
48.             , _endofstoage(nullptr)
49.         {
50.             vector<T> tmp(v.begin(), v.end());//复用用迭代器构造的构造函数
51.             swap(tmp);
52.         }        vector<T>& operator=(vector<T> v)//赋值重载   不用引用  现代写法
53.         {
54.             swap(v);//现代写法
55.             return *this;
56.         }        // 资源管理
57.         ~vector()
58.         {
59.             if (_start)
60.             {
61.                 delete[] _start;
62.                 _start = _finish = _endofstoage = nullptr;
63.             }
64.         }        iterator begin()
65.         {
66.             return _start;
67.         }
69.         iterator end()
70.         {
71.             return _finish;
72.         }
74.         const_iterator begin() const
75.         {
76.             return _start;
77.         }
79.         const_iterator end() const
80.         {
81.             return _finish;
82.         }        size_t size() const
83.         {
84.             return _finish - _start;
85.         }        size_t capacity() const
86.         {
87.             return _endofstoage - _start;
88.         }        void reserve(size_t n)
89.         {
90.             size_t sz = size();
91.             if (n > capacity())
92.             {
93.                 T* tmp = new T[n];
94.                 if (_start)  //如果_start为空时 就不需要拷贝数据了
95.                 {
96.                     //memcpy(tmp, _start, size() * sizeof(T));//把_start的数据拷贝到tmp  //这样做 在嵌套时，会发生浅拷贝
97.                     for (size_t i = 0; i < size(); i++)//正确做法是直接赋值  在vector<vector> 这种嵌套时 是深拷贝
98.                     {
99.                         tmp[i] = _start[i];
100.                     }
101.                     delete[] _start;
102.                 }
103.                 _start = tmp;//更新过后 _start就不再是nullptr
104.             }
105.             //_finish = _start + size();//×  结果为空 解引用无地址 赋值会崩溃 ==_start+(_finish-_start)  这里的_finsih最后是等于空  
106.             //而跳出函数后 _finish解引用再赋值会崩溃 因为空地址无法赋值
108.             _finish = _start + sz;//√ 结果为_start有地址。解引用能赋值   ==_start+0 ==  这里先让原先的_finish-_start==0  再+上0  因为_start已经更新过了 所以需要在开头记录_size的大小
109.             //而更新过的_start不是空 这时候在调用size _finish-_start就不是0了 而是其他值了
110.             _endofstoage = _start + n;
111.         }        void resize(size_t n, T val = T())
112.         {
113.             if (n > capacity())
114.             {
115.                 reserve(n);
116.             }
118.             if (n > size())
119.             {
120.                 while (_finish < _start + n)
121.                 {
122.                     *_finish = val;
123.                     ++_finish;
124.                 }
125.             }
126.             else
127.             {
128.                 _finish = _start + n;
129.             }
130.         }        void push_back(const T& x)
131.         {
132.             /*if (_finish == _endofstoage)
133.             {
134.                 size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
135.                 reserve(newCapacity);
136.             }
138.             *_finish = x;
139.             ++_finish;*/
141.             insert(end(), x);
142.         }        void pop_back()
143.         {
144.             /*        if (_finish > _start)
145.                     {
146.                         --_finish;
147.                     }*/
148.             erase(end() - 1);
149.         }        T& operator[](size_t n)
150.         {
151.             assert(n < size());
152.             //return *(_start + n);
153.             return _start[n]; //这个也可以
154.         }        const T& operator[](size_t n) const
155.         {
156.             assert(n < size());
157.             //return *(_start + n);
158.             return _start[n]; //这个也可以
159.         }        //插入 注意会有迭代器失效问题!        iterator insert(iterator pos, const T& val)        {            assert(pos >= _start && pos = pos)            {                *(cur + 1) = *cur;                --cur;            }            *pos = val;            ++_finish;            return pos;        }        //删除        iterator erase(iterator pos)//返回删除后的下一个位置        {            assert(pos >= _start && pos < _finish);            iterator it = pos+1;            while (it != _finish)            {                *(it-1) = *it;                ++it;            }            --_finish;            return pos++;//返回删除后的下一个位置        }        //置空
160.         void clear()
161.         {
162.             _finish = _start;//把有效字符改为初始
163.         }    private:        iterator _start;        iterator _finish;        iterator _endofstoage;    };

复制代码

 
接下来是用来测试这个vector的可行性  杨辉三角
大家可以源码拿去编译器上，然后调用这个test4函数即可
[code]    class Solution {    public:        vector generate(int numRows) {            vector vv;            vv.resize(numRows);            for (size_t i = 0; i < vv.size(); ++i)            {                // 杨辉三角，每行个数依次递增                vv.resize(i + 1, 0);                // 第一个和最后一个初始化成1                vv[0] = 1;                vv[vv.size() - 1] = 1;            }            for (size_t i = 0; i < vv.size(); ++i)            {                for (size_t j = 0; j < vv.size(); ++j)                {                    if (vv[j] == 0)                    {                        // 中间位置等于上一行j-1 和 j个相加                        vv[j] = vv[i - 1][j - 1] + vv[i - 1][j];                    }                }            }            for (size_t i = 0; i < vv.size(); ++i)            {                for (size_t j = 0; j < vv.size(); ++j)                {                    cout