【C++】STL：vector

STL的第二站，便是vector了。

对于学习STL，有一个非常大的好处便是，它们有很多函数都是相通的！这也是面向对象的一大好处：背后的函数实现可能不同，但是使用方式相同。

1.简单了解vector

https://m.cplusplus.com/reference/vector/vector/

老样子，打开我们的cplusplus——然后惊奇的发现，它换UI了！终于不再是那个2000年初的模样了（虽然这和我们的使用没啥关系）

不摸鱼了，来看看vector究竟是何方神圣——其实他就是一个顺序表

和string不同的是，vector有模板参数，可以存储任何类型的内容。int、double、char、甚至string。

这一点在cplusplus网站上的第一行便告诉了我们

1	template < class T, class Alloc = allocator<T> > class vector; // generic template

你还可以看到，标题下方给了一个这样的类模板定义，其中T代表的是存放数据类型，allocator<T>也是STL库中的一部分，用于向堆申请空间（类似一个内存池）可以提高访问的效率

前期的学习我们不需要知道allocator<T>是怎么实现的，只要知道它有这个功能就ok了。

1.1函数接口

往下滑，你会发现vector的函数接口，我们很多都已经学过了！

这些函数的操作和string类型都是一样的，这里就不再讲解了！

对比发现，其实vector多出来的函数并不多，这便是学习STL的好处！

2.使用vector

因为大部分函数的功能、操作和string一样，有问题可以去看看我之前string的博客

2.1 构造

对于vector而言，比较常用的构造函数是下面这几个

这里说说最后一个，利用迭代器进行初始化，它的使用如下

std::string s1("hello");
vector<char> v2(s1.begin(),s1.end());
for (auto ch : v2)
{
	cout << ch << " ";
}
cout << endl;

当我们已经有一个其他的支持迭代器的容器之后，便可以使用该容器的迭代器初始化一个vector

这里的区间可以自行控制，对应的初始化的内容也会有所不同

2.2 迭代器

vector的迭代器和string基本相同，都拥有正向和反向两种方式

迭代器	说明
begin+end	获取第一个数据位置iterator/const_iterator，获取最后一个数据的下一个位置iterator/const_iterator
rbegin+rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator

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

利用迭代器，我们可以打印vector的内容

2.3 迭代器失效问题

在vector中的一些操作会导致迭代器失效，即迭代器指向的内容含义变了。包括但不限于：

因为erase导致的数据擦除；
扩容导致的原有空间被释放（此时迭代器依旧指向原有空间）
所有会导致扩容的操作（插入操作和reverse/resize）；

这时候我们需要借助函数的返回值对it进行重新赋值，比如下图是erase和insert的返回参数

我们只需要在使用迭代器遍历的时候用it来接受返回值（更新迭代器）就可以规避这个问题

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

    vector<int>::iterator it = v1.begin();
    while (it != v1.end())
    {
        if (*it % 2 == 0)//在偶数之前插入内容
        {
            //不这样写会出现it的含义变化而导致的死循环
            //程序内出现了扩容，it原先指向的空间已经被释放
            it = v1.insert(it, 99);	
            it++;
        }

        it++;
    }

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

}

2.4 emplace_back和push_back的区别

emplace_back() 和push_back() 的区别，就在于底层实现的机制不同。

push_back()向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；
而emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。

emplace_back是C++11添加的，定义如下

1 2	template <class... Args> void emplace_back (Args&&... args);

而C++11中也给push_back提供了一个右值引用方式的重载，这时候右值的操作就会调用移动构造了；

1 2	void push_back (const value_type& val); void push_back (value_type&& val); // C++11

push_back需要构造对象后传入对象，emplace_back直接传入构造函数的参数就行了。

对比测试

在这个自定义类型中，我实现了全缺省的默认构造，以及拷贝构造和移动构造；

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class inclass {
public:
	inclass(int a = -10,const string& info = "dft") :_a(a),_str(info) {
		cout << "init inclass | " << info << " " << a << endl;
	}
	inclass(const inclass& d):_a(d._a),_str(d._str) {
		cout << "init inclass copy | " << _str << " " <<  d._a << endl;
	}
	inclass(const inclass&& d) :_a(d._a), _str(std::move(d._str)) {
		cout << "init inclass copy&& | " << _str << " " << d._a << endl;
	}
	int _a;
	string _str;
};

