文章目录

全部的实现代码放在了文章末尾准备工作包含头文件定义命名空间和类类的成员变量

迭代器迭代器获取函数

构造函数默认构造使用n个值构造迭代器区间构造解决迭代器区间构造 和 用n个值构造的冲突拷贝构造

析构函数swap【交换函数】赋值运算符重载emptysize和capacityoperator[]reserve【调整容量大小】resize【调整size大小】push_backassign【把所有数据替换成迭代器区间中的数据】insert为什么扩容会导致pos迭代器失效？为什么要返回pos-1？

erase为什么要返回pos？

全部代码

全部的实现代码放在了文章末尾

准备工作

创建两个文件，一个头文件<code>myvector.hpp，一个源文件 tesr.cpp

【因为模板的声明和定义不能分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件myvector.hpp中】

mystring.hpp：存放包含的头文件，命名空间的定义，成员函数和命名空间中的函数的定义

test.cpp：存放main函数，以及测试代码

---

包含头文件

iostream：用于输入输出

assert.h：用于使用报错函数assert

---

定义命名空间和类

在文件myvector.hpp中定义上一个命名空间myvector

把vector类和它的成员函数放进命名空间封装起来，防止与包含的头文件中的函数/变量重名的冲突问题

类的成员变量

参考了stl源码中的vector的实现

成员变量有3个，都是迭代器

画图理解一下

---

迭代器

迭代器

因为存放数据的空间是从堆区申请的<code>连续的内存，且只是简单模拟

所以我用了指针T*作为普通迭代器，const T*作为const迭代器

【T是vector中存储的数据的类型】

直接把T*重命名为iterator，把const T*重命名为const_iterator就完成了迭代器的实现

迭代器获取函数

因为const修饰的对象只能调用const修饰的成员函数

所以如果是const修饰的对象调用begin()和end()的时候，就会自动调用到const修饰的begin和end.

---

构造函数

默认构造

因为stl库里实现的默认构造是没开空间的，所以默认构造直接让3个成员变量都为<code>nullptr就行

直接在声明的时候给缺省值，缺省值会传给成员初始化列表

即

而成员初始化列表会比构造函数先调用

并且每个构造函数调用之前都会先调用成员初始化列表，这样不管调用哪一个构造函数初始化，都会先把3个成员变量初始化成<code>nullptr

---

使用n个值构造

---

迭代器区间构造

---

解决迭代器区间构造 和 用n个值构造的冲突

当重载了迭代器区间构造和用n个值构造的时候

如果传入的<code>两个参数都是int类型的话就会报错

为什么？

因为在模板函数构成重载时，编译器会调用更合适的那一个

什么叫更合适？

就是不会类型转

如果传入的两个参数都是int类型，那么调用的应该是使用n个值构造，因为没有int类型的迭代器

但是使用n个值构造的第一个参数是size_t,int传进去要隐式类型转换

而调用迭代器区间构造，两个int的实参传进去，就会直接把InputIterator推导成int，不会发生类型转换，所以编译器会调用迭代器区间构造

解决方法：

再重载一个使用n个值构造的函数，把第一个参数改成int，这样根据模板偏特化，就会在都不类型转换时优先调用第一个参数特化成int的那个构造函数

---

拷贝构造

因为成员申请了堆区空间，所以要<code>深拷贝

【不知道什么是深拷贝的可以看我这篇文章：类和对象【三】析构函数和拷贝构造函数】

---

析构函数

---

swap【交换函数】

因为存放数据的空间是在堆区开辟的，用3个成员变量去指向的

所以直接交换两个对象的成员变量就可以了

不需要拷贝数据

---

赋值运算符重载

因为成员申请了堆区空间，所以要<code>深拷贝

【不知道什么是深拷贝的可以看我这篇文章：类和对象【三】析构函数和拷贝构造函数】

为什么上面的两句代码就可以完成深拷贝呢？

这是因为：

使用了传值传参，会在传参之前调用拷贝构造，再把拷贝构造出的临时对象作为参数传递进去

赋值运算符的左操作数，*this再与传入的临时对象obj交换，就直接完成了拷贝

在函数结束之后，存储在栈区的obj再函数结束之后，obj生命周期结束

obj调用析构函数，把指向的从*this那里交换来的不需要的空间销毁

---

empty

---

size和capacity

---

---

operator[]

因为

const修饰的对象只能调用const修饰的成员函数

所以const对象只会调用下面的那个重载

---

reserve【调整容量大小】

---

resize【调整size大小】

---

push_back

---

assign【把所有数据替换成迭代器区间中的数据】

---

insert

<code>iterator insert(iterator pos, const T& val)

