【C++】STL——vector 深度剖析 及 模拟实现(一)

前言

这篇文章我们来学习一下STL里面的vector，它属于STL中容器的一员，我们先来学习一下它的使用，然后，我们也会对vector进行一个深度的剖析和模拟实现。

1. vector的介绍及使用

1.1 vector的介绍

vector的文档介绍

vector 是表示大小可以更改的数组的序列容器：

其实大家可以认为vector就是我们之前数据结构学的顺序表，那说到顺序表，相信就不用给大家过多解释了。

1.2 vector的使用

下面我们来学习一下vector的使用：

其实我们看一下，vector提供的接口跟string是非常相似的，所以经过前面string的学习，再去学习vector，成本就很低了。

那下面我们还是给大家介绍一些常用的接口。

1.2.1 构造函数

首先我们来看一下vector的构造函数：

首先看第一个

explicit vector (const allocator_type& alloc = allocator_type());

只有一个参数，而且有缺省值，但是这个我们平时一般不用管，这个是用来传空间配置器的

它也可以在模板参数这里传。

我们可以认为这个就是无参的构造函数就行了，就是构造一个空的vector。

注意使用vector需要包对应的头文件。

那vector是一个类模板，经过之前的学习我们知道：

类模板实例化只能显式实例化，即需要在类模板名字后跟<>，然后将实例化的类型放在<>中即可。

类模板不是真正的类，其实例化的结果才是真正的类。

这里我们想往vector里放什么类型的数据，直接指定就行了。

我们继续往下看：

第二个的话就是支持用n个val去构造一个vector对象

然后第三个：

就是支持用一段迭代器区间去构造，这里在string的使用里面我们没有给大家演示，现在我们可以试一下：

另外大家可能注意到了它是一个模板：

也就是说这里我们不仅可以传vector的迭代器，也可以传其它容器的迭代器，只要它们的数据类型能够匹配或者能进行一个转换。

我们可以试一下，比如我们传一个string类型的迭代器：

当然这里s里面是char类型的数据，给vector 其实给过去的是ASCII码值。

另外我们是可以控制传过去的这个迭代器区间的范围的，怎么控制呢？

🆗，其实迭代器我们之前讲的什么正向反向，const迭代器，这些是使用属性；那还有一个特性属性，迭代器严格来说还可以细分为单向迭代器，双向的和随机的，单向的就是只能++不能- -，双向就是可以++也可以- -，那随机就是除了可以++和- -之外还可以+或- 。

那我们学的string和vector的迭代器其实本质就是随机迭代器。

我们试一下：

我们对左边的迭代器++，右边的- -，那这样两边的两个数据是不是就没有放进去啊。

当然这里把数据类型换成char更好看一点：

当然我们说它是随机的，就还可以这样：

不过其实这个构造函数用的不多。

那最后一个就是拷贝构造：

1.2.2 vector对象的遍历

那想遍历vector对象，有哪些方式呢？

我们先创建一个vector对象，尾插几个数据。

有哪些遍历的方式？

首先vector也重载了[ ]，我们可以用for循环+[ ]：

另外：

可以用迭代器，那也就支持了范围for：

当然遍历的同时我们也可以修改它。

1.2.3 vector的迭代器

那vector的迭代器呢我们看到其实还是这几个：

跟string的一样，那在之前文章里我们也对这几个迭代器进行了介绍，所以这里我就不再过多解释了。

直接给大家简单演示一下：

当然如果是const对象就会自动去调用const版本的。

1.2.4 reserve和resize

首先我们来看一下vector的扩容机制：

int main()
{
    // 测试vector的默认扩容机制
    size_t sz;
    vector<int> v;
    sz = v.capacity();
    cout << "making v grow:\n";
    for (int i = 0; i < 100; ++i)
    {
        v.push_back(i);
        if (sz != v.capacity())
        {
            sz = v.capacity();
            cout << "capacity changed: " << sz << '\n';
        }
    }
    return 0;
}

在vs上，我们运行一下：

LinuxG++下：

我们看到和string一样，vector的扩容，在vs上基本上也是1.5倍扩容，在G++上也是二倍去扩。

vs是PJ版本STL，g++是SGI版本STL。

那这个时候：

如果我们知道需要多少空间，直接用reverse把空间开好，是不是就可以减少频繁扩容的一个消耗。

reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。

然后还有resize：

resize在开空间的同时还会进行初始化，影响size。当然如果传的n比size小，那它还会删除多余的数据。

1.2.5 insert和erase

vector的insert和erase于string相比，差别就有点大了：

