目录
一、内部成员的定义
1.1 STL源码中的成员定义
1.2 My_vector 的成员变量
1.3 实现的成员函数
二、vector 的功能实现
2.1 构造/析构函数
2.2 获取数据函数
2.3 reserve
2.4 push_back
2.5 迭代器
2.6 insert
2.6.1 迭代器失效
2.7 pop_back 与 erase
2.8 拷贝构造函数的实现
2.8.1 传统写法
2.8.2 复用 push_back 实现
2.8.3 现代写法
2.9 赋值运算符重载
2.10 带参的构造函数
2.11 resize 的实现
2.12 深层次的拷贝构造
一、内部成员的定义 1.1 STL源码中的成员定义
STL版本很多,实现 vector 的风格也各不相同,这里我举一个常见、可读性强的版本,来看看他 vector 的成员是如何定义的。
不难发现,vector 中迭代器就是原生指针,而他的成员变量有 statr、finish、end_of_storage三个。
所以我们来以此为标准来定义我们自己 vector。
1.2 My_vector 的成员变量 1.3 实现的成员函数这里先把我们要实现的成员函数以及成员变量罗列出来,接下来我们就会按这个顺序进行实现。
template
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
size_t size() const;
size_t capacity()const;
T& operator[](size_t pos);
const T& operator[](size_t pos) const;
iterator begin();
iterator end();
iterator front();
iterator back();
const_iterator begin() const;
const_iterator end() const;
const_iterator front() const;
const_iterator back() const;
vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr);
//使用(迭代器)区间的构造函数
template
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr);
//特殊的构造函数
vector(size_t n, const T& val = T());
vector(int n, const T& val = T());
//拷贝构造函数 传统&优化
void swap(vector& v);
vector(const vector & v);
vector(const vector & v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr);
//赋值运算符重载
vector& operator=(vector v);
~vector();
//深浅拷贝问题 memcpy/operator=
void reserve(size_t n);
//内置类型的升级
void resize(size_t n, const T& val = T());
void push_back(const T& x);
void pop_back();
//迭代器失效
iterator insert(iterator pos, const T& x);
iterator erase(iterator pos);
};
二、vector 的功能实现
2.1 构造/析构函数
2.2 获取数据函数
因为 vector 的控制是由迭代器实现的,所以如果我们想很容易的了解到当前容器的大小、容量、begin、end……则要自己实现其对应的成员函数。
此外,我们还需要实现一个 [ ] 重载函数,方便我们像数组一样提取出数据。
注意,要实现const型和非const型的重载函数,如果一个 const 对象来调用 [ ] ,不提供 const 型的 [ ] 重载函数,会出现 “没有与 *** 作符匹配的运算符”的错误。
关于这个问题,下面的迭代器还会有细致的说明。
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
iterator front()
{
assert(size());
return _start;
}
iterator back()
{
assert(size());
return _finish;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
size_t size() const
{
return _finish - _start;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
2.3 reserve
实现细节:
- 如果所需空间大于当前的容量,则扩容
- 开辟(new)一个所需空间大小的空间
- 如果原数组中有数据则进行拷贝,即(_start != nullptr ),并释放原空间
- 将_start 指向新开辟的空间
- _finish 更新为新空间的 size 处
- _end_of_storage 则为新空间的大小 (_start + n)
大家看下面的代码有没有什么问题:
这是一个很难发现的点,如果不解决则会导致程序的崩溃。
当我们开辟了新的空间,并释放了原来的空间,进行指向的更新时。
此时_start 指向新的空间,而 _finish 仍然指向原来的空间 (经典野指针),此时我们调用 size() 成员函数,size()函数会用_finish 减去 _start,则会发生程序的崩溃或错误。
所以我们在进行数据拷贝之前,要记录一下原数组中数据的个数,否则当原空间释放时后就无法便捷地获取数据的个数。
目前来说 reserve 已经没有了问题,但是关于 reserve 还有一个大坑,我们先继续往下学习。
2.4 push_back
- 检查 _finish 是否等于 _end_of_storage,相等则说明需要进行 reverse 扩容
- reverse时,检查当前容量是否为空,即_end_of_storage == _finish == nullptr ,当然我们可以直接使用 capacity 成员函数来检查,如果 capacity 为 0 ,我们则手动传入大小,如果不为 0 ,则扩容两倍。
- 在 _finish 出插入数据,将 _finish++
一个小细节,函数参数使用 const T& 型进行传参,因为我们只负责插入值,并不改变这个值。所以我们进行引用传参,并进行 const 修饰,防止对值进行了改变。
2.5 迭代器实现了以上的功能,我们先来检验一下成果。
但是作为 vector ,当我们直接遍历的时候会使用迭代器,而 vector 中的迭代器 (iterator)其实就是原生的指针,所以我们这样使用:
显然,这样写迭代器还是有些繁杂,所以我们可以采用范围for。
我们知道,范围 for 的底层其实就是迭代器,在编译阶段,编译器会无脑将其转为迭代器进行编译,所以这里引申出一个问题,如果我们是一个 const 型对象呢?
这里便出现了一个问题,函数传参中传来的是 const型的对象v1,所以 v1是 const 成员便只能调用 const 成员函数,所以v1.begin()这里是无法调用成功的,所以我们要提供 const 型的成员函数。
并且,因为返回值为const_iterator,所以我们生成的迭代器也要是 const_iterator 型。
如果 it 不是 const 型,则会出现类型不匹配的问题
这便不能发现,范围 for 本质就是一个迭代器,如果我们迭代器实现有缺失或是有错误,那范围for便会直接报错。
2.6 insert实现思路:
- 检查 pos 的合法性
- 如果 _finish == _end_of_storage则进行扩容,并检测 capacity
- 将 pos 位置及pos位置以后的值向后挪动。
- 将值插入、++_finish
以上是实现 insert 的常规思路,与我们当初实现顺序表的思路没有差别,但是这样的 *** 作,在 vector 中真的可行吗? 我们来看看一下代码。
这样一看代码好像没什么问题,如果我们做一个行为,不插入push_bakc(5);如果不插入5,接着insert,则会在 insert 中调用扩容,那我们来看看什么情况。
不难发现,此时插入数据就出现了随机值。我们来看看是哪里出了错。
大家可以看下面的图片
2.6.1 迭代器失效这本质便是一个野指针的问题。也是我们要知道的迭代器失效问题。
迭代器的主要作用是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对指针进行了封装。比如: vector 的迭代器就是原生态指针 T* 。因此迭代器失效,实际就是迭代器底层对应指针所指的空间被销毁了,而使用一块已经释放的空间。造成的后果是程序崩溃 (及如果继续使用失效的迭代器,程序可能就会崩溃)。
是会引起其底层空间改变的 *** 作,都有可能是迭代器失效,如果:resize、reserve、insert、assign、push_back等。
所以,解决方法就是将 pos 进行修正,让其指向新空间中的相对位置。
但是,关于 insert 还有下面一个问题:
虽然我们在插入数据时,进行 pos 处的修正,但是 insert外部的 p没有修改,这个迭代器失效的问题仍为解决。
此时就有靓仔就说了,那直接使用引用传参就行了啊,那我们来继续看看下面 这种情况。
我们经常会直接使用迭代器来插入,并常常会调用begin()函数,如果使用引用传参就无法实现这一常用的写法。
原因如下图:
所以说不能在参数处加上引用。
我们看看标准库中的 insert 是什么样的。
所以说我们要实现带返回值的 方式 来解决这个问题。主动将更新了的 pos 进行返回。
2.7 pop_back 与 erase
关于erase还是比较简单的。
接下来我们使用 earse 实现删除所有的偶数的功能
接下来我们使用上面代码代入下面3组案例,得到以下结果
下面是示例一的GIF 实现erase步骤
示例二:
示例三就不演示了,大家自己走读一下代码配合调试很快就可以发现问题。
示例二中,因为 pos 处检测到 _finish 外的偶数,并去调用了 erase ,所以 assert 进行了报错。
这里,解决上面迭代器失效的问题,同样只能采用返回值的方式更新 pos 的值。
正确的调用:
这样,迭代器自动根据情况更新,迭代器失效的问题就可以解决了。
根据上面实现了 insert/erase 我们可以得出一个结论:不能直接访问 pos,一定要更新 pos ,直接访问可能会出现各种出乎意料的错误,认为 pos 失效,不要访问。
这里注意一下问题,关于STL,它是一个标准,在VS和g++中实现方式不同。
2.8 拷贝构造函数的实现
关于拷贝构造函数的实现,需要我们自己来实现,因为 vector 是额外开辟的空间,如果使用默认的拷贝构造函数,就会出现浅拷贝的问题(如下图),两个对象指向同一块空间,所以这里拷贝构造的实现是十分重要的。
2.8.1 传统写法这里使用 size() 或者 capacity 都是可以的。但是推荐使用 size(),可以起到节约空间的作用.
2.8.2 复用 push_back 实现思路也是非常的简单,使用 reserve 开辟 v.size() 个空间,然后将数据一个一个进行尾插。这样的写法就是不需要去管 _finish 和 _end_of_storage。
这里特别注意的一点就是,插入时,尽量使用 const & 进行传参。
2.8.3 现代写法在 string 中我们使用了现代写法实现了拷贝构造,那在 vector 中,我们仍然可以使用现代写法实现。现代写法的的优点就在于:语法简洁,思路清晰,并且不易出错。
关于 现代写法的关键就在于,该类中有一个带参的构造函数,所以可以使用现代写法的方式,所以我们先来实现一个带参构造函数。
有人会问了,为什么你要用迭代器区间来构造。这样的一个迭代器区间可以实现不同的类型进行构造,比如vector>、vector
,这样就很好的实现了通用性。
好的,现在我们检验一下成果。
成果好像没什么问题,因为我用的 VS 2022,是一个非常智能的版本,它对我以上的代码其实进行了初始化,所以能正常运行,其实以上的代码有很大问题,好在他给出了一个提示,我们来看看。
上面代码的问题是在未对_end_of_storage、_finish、_start初始化,我在插入数据时,push_back 因为_end_of_storage == _finish调用 reserve ,reserve 开辟空间进行数据拷贝并释放原空间时判断 _start 为真,释放了随机空间,所以导致程序崩溃。因为2022的优化,无法给大家演示。
所以,大家一定要记得初始化噢!尤其是写构造函数时。
这样,我们使用这个带参的构造,构造出一个临时变量,这个临时变量将空间、数据准备好。然后我们将这两个对象中的_start、_finish、_end_of_storage进行互换(swap),就实现了 vector 中的现代拷贝构造函数(附上套用全局swap的My_swap函数)。
2.9 赋值运算符重载实现了上面的拷贝构造函数,便可以利用传值传参本质调用了拷贝构造创建的临时变量来进行赋值 *** 作。将现代写法的精髓发挥到了极值。
这里最重要的点是:
我们自己实现了拷贝构造函数,这导致传值传参时调用的都是我们自己实现的拷贝构造函数。所以我们要尽量使用引用传值、引用做返回值,这样就能拷贝出一个新对象出来。这点要十分注意。
比如上面代码中我们做引用返回,如果我们使用传值返回,就会再次调用我们自己实现的拷贝构造函数,不经意间就多开辟了一块空间。
大家可以看下面做的这个小实验。
2.10 带参的构造函数接下来我们来实现一个特别(带参)的构造函数,我们先来看看文档中这个构造函数的样子。
最后的空间配置器我们先忽略,我们来看看这个常用并奇特的构造函数如果我们要实现的话,因该是什么样的。
这其中的 const T& val = T() 是重点。
其中 T()相当于一个匿名对象,在这个构造函数中,使用匿名对象做缺省参数;这个匿名对象就会去调用它的默认构造,最后会返回一个临时对象的值。比如我们上面代码中的 T ,为 int 类型,就会返回一个 0,如果我们 T 为 vector
关于C++引入了类和模板,所以原本的内置类型已经不能适应模板的泛型编程需要,所以C++其实对内置类型也进行了升级,我们可以将C++中的内置类型也看作一种类,比如 int 类型在C++中其实也有自己的默认构造函数——默认初始化值就是0,比如下面这中赋值。
但是以上这么写解决不了以下的这个问题,如果我们需要解决可以去看看源码进行解决。
2.11 resize 的实现
2.12 深层次的拷贝构造实现思路:
- n > capacity ,表示空间不够,需要扩容到 n
- n > size ,表示空间足够,数据不够,需要插入数据直到 n 位置处。
- n < size ,则进行数据的删除,将 _finish 进行调整。
关于 vector 我们还有最后一个大坑,就是关于 vector> 此类的拷贝构造。我们当前的代码对以上形式的 vector 进行拷贝构造是会报错的。
例如,我们将杨辉三角中(一个vector
我们使用一个 ret 来接收 vv 。发现第一层确实是深拷贝,但其 _start 中的 _start 指向的是同一块空间。
大家观察下图可以清晰的观察其指向关系。
所以我们要做到其第二层也是深拷贝,这便不能使用 memcpy,因为 memcpy 本质就是浅拷贝。
这里我们可以要套用我们的赋值运算符重载,使其第二层指向不同的、开辟好了的空间。
以上我们改造的是传统写法的拷贝构造函数,所以接下来我们来改变现代写法的拷贝构造函数,因为现代写法调用的是 push_back,而 push_back 调用的是 reserve,所以我们要对 reserve 进行改进。
让 reserve 也使用赋值运算符重载进行赋值。
这样,拷贝构造的大坑就被填完了,我们在对vector
同样这样写对内置类型也不会有太大影响,因为temp[i] = _start[i]会直接进行值赋值,并且像[ ] 运算符重载这种成员函数通常会被设置为内联函数,也不会有太大的消耗。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)