博主主页：Yan. yan.
C语言专栏
数据结构专栏
力扣牛客经典题目专栏
C++专栏
文章目录
- 一、Vector的成员变量
- 二、默认成员函数
- 1、构造函数
- 2、拷贝构造函数
- 3、析构函数
- 三、增删查改工作
- 1、reserve()
- 2、 resize（）
- 3、insert()
- 4、erase（）
- 四、[]重载和迭代器
- 1、begin迭代器
- 2、end迭代器
- 3、[]运算符重载
一、Vector的成员变量
我们以类模板的方式来实现Vector的实现。
template<class T>
类型名称也重新进行修改
typedef T* iterator;
typedef const T* const_iterator;
根据库的实现方式，成员函数如下：
private:iterator _start;iterator _finish;iterator _end_of_storage;
二、默认成员函数
1、构造函数
构造函数可分为3种：
- 无参构造
- 构造n个val对象
- 根据迭代区间构造
对于无参的构造，我们只需要初始化成员函数即可。
无参构造
//无参构造函数
vector()//:_start(nullptr)//,_finish(nullptr)//,_end_of_storage(nullptr)
{}
构造n个val对象
//构造n个对象
vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{//1.开空间reserve(n);//2.将空间填充为val对象for (size_t i = 0; i < capacity(); i++){_start[i] = val;}//也可以复用resize//resize(n, val);
}
注意：这里在构造时必须初始化，如果不初始化，在调用reserve函数开空间时会出现访问野指针的问题。也可以调用resize函数进行拷贝构造n个对象。
使用迭代区间进行构造
同理，如果不初始化，会出现扩容后访问野指针的情况。
template<class Inputiterator>
vector(Inputiterator first, Inputiterator last)
{while (first != last){push_back(*first);++first;}
}
2、拷贝构造函数
vector(const vector<T>& v)
//这里必须初始化，否则扩容时会访问不属于自己的空间
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
//如果私有成员给了缺省值，就不用再再次初始化了
{
reserve(v.capacity());
//memcpy(_start, v._start, sizeof(T) * v.size());
//这里使用memcpy的错误跟扩容的错误一样，不再赘述
for (size_t i = 0; i < v.size(); i++) // 如果是string类，会调用string的赋值重载，赋值重载调用string的拷贝构造，完成深拷贝
{_start[i] = v._start[i];
}_finish = _start + v.size();
}
拷贝构造需要注意的几个问题：
- 拷贝构造同构造函数一样，如果不初始化，在开空间时会出现访问野指针的情况。
- 拷贝构造必须进行深拷贝，否则如果vector的对象是自定义类型，比如string，会出现两次释放同一块空间的问题。
3、析构函数
释放_start指向的空间，然后全部置为空即可。
~vector()
{if (_start){delete[] _start;_start = _finish = _end_of_storage;}
}
三、增删查改工作
说明size()和capapcity()
size的大小为_finish - _start
capacity的大小为_end_of_storage - _start
1、reserve()
该函数的作用是：扩容。
void reserve (size_type n);
- 思路：
- 如果要扩容的大小n小于capacity，则不会缩容。
- 否则执行扩容。
- 先申请一块n大小的空间
- 拷贝原空间的数据到新空间，并释放原空间
- 将新空间的数据交给_start管理。
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;_end_of_storage = _start + n;}
}
2、 resize（）
该函数的功能是：重新改变vector容器的大小，让其到达n。新的空间默认初始化为val。
- 思路：
- 如果n小于size，则让_finish指向_start + n位置。
- 如果n大于等于size，先调用reserve函数进行扩容，再将新的空间填充为val。
void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{//扩容到n,如果n<capacity()，则啥事不做，否则，扩容到nreserve(n);//将多的空间全部设置成缺省值while (_finish != _start + n){*_finish = val;++_finish;}}}
3、insert()
该函数的作用是：在pos位置插入模板对象val。
- 思路：
- 插入元素前先检查容量
- 如果容量满了,则调用reserve函数执行扩容操作
- 然后从pos位置开始将其之后的元素全部都往后挪。
- 再在pos位置插入val。
void insert(iterator pos, const T& val)
{
assert(pos <= _finish);
//插入前先检查扩容
if (_finish == _end_of_storage)
{size_t oldpos = pos - _start;//记录相对位置size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);pos = _start + oldpos;
}//记录旧的size，防止出现迭代器失效问题。//将pos之后的位置往后挪，再插入
iterator end = _finish - 1; // reserve之后，_finish也跟着更新了。
while (end >= pos)
{*(end + 1) = *end;--end;
}*pos = val;
_finish += 1;
}
4、erase（）
该函数的功能是：删除pos位置的值。
iterator erase(iterator pos)
{assert(pos < _finish);iterator end = pos;while (end != _finish){*end = *(end + 1);++end;}--_finish;return pos;
}
有一个需要注意的点：当我们删除元素后，pos迭代器就会失效，因为空间已经释放，这时候不能使用pos迭代器。
解决方法：返回删除位置的下一个元素的位置，即pos位置。
然而，在只剩下一个待删除元素或者删除最后一个位置的元素时，不能再使用pos迭代器。
四、[]重载和迭代器
1、begin迭代器
返回_start地址即可。
iterator begin()
{return _start;
}const_iterator begin() const
{return _start;
}
2、end迭代器
返回_finish地址即可。
iterator end()
{return _finish;
}const_iterator end() const
{return _finish;
}
3、[]运算符重载
只需给定pos下标即可。
在此之前需要判断pos位置不能超过整个顺序表的size大小。
T& operator[]( size_t pos)
{assert(pos < size());return *(_start + pos);
}//不可修改的
const T& operator[]( size_t pos) const
{assert(pos < size());return *(_start + pos);
}