int main()
{
	vector<inclass> v;
	v.reserve(15);
	cout << " -----  " << endl;
	inclass tmp_copy(-1, "tmp_copy");
	inclass tmp_move(-2, "tmp_move");
	cout << " -----  " << endl;
	v.push_back(tmp_copy);
	v.push_back(std::move(tmp_copy));
	v.push_back(inclass(3,"push back"));
	v.push_back(std::move(inclass(4, "push back move")));
	v.push_back({ 10,"push back initializer list" });
	// v.push_back(15,"push back direct_init" ); // 不支持
	cout << " -----  " << endl;
	v.emplace_back(tmp_move);
	v.emplace_back(std::move(tmp_move));
	v.emplace_back(inclass(5,"emplace back"));
	v.emplace_back(std::move(inclass(6, "emplace back move")));
	// v.emplace_back({ 20,"enplace back initializer list" });// 不支持
	v.emplace_back( 30,"enplace back direct_init" );

	return 0;
}

最终输出结果如下，可以看到在这之前，所有的插入操作都会先构建这个临时对象，再调用移动构造来插入到vector中，即便采用初始化列表，也是会去构造临时对象的；因为零时对象是将亡值，所以调用的都是移动构造。

 -----
init inclass | tmp_copy -1
init inclass | tmp_move -2
 -----
init inclass copy | tmp_copy -1
init inclass copy&& | tmp_copy -1
init inclass | push back 3
init inclass copy&& | push back 3
init inclass | push back move 4
init inclass copy&& | push back move 4
init inclass | push back initializer list 10
init inclass copy&& | push back initializer list 10
 -----
init inclass copy | tmp_move -2
init inclass copy&& | tmp_move -2
init inclass | emplace back 5
init inclass copy&& | emplace back 5
init inclass | emplace back move 6
init inclass copy&& | emplace back move 6
init inclass | enplace back direct_init 30

而emplace_back采用了完美转发，支持直接传入参数作为自定义类型的构造函数的参数，所以可以看到最后一个插入操作中只有一次构造，而没有任何拷贝构造！

2.5 vector的扩容问题

我们都知道，vector在空间不够的时候，需要重新申请一个大块内存。这里就涉及到了一个面试常考点，即vector的扩容策略。

https://zhuanlan.zhihu.com/p/554384316

一般情况下windows的VS中是1.5倍扩容，GCC中是2倍扩容。

呈1.5倍扩容可以更好的利用之前的空间（之前的空间有很大概率会重新变成连续，方便下一次开辟更大的空间）
呈2倍扩容效率会更高，累计到push_back中可以让最终的时间复杂度趋近于O(1)，注意说的是累积的时间复杂度。

具体的就不是很了解了。

3.模拟实现

代码详见我的gitee仓库【链接】STL-Vector的源码也在里面！

和string类不同的是，在vector里面并不是用size和capacity这两个成员变量来确认有效长度和容量的。

通过查看stl源码可以看到，其使用了3个迭代器进行标识

private:
    iterator _start;//指向开头（存放数据）
    iterator _finish;//指向结尾的下一个
    iterator _endofstorage;//指向空间尾部

了解结构后，便可以先把无参构造和析构函数写出来待用

//无参构造函数
vector()
    :_start(nullptr),
	_finish(nullptr),
	_endofstorage(nullptr)
{ }

//析构
~vector()
{
    if (_start)
    {
        delete[] _start;
        _start = _finish = _endofstorage = nullptr;
    }
}

那么要怎么知道size和capacity的大小呢？很简单，通过指针相减即可得出结果

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

3.0 迭代器

在模拟实现一开始，我们就要用typdef定义两个迭代器，方便后面的使用

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;
}

3.1 reserve/resize

现在我们的vector内容还是空空的，我们需要先实现一下push_back函数，可以基本操作一下我们的数据。但没有构造函数去申请空间，哪来的目标给我们操作呢？

这时候就需要先实现reserve来扩容和获取空间了！

在扩容之前，我们需要获取原有数据的长度，再new将空间整出来，并给_start。操作结束后，我们需要修改_finish和_endofstorage，否则这两个迭代器指向的还是原有空间，出现了迭代器失效问题

