单位建网站怎么做/百度贴吧官网入口

vector引入
​​
vector的实现主要依靠三个成员变量:start,finish和end_of_storage
其中：
[start]指向容器中的起始位置
[finish]指向容器中最后一个有效数据的下一个位置
[end_of_storage]指向容器中现有容量的位置
通过这三个指针，就使得vector的size() = finish - start
capacity = end_of_storage - start.

成员函数

[函数模板]
为了使我们的vector实用性更好，我们需要使用函数模板。

[迭代器]

构造函数

上面是vector的构造函数，每个构造函数的使用如下：

我们根据这里提供的接口自己实现构造函数。

[默认构造]

[迭代器构造]

左边是迭代器构造函数的实现，右边是调用迭代器构造，发现确实是调用了迭代器构造。
需要注意的地方为什么迭代器要使用模板？

因为我们不知道传进来的是什么类型，就需要用模板来接收，保证泛型编程。

[拷贝构造函数]

下面有两种拷贝构造函数的实现，都是错误的，因为这是浅拷贝。

浅拷贝会导致两个vector指向同一个地址空间。
对v1的操作同时也是对v的操作了。

浅拷贝对内置类型没有影响，因为不会对堆上的内容进行析构。
例如下面这样：

但是浅拷贝对自定义类型影响很大，会导致析构的的时候析构两次，导致崩溃：

//1.4 拷贝构造  -- 用v来初始化thisvector(const vector<T>& v){//注意：不能使用memcpy,memcpy是浅拷贝_start = new T[v.capacity()];   //开辟一块新的空间for (size_t i = 0; i < v.size(); ++i){_start[i] = v[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}

对拷贝构造函数进行测试：

[赋值运算符重载函数]

需要注意的地方有两个：
1. 判断一下，不能自己给自己赋值
2. 要先释放掉原来的空间