{

assert(pos <= _finish); 防止插入的位置是 越界的

if (_finish == _end_of_storage) 如果容量满了

{

记录一下扩容前的pos与start的相对位置

因为扩容的话会导致pos迭代器失效

size_t n = pos-_start;

if (capacity() == 0) 如果容量为0

reserve(2);

else 容量不为0，就扩2倍

reserve(capacity() * 2);

更新pos

pos = _start + n;

}

iterator it = end()-1;

把pos及其之后的数据向后挪动一位

while (it >= pos)

{

*(it + 1) = *it;

it--;

}

_finish++;

*pos = val;插入数据

返回指向新插入的数据的迭代器

用于处理迭代器失效问题

return pos-1;

}

为什么扩容会导致pos迭代器失效？

因为扩容之后原来的空间被释放了

又因为使用的扩容方式是reserve所以那3个成员变量的值扩容后可以指向正确的位置。

但是pos如果不更新的话，就还是指向被释放的空间，就成了野指针了。

更新方法也很简单，保存扩容之前的pos与start的相对距离n，扩容之后再让pos=_start+n就可以了。

为什么要返回pos-1？

这是stl库里面处理迭代器失效的方法之一

因为我们在使用stl库里面的insert函数的时候，是不知道什么时候会扩容的【每个平台实现的vector<code>是不同的】

只能默认使用了之后传进去pos，在调用一次insert之后就失效了，失效的迭代器是不能使用的。

所以如果还要用pos就要把它更新一下，stl库里提供的更新方式就是：

==让pos接收insert的返回值。【pos是传值调用，形参改变不影响实参】==并且规定insert的返回值要是指向新插入的数据的迭代器

---

erase

为什么要返回pos？

因为使用了erase之后的迭代器也会失效，需要提供更新的方法

为什么使用了erase之后的迭代器会失效？

不确定是否删除到一定数据时，会不会减小容量，以适应size

此时和insert的一样，因为不能部分释放，所以会把原来的空间释放掉，申请新空间不确定是否删除的是最后一个数据，如果是那么调用完erase之后pos指向的就

<code>不是vector的有效数据范围了

所以和insert一样，调用了erase之后如果还要使用pos，就要接收返回值。

stl库里面规定erase的返回值是指向删除数据的下一个数据的迭代器，因为挪动覆盖的原因，下一个数据就是pos指向的数据，所以返回pos【没有接收返回值的迭代器，在检测较严格的编译器中，不管指向的位置是否正确，都会禁止使用，使用了就报错】

---

全部代码

#include<iostream>

#include<assert.h>

using namespace std;

namespace myvector