void reserve(size_t n)//扩容
{
    size_t sz = size();//计算原有的长度
    if( n > capacity())
    {
        T* tmp = new T[n];
        if (_start) //只有_start不为空才进行拷贝操作
        {
            //memcpy是浅拷贝，当遇到vector类型是自定义类型（比如string和vector<T>这种包含堆区内存的类型）
            //浅拷贝会失效，string的成员变量拷贝过去了，但是成员变量指向的堆区空间被释放，出现野指针
            //memcpy(tmp, _start, size());
            for (size_t i = 0; i < size(); i++)
            {
                tmp[i] = _start[i];//手动赋值，当成员是自定义类型的时候，会调用=重载
            }
            delete[] _start;//释放原有空间
        }
        _start = tmp;
    }
    //这里必须要先计算sz，如果在这里直接调用sz的话：finish已经是野指针了，finish-start会出现问题
    _finish = _start + sz;
    _endofstorage = _start + n;
}

关于为何拷贝内容的时候需要用=而不能直接memcpy，后文会提到。

resize和reserve唯一不同的一点，就是reserve会修改原有空间的数据，其余的实现是一样的。所以这里面我们直接复用reserve进行扩容即可

//在C++中，内置类型也有一个“构造函数”
//这是为了更好的支持模板操作
void resize(size_t n,T val = T())
{
    if (n > capacity())
    {
        reserve(n);
    }

    if (n > size())
    {
        //初始化
        while (_finish < _start + n)
        {
            *_finish = val;
            ++_finish;
        }
    }
    else
    {
        _finish = _start + n;
    }
}

注意，T()的含义是用模板参数的构造函数作为缺省值。在C++中，内置类型也可以进行这个操作

当你不进行传值的时候，int类型默认是0

3.2 插入/删除

空间拿到了，现在就可以对我们的数据进行插入操作了

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

    *_finish = x;
    _finish++;
}

void pop_back()
{
    if (_finish > _start) 
    {
		_finish--;
	}
}

简单测试一下插入和删除功能，没啥问题

更好的办法，其实是写好insert和earse，然后尾插尾删的时候直接复用即可

//pos位置插入val
iterator insert(iterator pos, const T x)
{
    assert(pos >= _start && pos <= _finish);
    //assert(pos >= _start && pos <= _endofstorage);
    if (_finish == _endofstorage)
    {
        size_t n = pos - _start;
        size_t newcapa = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newcapa);
        pos = _start + n;
    }

    iterator end = _finish - 1;
    while (end >= pos)
    {
        *(end + 1) = *end;
        end--;
    }

    *pos = x;
    _finish++;

    return pos;
}
//删除数据
iterator erase(iterator pos)
{
    assert(pos >= _start && pos <= _finish);
    iterator tmp = pos;
    iterator end = _finish - 1;
    while (tmp < end)
    {
        *tmp = *(tmp + 1);
        tmp++;
    }

    _finish--;

    return pos;
}

因为这里我们只需要操作一个元素，所以就不需要担心移动多个数据可能导致的问题，事情也变得简单多了

void push_back(const T& x)
{
    insert(end(),x);
}

void pop_back()
{
    erase(end()-1);
}

尾插尾删操作直接复用源码即可

3.3 重载中括号操作符

因为vector本身只是个顺序表，所以我们需要对它的对象重载一下[]操作符，这样就能和数组一样去访问vector的数据

//重载[]操作符
T& operator[](size_t pos)
{
    assert(pos < size());

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

    return _start[pos];
}

关于构造函数，这里重点介绍一下迭代器区间的构造函数，因为后面的拷贝构造我们会用上它。

3.4 迭代器区间构造/拷贝/赋值

库里面关于该构造函数的定义如下

1
2
3

template <class InputIterator>
   vector (InputIterator first, InputIterator last,
           const allocator_type& alloc = allocator_type());

因为这时候我的水平还很垃，就暂且不管这个allocator了

该函数需要我们传参两个迭代器，因为我们底层就是用指针实现的，所以直接解引用然后将内容尾插即可（如果没有空间，尾插会调用reserve来获取空间/扩容）

template <class InputIterator>
vector(InputIterator first, InputIterator last)
    :_start(nullptr),
	_finish(nullptr),
	_endofstorage(nullptr)
{
    while (first != last)
    {
        push_back(*first);
        first++;
    }
}

有了这个构造函数后，拷贝构造就很容易了！

void swap(vector<T>& v)
{
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_endofstorage, v._endofstorage);
}
//拷贝构造
vector(const vector<T>& v)
    :_start(nullptr),
_finish(nullptr),
_endofstorage(nullptr)
{
    vector<T> tmp(v.begin(), v.end());
    swap(tmp);
}

利用迭代器区间构造出来一个tmp对象，再将该对象和我们本身进行交换即可！

你可能会问：欸你这样交换了，原本的内容岂不是没人管了，有内存泄漏啊！

