目录

成员变量与迭代器

size

capacity

empty

迭代器有关函数

实现默认成员函数的前置准备

reserve

​编辑

​编辑

push_back

构造函数

无参构造

迭代器区间构造

n个val来进行构造 

析构函数

拷贝构造函数

赋值重载

增删查改

clear

resize

pop_back

insert

erase

重载[]

print_Container

---

成员变量与迭代器

我们还是需要在一个命名空间里模拟实现vector，防止和标准库里的起冲突。

<code>namespace zh

{

template<class T>

class vector

{

public:

typedef T* iterator;

typedef const T* const_iterator;

private:

iterator _start = nullptr;

iterator _finish = nullptr;

iterator _end_of_storage = nullptr;

};

}

解释说明：

1.vector是一个非常通用的容器，是一个动态大小的数组，可以存储任意类型的元素，并且能够自动调整大小以适应元素的添加和删除。所以我们的模拟实现要写成类模板。

2.vector可以看做顺序表的升级，但是模拟实现vector跟我们以往实现顺序表有所不同，顺序表是使用一个动态开辟的数组、数组有效元素个数size和数组容纳最大有效数据的个数capacity维护的，而模拟实现vector需要三个（模板参数）T* 类型的指针，而vector的迭代器功能恰恰又和T*类型指针类似，所以干脆把T*封装成迭代器。当然迭代器需要有两个版本，普通版本和const版本。

3.参数的含义

_start指向数组首元素，_finish指向最后一个有效元素的下一个位置， _end_of_storage指向数组空间末尾。

通过三个指针也可以模拟出size和capacity的功能。

size

返回有效数据个数的函数。

<code>size_t size() const

{

return _finish - _start;

}

capacity

返回数组最大容纳有效数据个数（容量大小）的函数。

size_t capacity() const

{

return _end_of_storage - _start;

}

empty

判断数组是否为空，判断_start与_finish是否相等即可。

bool empty() const

{

return _finish == _start;

}

迭代器有关函数

主要实现begin函数和end函数。

iterator begin()

{

return _start;

}

iterator end()

{

return _finish;

}

const_iterator begin() const

{

return _start;

}

const_iterator end() const

{

return _finish;

}

实现默认成员函数的前置准备

reserve

用于vector数组空间不足时扩容的函数（扩容成n个空间）。

void reserve(size_t n)

{

if (n > capacity()) //n大于数组容量才扩容

{

size_t oldsize = size(); //用oldsize避免新_start和老_finish的问题

T* tmp = new T[n];

//memcpy(tmp, _start, size() * sizeof(T)); //这里是浅拷贝，如果是内置类型，没问题

//如果vector存的是自定义类型，就是大坑

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

{

tmp[i] = _start[i];

}

delete _start; //这里delete_start，_finish 和_end_of_storage是野指针

//更新成员变量

_start = tmp;

_finish = tmp + oldsize;

_end_of_storage = tmp + n;

}

}

reserve有几个问题需要注意：

1.开空间的时候要使用new而不要用malloc，因为malloc只是去开空间，不会去调用构造函数。

2.新_start和_finish的问题。

错误示范。

将原有数据拷贝到新空间后，释放了旧空间的资源，_strat指向了新的空间，但是_finish和_end_of_storage还是指向旧空间，这两个指针就变成野指针了。而最关键的是_finish不能被正确赋值。

3.memcpy浅拷贝问题

<code>memcpy(tmp, _start, size() * sizeof(T));

memcpy是浅拷贝，如果vector存的是内置类型，那么浅拷贝就没有问题，如果存的是自定义类型，那浅拷贝就是个大坑。假如vector存的是string类型，那么扩容时，将数据从旧空间拷贝到新空间时，因为是浅拷贝，所以两个空间里的string的_str是同一个地址，释放旧空间的时候就连带这把新空间的资源也释放了。

这样就扩容失败了，因为你把原空间的数据丢失了，而且搞不好有可能程序还会崩溃。

要解决这个问题，我们就得手动实现深拷贝， 因为new出来的空间如果是自定义类型的话就自动调用构造函数初始化了，所以这里走的是赋值重载来实现深拷贝。

push_back

用于在数组末尾尾插一个元素的函数。

<code>void push_back(const T& x)

{

//插入之前先判断空间是否足够

if (_finish == _end_of_storage)

{

reserve(capacity() == 0 ? 4 : 2 * capacity());

}

//插入元素，更新_finish

*_finish = x;

_finish++;

}

构造函数

vector的构造函数我们实现无参构造、迭代器区间构造和n个val构造。

无参构造

无参构造其实我们并不需要写，因为已经在成员变声明时给了缺省值，编译器自动生成的无参构造函数走初始化列表满足需求了。但是由于我们写了其他构造函数，编译器就不自动生成了。

这里时候可以自己写无参构造，也可以用default强制编译器生成（C++11的用法）。

<code>//构造

/*vector()

{}*/

//c++11 强制生成构造

vector() = default;

迭代器区间构造

//类模板的成员函数，还可以继续是函数模版

template<class InputIerator>

vector(InputIerator first, InputIerator last)