vector<T>& operator=(const vector<T> &v){//防止自己给自己赋值if (this != &v){//1.释放掉原来的空间delete[] _start;_start = new T[v.capacity()];for (int i = 0; i < v.size(); ++i){_start[i] = v[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}return *this;}

对赋值运算符重载函数进行测试：

n个值构造因为涉及调用resize()函数，所以放在后面写。

扩容函数

实现reserve()函数 reserve()函数实现逻辑是什么？

[reserve()函数]

这样写会出现什么问题？ 我们用如下代码对reserve()进行测试。

测试结果如下：

这是因为在计算新空间的_finish的时候，调用的是size()函数。
先看看size()函数是如何实现的？

因此，改进的方式，是在_start指向新空间之前将size()的内容存储下来。

		void reserve(size_t n){if (n <= capacity()){//不进行任何操作}else{//先将size()的内容存储下来int sz = size();//这里的扩容是开辟一块空间，将旧的内容拷贝的新空间上T* tmp = new T[n]; if (_start){for (int i = 0; i < size(); ++i){tmp[i] = _start[i];}//释放掉以前的空间delete[] _start;}//让_start指向新开辟的空间_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}

运行测试：

resize()函数]

实现resize()函数可以分为三种情况：
1.n <= _finish
2.n >_finish && n <= _end_of_storage
3.n > _end_of_storage

其实，前两种可以合并成一种。因为他们都不需要对vector进行扩容。
后面的一种需要对vector进行扩容，可以使用reserve()函数进行复用。
resize()函数的具体实现：

		void resize(size_t n, const T& value = T()){if (n <= size()){_finish = _start + n;}else{//1.扩容reserve(n);//2.将内容插入到vector中while (_finish != _start + n){*_finish = value;++_finish;}}}

测试：

测试n个值构造的时候，出现报错，非法的间接寻址：

首先弄明白，什么是非法的间接寻址？
只有指针和迭代器可以解引用，内置类型不能解引用。而如果对内置类型解引用，就会出现非法的间接寻址。
为什么明明我们调用的是n个值的构造函数，确走到了迭代器初始化？

这就要提一下最匹配的问题了。因为我们传递的是int类型，但是n个值的构造函数却是size_t类型。所以不是最匹配，就会走到迭代器构造函数这里来。
因此，解决办法就是调用最匹配的构造函数，对原来的构造函数进行重载即可。

修改

[pop_back()函数]

函数实现：

不需要将删除的元素置空，只用挪动_finish指针，以后有新的操作时，直接对原数据进行覆盖

对函数进行测试：

[pop_back()函数]

void push_back(const T& x)
{if (_finish == _end_of_storage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = x;_finish++;
}

[insert()函数]迭代器失效问题

_finish是最后一个元素的下一个位置。我们要插入值，就需要找到最后一个元素，并且将这些元素一个一个往后挪动，直到空出pos的位置，插入value

实现逻辑如下：

void insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);//1.判断扩容逻辑if (_finish == _end_of_storage){int newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}//2.将pos后的内容往后移动auto end = _finish - 1;   //_finish指向的是最后一个元素的下一个位置while (end >= pos){*(end + 1) = *end;--end;}//3.将val插入到vector中*pos = val;++_finish;}

当没有扩容时，对函数进行测试：

一旦前面进行扩容：

插入的数是随机数。
这就是内部迭代器失效的问题。

为什么会出现迭代器失效的问题？
从刚刚的测试可以看出，迭代器失效应该是和是否扩容有关的，我们从调试的角度来看看。
扩容之前_start和pos的内容：

扩容之后，_start因为使用reserve()进行异地扩容，位置就会发生改变，而pos没有改变位置。会导致后面的pos和end无法比较：

通过图示更直观的理解：

解决办法就是，让pos和_start一起走。计算出pos和_start之间的偏移量，在_start换到新的地址之后，根据偏移量计算出pos的新位置。
代码：

		void insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);//1.判断扩容逻辑if (_finish == _end_of_storage){//1.1计算出pos和_start的偏移量int n = _start - pos;int newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);//1.2扩容完之后根据偏移量找到新pos的位置pos = _start + n;}//2.将pos后的内容往后移动auto end = _finish - 1;   //_finish指向的是最后一个元素的下一个位置while (end >= pos){*(end + 1) = *end;--end;}//3.将val插入到vector中*pos = val;++_finish;}

运行结果：

解决完内部迭代器失效问题之后，还存在外部迭代器失效的情况。

什么是外部迭代器失效？

用自己写的vector，看看会出现什么结果：

对迭代器解引用是随机值，这就代表迭代器失效了。

为什么会失效？

因为我们调用insert()插入值之后，迭代器的位置会改变，因此就失效了。

如何解决外部迭代器失效的问题呢？

1.在insert()函数中返回迭代器
2.在调用insert()之后接收改变后的迭代器

必须要接收迭代器，不然还是会出现迭代器失效的问题。

		iterator insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);//1.判断扩容逻辑if (_finish == _end_of_storage){//1.1计算出pos和_start的偏移量int n = _start - pos;int newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);//1.2扩容完之后根据偏移量找到新pos的位置pos = _start + n;}//2.将pos后的内容往后移动auto end = _finish - 1;   //_finish指向的是最后一个元素的下一个位置while (end >= pos){*(end + 1) = *end;--end;}//3.将val插入到vector中*pos = val;++_finish;//返回迭代器return pos;}

[erase()函数]迭代器失效问题

删除的逻辑：

iterator erase(iterator pos){assert(pos >= _start && pos <= _finish);auto it = pos + 1;while (it != _finish){*(it - 1) = *it;++it;}--_finish;return pos;}

测试：

元素访问

[operation[]函数]

		T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}

[迭代器]

		iterator begin(){return _start;}iterator end(){return _finish;}const_itertator begin() const{return _start;}const_itertator end() const{return _finish;}

容量

[size()函数]

		size_t size() const{return _finish - _start;}

[capacity()函数]

		size_t capacity() const{return _end_of_storage - _start;}

代码

模拟实现vector的全部代码

#pragma once
#include<iostream>
#include<assert.h>
using std::cout;
using std::cin;
using std::endl;namespace zyy 
{template<class T>class vector{typedef T* iterator;typedef const T* const_itertator;public://1.1默认构造vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}//1.2 n个值构造 -- 这里使用匿名对象，是因为不知道要构造的对象是什么类型，vector(size_t n, const T& value = T()){resize(n, value);}//防止出现 非法的间接寻址 问题vector(int n, const T& value = T()){resize(n, value);}//1.3 用迭代器初始化template <class InputIterator>    //这里使用模板的原因是可能有很多类型的迭代器,string,int, double等vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}//1.4 拷贝构造  -- 用v来初始化this//vector(const vector<T>& v)//{//	//注意：不能使用memcpy,memcpy是浅拷贝//	_start = new T[v.capacity()];   //开辟一块新的空间//	for (size_t i = 0; i < v.size(); ++i)//	{//		_start[i] = v[i];//	}//	_finish = _start + v.size();//	_end_of_storage = _start + v.capacity();//}// 拷贝构造vector(const vector<T>& v){_start = new T[v.capacity()]; //开辟一块和容器v大小相同的空间memcpy(_start, v._start, sizeof(T) * v.size());//将容器v当中的数据一个个拷贝过来_finish = _start + v.size(); //容器有效数据的尾_end_of_storage = _start + v.capacity(); //整个容器的尾}//vector(const vector<T>& v)//{//	_start = v._start;//	_finish = _start + v.size(); //容器有效数据的尾//	_end_of_storage = _start + v.capacity(); //整个容器的尾//}//赋值运算符重载函数vector<T>& operator=(const vector<T> &v){//防止自己给自己赋值if (this != &v){//1.释放掉原来的空间delete[] _start;_start = new T[v.capacity()];for (int i = 0; i < v.size(); ++i){_start[i] = v[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}return *this;}~vector(){delete[] _start;_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;}//迭代器iterator begin(){return _start;}iterator end(){return _finish;}const_itertator begin() const{return _start;}const_itertator end() const{return _finish;}//operator[]T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}//2.操作函数//2.1尾插void push_back(const T& val){if (_finish == _end_of_storage){int newCapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newCapacity);}*_finish = val;++_finish;}void pop_back(){assert(_finish >= _start);--_finish;}iterator insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);//1.判断扩容逻辑if (_finish == _end_of_storage){//1.1计算出pos和_start的偏移量int n = _start - pos;int newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);//1.2扩容完之后根据偏移量找到新pos的位置pos = _start + n;}//2.将pos后的内容往后移动auto end = _finish - 1;   //_finish指向的是最后一个元素的下一个位置while (end >= pos){*(end + 1) = *end;--end;}//3.将val插入到vector中*pos = val;++_finish;//返回迭代器return pos;}iterator erase(iterator pos){assert(pos >= _start && pos <= _finish);auto it = pos + 1;while (it != _finish){*(it - 1) = *it;++it;}--_finish;return pos;}//2.2 扩容函数，将vector的容量扩大到nvoid reserve(size_t n){if (n <= capacity()){//不进行任何操作}else{//先将size()的内容存储下来int sz = size();//这里的扩容是开辟一块空间，将旧的内容拷贝的新空间上T* tmp = new T[n]; if (_start){for (int i = 0; i < size(); ++i){tmp[i] = _start[i];}//释放掉以前的空间delete[] _start;}//让_start指向新开辟的空间_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}void resize(size_t n, const T& value = T()){if (n <= size()){_finish = _start + n;}else{//1.扩容reserve(n);//2.将内容插入到vector中while (_finish != _start + n){*_finish = value;++_finish;}}}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}void print(){for (int i = 0; i < size(); ++i){cout << _start[i] << " ";}cout << endl;}private:T* _start = nullptr;T* _finish = nullptr;T* _end_of_storage = nullptr;};
}

总结

在模拟实现vector中需要注意的地方：

1. 拷贝构造函数必须使用深拷贝，不能使用memcpy()函数，因为memcpy()函数是浅拷贝。浅拷贝对内置类型没有什么影响，但是对自定义类型，可能会导致析构两次的错误。

2. 在对vector进行扩容时，主要的思想是开辟一块新的空间，然后将原来的空间的内容拷贝到新的空间中。需要重新计算_finish和_end_of_storage，_finish = _start + size()。 如果调用size()函数就会导致访问出现问题。具体原因是size()函数的实现逻辑是_finish - _start。 在扩容之后，_start指向了新的空间，_finish还在原来的空间，使用_finish - _start会导致访问越界。因此解决办法就是在_start指向新空间时先用sz接收size()的返回值，在后续修改_finish时，就不会调用函数导致访问越界了。

3. 当进行insert()插入时，可能会出现迭代器失效的问题。 主要原因是，在插入过程中，如果遇到扩容的情况，就会导致_start指向了新的空间，但是传入的pos还指向原来的空间，在扩容之后再进行插入，就会出现pos访问越界。
   做法和size()是一样的，先保存一下pos到_start的偏移量，在_start指向新空间之后，使用偏移量找到pos在新空间的位置。

4. 外部迭代器失效的问题。在进行插入或者删除值之后，如果不对原来的迭代器进行更新，并且再次访问该迭代器时，就会出现迭代器失效问题。具体表现在访问迭代器为随机值。
   解决办法为：1.insert()和erase()函数都返回迭代器，并且在自己调用的时候接收迭代器（做到对迭代器的更新）。