个人主页~
vector(上)~
vector
- 二、vector的模拟实现
- 1、了解组成
- 2、vector.h
- (1)为什么有了size_t参数的vector构造函数还要再写一个int参数的重载vector构造函数
- (2)为什么reserve不用memcpy
- (3)reserve和resize的相关解释
- (4)迭代器失效问题详解
二、vector的模拟实现
1、了解组成
首先我们需要在头文件stl_vector.h中了解vector的构成,它的三个私有成员分别是迭代器start、迭代器finish、迭代器endofstorage,分别指向vector的头、size的尾、capacity的尾
既然要实现了,自然要按照人家的标准最好,所以我们选择它们三个为私有成员变量
看一下vector的接口有哪些,当然我们还是去实现最基本也是重要最常用的那部分
2、vector.h
#pragma once#include <iostream>
#include <assert.h>namespace little_monster
{template <class T>class vector{public: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;}//构造、拷贝、析构函数vector(){}vector(size_t n, const T& value = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(value);}}vector(int n, const T& value = T()){reserve(n);for (int i = 0; i < n; i++){push_back(value);}}//(1)为什么有了size_t参数的vector还要再写一个int参数的template <class InputIterator>vector(InputIterator first, InputIterator end){while (first != end){push_back(*first);++first;}}vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}//容量size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}bool empty() const{if (_start == _finish){return 1;}return 0;}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t sz = size();if (_start){for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}//(2)为什么reserve不用memcpyvoid resize(size_t n, const T& val = T()){if (n > size()){reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}//(3)reserve和resize的相关解释//增删查改void push_back(const T& x){if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}void pop_back(){assert(_start < _finish);--_finish;}iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];} private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};
}
有关模拟实现的几个问题,在下面一一解释
(1)为什么有了size_t参数的vector构造函数还要再写一个int参数的重载vector构造函数
在两个构造函数都存在的情况下程序正常运行
void test()
{vector<int> v(10,0);for (auto e : v){std::cout << e << " ";}std::cout << std::endl;}
屏蔽掉int参数的构造函数后,发生报错
这里的原因其实是下面的这个函数
template <class InputIterator>
vector(InputIterator first, InputIterator end)
{while (first != end){push_back(*first);++first;}
}
这里的template < class InputIterator >用来声明一个类模版,它将接受一个迭代器类型的参数
我们看参数为10和0,在size_t参数构造函数中,两参数的类型为size_t和一个模版,而在该函数中为两个迭代器,也就是两个指针,在size_t参数构造函数中int需要强制类型转换为size_t,而该函数不用,两相比较下,软件会选择更合适的,但end一定要比begin大的,所以这里报错了,重载一个int类型的构造函数就能解决这个问题
(2)为什么reserve不用memcpy
reserve使用memcpy就会发生浅拷贝的问题,当删除旧空间的时候会发现我们reserve出来的空间不能使用了,因为memcpy将指针给拷贝过去,新的指针还是指向旧的空间,当旧的空间释放了就会出现野指针的错误(前面其他文章也有多次提到过深浅拷贝的问题了)
(3)reserve和resize的相关解释
关于reserve,它的参数有两种情况,第一种是参数n>capacity(),第二种就是n<=capacity()
在第二种情况下相当于是无事发生,第一种情况需要开辟新的空间之后,将数据转移到新空间,然后释放旧空间
关于resize,它的第一个参数有两种情况,第一种是参数n>size(),第二种是n<=size()
第一种情况下,会将size()和capacity()的大小都改变,将从原本的_finish位置开始一直到_endofstorage的前一个位置都初始化为第二个参数,第二种情况下直接将_finish提前就可以了
(4)迭代器失效问题详解
迭代器失效的问题在前面的文章当中提到过,这里搭配着insert和erase函数详细分析一下
迭代器失效问题跟上面第三个问题在根本是一样的,在reserve时,需要扩容,开辟新的空间之后,将数据转移到新空间,然后释放旧空间,那么这个指针就不能用了,因为其指向的空间已经释放了,当然resize也一样,所以我们要用深拷贝,new一个新空间然后数据转移释放旧空间
今日分享完毕~