【C++】STL:vector
慕雪年华

STL的第二站,便是vector了。

对于学习STL,有一个非常大的好处便是,它们有很多函数都是相通的!这也是面向对象的一大好处:背后的函数实现可能不同,但是使用方式相同。

1.简单了解vector

https://m.cplusplus.com/reference/vector/vector/

老样子,打开我们的cplusplus——然后惊奇的发现,它换UI了!终于不再是那个2000年初的模样了(虽然这和我们的使用没啥关系)

image

不摸鱼了,来看看vector究竟是何方神圣——其实他就是一个顺序表

和string不同的是,vector有模板参数,可以存储任何类型的内容。int、double、char、甚至string。

这一点在cplusplus网站上的第一行便告诉了我们

image

1
template < class T, class Alloc = allocator<T> > class vector; // generic template

你还可以看到,标题下方给了一个这样的类模板定义,其中T代表的是存放数据类型,allocator<T>也是STL库中的一部分,用于向堆申请空间(类似一个内存池)可以提高访问的效率

前期的学习我们不需要知道allocator<T>是怎么实现的,只要知道它有这个功能就ok了。


1.1函数接口

往下滑,你会发现vector的函数接口,我们很多都已经学过了!

image

这些函数的操作和string类型都是一样的,这里就不再讲解了!

image

对比发现,其实vector多出来的函数并不多,这便是学习STL的好处!


2.使用vector

因为大部分函数的功能、操作和string一样,有问题可以去看看我之前string的博客

2.1构造

image

对于vector而言,比较常用的构造函数是下面这几个

image

这里说说最后一个,利用迭代器进行初始化,它的使用如下

1
2
3
4
5
6
7
std::string s1("hello");
vector<char> v2(s1.begin(),s1.end());
for (auto ch : v2)
{
cout << ch << " ";
}
cout << endl;

当我们已经有一个其他的支持迭代器的容器之后,便可以使用该容器的迭代器初始化一个vector

这里的区间可以自行控制,对应的初始化的内容也会有所不同

image


2.2迭代器

vector的迭代器和string基本相同,都拥有正向和反向两种方式

迭代器说明
begin+end获取第一个数据位置iterator/const_iterator, 获取最后一个数据的下一个位置iterator/const_iterator
rbegin+rend获取最后一个数据位置的reverse_iterator,获取第一个数据前一个位置的 reverse_iterator

image

1
2
3
4
5
6
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}

利用迭代器,我们可以打印vector的内容

2.3迭代器失效问题

在vector中的一些操作会导致迭代器失效,即迭代器指向的内容含义变了。包括但不限于:

  • 因为erase导致的数据擦除
  • 扩容导致的原有空间被释放(此时迭代器依旧指向原有空间)
  • 所有会导致扩容的操作

这时候我们需要借助函数的返回值对it进行重新赋值,比如下图是eraseinsert的返回参数

image

image

我们只需要在使用迭代器遍历的时候用it来接受返回值(更新迭代器)就可以规避这个问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void test02()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.push_back(6);
v1.push_back(7);

vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
if (*it % 2 == 0)//在偶数之前插入内容
{
//不这样写会出现it的含义变化而导致的死循环
//程序内出现了扩容,it原先指向的空间已经被释放
it = v1.insert(it, 99);
it++;
}

it++;
}

for (auto ch : v1)
{
cout << ch << " ";
}
cout << endl;

}

image


库里面的其他函数就不进行讲解啦,有问题的可以去看看之前string的博客。当然最好的学习办法就是依据cplusplus上面的函数定义,尝试自己弄明白这些库函数的使用方法。

image

3.模拟实现

代码详见我的gitee仓库【链接】STL-Vector的源码也在里面!

string类不同的是,在vector里面并不是用size和capacity这两个成员变量来确认有效长度和容量的。

通过查看stl源码可以看到,其使用了3个迭代器进行标识

image

1
2
3
4
private:
iterator _start;//指向开头(存放数据)
iterator _finish;//指向结尾的下一个
iterator _endofstorage;//指向空间尾部

了解结构后,便可以先把无参构造和析构函数写出来待用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//无参构造函数
vector()
:_start(nullptr),
_finish(nullptr),
_endofstorage(nullptr)
{ }

//析构
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}

那么要怎么知道size和capacity的大小呢?很简单,通过指针相减即可得出结果

1
2
3
4
5
6
7
8
size_t size()const
{
return _finish - _start;
}
size_t capacity()const
{
return _endofstorage - _start;
}

3.0 迭代器

在模拟实现一开始,我们就要用typdef定义两个迭代器,方便后面的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

