CD43.vector模拟实现(2)

目录

1.拷贝构造函数

写法1

写法2

测试代码

调试找bug

解决方法:修改拷贝构造函数

测试代码

2.operator[ ]

测试代码

1.没有const修饰

2.有const修饰

3.insert

迭代器失效问题

---

承接CD42.vector模拟实现(1)文章

1.拷贝构造函数

设置start、finish和end_of_storage这几个参数就行,注意是深拷贝!

写法1

vector(const vector<value_type>& x):start(0), finish(0), end_of_storage(0)
{start = new T[x.capacity()];memmove(start, x.start, x.size()*sizeof(value_type));finish = start + x.size();end_of_storage = start + x.capacity();
}

注:new的参数可以为capacity,也可以为size,这个C++标准没有规定,空间可以不一样,但是有效元素必须一样

写法2

复用reserve和memmove函数

这个代码有问题:

vector(const vector<value_type>& x):start(0), finish(0), end_of_storage(0)
{reserve(x.capacity());memmove(start, x.start, x.size() * sizeof(value_type));
}

测试代码

void const_vector_print(const mystl::vector<int> v)
{for (size_t i = 0;i < v.size(); i++)std::cout << v[i] << " ";
}void test6()
{mystl::vector<int> v;v.push_back(1); v.push_back(2);v.push_back(3); const_vector_print(v);return;
}

运行结果:什么都没有打印

调试找bug

什么都没有打印,可以判定没有进入循环,

下断点到循环,看看情况:

start和finish的地址一样,v.size()计算出来为0,没有进入循环,可以断定拷贝构造函数出了问题,

下断点到拷贝构造函数,再次调试:

x.capacity()计算出来是4,进入reserve函数内部:

对空的vector进行reserve,看以下分析图:

解决方法:修改拷贝构造函数

reserve没有更新finish,那就手动更新finish

vector(const vector<value_type>& x):start(0), finish(0), end_of_storage(0)
{reserve(x.capacity());finish = start + x.size();memmove(start, x.start, x.size() * sizeof(value_type));
}

而且标准库也是这样实现的:

运行结果:

同理,reserve函数也要修改:

void  reserve(size_type n)
{if (n > capacity()){T* tmp = new T[n];size_t len = size();//delete前先保存元素的个数!bool flag = false;if (size() == 0){flag = true;len = n;}memmove(tmp,start , size()* sizeof(value_type));delete[] start;if (flag)//如果vector在什么元素都没有{start = finish = tmp;}else{start = tmp;finish = start + len;}end_of_storage = start + n;}
}

测试代码

void test4()
{mystl::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);mystl::vector<int> v2(v1);for (auto& a:v2)std::cout << a << " ";
}

运行结果:

2.operator[ ]

参数保持一样的类型:

注意到返回类型被重定义过,因此先进行重定义:

typedef value_type& reference;
typedef const value_type& const_reference;

必须保证提供的n是合法的,换句话说,n<size(),可以使用assert断言

reference operator[] (size_type n)
{assert(n < size());return *(start + n);//也可以写成start[n]
}const_reference operator[] (size_type n) const
{assert(n < size());return *(start + n);//也可以写成start[n]
}

测试代码

1.没有const修饰

void test5()
{mystl::vector<int> v;v.push_back(1); v[0]++;v.push_back(2); v[1]++;v.push_back(3); v[2]++;for (auto& a : v)std::cout << a << std::endl;return;
}

运行结果:

2.有const修饰

void const_vector_print(const mystl::vector<int> v)
{for (size_t i = 0;i < v.size(); i++)std::cout << v[i] << " ";
}void test6()
{mystl::vector<int> v;v.push_back(1); v.push_back(2);v.push_back(3); const_vector_print(v);return;
}

运行结果:

3.insert

参数保持一样的类型,为了简单起见,这里只实现第一个

首先要断言,position必须合法:

assert(position >= start && position <= finish);

插入前先看看是否需要扩容,可以直接借用CD42.vector模拟实现(1)文章的push_back函数的代码:

if (finish == nullptr)reserve(4);
if (finish == end_of_storage)reserve(capacity() * 2);

和CD38.【C++ Dev】string类的模拟实现(2)文章类似的思路,先移动再插入

迭代器失效问题

如果insert的返回值是void,

void insert(iterator position, const value_type& val)
{assert(position >= start && position <= finish);if(finish == nullptr)reserve(4);if (finish == end_of_storage)reserve(capacity() * 2);iterator i = finish-1;while (i >= position){*(i+1) = *i;i--;}*position = val;finish++;
}

头插:

void test7()
{mystl::vector<int> v;v.push_back(1);v.push_back(2);v.insert(v.begin(), 3);return;
}

 

尾插:

void test7()
{mystl::vector<int> v;v.push_back(1);v.push_back(2);v.insert(v.end(), 3);return;
}

中间位置插入:

void test7()
{mystl::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.insert(v.begin() + 1, 4);return;
}

貌似没有问题,但是如果是这个测试代码:

void test7()
{mystl::vector<int> v;v.push_back(1);auto pos = v.begin();for (size_t i = 2; i <= 8; i++)v.insert(pos, i);return;
}

运行结果会出问题: 

引出迭代器失效问题

pos记录的是原来v的start的值,如果v扩容,start的值会改变,但pos的值没有更新,而且原先的内存空间被释放会导致非法访问,因此再执行v.insert(pos, i);就会出问题(即pos为野指针)

解决方法:扩容后更新pos的值,STL的解决方法:返回值为iterator

 

iterator insert(iterator position, const value_type& val)
{assert(position >= start && position <= finish);if(finish == nullptr)reserve(4);if (finish == end_of_storage)reserve(capacity() * 2);iterator i = finish-1;while (i >= position){*(i+1) = *i;i--;}*position = val;finish++;return start;
}

注:position不能引用传参,有可能insert的第一个参数会做算术运算,例如:
 

v.insert(pos+20, i);

测试代码: 

void test7()
{mystl::vector<int> v;v.push_back(1);auto pos = v.begin();for (size_t i = 2; i <= 8; i++)pos=v.insert(pos, i);return;
}

验证pos是否更新:
原先:

扩容更新后:

运行结果:退出代码为0

当然CD42.vector模拟实现(1)文章的push_back可以复用insert的代码

1.如果不接收insert的返回值,扩容要慎重,修改可能会报错,因为不一定扩容,所以不一定失效;

2.insert以后就不要使用原本定义的迭代器