Vector底层实现
vector的三个私有成员
:_start 记录初始位置
, _finish记录有效字符
, _endofstoage 记录容量大小
vector会存储的类型不同 ，所以要用模版来定类型
typedef T* iterator;
iterator _start;
iterator _finish;
iterator _endofstoage;
也就是T*
构造函数的方法很多可以用迭代器的范围来构造
//用迭代器构造的构造函数
传过来的是它的迭代器的类型我们也用它的类型来接收不比加* &
三个属性先初始化
只要根据传过来的范围来push_back（）即可
push_back函数后面会实现
构造是也可以根据n分val来构造所以这个功能也需要提供
传过来的是n个用size_t接收因为n必须是>=0的 而val是根据类型所以用模版类型接受
有些情况下val会不传参 那么我们就会提供他的默认构造 （注意在C++中 ，内置类型也是有默认构造的）
三个属性初始话
先用reserve函数创建n个空间
在分别push_back（）添加val
//构造n个val的构造函数
vector(size_t n, const T& val = T())
: _start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
因为某些情况第一个参数是int 第二个参数也是int会调用到迭代器的函数因为这两个类型更加适配 ，所以会出问题 ，所以需要再提供一个第一个参数为int的相同函数 ，来避免这种情况
//构造n个val的构造函数
//因为用int会调用到其他函数 所以为了区分 单独写出一个第一个为int
vector(int n, const T& val = T())
: _start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
reserve(n);
for (int i = 0; i < n; ++i)
{
push_back(val);
}
}
swap函数
这个函数是用来给拷贝构造使用
交换类的三个属性成员
//交换
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstoage, v._endofstoage);
}
拷贝构造
拷贝的本质是把一个有数据的拷贝给一个无数据的 ，只需要用这个无数据的迭代器去调用迭代器构造 ，给一个临时tmp ，最后再用这个无数据的与临时tmp交换 即可
因为传过来的是另一个vector所以必须用vector<T>接收 C++传参是特别需要注意的 ，真的很容易乱
//拷贝构造
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
vector<T> tmp(v.begin(), v.end());//复用用迭代器构造的构造函数
swap(tmp);
}
赋值重载
v1=v2 是两个vector的数据赋值所以它的返回值必须是vector<t> 而传参数时也必须是vector<t>
函数本质也是交换 ，所以直接调用swap 这里之所以能直接调用而不影响到v2是因为函数是用传值传参 ，它是不会影响到v2本体的 ，（现代写法）
返回时是返回本体 （*this）
vector<T>& operator=(vector<T> v)//赋值重载 不用引用 现代写法
{
swap(v);//现代写法
return *this;
}
析构函数
判断是否为空当不为空时才需要析构 如果为空去析构会崩溃
把数据释放 ，并且它三个属性置空
// 资源管理
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstoage = nullptr;
}
}
迭代器部分
vector的迭代器本质就是指针 根据传进来的类型 iterator就是这个类型的指针
并且迭代器分为const版本和非const版本
所以需要提供两个版本
//迭代器
typedef T* iterator;
typedef const T* const_iterator;
注意end返回的是你的实际有效字符而不是你的的空间多大
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
size
你的有效字符 _finish 而_finish实际上是有效字符的下一个位置
所以需要减去初始的位置得到它真正的有效字符
size_t size() const
{
return _finish - _start;
}
capacity
计算的是vector的空间大小也就是你的记录空间大小减去初始位置
size_t capacity() const
{
return _endofstoage - _start;
}
【】重载
vector是支持随意访问的 ，所以【】的重载必不可少
返回的是vector里存储的类型 实际上就是模版类型 因为传出去也代表它需要改变所以需要传引用
T& operator[](size_t n)
{
assert(n < size());
//return *(_start + n);
return _start[n]; //这个也可以
}
【】重载有些地方是需要提供const版本不允许更改的版本
const T& operator[](size_t n) const
{
assert(n < size());
//return *(_start + n);
return _start[n]; //这个也可以
}
reserve
扩容空间 但不初始化
这里需要注意扩容后的三个属性更新出现的问题 正常运行会崩溃 。 问题的关键：开辟一个新空间时 ，他们三个的类型是指针！而不是下标 ，一个地址更新 ，去用以前的指针 ，去更改这个新的地址 ，是会崩溃的 ，而下标是固定位置 ，地址在怎么更新 ，下标的位置就是固定的 。
我们需要记录原先的有效字符个数
正常比较和扩容 ，只是这里用memcpy函数时 ，出现嵌套情况时 ，会出现浅拷贝情况
需要用赋值深拷贝
另外两个要更新时 ，要用预先存储好的数据来更新详情看注释！
void reserve(size_t n)
{
size_t sz = size();
if (n > capacity())
{
T* tmp = new T[n];
if (_start) //如果_start为空时 就不需要拷贝数据了
{
//memcpy(tmp, _start, size() * sizeof(T));//把_start的数据拷贝到tmp //这样做 在嵌套时 ，会发生浅拷贝
for (size_t i = 0; i < size(); i++)//正确做法是直接赋值 在vector<vector> 这种嵌套时 是深拷贝
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;//更新过后 _start就不再是nullptr
}
//_finish = _start + size();//× 结果为空 解引用无地址 赋值会崩溃 ==_start+(_finish-_start) 这里的_finsih最后是等于空
//而跳出函数后 _finish解引用再赋值会崩溃 因为空地址无法赋值
_finish = _start + sz;//√ 结果为_start有地址 。解引用能赋值 ==_start+0 == 这里先让原先的_finish-_start==0 再+上0 因为_start已经更新过了 所以需要在开头记录_size的大小
//而更新过的_start不是空 这时候在调用size _finish-_start就不是0了 而是其他值了
_endofstoage = _start + n;
}
resize
扩容 ，但会初始化数据
要扩容的大小大于实际空间大小（不是实际字符大小！）时 ，我们先开需要大小空间即可
如果n大于实际字符大小时
我们需要在实际字符的位置后开始不断添加val（要初始化的值）
如果n小于实际字符大小
那么就把实际字符大小改为 n个 即初始值+n
void resize(size_t n, T val = T())
{
if (n > capacity())
{
reserve(n);
}
if (n > size())
{
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
_finish = _start + n;
}
}
push_back()
添加字符
只要需要添加字符的函数 ，基本是需要检查空间是否足够的
一种情况为实际空间为0还未扩容时默认给它开4个空间 ，如果有空间 ，但满时 ，扩二倍即可（为什么扩容二倍？没什么！因为合适或者1.5倍 ，扩容其他倍数要么太小 ，要么太大 ，1.5和2的倍数是适应性最好的）
扩容好后 ，或者空间足够时
直接在有效字符的位置添加字符 （为什么不先++？因为前面说过 ，实际字符的指针实际上是指向实际字符的后一位 ，所以你要添加 ，直接在实际字符指针添加即可）
最后添加好后 ，实际字符++ （这也是返回真实字符时 ，不直接返回_finish ，而是返回_finish-_start
因为嵌套的作用 ，此函数在insert函数实现后 ，可以直接复用insert就可以了
void push_back(const T& x)
{
/*if (_finish == _endofstoage)
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}
*_finish = x;
++_finish;*/
insert(end(), x);
}
pop_back()
此函数只需要把实际字符--即可
先判断合法性 ，实际字符必须大于初始值
因为嵌套的作用 ，此函数在erase函数实现后 ，可以直接复用erase就可以了
void pop_back()
{
/* if (_finish > _start)
{
--_finish;
}*/
erase(end() - 1);
}
insert
注意此函数会有迭代器失效问题！
通常此函数是不需要返回的 ，但因为迭代器失效问题 ，所以必须有返回值 ，因为返回的就是此指向此函数的指针也就是T*模版类型指针 所以用重命名的iterator即可
pos是指向要插入的位置 ，这个函数都是用指针来指针 ，所以没办法使用下标 ，这也是它的失效的问题之一！
首先判断是否需要扩容
上面的reserve提到过 ，扩容后 ，_start的地址是会变的 ，而pos也是迭代器 ，它也是指向这个地址的指针 ，它不会跟着更新地址而变化 。
所以这个pos它指向的位置 ，是原来_start的位置 ，而这个位置已经被释放了 ，所以再去使用这个pos时 ，是会崩溃的！
所以为了防止这种情况 ，我们需要先记录这个pos的位置 ，等待_start的地址更新好后 ，我们要根据原先这个存储好pos的位置 ，在去用_start的地址 ，去更新新的pos位置 ，并且pos的位置不变 。
然后开始移动pos后的数据给pos位置开出空间 ，能让val插入
最后在pos的位置插入val
再++实际空间
最后需要放回插入后的位置
那么我们在使用是 ，需要用迭代器去接收 ，才能防止迭代器的失效 ，因为原先的迭代器已经失效 ，需要根据这个返回值 ，来更新迭代器 。
while (it != v1.end())
{
if (*it % 2 == 0)
{
it = v1.insert(it, 100);//因为迭代器更新数据会失效 所以要用it接收 防止失效
++ it;//返回的是插入的位置 再次++会再次遇到原来的位置 所以插入后 要自增++一次
}
++it;
}
erase
此函数存在迭代器失效的问题
正常删除即可
只是返回必须返回删除后的下一个值
使用这个函数时 ，也是需要迭代器用函数返回值接收 ，来更新迭代器
while (it != v.end())
{
if ((*it) % 2 == 0)
{
it = v.erase(it);
}
else
{
++it;
}
}
clear
置空功能 ，只需要把有效字符置为初始值即可 。
//置空
void clear()
{
_finish = _start;//把有效字符改为初始
}
接下来是源码
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace moxuan
{
template<class T>
class vector
{
public:
//迭代器
typedef T* iterator;
typedef const T* const_iterator;
//默认无参构造
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{}
//用迭代器构造的构造函数
template <class InputIterator>
vector(InputIterator first, InputIterator last)
: _start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}
//构造n个val的构造函数
vector(size_t n, const T& val = T())
: _start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
//构造n个val的构造函数
//因为用int会调用到其他函数 所以为了区分 单独写出一个第一个为int
vector(int n, const T& val = T())
: _start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
reserve(n);
for (int i = 0; i < n; ++i)
{
push_back(val);
}
}
//交换
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstoage, v._endofstoage);
}
//拷贝构造
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
vector<T> tmp(v.begin(), v.end());//复用用迭代器构造的构造函数
swap(tmp);
}
vector<T>& operator=(vector<T> v)//赋值重载 不用引用 现代写法
{
swap(v);//现代写法
return *this;
}
// 资源管理
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstoage = nullptr;
}
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstoage - _start;
}
void reserve(size_t n)
{
size_t sz = size();
if (n > capacity())
{
T* tmp = new T[n];
if (_start) //如果_start为空时 就不需要拷贝数据了
{
//memcpy(tmp, _start, size() * sizeof(T));//把_start的数据拷贝到tmp //这样做 在嵌套时 ，会发生浅拷贝
for (size_t i = 0; i < size(); i++)//正确做法是直接赋值 在vector<vector> 这种嵌套时 是深拷贝
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;//更新过后 _start就不再是nullptr
}
//_finish = _start + size();//× 结果为空 解引用无地址 赋值会崩溃 ==_start+(_finish-_start) 这里的_finsih最后是等于空
//而跳出函数后 _finish解引用再赋值会崩溃 因为空地址无法赋值
_finish = _start + sz;//√ 结果为_start有地址 。解引用能赋值 ==_start+0 == 这里先让原先的_finish-_start==0 再+上0 因为_start已经更新过了 所以需要在开头记录_size的大小
//而更新过的_start不是空 这时候在调用size _finish-_start就不是0了 而是其他值了
_endofstoage = _start + n;
}
void resize(size_t n, T val = T())
{
if (n > capacity())
{
reserve(n);
}
if (n > size())
{
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
_finish = _start + n;
}
}
void push_back(const T& x)
{
/*if (_finish == _endofstoage)
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}
*_finish = x;
++_finish;*/
insert(end(), x);
}
void pop_back()
{
/* if (_finish > _start)
{
--_finish;
}*/
erase(end() - 1);
}
T& operator[](size_t n)
{
assert(n < size());
//return *(_start + n);
return _start[n]; //这个也可以
}
const T& operator[](size_t n) const
{
assert(n < size());
//return *(_start + n);
return _start[n]; //这个也可以
}
//插入 注意会有迭代器失效问题!
iterator insert(iterator pos, const T& val)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endofstoage)
{
size_t n = pos - _start;//因为更新start后 pos无法跟着更新 所以要记录pos的位置
size_t newsize = capacity() == 0 ? 4 : capacity() * 2;
reserve(newsize);
pos = _start + n;
}
iterator cur = _finish - 1;
while (cur >= 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++;//返回删除后的下一个位置
}
//置空
void clear()
{
_finish = _start;//把有效字符改为初始
}
private:
iterator _start;
iterator _finish;
iterator _endofstoage;
};
接下来是用来测试这个vector的可行性 杨辉三角
大家可以源码拿去编译器上 ，然后调用这个test4函数即可
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv;
vv.resize(numRows);
for (size_t i = 0; i < vv.size(); ++i)
{
// 杨辉三角 ，每行个数依次递增
vv[i].resize(i + 1, 0);
// 第一个和最后一个初始化成1
vv[i][0] = 1;
vv[i][vv[i].size() - 1] = 1;
}
for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
if (vv[i][j] == 0)
{
// 中间位置等于上一行j-1 和 j个相加
vv[i][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[i].size(); ++j)
{
cout << vv[i][j] << " ";
}
cout << endl;
}
cout << endl;
return vv;
}
};
void test4()
{
vector<vector<int>> ret = Solution().generate(5);
for (size_t i = 0; i < ret.size(); ++i)
{
for (size_t j = 0; j < ret[i].size(); ++j)
{
cout << ret[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
}
这就是本文章的全部内容 ，感谢您能观看到这里 ，如有问题请评论或私信 。感谢观看！
声明：本站所有文章 ，如无特殊说明或标注 ，均为本站原创发布 。任何个人或组织 ，在未征得本站同意时 ，禁止复制 、盗用 、采集 、发布本站内容到任何网站 、书籍等各类媒体平台 。如若本站内容侵犯了原著者的合法权益 ，可联系我们进行处理 。
