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

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

前言

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

1. vector的介绍及使用

1.1 vector的介绍

vector的文档介绍

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

0ab076b0e1044262aa5164492e6f637a.png

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

1.2 vector的使用

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

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

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

1.2.1 构造函数

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

67ce8d35ab0e4594aa2bef415daa08aa.png

首先看第一个

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

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

133def5eae3b499e9e9de7ae3284782e.png

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

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

a65dd87afee749dbb4583e4ec8c92f53.png

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

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

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

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

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


我们继续往下看:

3d1eb07aebef4d6e8ba3e2180f4887cd.png

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

b53335cfc05b438a85fa8fbe6da8281e.png

然后第三个:

9685a73faad3426a9976846e3e33d825.png

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

8ab9e07525844e0182b6a28d43dd3734.png

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

d5b4229056584860b46318c231b79c5b.png

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

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

9c2d211ce0bc44f1b248e7482c4401da.png

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

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

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

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

我们试一下:

e1b4b3b4d1ca45a39fb3e4306086d8d9.png

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

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

0f249b6e371d498e8bc94b068b1a3b65.png

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

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

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

308309cbf46f4833af4dba876b922cb8.png

62b47329b2be460b96ff9bfb71d8a8bd.png

1.2.2 vector对象的遍历

那想遍历vector对象,有哪些方式呢?

c14ca0623f9c42d29fb19b4b44ce2a61.png

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

有哪些遍历的方式?

4e9b2b0e9acf466084506e95ab0cb48a.png

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

d3c2a820c2a84fee85ed483fe603ae53.png

另外:

cc6dae1f9e5b45aba1594f959ea7bc9a.png

可以用迭代器,那也就支持了范围for:

05ce1c947b9546c493bb643863881ba6.png

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

1.2.3 vector的迭代器098357e8a85d4d2ab226901be3f1b2d2.png

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

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

66d2db2af37e433189ea2a653cbf89a4.png

c262840b1637402eaf74fd515f0e0bb3.png

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

0aea036d64654570b537390f51663dc6.png

92182d2a35964ddd80a8e92d173c252c.png

当然如果是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上,我们运行一下:

98d4ce5d37ce436bbb94ecde7c825578.png

LinuxG++下:

7d23f1d98bff400dbc1d498bc442be67.png

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

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

那这个时候:

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

a88926402a80458b8699a39acf057925.png

a484405fe9664e76b67a0a800b37ef7a.png

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

然后还有resize:

a4fe98f930254724a6cc4e9b835da6b9.png

a9d631028db84b98a8e17d5b10173352.png

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


1.2.5 insert和erase

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


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

60f5965203eb4f1f89feef926c5081f6.png但是vector呢:

7764685830ec4fd2844eaefe6b8c62b6.png

73049a5760974764a586d7ff5f3e1ea7.png

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


那要传迭代器的话:


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

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

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

099d5f2289d74b3e94e36034e0a73db3.png

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

c9b049ebfba04e54908671ad257c467f.png

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

那我们来演示一下:

首先试一下insert:

e79661e0adaa4c2ca6c80246b2b0c7b4.png

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

94f7be869784484f8728367e20d3e0d1.png

哦豁,怎么回事?

挂了?

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

所以,这里要删的话,需要我们重新去找:

a14f6bbd2cf74e4a9592f5fdeda523cb.png

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

a931003f5b5549eaaf6d40f9a7b91215.png

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


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


1.2.6 vector< char > 能否替代string

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


答案肯定是不行的!

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

首先string的话,结尾是有\0的,vector 有吗?

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

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

vector和string是不一样的:

7a9173834ad24bb9b95b445ca8c8a071.png

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

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


2. vector的模拟实现

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


2.1 STL_vector源码浏览

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


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


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


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

我们来看一下:

98ea9a0fc98a4cdc8774ac48d7d3c381.png

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

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

c3effb93b9b74af59efdc41e50837d71.png

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

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

我们可以看一下:

5242e20bf5c943fdb478f75675562dc2.png

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

那这样的话呢:


053ae585ede1482ea6810e968b51f6d7.png

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

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

7dec0f4fd8334f409e2a1de3bcf6d30a.png

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

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

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

d6ef5339fa004be4b3c160cda5d3dc01.png

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

a7d3f6653ace4de89d71eb14c1e70e8c.png就是size_t。

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

58307ae63cb14398ab5ef87453bfb619.png

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

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

4d1fd80c1619470bbca866a58bdf9242.png


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

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

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模拟实现的经历,那我们来快速的实现一下。


构造

首先写一下构造:

9bda67e7beb249f5980d94d0fdf8844d.png

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

push_back

然后来一下push_back:

