@TOC
1.查看STL源码
start、finish、end_of_storage 都是指针
通过观察函数的实现过程,可以得知 start与begin等价 ,end与finish等价
2.vector的模拟实现
为了模拟实现vector,所以使用自己的名空间包含vector类
1. 构造函数
无参构造
vector()//构造函数
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
}
只是将_start 、_finish 、_end_of_storage 初始化为nullptr
构造n个 val
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);//扩容
for (int i = 0; i
正常来说匿名对象生命周期只有这一行,因为这行之后没有会用它了
当调用完匿名对象后,会调用析构函数
引用会延长匿名对象的生命周期到引用对象域结束,因为后面用xx就是用匿名对象
由于匿名对象具有常性,所以需要用const修饰
此时调用完匿名对象,并不会调用析构函数释放
迭代器模板
template //随机迭代器
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
//[first,last)
while (first != last)
{
push_back(*first);
first++;
}
}
template //随机迭代器
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
//[first,last)
while (first != last)
{
push_back(*first);
first++;
}
}
提供迭代器模板,可以使用任意类型迭代器
调用vector本身迭代器
对于数组和string类型也同样适用
2. reserve
void reserve(size_t n)//开辟空间
{
if (n > capacity())//避免缩容
{
size_t sz = size();
T* tmp = new T[n];
if (_start != NULL)//为NULL时没有意义
{
memcpy(tmp, _start, sizeof(T)*size());//拷贝数据
delete[]_start;//释放旧空间
}
_start = tmp;//指向新空间
_finish = tmp + sz;
_end_of_storage = tmp + n;//容量变大了
}
}
为了避免缩容的情况,所以使用 n>capacity() , 开辟一块空间tmp,将start中的数据拷贝到新空间,释放旧空间,指向新空间,同时更新_finish 和_end_of_storage
在计算_finish的大小时,由于size里面的_start改变了,所以需要提前储存原来的size
3. 迭代器
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
正向迭代器的应用
const迭代器的应用
此时v由const修饰,所以需要const_iterator类型的迭代器
4.pop_back 尾删
为了防止没有数据继续删除,使用断言报错
bool empty()
{
return _start = _finish;
}
void pop_back()//尾删
{
assert(!empty());
_finish--;
}
5.resize
void resize(size_t n ,T val=T())//扩容+初始化
{
if (n capacity())
{
reserve(n);//扩容
}
while (_finish != _start + n)//将剩余空间初始化
{
*_finish = val;
_finish++;
}
}
}
T val= T() ,T()是匿名对象,因为T模板泛型,所以有可能是内置类型int char,也有可能是自定义类型,为了两者都可以使用,所以使用匿名对象调用默认构造函数
内置类型也是有构造函数的
6.push_back
void push_back(const T& x)//尾插
{
if (_finish == _end_of_storage)//扩容
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
*_finish = x;
_finish++;
}
需要考虑扩容问题,而若capacity本身为0的情况也要考虑
7.insert
void insert(iterator pos, const T& val)//在pos位置前插入n
{
assert(pos >= _start);
assert(pos = pos)
{
*(end+1) = *end ;
end--;
}
*pos = val;
_finish++;
}
迭代器失效—— pos为野指针
扩容时出现了问题,由于pos指向原来的空间,但是扩容时将释放了旧空间,但是pos依旧指向原来的空间,所以pos变成了野指针
所以需要记录pos在旧空间所处位置,再更新pos在新空间的位置
迭代器失效——修改迭代器位置
加入修改迭代器位置后,会直接报错
形参pos位置的改变不会影响实参,所以pos依旧指向旧空间
若将形参pos加入引用,会报错,当调用begin时,因为是传值返回,所以返回临时对象,而临时对象具有常性,所以不能直接传给引用
为了解决这个问题,将修改指向的pos返回
8. erase
void erase(iterator pos)//删除pos位置数据
{
assert(pos >= _start);
assert(pos
对于VS和Linux环境测试
VS做了强制检查,只要使用了erase,迭代器就失效了,所以会报错
而同样的代码在Linux下会就能正常运行
遇到偶数就删除,并且每次结尾pos都会++,运行结束时正好pos位置等于finish
VS做了强制检查,使用erase后,迭代器失效了,所以会报错
同样的代码在Linux下就会发生段错误
假设为最后一个位置被删除,finish会移动到到最后到3位置的后面,同时pos++,此时pos位置已经在finish位置后面,就会造成一直循环下去
说明g++没有强制类型检查,具体问题具体分析,结果未定义
3.深浅拷贝问题
对内置类型调用默认拷贝构造函数会进行浅拷贝,所以需要我们自己来实现深拷贝
vector(const vector& v)//拷贝构造
{
_start = new T[v.capacity()];
memcpy(_start, v._start, sizeof(T) * v.size());
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}
若为上面内置类型,那报错的问题就可以解决了,但若为自定义类型依旧会报错
因为自己实现的拷贝构造中memcpy也是一种浅拷贝(按字节拷贝)
深拷贝是重新开辟一块与原空间大小相同的新空间,并将原空间的数据拷贝给新空间,但是若为string 类型,本身的_str指向字符串,而新空间只是将_str拷贝过去了,依旧指向同一字符串
v2先进行析构,会调用delete[ ] ,会对数组上每个成员依次调用析构函数,此时指向的字符串旧全部被析构了,再次使v1析构,依旧会析构字符串,所以会报错
属于深拷贝内的浅拷贝
这样v1与v2中的_str都指向自己的字符串,不会发生析构两次的问题了
同样reserve也存在使用memcp造成浅拷贝的问题
将旧空间上的_str等拷贝到新空间上,释放旧空间就导致_str所指向的字符串析构
当新空间析构时,_str所指向的字符串就会造成二次析构,从而报错
4. 整体代码实现
#include
#include
#include
#include
#include
using namespace std;
namespace yzq
{
template
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector()//构造函数
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
}
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
reserve(n);//扩容
for (int i = 0; i &v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
// v1 = v2
vector& operator=(vector v)//自己实现赋值运算符
{
swap(v);
return *this;
}
vector(const vector& v)//拷贝构造
{
reserve(v.capacity());
for (size_t i = 0; i capacity())//避免缩容
{
size_t sz = size();
T* tmp = new T[n];
if (_start != NULL)//为NULL时没有意义
{
for (size_t i = 0; i v1(3, "111111111111111111111111");
for (auto e : v1)
{
cout v2(v1);
v2.push_back("333333333");
v2.push_back("333333333");
v2.push_back("333333333");
for (auto e : v2)
{
cout
服务器租用托管,机房租用托管,主机租用托管,https://www.e1idc.com