低头赶路，敬事如仪

目录

1、模拟vector

1.1底层结构

1.2构造析构

1.3尾插扩容

1.4迭代器

1.5增删查改

1.6模拟中的注意事项

2、vector模拟补充

2.1迭代器区间构造问题

2.2memcpy深浅拷贝问题

2.3动态二维数组的模拟及遍历

1、模拟vector

想要模拟实现自己的vector，得知其所以然！

分析一下STL源码里的vector底层成员变量

可以看到是三个迭代器类型成员变量，迭代器类型是什么呢？

经过typedef的底层指针，而T类型是模版类的参数。

大致框架如图：

1.1底层结构

根据我们刚才所查看的源码，我们要使用三个迭代器，要使用迭代器，我们可以使用指针进行模拟。

<code>namespace xc

{

//设置成模板 兼容各种参数 但是不能分离编译否则链接错误

template<class T>

class vector

{

public:

typedef T* iterator;

private:

iterator _start = nullptr;//指向容器开始

iterator _finish = nullptr;//指向有效数据下一个位置

iterator _end_of_storage = nullptr;//指向空间容量的下一个位置

};

}

写出三个迭代器（指针）后，我们可以接着实现构造函数：需要初始化三个迭代器，所以我们给予初始值nullptr。然后进行开辟空间。

1.2构造析构

实现常用的构造析构以及赋值重载

/*vector()

{}*/

//C++11 强制生成默认构造

vector() = default;

//优先匹配构造函数，防止非法的间接寻址问题

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

{

reserve(n);

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

{

push_back(val);

}

}

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

{

reserve(n);

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

{

push_back(val);

}

}

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

{

reserve(n);

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

{

push_back(val);

}

}

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

template<class InputIterator> //写成模板是为了兼容所有容器

vector(InputIterator first, InputIterator last)

{

while(first != last)

{

push_back(*first);

++first;

}

}

// v1(v)

vector(const vector<T>& v)

{

reserve(v.size());

for (auto& e : v)

{

push_back(e);

}

}

void clear()

{

_finish = _start;

}

v1=v

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

//{

//if (this != &v)

//{

//clear();

//reserve(v.size());

//for (auto& e : v)

//{

//push_back(e);

//}

//}

//return *this;

//}

void swap(vector<T>&v)

{

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

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

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

}

//现代写法 V1=v

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

{

swap(v);

return *this;

}

~vector()

{

if (_start)

{

delete[]_start;

_start = _finish = _end_of_storage = nullptr;

}

}

1.3尾插扩容

想要实现尾插的操作，根据之前的经验，可以知道需要复用一些常用的简单接口（size() capacity() reserve() 等）

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

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

bool empty()const { _start == _finish; }

//void reserve(size_t n)

//{

//if (n > capacity())

//{

//T* tmp = new T[n];

//memcpy(tmp, _start, sizeof(T));

//delete[]_start;

//_start = tmp;

//_finish = _start + size();//这是错误的 _start 已经是扩容后的 start了 而size调用的是 finish - start

////解决方法 可以先更新 finish 或者记录一下 size的值

//_end_of_storage = _start + n;

//}

//}

void reserve(size_t n)

{

if (n > capacity())

{

size_t old_size = size();

T* tmp = new T[n];

memcpy(tmp, _start, size()*sizeof(T));

delete[] _start;

_start = tmp;

_finish = tmp + old_size;

_end_of_storage = tmp + n;

}

}

void reseize(size_t n, T val = T())//内置类型也具有的构造析构等函数行为 但是并没有概念

{

if (n < size())

{

_finih = _start + n;

}

else

{

reserve(n);

while (_finsh < _start+n)

{

*_finish++ = val;

}

}

}

void push_back(const T& x)

{

//扩容

if (_finish == _end_of_storage)

{

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

}

*_finish++ = x;

}

注意：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

1.4迭代器

所需要实现的迭代器其实很简单，对指针 typedef 即可

typedef T* iterator;

typedef const T* const_iterator;

iterator begin() { return _start; }

iterator end() { return _finish; }

const_iterator begin()const { return _start; }

const_iterator end()const { return _finish; }

实现了简单的迭代器，我们可以测试一下 迭代器遍历和范围for遍历

void test_vector1()

{

vector<int> v;

v.push_back(1);

v.push_back(1);

v.push_back(1);

v.push_back(1);

vector<int>::iterator it = v.begin();

while (it != v.end())

{

cout << *it << ' ';

++it;

}

cout << endl;

for (auto e : v)

{

cout << e << ' ';

}

cout << endl;

}

这里我们为了后续方便封装一个打印函数

<code>template<class T>

void print_vector(const vector<T>& v)

