好对待好好珍惜

vector实现时最难想的是赋值重载时的现代写法很妙最有趣的是两种迭代器的失效问题。

与数组相同但又多少有点不同。

vector是一个序列式容器其中的元素都可序ordered但是未必有序sorted本质上是可变数组尾插尾删效率较高。

二、vector如何实现

源代码中vector的实现使用到了alloc空间配置器但是鉴于自身技术水平个人只在本文中阐述如何实现无alloc版本的vector。

因为vector是一段连续的物理存储空间实现增删查改时需要对位置进行、--、、-、、-、-这些都是普通指针就具备的能力所以vector提供的是Random

Access

vector是一段连续的物理空间其中SGI版本使用了三个指针去管理这个变长数组、使用了两个unsigned

与之前学习数据结构实现的动态顺序表内存管理其实大同小异一开始有一块默认大小的内存

1.push_back()

_endOfStorage){reserve((capacity()

capacity()

原stl给出的模板中insert()是返回了一个迭代器指向插入元素的位置。

目的若迭代器已经失效尽管在增容操作中更新迭代器的值进行规避风险但是调用时的迭代器仍为野指针失效状态若后续操作需要使用插入元素位置那就会在此出现问题所以可以再用这个迭代器接受insert()的返回值来进行更新。

代码如下:

①使用一块新的、够大的tmp空间去拷贝原来_start指向的数据

但是此时传进来的、想要插入数据的迭代器仍然指向原来的_start空间这个迭代器就变成了野指针再下一步对这个迭代器指向位置进行操作时就会非法访问所以需要在进行扩容操作是对于迭代器也进行相应的更新尽量避免失效问题。

4.erase()

原stl给出的模板中erase()是返回了一个迭代器指向删除元素的位置的下一个位置。

A因为删除操作本质上是对数据的覆盖这样一来从操作位置开始向后的数据向前挪动也相当于操作位置向后移动了一位指向了下一个位置。

代码如下:

erase()的迭代器失效主要是因为迭代器的意义改变当然也有野指针的问题。

①意义改变当数据向前挪动时这个迭代器已经不再是我们想要的迭代器了他一次性向后跳了两个位置。

②野指针当数据向前挪动时迭代器可能跳过了_finish当第一次与_finish相遇时begin的操作还在继续进行从而继续向后移动宛如脱缰野马永远不可能再停下与_finish相遇才会结束。

迭代器

改变的是容器的容量需要进行开辟空间、释放空间、拷贝数据的操作效率不是很高也正因为扩容的效率不高所以才有了_endofStorage和_finish去标识容量与元素个数。

代码如下

valueType[newCapacity]();size_t

size();//

因为memcpy()进行的是位操作如果copy的是内置类型int、char等那么直接使用memcpy()会效率很高很方便但是牵扯到指针这会导致内存错误

当两个指针的内容相同那就意味着它们指向了同一块空间如果一个指针释放另一个指针仍对其进行操作就会使得内存发生错误。

改进版

valueType[newCapacity]();size_t

size();//

①如果newSize比size小那么就发生了删除直接改变_finish即可但是不缩容以防后续操作频繁删除增容、频繁向操作系统申请、释放内存造成抖动。

vaueType

长增长并初始化else{reserve(newSize);while

(_finish

obj.capacity();//memcpy(_start,

obj._start,

使用tmp变量让其使用构造函数构造出我们想要copy的对象然后将tmp和我们将要copy的对象进行交换从而帮助我们实现copy构造。

swap(tmp,

*this)这一点就是将*this中的垃圾扔给了tmptmp还把自己有用的数据全部交给了*this就好比是外卖员替你送了外卖还得帮你扔垃圾。

但是很明显的是已有的构造函数并不能根据传进来的obj对tmp进行构造。

我们需要重载实现一个支持用迭代器区间的copy构造函数stl本来也支持这样的方式构造。

见下一点

代码如下

现代写法//类模板的成员函数也可以变成函数模板vector(const

vectorvalueType

obj):_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){vectorvalueType

tmp(obj.begin(),

其他的迭代器string、int、char等都可以通过迭代器去构造。

class

InputIteratorvector(InputIterator

first,

last){this-push_back(*first);first;}}

4.析构

析构是释放空间因为三个指针指向的是同一段空间所以只需要释放_start。

代码如下

size就是_finish与_start之间的距离使用两个指针相减即可得到。

代码如下

ps但是需要注意的是这两个成员函数最好实现为const成员函数因为在copy构造与的default构造时传的参数均使用了const。

常对象与非常对象都可以用const

3.访问元素

必须是begin与end同名才能使用范围foriterator

begin()

②copy构造是相对于一个即将创建一个已经存在的对象之间的操作。

②需要传引用返回减少拷贝

与copy构造相同的是它也要实现释放旧空间、开辟新空间、拷贝数据。

传统写法vectorvalueType

(valueType*)calloc(obj.capacity(),

new

valueType[obj.capacity()];_finish

_start

(valueType*)calloc(obj.capacity(),

new

valueType[obj.capacity()];_finish

_start

obj.capacity();//memcpy(_start,

obj._start,

这种写法很巧妙地使用了传值传参需要进行拷贝构造的特点利用这一点在传参的时候就可以深拷贝出来一个obj这样进行交换的时候就不会把原来的obj更改。

代码如下

_finish);std::swap(tmp._endOfStorage,

_endOfStorage);}

vector的实现是对于stl源码的一次深入理解但是仍然没有学会alloc只学习了一部分自己模拟实现vector不在于造一个更好的轮子但是可以帮助我更好的了解它、使用它。