{

template<class T>

class vector

{

public:

typedef T* iterator;

typedef const T* const_iterator;

vector()

{

}

vector(size_t n,const T& val=T())

{

_start = new T[n];//从堆区可容纳申请n个元素大小的空间

_finish = _start;//还没有 有效数据 时start与finish重合

_end_of_storage = _start + n;//指向最大容量 的 下一个位置

for (size_t i = 0; i < n; i++)//循环n次

{

push_back(val);//把数据尾插进去

}

}

vector(int n, const T& val = T())

{

_start = new T[n];

_finish = _start;

_end_of_storage = _start + n;

for (size_t i = 0; i < n; i++)

{

push_back(val);

}

}

template<class InputIterator>

vector(InputIterator first, InputIterator last)

{

//使用迭代器进行循环

while (first != last)

{

push_back(*first);//把数据尾插进去

++first;

}

}

void swap(vector<T>& obj)

{

//使用库里面的swap交换3个成员变量

std::swap(_start, obj._start);

std::swap(_finish, obj._finish);

std::swap(_end_of_storage, obj._end_of_storage);

}

vector(const vector<T>& obj)

{

size_t size = obj.size();//记录有效数据个数

size_t capacity = obj.capacity();//记录容量大小

_start = new T[capacity];//申请与obj相同大小的空间

_end_of_storage = _start + capacity;//指向最大容量 的 下一个位置

for (size_t i = 0; i < size; i++)//循环size次

{

_start[i] = obj._start[i];//把有效数据拷贝过去

}

_finish = _start + size;//指向最后一个有效数据的 下一个 位置

}

~vector()

{

//释放从堆区申请的空间

delete[] _start;

//把3个成员变量 置空

_start = nullptr;

_finish = nullptr;

_end_of_storage = nullptr;

}

vector<T>& operator= (vector<T> obj)

{

swap(obj);

return *this;

}

bool empty() const

{

//如果size等于0，就是空的

return size() == 0;

}

size_t size()const

{

//finish指向最后一个有效数据的 下一个

//start指向第一个有效数据

//两个指针相减就是 两个指针之间的 数据个数

return _finish - _start;

}

size_t capacity()const

{

//end_of_storage指向最大容量的 下一个位置

//start指向第一个有效数据

//两个指针相减就是 两个指针之间的 数据个数

return _end_of_storage - _start;

}

T& operator[] (size_t n)

{

//防止越界访问

assert(n < size());

//因为start是T*类型，所以可以像数组一样直接随机访问

return _start[n];

}

const T& operator[] (size_t n) const

{

//防止越界访问

assert(n < size());

//因为start是T*类型，所以可以像数组一样直接随机访问

return _start[n];

}

iterator begin()//普通起始迭代器

{

return _start;

}

iterator end()// 普通结束迭代器

{

return _finish;

}

const_iterator begin()const//const起始迭代器

{

return _start;

}

const_iterator end()const//const结束迭代器

{

return _finish;

}

void reserve(size_t n)

{

if (n > capacity())//要调整的容量n，大于capacity才扩容

{

size_t origsize = size();//记录扩容前的size

T* tmp = new T[n];//申请空间

//把原来的数据拷贝到 新空间

for (size_t i = 0; i <origsize; i++)

{

tmp[i] = _start[i];

}

delete[] _start;//释放旧空间

//让成员变量指向 新的空间的相对位置

_start = tmp;

_finish = _start + origsize;

_end_of_storage = _start + n;

}

}

void resize(size_t n, const T& val = T())

{

if (size() == n)//如果size与要调整的n相等

return;//直接返回

else if (size() < n)//如果size小于n

{

if (n > capacity())//如果n大于capacity

{

reserve(n);//把容量调整到n

}

//再把size到n 之间的空间用 val填上

for (size_t i = size(); i < n; i++)

{

push_back(val);

}

}

else//如果size 大于 n

{

//就调整标识有效数据的末尾的finish

//让size=_finish - _start = n

_finish = _start + n;

}

}

void push_back(const T&val)

{

if (_end_of_storage == nullptr)//如果容量为0

{

reserve(2);//把容量调整到可容纳 2个元素大小

}

else if (_finish==_end_of_storage)//容量满了

{

reserve(capacity()*2);//扩容

}

//在下标为size【最后一个有效数据的下一个】

//插入值

_start[size()] = val;

_finish++;//更新有效数据的末尾

}

void pop_back()

{

assret(size() > 0);

_finish--;

}

template <class InputIterator>

void assign(InputIterator first, InputIterator last)

{

delete[] _start;//释放原来申请的空间

//把3个成员变量置空

_start = nullptr;

_finish = nullptr;

_end_of_storage = nullptr;

while (first != last)

{

//一个一个尾插进去

push_back(*first);

++first;

}

}

iterator insert(iterator pos, const T& val)

{

assert(pos <= _finish);//防止插入的位置是 越界的

if (_finish == _end_of_storage)//如果容量满了

{

//记录一下扩容前的pos与start的相对位置

//因为扩容的话会导致pos迭代器失效

size_t n = pos-_start;

if (capacity() == 0)//如果容量为0

reserve(2);

else//容量不为0，就扩2倍

reserve(capacity() * 2);

//更新pos

pos = _start + n;

}

iterator it = end()-1;

//把pos及其之后的数据向后挪动一位

while (it >= pos)

{

*(it + 1) = *it;

it--;

}

_finish++;

*pos = val;//插入数据

return pos-1;

}

template <class InputIterator>

void insert(iterator pos, InputIterator first, InputIterator last)

{

assert(pos <= _finish);

size_t len = 0;

InputIterator in = first;

while (in != last)

{

in++;

len++;

}

if (_finish + len >= _end_of_storage)

{

size_t n = pos - _start;

if (capacity() == 0)

{

reserve(len);

}

reserve(capacity()+len);

pos = _start + n;

}

iterator it = end() - 1;

while (it >= pos)

{

*(it + len) = *it;

it--;

}

_finish+=len;

it = pos;

while (it != pos + len)

{

*it = *first;

it++;

first++;

}

}

iterator erase(iterator pos)

{

// 防止传入的pos 是越界的

assert(pos < _finish);

iterator it = pos;

//把pos之后的数据都向前挪动一位，把pos指向的位置给覆盖掉

while (it <end()-1)

{

*it = *(it + 1);

it++;

}

//更新数据末尾 迭代器

_finish--;

//返回pos

return pos;

}

iterator erase(iterator first, iterator last)

{

assert(first >= begin());

assert(last <= end());

iterator fi = first;

iterator la = last;

size_t len = last - first;

while (la != end())

{

*fi = *la;

fi++;

la++;

}

_finish -= len;

return first;

}

private:

//start指向从堆区申请的空间的 起始 位置，与begin()返回的迭代器相等

//标识有效数组的开始

iterator _start = nullptr;

//finish指向 最后一个有效数据的 下一个位置，与end()返回的迭代器相等

//标识有效数据的结束

iterator _finish = nullptr;

//_end_of_storage指向从堆区申请的空间的 末尾的 下一个位置

//标识容量

iterator _end_of_storage = nullptr;

};

}