{

vector<T>::const_iterator it = v.begin();

while (it != v.end())

{

cout << *it << ' ';

++it;

}

cout << endl;

}

可是这居然报错

为什么呢？没有实例化的类模板里面取东西，编译器是分不清 const_iterator 是静态成员变量还是类型的，在前面加一个 typename 显示告诉编译器是类型即可

<code>template<class T>

void print_vector(const vector<T>& v)

{

typename vector<T>::const_iterator it = v.begin();

while (it != v.end())

{

cout << *it << ' ';

++it;

}

cout << endl;

}

1.5增删查改

void insert(iterator pos, const T& x)

{

if (_finish == _end_of_storage)

{

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

}

iterator end = _finish;

while (pos < end)

{

*end = *(end - 1);

--end;

}

*pos = x;

++_finish;

}

看起来没什么问题，但是存在着迭代器失效的风险

pos仍指向原来的空间！记录相对位置，修正一下pos即可

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

{

if (_finish == _end_of_storage)

{

size_t len = pos - _start;//记录相对位置

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

pos = _start + len;

}

iterator end = _finish;

while (pos < end)

{

*end = *(end - 1);

--end;

}

*pos = x;

++_finish;

}

值得注意的是STL里的 insert有返回值！

这是为什么呢？还是防止迭代器失效的一种措施。

<code>void test_vector2()

{

vector<int>v;

v.push_back(1);

v.push_back(2);

v.push_back(3);

v.push_back(4);

v.push_back(5);

print_vector(v);

/*v.insert(v.begin() + 1, 10);

print_vector(v);*/

int x;

cin >> x;// x==2

auto pos = find(v.begin(), v.end(), x);//没找到返回 last 左闭右开区间

if (pos != v.end())

{

v.insert(pos, 40);//pos 可以理解为下标位置 也可以理解为原来位置数据前面插入一个数据

print_vector(v);

(*pos) *= 10;//期望将x乘以10 但是是插入的40*10 并没有指向原来的数据

//归为迭代器失效一类

}

print_vector(v);

}

如果这里还发生了扩容呢？？就是将push的5给删掉

这是什么鬼？我们不是已经修正了pos的位置吗？显然这里的p已经失效了！形参是无法改变实参的，我们修正了pos，但是影响不了p

传const 引用过去影响实参。但不是常量引用的话 ，下面代码会报错！

因为函数调用返回的参数是临时变量，且临时变量具有常性。

而事实上加了const引用里面的pos就无法修正了！我们的思路错了，STL的操作是加一个返回值 （返回的是新插入数据的下标）

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

{

assert(pos <= _finish && pos >= _start);

if (_finish == _end_of_storage)

{

size_t len = pos - _start;//记录相对位置

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

pos = _start + len;

}

iterator end = _finish;

while (pos < end)

{

*end = *(end - 1);

--end;

}

*pos = x;

++_finish;

return pos;

}

所以 insert后不能再访问find 的 p 想要访问得更新！

增删查改：

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

{

assert(pos <= _finish && pos >= _start);

if (_finish == _end_of_storage)

{

size_t len = pos - _start;//记录相对位置

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

pos = _start + len;

}

iterator end = _finish;

while (pos < end)

{

*end = *(end - 1);

--end;

}

*pos = x;

++_finish;

return pos;

}

iterator erase(iterator pos)

{

assert(pos < _finish && pos >= _start);

iterator it = pos + 1;

while (it != end())

{

*(it - 1) = *it;

++it;

}

--_finish;

return pos;

}

size_t find(T val = T())

{

for (auto it = _start; it < _finish; it++)

{

if (*it == val)

{

return it - _start;

}

}

return -1;

}

T& operator[](size_t i)

{

assert(i < size());

return _start[i];

}

const T& operator[](size_t i)const

{

assert(i < size());

return _start[i];

}

void pop_back()

{

assert(!empty());

--_finish;

}

1.6模拟中的注意事项

规定：类模板在没有实例化时，迭代器无法读取！编译器不能区分这里const_iterator是类型还是静态成员变量。要想解决：第一可以在前面加上typename用来证明这里是类型；第二用auto，让编译器判断为类型

内置类型是没有构造函数的概念，但为了兼容模板（T val = T( ) ），可以被视为具有默认构造函数的行为

<code>void reseize(size_t n, T val = T())//内置类型具有的构造析构等函数行为，并没有对应概念

{

if (n < size())

{

_finish = _start + n;

}

else

{

reserve(n);

while (_finish < _start+n)

{

*_finish++ = val;

}

}

}

 c++11中有强制生成默认构造的操作，即使类中已有其他构造函数，也能强制生成。eg：vector( ) = default

类里面可以用类名替代类型（特殊化），类外面规定：类名不能代表类型

