C++vector类

目录

一、vector的使用

1.1、vector的构造，push_back，和 [ ]运算符

1.2、迭代器和范围for

1.3、vector> 和 sort 算法

二、vector的实现

2.1、成员变量

2.2、构造函数，析构函数，赋值重载

​编辑

2.3、push_back，reserve，size，capacity和重载 [] 运算符

2.4、迭代器和范围for

2.5、pop

2.6、insert和erase以及算法库中的find算法

一、vector的使用

1.1、vector的构造，push_back，和 [ ]运算符

从上述图片中可以看出 vector 是使用模版实现的一个容器，我们可以把 vector 看做是一个数组，因为使用了模版，所以 vector 可以存储任意类型的数据，只不过在使用时需要我们自己显式实例化模版，告诉当前 vector 对象存储什么类型的数据。vector 的很多方法使用起来和 string 的很像，所以我们可以类比 string 来学习 vector。

构造函数：

在 vector 的构造函数中，最常用的是无参构造和拷贝构造，使用如图：

push_back 方法：

push_back 方法的作用就是向 vector 对象末尾插入一个数据，使用时只需要像上图代码中那样传入符合存储类型的数据即可。

[ ] 运算符：

这个 [ ] 运算符和 string 类那里的使用起来一样，传入下标，返回该下标对应位置的数据，下标也是从零开始的。前面说过我们可以把 vector 看做是一个数组，这样就很容易理解 [ ] 的用法了。 

使用：

1.2、迭代器和范围for

上面 begin 和 end 方法使用起来和 string 非常相似，但是需要注意接收返回值时的类型写法，vector 的迭代器在 vector 类域里面，所以接收返回值时要指定类域，其次 vector 是用模版写的，所以还要把模版的实例化带上。范围 for 的底层使用的是迭代器，所以支持了迭代器也就支持了范围 for。如图：

vector 也有反向迭代器，这里就不演示了。如图：

vector 使用时的小技巧：假如我们想用 vector 来存储 string 类型的数据。在插入数据时我们可以先创建 string 对象，然后再将该对象存入，也可以直接存放匿名对象，但是这两种方法还是有些麻烦，我们可以利用隐式类型转换，直接存入字符串，它会通过隐式类型转换转换为 string 对象并存储起来。（其他自定义类型，只要支持隐式类型转换都可以这么做）如图：

1.3、vector<vector<类型>> 和 sort 算法

vector<vector<类型>> 在算法题中很常见，我们可以把 vector<vector<类型>> 想象成一个二维数组，这样容易我们理解。如图：

以 vector<vector<int>> 为例，vv 是一个 vector 类型的对象，它的里面存的是一个一个的 vector 容器，而里面的每一个 vector 容器存的是 int 类型的数据，我们可以通过 vv[i][j] 来访问到具体的某一个 int 类型的数据，如图：

上图如果我们使用的是 push_back 方法插入数据就不需要提前更改 size 了，而且 push_back  方法会自动扩容。

sort 算法：

sort 算法不是 vector 的成员方法，这是算法库里面的一个算法，但是可以搭配 vector 在一些算法题中使用，从图中可以看出 sort 算法需要传入一段迭代器区间，它会对这段迭代器区间进行排序，默认是升序，如图：

如果我们需要对一段没有顺序的数据进行降序排列，sort 算法也是可以实现的，sort 算法共重载了两个版本，第一个版本只需要传入一段迭代器区间并排升序，第二个版本除了传入迭代器区间还需要传入一个参数，这个参数叫做仿函数，仿函数并不是一个函数，而是一个类的对象，这个类里面重载了 () 运算符，在这个重载的运算符中编写了比较逻辑，这样就可以通过调这个重载的运算符实现比较并根据比较结果进行排序。C++中有两个写好的仿函数可以在这里使用，一个是greater，一个是 less，通过传入它们，就可以控制升序还是降序，如图：