string的insert和erase呢，还支持我们传下标去确定位置

但是vector呢：

就只支持我们去传迭代器和迭代器区间了。

那要传迭代器的话：

我们就需要先找到目标位置的迭代器，怎么找呢？

我们发现vector并没有提供find这个接口（大家可以去文档里翻，确实没有），那我们怎么获取目标位置的迭代器呢？

🆗，虽然vector自己没有提供，不过算法库里面提供了一个find：

也是一个函数模板，可以传任意类型的迭代器，在指定的迭代器范围去寻找要查找的值，找到就返回该位置的迭代器，找不到就返回last（即我们传过来的迭代器区间的右边界）。

为什么返回last，因为任何一个迭代器区间都是左闭右开的，

那我们来演示一下：

首先试一下insert：

🆗，那我们现在想把pos位置的元素再删掉，可以这样吗？

哦豁，怎么回事？

挂了？

🆗，这里涉及到一个迭代器失效的问题，我们后面也会讲到。

所以，这里要删的话，需要我们重新去找：

当然如果我们可以直接确定要insert或者erase的位置的迭代器，那就没必要find了，比如头删：

那我们vector使用的讲解就差不多到这里了：

因为本身我们已经学了string了，那上手vector就很容易了，成本就很低了，剩下我们没提到的接口，要么就是不重要的，不常用的，要么就是大家一看就会，很简单的，没必要再过多解释了。

1.2.6 vector< char > 能否替代string

然后大家来思考一个问题：vector< char > 能否替代string呢？

答案肯定是不行的！

vector< char >和string感觉好像挺像的，但是还是有差别的：

首先string的话，结尾是有\0的，vector 有吗？

没有啊，除非我们自己插入。

另外，string对象之间的比较是不是有一套自己的规则啊，一个字符一个字符比较ASCII码值。

vector和string是不一样的：

再其次string有+=和find，这下vector根本都没有。

所以vector 是满足不了string的需求的。

2. vector的模拟实现

那接下来，我们就对vector进行一个模拟实现。

2.1 STL_vector源码浏览

那首先我们来一起简单浏览一下STL里面vector的源码，看看源码大致是怎样实现的：

那我们之前介绍STL就说了，STL有好几个版本，我们这里看源码的话推荐大家去看SGI版本的3.0这个版本，大家可能听说过一本书《STL源码剖析》就是用的这个版本。

那大家想一下，我们要了解一个类，首先应该看什么？

是不是要看一下它有哪些成员变量和成员函数啊，然后你想了解哪一个函数，可以再去看它具体的实现。

我们来看一下：

首先我们可以找到这三个应该是它的成员变量，那跟我们之前学的顺序表的结构是不是还有点差异啊，我们之前写顺序表是一个指针指向动态数组，然后一个size，一个capacity是吧。

我们看到它们的类型都是iterator，这不是迭代器嘛。那我们说了迭代器可以理解成一个像指针一样的东西，但不一定是指针，不过我们看到再当前的SGI版本中：

迭代器的实现就是用的原生指针。

也就是说它可以用原生指针实现，但不一定都是用原生指针，那我们现在用的vs（采用的PJ版本）上其实就不是原生指针。

我们可以看一下：

我们看到是一个类，这个版本的实现是比较复杂的。

那这样的话呢：

也就是说它的三个成员变量其实就是三个指针，那它们三个是什么功能呢？我们怎么去源码中去探索呢？

🆗，那我们可以先去考虑看一下构造，在构造函数里是怎么对它们初始化的。

有个无参的构造吧它们都初始化成0 了，但是从这好像看不出什么东西。

那接着我们可以考虑看一下size和capacity，它这里三个指针，是怎么求size和capacity呢？

或许从中我们能发现它们的关系。

首先看到有个size_type其实就是一个typedef：

就是size_t。

那我们再看它这里求size就是end() - begin()，求capacity是end_of_storage - begin()，那这里的end() 和 begin()是啥？

那我们又可以找到end()其实就是finish，begin()就是start。

🆗，那根据这些东西，我们大致就能猜出它们的含义了。

所以它的结构大致是这样一个样子的。

那了解了它的结构，我们就可以自己去实现了。

2.2 vector的结构

新建一个vector.h，定义一个名为vector的类模板

namespace yin
{
    template<class T>
    class vector
    {
    public:
        typedef T* iterator;
    private:
        iterator _start;
        iterator _finish;
        iterator _end_of_storagre;
    };
}

为了防止冲突，我们还是定义在自己的命名空间里。