3.1 reserve/resize

现在我们的vector内容还是空空的,我们需要先实现一下push_back函数,可以基本操作一下我们的数据。但没有构造函数去申请空间,哪来的目标给我们操作呢?

  • 这时候就需要先实现reserve来扩容和获取空间了!

在扩容之前,我们需要获取原有数据的长度,再new将空间整出来,并给_start。操作结束后,我们需要修改_finish_endofstorage,否则这两个迭代器指向的还是原有空间,出现了迭代器失效问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void reserve(size_t n)//扩容
{
size_t sz = size();//计算原有的长度
if( n > capacity())
{
T* tmp = new T[n];
if (_start) //只有_start不为空才进行拷贝操作
{
//memcpy是浅拷贝,当遇到vector类型是自定义类型(比如string和vector<T>这种包含堆区内存的类型)
//浅拷贝会失效,string的成员变量拷贝过去了,但是成员变量指向的堆区空间被释放,出现野指针
//memcpy(tmp, _start, size());
for (size_t i = 0; i < size(); i++)
{
tmp[i] = _start[i];//手动赋值,当成员是自定义类型的时候,会调用=重载
}
delete[] _start;//释放原有空间
}
_start = tmp;
}
//这里必须要先计算sz,如果在这里直接调用sz的话:finish已经是野指针了,finish-start会出现问题
_finish = _start + sz;
_endofstorage = _start + n;
}

关于为何拷贝内容的时候需要用=而不能直接memcpy,后文会提到。

resize和reserve唯一不同的一点,就是reserve会修改原有空间的数据,其余的实现是一样的。所以这里面我们直接复用reserve进行扩容即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//在C++中,内置类型也有一个“构造函数”
//这是为了更好的支持模板操作
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;
}
}

注意,T()的含义是用模板参数的构造函数作为缺省值。在C++中,内置类型也可以进行这个操作

image

当你不进行传值的时候,int类型默认是0

image

3.2插入/删除

空间拿到了,现在就可以对我们的数据进行插入操作了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void push_back(const T& x)
{
if (_finish == _endofstorage)
{
size_t newcapa = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapa);
}

*_finish = x;
_finish++;
}

void pop_back()
{
if (_finish > _start)
{
_finish--;
}
}

简单测试一下插入和删除功能,没啥问题

image

更好的办法,其实是写好insert和earse,然后尾插尾删的时候直接复用即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//pos位置插入val
iterator insert(iterator pos, const T x)
{
assert(pos >= _start && pos <= _finish);
//assert(pos >= _start && pos <= _endofstorage);
if (_finish == _endofstorage)
{
size_t n = pos - _start;
size_t newcapa = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapa);
pos = _start + n;
}

iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
end--;
}

*pos = x;
_finish++;

return pos;
}
//删除数据
iterator erase(iterator pos)
{
assert(pos >= _start && pos <= _finish);
iterator tmp = pos;
iterator end = _finish - 1;
while (tmp < end)
{
*tmp = *(tmp + 1);
tmp++;
}

_finish--;

return pos;
}

因为这里我们只需要操作一个元素,所以就不需要担心移动多个数据可能导致的问题,事情也变得简单多了

1
2
3
4
5
6
7
8
9
void push_back(const T& x)
{
insert(end(),x);
}

void pop_back()
{
erase(end()-1);
}

尾插尾删操作直接复用源码即可

3.3重载[ ]操作符

因为vector本身只是个顺序表,所以我们需要对它的对象重载一下[]操作符,这样就能和数组一样去访问vector的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
//重载[]操作符
T& operator[](size_t pos)
{
assert(pos < size());

return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());

return _start[pos];
}

关于构造函数,这里重点介绍一下迭代器区间的构造函数,因为后面的拷贝构造我们会用上它。

3.4迭代器区间构造/拷贝/赋值

库里面关于该构造函数的定义如下

1
2
3
template <class InputIterator>
vector (InputIterator first, InputIterator last,
const allocator_type& alloc = allocator_type());

因为这时候我的水平还很垃,就暂且不管这个allocator

该函数需要我们传参两个迭代器,因为我们底层就是用指针实现的,所以直接解引用然后将内容尾插即可(如果没有空间,尾插会调用reserve来获取空间/扩容)

1
2
3
4
5
6
7
8
9
10
11
12
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr),
_finish(nullptr),
_endofstorage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}

有了这个构造函数后,拷贝构造就很容易了!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
//拷贝构造
vector(const vector<T>& v)
:_start(nullptr),
_finish(nullptr),
_endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}