如果觉得创建仿函数有名对象麻烦，可以直接传匿名对象也可以。

二、vector的实现

2.1、成员变量

首先 vector 是一个可以存储任意类型数据的容器，所以我们需要使用模版来写，其次这里我们仿照库里面的实现来，库里面使用了三个迭代器作为成员变量，其中 _start 指向容器的起始位置（即第一个元素），_finish 指向了最后一个元素的后一个位置，_end_of_storage 指向当前容器总空间的后一个位置，如图：

2.2、构造函数，析构函数，赋值重载

因为使用了模版，所以声明和定义分离会有链接错误，所以我们将所有类的实现的代码写在一个文件中。

无参构造：

无参构造中我们直接将所有的迭代器直接置空就可以了，这里可以显示的写无参构造，也可以直接强制编译器生成默认的，因为后面还会实现别的构造，而一旦有别的构造编译器就不会生成默认构造了，但是我们又有用到无参构造的场景，所以既可以自己写，也可以通过关键字强制生成。如图：

拷贝构造：

拷贝构造只需要遍历 vector 容器，并将里面所有数据通过 push_back 方法插入当前对象中即可，这里可以先提前开好空间，防止 push_back 过程中频繁扩容，影响效率。

用一段迭代器区间进行构造：（也用push_back方法即可）

用 n 个相同元素构造（n有缺省值）：

这里实现构造的思路和拷贝构造一样，但是给的缺省值要注意，如果给0，可能 T 是 int 类型，这样就分不清这个0是缺省值还是赋的值，最合适的值就是当前类类型的匿名对象。但是这里还有一个问题，如果使用者传入的 n 是 int 类型，传入的数据也是 int 类型，这时会走迭代器区间的那个构造，对于这个构造，我们期望的是传入一段迭代器区间，但是对于模版而言，它可以是任何数据类型，实际上只要我们传入两个类型相同的参数，并且没有更合适的构造，就会调用这个构造，因为它推导出来的构造更合适，两个类型都是匹配的，所以为了解决这个问题，我们可以实现一个第一个参数是 int 类型的版本，这样有合适的构造就不会在走模版了。如图：

赋值重载：

这里赋值重载采用 string 实现那里的简便方法，直接交换即可。

析构函数：

2.3、push_back，reserve，size，capacity和重载 [] 运算符

因为在插入数据之前我们需要先判断是否需要扩容，所以我们在实现 push_back 方法之前需要先实现 reserve，而扩容又需要用到当前 vector 的容量和有效元素个数，所以我们还需要先实现一个获取容量大小的 capacity 方法，和一个获取有效元素个数的 size 方法。

capacity 方法只需要用指向当前容器总空间的后一个位置的迭代器和指向开头的迭代器相减就可以，因为这里的迭代器是我们用指针封装的，指针相减可以得到中间的元素个数。如图：

size 同理：

reserve 方法的基本思路就是开辟新空间，将旧数据拷贝到新空间中，在释放旧空间并让指向起始位置的迭代器指向新空间，最后在更新 _finish 和 _end_of_storage。这里需要注意的是如果没有提前记录有效数据个数，更新 _finish 采用的是 _start + size() 就会出问题，因为这时 _finish 没有更新还指向旧空间，但是 _start 已经指向新空间了，size() 方法是通过它们相减得到的有效数据个数，但是这时它们相减得到的结果并不正确。

上述代码对于自定义类型还是有一点小问题，比如当前 vector 对象存储的是 string 类型，因为string 并不是直接存储的字符串，string 内部有很多的成员变量，其中有一个用来存储字符串地址的指针，而 memcpy 执行的是浅拷贝，使用该函数，会将这个指针的值直接拷贝下来而不是新开空间存储字符串，这样就造成了多个 string 对象指向同一块空间，这样释放旧空间的时候，这个新申请的空间里面的 string 对象所指向的字符串空间已经被释放了，这时再访问就造成了野指针。如图：

可以这样解决：