<code>//类里面可以用类名替代类型（特殊化）

//vector & operator=(vector v)

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

{

swap(v);

return *this;

}

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

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

template<class InputIterator> //写成模板是为了兼容所有容器

vector(InputIterator first, InputIterator last)

{

while(first != last)

{

push_back(*first);

++first;

}

}

2、vector模拟补充

2.1迭代器区间构造问题

//C++11 强制生成默认构造

vector() = default;

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

{

reserve(n);

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

{

push_back(val);

}

}

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

template<class InputIterator> //写成模板是为了兼容所有容器

vector(InputIterator first, InputIterator last)

{

while(first != last)

{

push_back(*first);

++first;

}

}

这个是对迭代器区间进行的构造函数，思路很简单，把迭代器区间的数据依次尾插就可以了（这里之所以另外使用一个新的模版，而不是使用vector类的模版，是为了兼容其他容器类型）。这样就可以通过一个现有的类型来构造容器。

但是出乎意料的是出现了一个问题： C2100 非法的间接寻址 （编译层面的问题） 。非法的间接寻址的造成原因有很多：

空指针引用：当一个指针没有被初始化或者为NULL时，对它进行间接寻址操作会导致非法访问。野指针引用：当一个指针超出了它所指向的内存范围，或者已经被释放但仍然被引用时，进行间接寻址操作也会导致非法访问。类型不匹配：如果试图将指针转换为不兼容的类型进行间接寻址，也会导致非法访问。

为什么报错在迭代器构造呢？因为编译器会寻找最合适的函数，但是这里与我们期望所违背！！

为了解决编译器选择的问题，可以多枚举几个构造函数：

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

{

reserve(n);

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

{

push_back(val);

}

}

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

{

reserve(n);

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

{

push_back(val);

}

}

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

{

reserve(n);

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

{

push_back(val);

}

}

这样可以做到优先匹配vector(int n,T val = T());，我们的问题也就解决了。 

2.2memcpy深浅拷贝问题

我们测试一下自定义类型的vector（这里以string为例）：

void vector_test6() {

vector<string> v1;

v1.push_back("11111");

v1.push_back("22222");

v1.push_back("33333");

v1.push_back("44444");

//再次插入扩容

v1.push_back("55555");

print_vector(v1);

}

程序崩溃了

分析：

<1> memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中

<2> 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃

解决方法：

<code>void reserve(size_t n)

{

if (n > capacity())

{

size_t old_size = size();

T* tmp = new T[n];

//memcpy(tmp, _start, size()*sizeof(T));//浅拷贝

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

{

tmp[i] = _start[i];//自定义类型的话 也是会调用自定义类型的赋值重载

}

delete[] _start;

_start = tmp;

_finish = tmp + old_size;

_end_of_storage = tmp + n;

}

}

2.3动态二维数组的模拟及遍历

结构框架图：

<code>//二维数组

vector<int>v(3, 1);

vector<vector<int>>vv(5, v);

vv[2][1] = 2;

//与上述等价 vv.operator[](2).operator[](1) = 2;

for (size_t i = 0; i < vv.size(); i++)

{

for (size_t j = 0; j < vv[i].size(); j++)

{

cout << vv[i][j] << ' ';

}

cout << endl;

}

cout << endl;

for (auto it = vv.begin(); it != vv.end(); it++)

{

for (auto jt = (*it).begin(); jt != (*it).end(); jt++)

{

cout << *jt << ' ';

}

cout << endl;

}

cout << endl;

auto it1 = vv.begin();

/*auto it2 = (*it1).begin();*/

while (it1 != vv.end())

{

auto it2 = (*it1).begin();//更新it2 指针在堆上分配，所以可以看见内存不是连续分配的

while (it2 != (*it1).end())

{

cout << *it2 << ' ';

it2++;

}

cout << endl;

it1++;

}

cout << endl;

for (auto row : vv)

{

for (auto column : row)

{

cout << column << ' ';

}

cout << endl;

}

cout << endl;

应用：杨辉三角

// 以杨慧三角的前n行为例：假设n为5

void test2vector(size_t n)

{

// 使用vector定义二维数组vv，vv中的每个元素都是vector<int>

vector<vector<int>> vv(n);

// 将二维数组每一行中的vecotr<int>中的元素全部设置为1

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

vv[i].resize(i + 1, 1);

// 给杨慧三角出第一列和对角线的所有元素赋值

for (int i = 2; i < n; ++i)

{

for (int j = 1; j < i; ++j)

{

vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];

}

}

}

构造一个vv动态二维数组，vv中总共有n个元素，每个元素 都是vector类型的，每行没有包含任何元素，n为5时如下所示：