C++-vector的代码实现（超详细）

vector的模拟实现

​

首先介绍基本架构，接着是：

1. 重要默认成员函数
2. 三种遍历方式（加上一些运算符重载）
3. 增删查改（核心部分）
4. 迭代器失效概念，问题，以及解决方法–重点

其他部分大家有兴趣可以参考C++官方文档（记得结合翻译）：https://cplusplus.com/reference/vector/vector/

本程序包含的头文件有：

#include<iostream>
#include<vector>
#include<algorithm>
#include<assert.h>
#include<string>
#include<stdlib.h>

using namespace std;

1.vector的基本架构😺

template <class T>//vector的内容类型可能有int，double，string，所以咱们用模板实现
namespace kcc
{
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;

    private:
        T* _start;
        T* _finish;//_start + size
        T* _endofstorage;//_start + capacity
    };
}

​ 可能稍微有点不理解的地方是，为什么基本架构里面没有了_size _capacity,其实这只是让vector的基本架构更加接近于STL的源码实现，所以将_size和_capacity换成了，类型的指针_finish 和_endofstorage。

大家看一下下面的图即可理解_finish和_endofstorage。

图片来自：侯捷老师翻译的《STL源码剖析》

2.重要默认成员函数🙉

构造函数–vector()

无参vector

vector()
{
     :_start(nullptr)
    , _finish(nullptr)
    , _endofstorage(nullptr)
    {}
}

让前n个空间初始化成val

这个涉及到push_back和reserve，大家可以先看看他们是如何实现的。

vector(size_t n,const T& val = T())
    :_start(nullptr)
    , _finish(nullptr)
    , _endofstorage(nullptr)
{
    reserve(n);
    while (n--)
    {
        push_back(val);
    }
}

迭代器区间初始化

其中vector的迭代器在基本架构的时候就已经声明了，vector的迭代器本质就是指针

vector(iterator first, iterator last)
    :_start(nullptr)
    , _finish(nullptr)
    , _endofstorage(nullptr)
{
    size_t capacity= last - first;
    reserve(capacity);
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}

温馨提示：下面的构造函数以及拷贝构造函数，不要忽略初始化列表的初始化，不然的话析构函数会报错

解释：如果不在初始化列表对指针进行赋nullptr，那么指针的值是一个随机地址，即野指针，在析构函数中delete时就会报错。

像这种内存报错是不容易找出来的（别问博主怎么知道的，一个悲伤的故事），不过大家满满总结bug即可。

析构函数–~vector()

只需要释放空间，然后将维护空间的指针都制空即可。

~vector()
{
    //释放空间，清理指针
    if (_start)
    delete[]_start;//如果new了多个空间，delete的时候需要加[]
    _start = _finish = _endofstorage = nullptr;
}

析构函数一不小心也会写出bug，reserve()–一个增容函数，如果你想增容多个空间，那么就要new多个空间

相应地我们在析构函数中也要写对应的delete[]–不然可怕的报错窗口就又会出现了。

拷贝构造

大家还记得之前介绍过的现代写法吗？代码会变得很简洁。忘记了的可以参考这篇文章：

(351条消息) C++的string你可能会用，但是你模拟实现过了吗？带你实现以下string的重要接口！_龟龟不断向前的博客-CSDN博客

首先咱们要写一个vector的交换函数swap，有同学可能会说库里面不是也写了swap函数吗，何必多此一举呢？但是库里面的swap

涉及多个调用拷贝构造和赋值运算符重载，如果是深拷贝会造成效率低下，写一个vector自己的会效率更高。

void swap(vector<T>& v)//憨逼swap怎么能加const，而且需要传引用
{
    ::swap(_start, v._start);
    ::swap(_finish, v._finish);
    ::swap(_endofstorage, v._endofstorage);
}

vector(vector<T>& v)//拷贝构造只能传引用
    :_start(nullptr)
    , _finish(nullptr)
    , _endofstorage(nullptr)
{
    vector<T> tmp(v.begin(), v.end());
    swap(tmp);
}

但凡是构造，大家都要记得在初始化列表里面对指针进行制空哦！

赋值运算符重载–operator=

vector<T>& operator=(vector<T> tmp)
{
    swap(tmp);
    return *this;
}

3.三种遍历方式🐱‍👓

下标遍历法–operator[]

要想vector可以像数组一样，自由的使用下标,那么我们就要进行运算符重载了。

const T& operator[](size_t i) const
{
    return _start[i];
}

T& operator[](size_t i)
{
    return _start[i];
}

有的同学可能会问，为什么要实现两个operator[]，大家可以参考下面的文章：

文章介绍了成员函数，

1. 什么时候加const修饰
2. 什么时候不加const修饰
3. 什么时候既要有const修饰的，又要有非const的