{

while (first != last)

{

push_back(*first);

++first;

}

}

这里给这个函数再套一层模板是为了让vector不仅能用vector的迭代器区间构造，还能用其他容器（list、string等）的迭代器来进行构造。

这里又有个问题，就是while循环判断条件的!=不能改成<，因为<对于vector的迭代器时可以的，但是对于其他容器的迭代器，如list，last不一定比first要大。

n个val来进行构造 

<code>vector(size_t n, const T& val = T())

{

//先开好空间

reserve(n);

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

{

push_back(val);

}

}

使用的时候val可能不传参，所以要给缺省值。

因为val的类型不确定，可能是内置类型，也可能是自定义类型。

在不传参使用缺省值时

对于自定义类型，比如strng，先调用构造函数构造一个匿名对象，再拷贝构造给val。（编译器会优化，直接对val进行构造），这样val就有了缺省值。

对于内置类型，本来是没有构造函数的说法的，但是为了适应这里，也支持类似类那种使用构造函数初始化的方式。

int a = int();

int b = int(2);

int c(3);

cout << a << endl;

cout << b << endl;

cout << c << endl;

析构函数

直接delete就可以了，把三个迭代器置空。

<code>//析构

~vector()

{

if (_start)

{

delete[] _start;

_start = _finish = _end_of_storage = nullptr;

}

}

拷贝构造函数

先开好空间，然后尾插就可以了。

//拷贝构造

vector(const vector<T>& v)

{

reserve(v.size());

for (auto& e : v)

{

push_back(e);

}

}

赋值重载

首先实现一个交换函数，然后传值调用，将两个对象交换即可。

//void swap(vector& v) 可以这样写

void swap(vector<T>& v)

{

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

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

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

}

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

{

swap(v);

return *this;

}

增删查改

clear

不需要真的删除，直接将更改_finish的值即可。

void clear()

{

_finish = _start;

}

resize

控制有效数据个数。

若n < size，直接将_finish更改为_start + n即可。若_size < n < capacity或者n > capacity，直接扩容成n个空间（空间足够就不会扩容），从_finish拷贝足够数量的val即可。

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

{

if (n < size())

{

_finish = _start + n;

}

else

{

reserve(n);

while (_finish != _start + n)

{

*_finish = val;

++_finish;

}

}

}

pop_back

先判断数组是否为空，尾删一个元素，_finish-- 即可。

void pop_back()

{

//判断下数组是否为空

assert(!empty());

--_finish;

}

insert

在pos位置插入一个元素。

iterator insert(iterator pos, const T& x) //pos不会为0，因为是有效的迭代器

{

assert(pos >= _start);

assert(pos <= _finish);

if (_finish == _end_of_storage) //涉及到扩容，pos会失效，pos指向原来的空间

{

size_t len = pos - _start;

reserve(capacity() == 0 ? 4 : 2 * capacity());

pos = _start + len;

}

iterator end = _finish - 1;

while (end >= pos)

{

*(end + 1) = *end;

--end;

}

//插入元素，更新

*pos = x;

++_finish;

return pos;

}

注意的问题：

1.如果插入涉及到了扩容，要提前把pos相对于首元素的相对长度记录下来，扩容完毕后，更新pos。因为扩容会导致pos失效。

2.插入之后要返回新元素的迭代器。（这里其实也算迭代器是失效了，因为pos指向的元素发生了更改，迭代器失效了就不要在使用了。）

erase

删除pos位置的元素，删除完后返回删除元素下一位置的迭代器。

iterator erase(iterator pos)

{

assert(pos >= _start);

assert(pos < _finish);

iterator it = pos + 1;

while (it != end())

{

*(it - 1) = *it;

++it;

}

--_finish;

return pos;

}

抛出一个问题，利用迭代器删除vector中所有的偶数。

错误做法

auto it = v.begin();

while (it != v.end())

{

if (*it % 2 == 0)

{

it = v.erase(it);

}

it++；

}

删完一个偶数后，it已经是下一元素的迭代器了，it不需要++了。

正确做法

auto it = v.begin();

while (it != v.end())

{

if (*it % 2 == 0)

{

it = v.erase(it);

}

else

{

++it;

}

}

重载[]

为了方便访问和修改数组中的元素。

T& operator[](size_t i)

{

assert(i < size());

return _start[i];

}

const T& operator[](size_t i) const

{

assert(i < size());

return _start[i];

}

print_Container

通用打印容器函数，套一层模板即可。

注意：

​

template<class Container>

void print_Container(const Container& v)

{

//typename vector<T>::const_iterator it = v.begin(); //typename标定为类型

//从没有实例化的类模板取出来的可能是类型或者成员变量，编译器无法区分

auto it = v.begin();

while (it != v.end())

{

cout << *it << ' ';

++it;

}

cout << endl;

/*for (auto num : v)

{

cout << num << ' ';

}

cout << endl;*/

}

​

从未实例化的类取出来的有可能是类型或者成员变量，要加关键字typename告诉编译器是类型，不加的话会发生编译错误。

当然直接用auto更方便。

---

拜拜，下期再见😏

摸鱼ing😴✨🎞