vector本质是一个类模板，那我们实例化时指定什么数据类型，vector里面就放什么类型的数据。

那结构定义好，接下来我们就可以实现它的成员函数了。

2.3 常用接口实现

有了string模拟实现的经历，那我们来快速的实现一下。

构造

首先写一下构造：

最开始呢，我们都初始化成空。

push_back

然后来一下push_back：

那push_back的话首先是不是要判断是否需要扩容啊，那确保容量够了，然后就插入数据：

size和capacity

那现在扩容还没实现，扩容会影响capacity，先写一下size()和capacity()

有了之前string模拟实现的经历，相信有些东西就不用给大家过多解释了。

reverse

接着我们来实现一下reverse：

同样为了防止缩容，这里也是n大于capacity才去扩，那扩的话就直接开新空间，然后如果原来有数据，就拷贝到新空间来，并释放旧空间，记得更新_start，_finish和_end_of_storagre

回过头来看push_back：

扩容的逻辑我们就可以实现了：

那我们这里就选择扩两倍，但是注意要进行一个判断，如果capacity为0，不能直接乘2，可以给个初始大小

operator[ ]

再来重载一下[]：

🆗，那先写到这里，我们来简单测试一下：

但是呢，我们发现程序挂掉了。

什么原因呢？

通过调式，我们会发现问题出现在这里：

大家看出来是什么问题了吗？

size()怎么算的啊？

是不是_finish - _start，但是，这里扩容之后，程序走到这一步，_finish 还是原来的_finish ，但是_start是不是已经变了啊。

这里第一次扩容之后，_start有了一个有效的地址，但是_finish还是空指针（0）

_finish = _start + size();

即_finish = _start + （_finish - _start）;

所以最后_finish 还是空指针，那后面后面一解引用就挂了。

那这里我们修改一下：

扩容之前，先保存一下原来的size

然后：

就可以了。

begin和end

然后我们再来写一下begin和end：

那这下我们是不是就可以用迭代器访问我们的vector了，那当然也就支持范围for了：

pop_back

接着再来实现一下pop_back:

怎么删？

是不是直接--_finish;

但是，如果一直pop的话，_finish是不是就会越界走到_start前面了，所以这里我们可以加一个断言判断一下：

不为空，再尾删。

那我们实现一下判空的接口：

测试一下：

就可以了，我们一直删断言也可以检查出来。

const成员函数

那同样的，有些成员函数包括迭代器我们是不是要提供普通版本和const两个版本啊:

这样普通对象就调普通版本，const对象就调const版本，那这个我们在之前string的模拟实现里也给大家进行了比较详细的讲解，所以这里我们就直接实现了。

我们看到直接调的话是会存在权限放大的问题。

然后就可以了：

resize

然后我们来实现一下resize：

那resize的话就要分情况了，string我们也实现过嘛，如果n<当前的size，那要删除数据，但不缩容；如果n>size，那又要分一下，n>size并且n>capacity，那要扩容，然后初始化，n>size但n

那现在有一个问题，这里的val是有缺省值的，也就是我们指定初始化的内容就按缺省值初始化，那这里val的缺省值要怎么给？

给个0，可以吗？

如果是vector那给0当然可以，但是，现在我们实现的是一个类模板，针对所有类型，包括自定义类型，那都给0，肯定是不合适的，怎么办？

🆗，我们来看一下库里面的实现是怎么写的：

这里的value_type其实就是T的typedef。

所以库里面是这样写的：

什么意思啊？

🆗，它这里这样写是不是调用默认构造函数产生一个匿名对象去作为这个缺省值啊。

那这样的话，如果这里的模板参数T是string或者其它的一些自定义类型，那这样是不是都说得过去啊，但是如果是int、double这样的内置类型呢？

它们好像没有默认构造函数这一说啊，那它们也可以吗？

🆗，那既然库里面这么写了，那就肯定是可以的。

理论上来说，内置类型是没有构造函数这一说的，构造函数是针对自定义类型的，但是有了模板以后呢？

内置类型就也需要支持有构造函数了。

我们可以试一下：

可以的，但是我们正常不会这样写的。

所以能够这样最主要还是为了模板。

不过这里对于指针类型我们直接这样写会报错

而本身我们也不会这样写，但是到了模板里面指针类型也照样支持：

所以：

这里写成这样，就可以统一处理任何类型了。

那我们继续实现我们的resize：

完成了上面的内容，那就剩初始化了，那搞定了val的问题，接下来直接填值就行了

那就写好了，我们来试一下：