1. vector的介绍
- vector是表示可变大小数组的序列容器。
- 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
2. vector的使用
必要时查看使用文档即可，这边介绍一些常见的使用(类似string中的使用，不过多赘述！)
2.1 push_back 和 遍历
2.2 reserve 和 resize
为啥string类和vector类当中的reserve都不缩容呢？
因为string类和vector类都是需要频繁插入数据，缩容也是有消耗的，缩容过后插入数据又需要频繁扩容，所以reserve只是实现扩容并没有缩容的作用
接口实现const和非const的条件
2.3 [ ] 和at
断言存在的缺陷：release版本下断言会失效，虽然说代码都要先通过debug版本测试后以release版本发布，但是这种情况也是需要注意的，因为越界访问，如果发生修改是很严重的情况(比如：金额数据发生改变)
2.4 assign 初始化填入数据
2.5 算法库中的find
2.6 swap接口
2.7 缩容函数(不推荐)
使用场景：当我们知道我们空间开辟过多，根本不需要用到这么多的空间，就采用缩容，归还给操作系统，以便其他程序使用
3. vector相关习题
3.1 只出现一次的数字
3.2 杨辉三角形
所以通常推荐使用C++写
二级指针的理解转化成二维数组的感觉(虽然不是二维数组，而是对对象的operator[ ])
4. vector的模拟实现
4.1 vector类中成员
namespace hx
{
template <class T>
class vector {
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
}
4.2 迭代器区间和operator[]
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos] ;
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
因为[ ]和迭代器都可能出现只读的情况，所以const接口也需要实现
4.3 size和capacity
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endofstorage - _start;
}
两个指针相减即可得到size和capacity的值
4.4 无参构造函数
// 无参构造函数
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
}
这里的无参构造函数是可以不显示实现的，因为编译器默认实现无参构造也是用nullptr来初始化这几个值
(什么时候需要用到显示实现呢？--有资源申请的时候，无资源申请针对内置类型用0/NULL/nullptr来实现，针对自定义类型调用其构造函数)
4.5 push_back
void push_back(const T& x)
{
if (size() == capacity())
{
int newCapacity = capacity() == 0 ? 4 : 2 * capacity();
//扩容
reserve(newCapacity);
}
*_finish = x;
_finish++;
}
4.6 reserve(错误版) -- 采用memcpy
那么该如何解决该问题呢？--在扩容前记录下原来的size加到_finish上即可
void reserve(size_t n)
{
if (n > capacity())
{
// 记录oldSize
size_t oldSize = _finish - _start;
T* tmp = new T[n];
if (_start)
{
memcpy(tmp, _start, sizeof(T) * size());
delete[] _start;
}
_start = tmp;
// 加上oldSize
_finish = _start + oldSize;
_endofstorage = _start + n;
}
}
4.7 resize
//val采用默认值：若T类型为自定义类型调用其构造函数，若T为内置类型用0或者nullptr初始化
//当然传参了就用传过来的参数
void resize(size_t n,T val = T())
{
//扩容
if (n > capacity())
{
reserve(n);
}
if (n > size())
{
//要插入数据
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
{
// 删除数据
_finish = _start + n;
}
}
4.8 pop_back
bool empty() const
{
return _finish == _start;
}
void pop_back()
{
assert(!empty());
--_finish;
}
迭代器失效问题(重点)
4.9 insert
问题1：野指针问题
==由扩容引起的pos迭代器失效问题，需要进行更新pos指向==
// 解决野指针问题
void insert(iterator pos, const T& val)
{
assert(pos >= _start);
assert(pos < _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
// 扩容会导致pos迭代器失效，需要更新处理一下
pos = _start + len;
}
// 挪动数据
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
}
那么既然存在扩容后迭代器失效的问题，而且失效后外部的it又无法再使用的场景，那么我们在设计insert接口时，为何不采用引用的方式来传参呢？
insert(iterator& pos, const T& val)
不传引用因为防止内部有可能会通过这个迭代器的引用破坏我原有的容器的结构，存在这种风险，所以需要规避风险
迭代器相较于容器只是一个工具
而且库中实现insert接口也是不传引用的，所以我们模拟实现时要跟库一致
4.10 erase
在模拟实现之前先看如下现象：
基于以上现象，我们认为it失效了在调用erase过后不能再去使用
我们来看看库函数的思路：
模拟实现如下：
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator begin = pos;
while (begin < _finish - 1)
{
*begin = *(begin + 1);
++begin;
}
--_finish;
return pos;
}
erase接口带返回值：返回删除该元素的位置(因为已经删除，所以不需要++)
4.11 clear
void clear()
{
_finish = _start;
}
clear并不会清空间，所以并不能将_finish和_start置为nullptr，否则就属于野指针
(此时_endofstorage还在原来的位置，_finsh和_start已经丢失)
4.12 swap
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
4.13 构造函数补充
n个T对象构造 -- 错误版
//拿n个T来初始化vector
vector(size_t n,const T& val = T())
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
采用接口复用的方式，这里为啥要初始化_start,_finish,_endofstorage呢？
因为reserve在扩容之前会记录下oldSize=_finish - _start的值，以便后续_finish好找到自己自己之前距离_start的位置
因为reserve中会用到所以需要先初始化为nullptr不然都是随机值oldSize也是随机值，扩容也就出现问题
迭代器区间构造
//迭代器区间初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}
也是接口复用的方式，但是当这个接口实现后，我们看如下情况：
那么该如何解决该问题呢？-- 将n改为int类型即可
n个T对象构造 -- 正确版
vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
将n改为int类型，那么编译器在匹配模板时会优先匹配现成的模板，而不是去推演模板(编译器的机制)，这时候拿10个1初始化就会匹配int,T的接口了
4.14 拷贝构造
方法1：传统写法
方法2：复用接口
// 复用接口
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
reserve(v.size());
for (auto e : v)
{
push_back(e);
}
}
方法3：现代写法
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
拿tmp构造T对象，当前对象用nullptr初始化，再交换this和tmp 此时tmp对象为nullptr，出了函数栈帧销毁不会报错
4.15 operator= (赋值重载)
//赋值重载
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
赋值重载中的参数必须是传值传参，而不能是传引用传参
因为传值传参会调用拷贝构造，构造出一个临时对象v来跟this指针对象进行交换，这个临时对象交换到this对象不需要的空间后释放，一举两得。
如果采用传引用传参，赋值重载反而会将之前的替换成不正确的数据(this对象中的数据--垃圾数据)，得不偿失
明明是赋值却实现成交换
4.16 析构函数
//必须实现 默认生成的析构函数对于内置类型直接置为0(nullptr)
//空间还未释放 内存泄漏
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
关键问题(深层次的浅拷贝问题 -- 重点)
4.17 reserve正确版 -- 采用深拷贝
// 正确版reserve -- 深拷贝
void reserve(size_t n)
{
if (n > capacity())
{
size_t oldSize = _finish - _start;
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(T) * size());
for (size_t i = 0; i < oldSize; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + oldSize;
_endofstorage = _start + n;
}
}
针对每个容器内部的对象进行赋值重载(深拷贝) -- 接口复用
