[C++知识库] C++-vector的代码实现（超详细）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> C++-vector的代码实现（超详细） -> 正文阅读

[C++知识库]C++-vector的代码实现（超详细）

vector的模拟实现

文章目录

- vector的模拟实现

? 本次vector的实现顺序是：

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

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

其他部分大家有兴趣可以参考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源码剖析》

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xi2EVTCF-1664073728789)(C:\Users\Cherish\AppData\Roaming\Typora\typora-user-images\image-20220925085810455.png)]$

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即可。

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZmGNRBuF-1664073728791)(D:\gitee仓库\博客使用的表情包\这是个悲伤的故事.jpg)]$

析构函数–~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[]，大家可以参考下面的文章：

文章介绍了成员函数，

什么时候加const修饰
什么时候不加const修饰
什么时候既要有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()–异地增容

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

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会造成迭代器失效。

什么是迭代器失效？

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

迭代器意义变了
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，看似没有问题，其实有蛮大的逻辑问题。

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

此时我们3这个位置没有进行判断就跳过去了
当it是4时，是偶数，进行erase，此时内容为1，3，5，6，++it，it变为6

此时我们5的位置又没有进行判断
当it是6时，进行erase操作，此时内容为1，3，5，it也变成了end()的位置，++it

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

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

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

vs编译器对迭代器失效有检查，当迭代器效率的时候，对齐进行++，–，*是会报错的，所以还是无法解决问题
其次，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的问题了。

总结一下：

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

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

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

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

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

7.心得分享🐣

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

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

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

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-P5pVsyRW-1664073728793)(D:\gitee仓库\博客使用的表情包\给点赞吧.jpg)]$
$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-h95BFwL8-1664073728796)(D:\gitee仓库\博客使用的表情包\要赞.jpg)]$