并不是这样的，我们使用库函数里面的swap交换了二者的成员变量，在拷贝构造函数完成之后，tmp生命周期结束，会自动调用构造函数处理掉我们的数据！

这就是让别人帮你干活😂

赋值重载就跟简单了，我们连tmp变量都不需要弄，直接使用传值（会自动调用拷贝构造一个临时变量）就可以啦！

//赋值重载（v没有引用，拷贝构造一个新的传参过来，所以不需要手动再构建一个tmp）
vector<T>& operator=(vector<T> v)
{
    swap(v);
    return *this;
}

3.5 用n个value进行构造

在库中的vector还有一个这样的构造函数，用n个val进行初始化

因为我们之前已经实现了一个相关功能的函数resize，我们只需要调用resize就可以完成这个操作！

//利用n个val进行构造
vector(size_t n, const T& val = T())
    :_start(nullptr),
	_finish(nullptr),
	_endofstorage(nullptr)
{
    resize(n, val);
}

只实现一个vector(size_t n, const T& val = T())的版本是不可以的，因为我们忽略了一种情况

1 2	vector<char> v1(10,'x')//可以成功调用 vector<int> v2(10,11) //不能成功调用！

为啥第二种情况不行呢？再来看看另外一个构造函数，我们之前实现过的迭代器区间构造

1 2	template <class InputIterator> vector(InputIterator first, InputIterator last)

你会发现，当我们传的两个参数都是int类型的时候，编译器会直接调用这个模板函数！因为first和last就是两个相同类型的参数！

通过调试也可以看到在进行构造的时候，调用了这个迭代器区间构造函数

为了避免这种情况，我们需要对int类型单独处理一下，修改一下传参即可

//如果不单独重载一个int类型版本，就会被识别成上面的模板函数
//int是不能当作迭代器进行解引用的，会报错
vector(int n, const T& val = T())
    :_start(nullptr),
	_finish(nullptr),
	_endofstorage(nullptr)
{
    resize(n,val);
}

这个问题是怎么发现并解决的？

我们可以直接查看stl源码，瞅瞅库里面是怎么实现的

可以看到库里面不但重载了一个int类型的版本，还重载了long长整型的情况

到这里，我们的模拟实现就基本完成了！

3.6 关于自定义类型的拷贝问题

为什么在3.1的reserve实现中，我使用了赋值重载，而没有使用memcpy？

来看看下面这个OJ题目杨辉三角的代码

leetcode118杨辉三角：https://leetcode.cn/problems/pascals-triangle/submissions/

class Solution {
	public:
		vector<vector<int>> generate(int numRows) {
			vector<vector<int>> vv;
			vv.resize(numRows);
			for (size_t i = 0; i < vv.size(); ++i)
			{
				// 杨辉三角，每行个数依次递增
				vv[i].resize(i + 1, 0);

				// 第一个和最后一个初始化成1
				vv[i][0] = 1;
				vv[i][vv[i].size() - 1] = 1;
			}

			for (size_t i = 0; i < vv.size(); ++i)
			{
				for (size_t j = 0; j < vv[i].size(); ++j)
				{
					if (vv[i][j] == 0)
					{
						// 中间位置等于上一行j-1 和 j个相加
						vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
					}
				}
			}

			return vv;
		}
	};

在这里面，我们有两层vector进行嵌套使用，外层的vector存放的是内层vector的对象。

它的结构如下图

这时候如果只用memcpy进行浅拷贝，相当于新的空间里面存放的是的确是新的vector对象，但这些vector对象存放的却是原有数据的指针，而原本的数据已经被我们delete掉了，出现了野指针问题！

反应到代码上，当我们在Solution内部进行一次打印，再在外部进行一次打印，结果就会完全不同

void test05()
{
    vector<vector<int>> ret = Solution().generate(5);
    cout << "外部打印" << endl;
    for (size_t i = 0; i < ret.size(); ++i)
    {
        for (size_t j = 0; j < ret[i].size(); ++j)
        {
            cout << ret[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

使用赋值重载，就可以进行深拷贝，每一个vector对象都能获得新的值，也就不会出现这个问题！

//reserve代码的一部分
for (size_t i = 0; i < size(); i++)
{
    tmp[i] = _start[i];//手动赋值，当成员是自定义类型的时候，会调用=重载
}

结语

到这里，vector的模拟实现就完成啦！通过模拟实现可以让我们更好的理解vector容器的结构，也方便后续的使用！

有任何问题，都可以在评论区提出哦！