那push_back的话首先是不是要判断是否需要扩容啊,那确保容量够了,然后就插入数据:9123003ffca6451a89dbf10f27713026.png

size和capacity

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

148838ed85884118aac02d1f8eb4b2c3.png

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


reverse

接着我们来实现一下reverse:


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

a21521ccaf3e4a69b3dec4658f469530.png

回过头来看push_back:

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

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

0558882d77c249b5bcb3a32430e36b26.png

operator[ ]

再来重载一下[]:

6614d4b854444747b1b8cfa34687c76b.png

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

67974bc47bde482bacc7afb181a4bbed.png

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

什么原因呢?

通过调式,我们会发现问题出现在这里:

f8806172aedc40c583d0b94080b72e5b.png

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

648c034624104d25b9df1b939bf62424.png

size()怎么算的啊?

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

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

_finish = _start + size();

即_finish = _start + (_finish - _start);

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

那这里我们修改一下:

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

565127e0d5ee45a885f45d6695770dce.png然后:

92ca6415e81d46cd82df4b8e9a7edd17.png

就可以了。

begin和end

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

b67e697ace3341f0978660a5093dba94.png

那这下我们是不是就可以用迭代器访问我们的vector了,那当然也就支持范围for了:a3293ca0a7f44ebda49f8968a0e573be.png

pop_back

接着再来实现一下pop_back:

怎么删?

是不是直接--_finish;

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

       ef50c918113a450baaa95c1ddeb8a2d9.png                                      

不为空,再尾删。

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

e0349baa64934812952011661a65d47a.png e0349baa64934812952011661a65d47a.png 测试一下:

04ec09c157ac43d49b176d647a561ce7.png

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


const成员函数

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


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

0909325c43dc45c9a7ad8fbd72945d94.png

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

70ecf8f3d83e4baeb2d1f0ff5ee1bd1b.png

496c11d72cfa4b70b7761e90659195cd.png

93dae46fda814dfc832c00069c3a40c3.png

然后就可以了:

bc43f45769864c60b65be22c7d7d51b8.png

resize

然后我们来实现一下resize:


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

ac52268aa585443f8f844bf039cf4f59.png

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

给个0,可以吗?

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

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

1ac086cd3b704b1fa2924f87a075d499.png

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

205792cdd27f41ae8b8554240451cd6a.png

所以库里面是这样写的:

什么意思啊?

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

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

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

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

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

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

我们可以试一下:

58142ad8cddd43a6834e00bf0556661b.png

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

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

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

0c0121ac366246c28a2a2955c759d7ab.png

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

b94987b8905748b3ad1f8c6a2e816c7a.png

所以:

29452c834fe94d6f855cf97208979405.png

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

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

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

9652053de13f4238bf4dd699f2aaf22f.png

那就写好了,我们来试一下:

5d402b5e048a4a3382e5357cbaf0ee57.png



目录
相关文章
|
13天前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器,包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组,能够根据需要自动调整大小,提供了丰富的操作接口,如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后,还展示了如何使用`vector`创建字符串数组,体现了`vector`在实际编程中的灵活性和实用性。
35 4
|
15天前
|
C语言 C++ 容器
【c++丨STL】string模拟实现(附源码)
本文详细介绍了如何模拟实现C++ STL中的`string`类,包括其构造函数、拷贝构造、赋值重载、析构函数等基本功能,以及字符串的插入、删除、查找、比较等操作。文章还展示了如何实现输入输出流操作符,使自定义的`string`类能够方便地与`cin`和`cout`配合使用。通过这些实现,读者不仅能加深对`string`类的理解,还能提升对C++编程技巧的掌握。
37 5
|
15天前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色,它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作,帮助读者更好地理解和掌握`string`类的应用。
25 2
|
20天前
|
存储 算法 Linux
【c++】STL简介
本文介绍了C++标准模板库(STL)的基本概念、组成部分及学习方法,强调了STL在提高编程效率和代码复用性方面的重要性。文章详细解析了STL的六大组件:容器、算法、迭代器、仿函数、配接器和空间配置器,并提出了学习STL的三个层次,旨在帮助读者深入理解和掌握STL。
40 0
|
2月前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
74 5
|
2月前
|
存储 C++ 索引
【C++打怪之路Lv9】-- vector
【C++打怪之路Lv9】-- vector
23 1
|
2月前
|
存储 自然语言处理 程序员
C++常用基础知识—STL库(1)
C++常用基础知识—STL库(1)
67 1
|
2月前
|
编译器 C++
【C++】—— vector模拟实现
【C++】—— vector模拟实现
|
2月前
|
算法 安全 Linux
【C++STL简介】——我与C++的不解之缘(八)
【C++STL简介】——我与C++的不解之缘(八)
|
2月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
29 0