利用迭代器区间构造出来一个tmp对象,再将该对象和我们本身进行交换即可!

  • 你可能会问:欸你这样交换了,原本的内容岂不是没人管了,有内存泄漏啊!

并不是这样的,我们使用库函数里面的swap交换了二者的成员变量,在拷贝构造函数完成之后,tmp生命周期结束,会自动调用构造函数处理掉我们的数据!

这就是让别人帮你干活😂

赋值重载就跟简单了,我们连tmp变量都不需要弄,直接使用传值(会自动调用拷贝构造一个临时变量)就可以啦!

1
2
3
4
5
6
//赋值重载(v没有引用,拷贝构造一个新的传参过来,所以不需要手动再构建一个tmp)
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}

3.5用n个value进行构造

在库中的vector还有一个这样的构造函数,用n个val进行初始化

image

因为我们之前已经实现了一个相关功能的函数resize,我们只需要调用resize就可以完成这个操作!

1
2
3
4
5
6
7
8
//利用n个val进行构造
vector(size_t n, const T& val = T())
:_start(nullptr),
_finish(nullptr),
_endofstorage(nullptr)
{
resize(n, val);
}

只实现一个vector(size_t n, const T& val = T())的版本是不可以的,因为我们忽略了一种情况

1
2
vector<char> v1(10,'x')//可以成功调用
vector<int> v2(10,11) //不能成功调用!

image

为啥第二种情况不行呢?再来看看另外一个构造函数,我们之前实现过的迭代器区间构造

1
2
template <class InputIterator>
vector(InputIterator first, InputIterator last)

你会发现,当我们传的两个参数都是int类型的时候,编译器会直接调用这个模板函数!因为firstlast就是两个相同类型的参数!

通过调试也可以看到在进行构造的时候,调用了这个迭代器区间构造函数

image

为了避免这种情况,我们需要对int类型单独处理一下,修改一下传参即可

1
2
3
4
5
6
7
8
9
//如果不单独重载一个int类型版本,就会被识别成上面的模板函数
//int是不能当作迭代器进行解引用的,会报错
vector(int n, const T& val = T())
:_start(nullptr),
_finish(nullptr),
_endofstorage(nullptr)
{
resize(n,val);
}
  • 这个问题是怎么发现并解决的?

我们可以直接查看stl源码,瞅瞅库里面是怎么实现的

image

可以看到库里面不但重载了一个int类型的版本,还重载了long长整型的情况

到这里,我们的模拟实现就基本完成了!


3.6关于自定义类型的拷贝问题

为什么在3.1的reserve实现中,我使用了赋值重载,而没有使用memcpy

来看看下面这个OJ题目杨辉三角的代码

leetcode118杨辉三角:https://leetcode.cn/problems/pascals-triangle/submissions/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv;
vv.resize(numRows);
for (size_t i = 0; i < vv.size(); ++i)
{
// 杨辉三角,每行个数依次递增
vv[i].resize(i + 1, 0);

// 第一个和最后一个初始化成1
vv[i][0] = 1;
vv[i][vv[i].size() - 1] = 1;
}

for (size_t i = 0; i < vv.size(); ++i)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
if (vv[i][j] == 0)
{
// 中间位置等于上一行j-1 和 j个相加
vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
}
}
}

return vv;
}
};

在这里面,我们有两层vector进行嵌套使用,外层的vector存放的是内层vector的对象。

它的结构如下图

image

这时候如果只用memcpy进行浅拷贝,相当于新的空间里面存放的是的确是新的vector对象,但这些vector对象存放的却是原有数据的指针,而原本的数据已经被我们delete掉了,出现了野指针问题!

反应到代码上,当我们在Solution内部进行一次打印,再在外部进行一次打印,结果就会完全不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void test05()
{
vector<vector<int>> ret = Solution().generate(5);
cout << "外部打印" << endl;
for (size_t i = 0; i < ret.size(); ++i)
{
for (size_t j = 0; j < ret[i].size(); ++j)
{
cout << ret[i][j] << " ";
}
cout << endl;
}
cout << endl;
}

image

使用赋值重载,就可以进行深拷贝,每一个vector对象都能获得新的值,也就不会出现这个问题!

1
2
3
4
5
//reserve代码的一部分
for (size_t i = 0; i < size(); i++)
{
tmp[i] = _start[i];//手动赋值,当成员是自定义类型的时候,会调用=重载
}

image

结语

到这里,vector的模拟实现就完成啦!通过模拟实现可以让我们更好的理解vector容器的结构,也方便后续的使用!

有任何问题,都可以在评论区提出哦!

image