有了下边，我们还得知道最后一个元素下一个位置的下标（左闭右开习惯），就可以实现下标遍历了

size_t size() const//返回元素个数，即最后一个元素的下一个位置的下标
{
    return _finish - _start;
}

size_t capacity() const//顺便也把容量这个函数也实现了
{
    return _endofstorage - _start;
}

void test_vector1()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);


    for (int i = 0; i < v1.size(); ++i)
    {
        cout << v1[i] << " ";
    }
    cout << endl;
}

迭代器遍历法–begin(),end()

vector迭代器的原理我们已经实现了，就是元素的指针。

注意博主每次说的是vector迭代器，string文章里面也说得是string迭代器，并没有普遍地说迭代器，因为有一些容器的迭代器并不是指针，例如list，之后的文章会介绍，尽情期待

我们现在只是要实现begin(),end()接口即可。

iterator begin()
{
    return _start;
}

const_iterator begin() const 
{
    return _start;
}

iterator end() 
{
    return _finish;
}

const_iterator end() const
{
    return _finish;
}

void test_vector2()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);

    vector<int>::iterator it = v1.begin();
    while (it != v1.end())
    {
        *it += 1;
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

常量迭代器的使用方法也类型，就是无法修改内容，大家可以自己试一试。

范围for遍历法

void test_vector2()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);

    for(auto& x: v1)
    {
        cout<<x<<" ";
    }
    cout<<endl;
}

其原理就是将迭代器的代码拷贝过来，如果没有迭代器，范围for是无法使用的。大家可以试一试。

4.增删查改👻

想到增，那么就会要增容的问题，所以咱们得实现一个reserve()接口

reserve()–异地增容

1. 申请一块新空间
2. 将旧空间的值拷贝到新空间
3. 将旧空间释放

void reserve(size_t n)
{
    if (n > capacity())//n大于容量才考虑增容
    {
        size_t sz = size();//要记录size的值，不然后面delete之后就找不到size了
        T* tmp = new T[n];
        for (int i = 0; i < sz; ++i)
        {
            tmp[i] = _start[i];
        }
        delete _start;
        _start = tmp;
        _finish = _start + sz;
        _endofstorage = _start + n;
    }
}

reserve的一些隐患（memcpy）

for (int i = 0; i < sz; ++i)
{
    tmp[i] = _start[i];
}

大家可以看到，将旧空间拷贝到新空间我是这么写的。可能有同学又会说好麻烦呀，还用了循环。

使用一个memcpy()–不是一下子搞定了吗？

没错的确是这样vector<int> ``vector<double> 都可以使用memcpy(),但是如果是vector<string>呢？

memcpy()是按字节进行值拷贝，而string是用指针来维护的，需要深拷贝，string用memcpy()就会导致旧空间的内容和新空间的

内容是一致的，当调用析构函数时就会调用两次，造成内存错误。大家千万小心。

resize()

我们顺便也把resize()也实现了，其作用就不再多说了。

void resize(size_t n ,  T val = T())
{
    if (n < size())
    {
        _finish = _start + n;
    }
    else
    {
        if (n > capacity())
        {
            reserve( n);
        }
        while (_finish < _start + n)
        {
            *_finish = val;
            ++_finish;
        }
    }
}

增–考虑增容

push_back()–尾插

void push_back(const T& val)
{
    if (_finish == _endofstorage)//增容
    {
        size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;//防止空vector的增容失败
        reserve(newcapacity);
    }

    *_finish = val;
    _finish++;

}

大家思考一样，push_back的增容为什么要这么写，顺便思考一下空vector的增容能不能二倍增。

insert()–中间插

iterator insert(iterator pos,const T& val)//在pos的前面插入val
{
    assert(pos <= _finish);
    if (_finish == _endofstorage)
    {
        size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newcapacity);
    }
    iterator end = _finish;
    while ( end > pos)
    {
        *end = *(end - 1);
        --end;
    }
    *pos = val;
    ++_finish;
    
    return pos;
}

这个返回值并不是之前的pos了

当然了insert是要配合find()使用的–算法头文件#include<algorithm>的函数

可以找到某个值的迭代器

删–考虑非空

empty()

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

pop_back()–尾删

void pop_back()
{
    if (!empty())
    {
        --_finish;
    }
}

erase()–中间删

iterator erase(iterator pos)//返回的是删除的元素的下一个元素
    {
        assert(pos <= _finish);
        iterator start = pos + 1;
        while (start < _finish)
        {
            *(start-1) = *(start);
            ++start;
        }
        --_finish;
        return pos;
    }

上述删除我们是通过将值覆盖来实现的！注意erase返回的是删除的值的下一个值的迭代器

