目录
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以后就不要使用原本定义的迭代器
--外观报表)