这样赋值调用的是 string 对象的赋值重载，而库里面 string 的实现要么是深拷贝，要么是引用计数的写实拷贝，所以不存在浅拷贝的问题。

push_back 只需要先检查是否需要扩容，当确定空间够用后直接放入数据并更新 _finish 就可以了。

重载 [ ] 运算符：先检查传入的参数是否符合允许访问的位置，在将要访问的数据进行返回就可以了。

测试：

2.4、迭代器和范围for

我们直接用指针封装迭代器，其中 const 迭代器只需要用 const 指针就可以了，这样限制解引用，迭代器本身可以进行加减操作也可以读数据，但是无法修改数据。

begin 和 end 方法：begin 方法只需要返回起始位置的迭代器即可（即_start），end 方法返回最后一个元素后一个位置的迭代器（即_finish）。

测试：（支持迭代器后自然就可以使用范围 for 了）

2.5、pop

pop 的实现只需要 --_finish 就可以了，但是在减之前需要先判断一下是否还有数据。

测试：

2.6、insert和erase以及算法库中的find算法

在实现 insert 之前我们先了解一下 find 算法，因为 vector 库里面没有实现 find 方法，所以如果我们想在 vector 对象里面查找某一个数据，需要使用算法库里面提供的 find 算法。如图：

这个方法需要我们传入一段左闭右开的迭代器区间，和一个要查找的值，他会在这段左闭右开的区间里面进行查找，找到返回该元素所在位置的迭代器，找不到返回传入的 last 迭代器。

注意：左闭右开是指 first 迭代器指向位置的值会被查找，last 迭代器指向位置的值不会被查找。

insert实现：我们实现的 insert 有两个参数，一个是要插入位置的迭代器，一个是要插入的数据，还是一样，插入数据之前需要先判断是否需要扩容，但是扩容这里存在一个问题，如果进行扩容了，那么 _start,_finish,_end_of_storage 都会更新指向新的空间，但是 pos 还指向已经被释放的旧空间呢，所以这时 pos 迭代器就无法使用了，我们管这种问题叫做迭代器失效。为了解决迭代器失效，我们可以先记录这个 pos 与 _start 之间的距离，即数据个数，然后在扩容完成后对 pos 迭代器进行更新。之后就可以开始移动旧数据，插入新的数据了，插入完成后还要更新 _finish。但是这里还涉及到一个迭代器失效问题，我们可以从测试中看出来。

测试：

上面测试中问题的答案是不一定，因为在 insert 方法中传迭代器是传值传入，形参的改变不会影响实参，所以虽然方法中更新了 pos 迭代器，但是 it 迭代器并没有更新，所以一旦进行扩容，it 迭代器就会失效，不扩容就不会。库里面也面临这个问题，它的解决办法就是通过返回值，它将更新后的 pos 迭代器返回，接收返回值就能防止迭代器失效了，这里我们也这样写。

erase 实现通过移动数据将要删除的数据覆盖就可以，然后再更新一下 _finish。如图：

测试：

erase 也面临着迭代器失效的问题，我们可以在VS2022上验证一下，如图：

运行结果：

我们可以看到上面代码的运行报错了，这就是因为 erase 这个位置的指针已经失效了，VS的语法检测非常严格，对于访问失效的迭代器直接报错了，这段代码在 Linux 环境下是不会报错的，但是迭代器同样失效了，所以我们统一认为 erase 后的迭代器就是失效的。失效的原因有两个，一个是erase 后是否会缩容不确定，如果缩容了，就和 insert 一样，迭代器失效，另一个是如果删除的是最后一个元素，因为每删除一个元素 _finish 都会向前移动一位，所以删除最后一位后迭代器就指向了 _finish（或者说 _finish 移动到了这个迭代器的位置），这个位置本就无法访问，所以迭代器也失效了。库里面解决这个问题也是通过返回值，但是如果是第二种情况失效，返回迭代器也无法进行访问（即解引用）。