查改

查和改其实我们都可以通过下标来实现

5.迭代器失效问题🦝

首先结论是insert和erase会造成迭代器失效。

什么是迭代器失效？

那么什么是迭代器失效呢？迭代器失效有两种情况

1. 迭代器意义变了
2. vector迭代器成为野指针

insert造成的迭代器失效–迭代器失效1

void test_vector4()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
    
		vector<int>::iterator pos = ::find(v.begin(), v.end(), 3);//找到3的迭代器
		v.insert(pos, 30);
		cout << *pos << endl;
	}

上述的vector迭代器是3的迭代器，可是进行insert操作之后，大家发现其变成了30的迭代器，这就是迭代器失效的第一种情况

意义变了，vs编译器会自动检测编译器是否失效，并且如果对失效的迭代器进行*，++，–等操作，vs编译器会报错。gcc编译器不会。

insert造成的迭代器失效的解决方法

解决方法很简单，只需要再次find一次3即可。

void test_vector3()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
    
		vector<int>::iterator pos = ::find(v.begin(), v.end(), 3);//找到3的迭代器
		v.insert(pos, 30);
    	pos = ::find(v.begin(), v.end(), 3);
		cout << *pos << endl;
	}

erase造成的迭代器失效–迭代器失效2

void test_vector5()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);
		auto it = v.begin();
		while (it != v.end())
		{
            
			if (*it % 2 == 0)
			{
				v.erase(it);
			}
				it++;
		}
    
	}

上述的程序目的为删除偶数。

大家会发现，上述的程序报错了，我带着大家走读一遍代码：首先v尾插，现在的内容为1，2，3，4，5，6

如果内容是偶数，就删除，然后++it，看似没有问题，其实有蛮大的逻辑问题。

1. 当it是1时，不是偶数，++it

2. 当it是2时，是偶数，进行erase操作，此时内容为1，3，4，5，6，++it，it变为4

   此时我们3这个位置没有进行判断就跳过去了

3. 当it是4时，是偶数，进行erase，此时内容为1，3，5，6，++it，it变为6

   此时我们5的位置又没有进行判断

4. 当it是6时，进行erase操作，此时内容为1，3，5，it也变成了end()的位置，++it

   此时it成为野指针，迭代器失效

   所以这段程序即有内容变了失效，又有成为野指针失效。

有同学会说，那简单呀，加一个else不就可以了嘛，的确gcc编译器下是可以这样达到目的的，但还是存在着两个问题。

1. vs编译器对迭代器失效有检查，当迭代器效率的时候，对齐进行++，–，*是会报错的，所以还是无法解决问题
2. 其次，vector迭代器是因为空间的连续性，下一个元素在erase操作之后正好落在了it上。但是链表可不会这样了

erase造成的迭代器失效–迭代器失效2

所以为了迭代器的通用性和移植性，我们的解决方法时这样的。

void test_vector5()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);
		auto it = v.begin();
		while (it != v.end())
		{
            
			if (*it % 2 == 0)
			{
				it = v.erase(it);
			}
			else
            {
                ++it;
            }
		}
    
	}

因为erase的返回值正好就是删除值得下一个值得迭代器，正好可以赋值给it这样就可以满足vector和list的问题了。

总结一下：

其实很多情况都会造成迭代器失效

1. insert
2. erase
3. 包括reserve异地增容，内存位置发生变化，pos成为野指针
4. 异地缩容也会

解决方法就是在进行上述操作之后，为迭代器重新赋一个值，从而解决迭代器失效问题。

希望大家细细体会这个迭代器失效问题，这个很重要。

6.vector的对应课后习题分享（题目来自leetcode，牛客网）🦄

1. 136. 只出现一次的数字 - 力扣（LeetCode）
2. 118. 杨辉三角 - 力扣（LeetCode）
3. 26. 删除有序数组中的重复项 - 力扣（LeetCode）
4. 137. 只出现一次的数字 II - 力扣（LeetCode）
5. 数组中出现次数超过一半的数字_牛客题霸_牛客网 (nowcoder.com)
6. 260. 只出现一次的数字 III - 力扣（LeetCode）
7. 17. 电话号码的字母组合 - 力扣（LeetCode）
8. 连续子数组的最大和_牛客题霸_牛客网 (nowcoder.com)

7.心得分享🐣

​ 最近还是挺迷的，而且特别不想写博客，因为想到博客就会去想写一篇博客至少得花两三个小时，真的很浪费时间，但是想了想如果写了博客：

1. 之后的复习会很方便
2. 对只是点的消化也会更好
3. 也时一种记录学习的方式

想到这些我觉还是不能停下来写博客，之后我会将我在c++学到的知识点都写进博客的，还请大家多多指点。