1.前言

最近把STL源码剖析的第四章序列式容器看了一遍。

但是看完之后,好像有些东西还没有装进自己的脑海里,所以总结一下每个容器的要点。

在大致看完之后,会发现有很多东西与自己之前的想法是完全不同的。

首先先知道迭代器的类型

· Input iterators 提供对数据的只读访问。
· Output iterators 提供对数据的只写访问。
· Forward iterators 提供读写操作,并能向前推进迭代器。
· Bidirectional iterators提供读写操作,并能向前和向后操作。
· Random access iterators提供读写操作,并能在数据中随机移动。

第一次用vector的时候,大概是大一的时候,还记得是hxk给我推荐这个容器,让我学一下,学了之后,真好用!

因为他类似于数组,但是不用再用一个变量来记录元素的个数,直接size()方法就可以获取到元素个数,很方便。

删除元素可以erase(iterator) 就可以,不用自己去移动元素。

当时是感性的感知,但是对内部机制的了解也是猜测,今天来看一下大致的实现。

2.vector实现的结构

vector有三种迭代器:
start:所使用空间的首部,finish:所使用空间的尾部(最后一个元素的下一个位置),end_of_storage(全空间的尾部)

所有的类方法都是根据这三个元素来实现的。

我自己总结了以下要点:

A.vector的内存分配比较特殊,因为他是随机迭代器,所以需要连续的内存空间来存储。如果当前vector的空间不够了,
是不会在当前内存的尾部继续申请一段空间的,因为很有可能分配不到自己需要大小的空间。而是另辟一块新的空间,
能达到目标内存大小的值,然后把原来vector的数据拷贝过去。

B.vector申请空间以及释放空间都是很特殊的,因为vector涉及到频繁的插入删除元素,所以可能设计到频繁的申请
释放空间。然后这种频繁的对空间的操作会大大降低效率(如上面频繁的复制元素),所以vector总会有一些预留的
空间,这个策略是:如果当前的空间不足,新的内存大小等于当前内存大小的两倍,以此递增。但是erase并不会
影响整个的空间大小的变化。erase的过程是把当前迭代器后面的元素移动到当前位置,并释放当前迭代器指向的对象。

iterator erase(iterator position) { //移除 position迭代器
if (position + 1 != end())
copy(position + 1, finish, position); //往前移动元素
–finish; //尾部指针移动
destroy(finish); //析构指向的对象
return position;
}

insert的时候原理也差不多:
首先判断当前剩余的空间是否够用,如果不够用,申请新的空间(两种策略,
要么是原空间大小的两倍或者插入元素的个数+原空间大小),然后copy元素进去,

欢迎留言

*