【C++】模拟实现STL容器：vector

---

需要云服务器等云产品来学习Linux的同学可以移步/-->腾讯云<--/-->阿里云<--/-->华为云<--/官网，轻量型云服务器低至112元/年，新用户首次下单享超低折扣。

---

 目录

一、vector迭代器失效问题

1、Visual Studio和g++对迭代器失效问题的表现

2、解决迭代器失效的方法

二、模拟实现构造函数调用不明确

1、问题描述

2、解决调用不明确的方法

三、reserve中的深浅拷贝问题

1、reserve中浅拷贝发生原因

2、浅拷贝发生的图解

3、解决方法

四、模拟实现vector整体代码

---

一、vector迭代器失效问题

1、Visual Studio和g++对迭代器失效问题的表现

在Visual Studio2022中，调用vector的insert()和erase()接口后，it迭代器（包括it之后的自定义迭代器）将会失效，如果仍操作这些已经失效的迭代器，编译器将会引发异常。

博主尝试在Linux的g++编译器（4.8.5版本）下运行相同debug版本的程序（编译时带上-g选项），发现g++中调用完insert()和erase()接口后，it迭代器并未失效，甚至可以操纵it读写_end_of_storage-_finish这部分空间，这是不安全的。

所以，后续调用完insert()和erase()接口后，我们一律认为当前迭代器失效！

2、解决迭代器失效的方法

使用时让当前迭代器接收insert()和erase()的返回值，更新迭代器即可。

二、模拟实现构造函数调用不明确

1、问题描述

vector(size_t n, const T& val = T())//这里的形参用size_t就会引发这两个构造函数调用问题
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
    reserve(n);
    for (size_t i = 0; i < n; ++i)
    {
        push_back(val);
    }
}
 
template <class InputIterator>
vector(InputIterator first, InputIterator last)
    :_start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
    while (first != last)
    {
        push_back(*first++);
    }
}

本意是想使用第一种构造方式，用3个6进行构造。编译器会根据形参调用最匹配的函数重载。

第一个构造函数的第一个形参是size_t，形参去匹配的话需要发生隐式类型转换。

但是这两个参数更匹配第二个构造函数（因为第二个模板可以为int，完全匹配），一旦走第二个构造函数，该构造函数内部是要对first进行解引用操作，所以编译器会报非法的间接寻址（解引用）错误。

2、解决调用不明确的方法

针对构造函数vector(size_t n, const T& val = T())，我们多重载一个vector(int n, const T& val = T())版本的构造函数即可解决该问题。

三、reserve中的深浅拷贝问题

1、reserve中浅拷贝发生原因

这句memcpy表面上把原来的数据全部拷贝到tmp里面了，但是，这只是按字节的拷贝，如果当前类型为vector>等涉及深浅拷贝类型，将会发生浅拷贝。

2、浅拷贝发生的图解

memcpy会把vector>,从_start位置开始，按字节进行拷贝。如图所示，拷贝的对象是4个vector,这是一种浅拷贝！

3、解决方法

void reserve(size_t n)
{
    //扩容
    if (n > capacity())
    {
        size_t oldSize = size();//先记录下size,后续解决finish失效
        T* tmp = new T[n];
        if (_start != nullptr)
        {
            //memcpy(tmp, _start, sizeof(T) * oldSize);//浅拷贝
            for (size_t i = 0; i < oldSize; ++i)
            {
                tmp[i] = _start[i];//调用赋值运算符重载完成深拷贝
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + oldSize;//异地扩容后_finish失效，需重新设定_finish
        _end_of_storage = _start + n;
    }
}

借助赋值运算符重载，完成深拷贝。

四、模拟实现vector整体代码

#pragma once
#include 
#include 
using std::cout;
using std::cin;
using std::endl;
namespace jly
{
	template <class T>
	class vector
	{
	public:
		//构造函数
		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{}
		vector(size_t n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(n);
			for (size_t i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}
		vector(int n, const T& val = T())//多重载一个int版本的构造，解决调函数不明确的问题
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(n);
			for (int i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}
 
		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			while (first != last)
			{
				push_back(*first++);
			}
		}
		//拷贝构造
		void swap(vector& v)//一定要加引用，不然拷贝构造函数调用swap会引发无限拷贝
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}
		vector(const vector& v)
			: _start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			vector tmp(v.begin(), v.end());
			swap(tmp);
		}
		//vector(const vector& v)//写法二
		//	: _start(nullptr)
		//	, _finish(nullptr)
		//	, _end_of_storage(nullptr)
		//{
		//	reserve(v.capacity());
		//	for (const auto& e : v)
		//	{
		//		push_back(e);
		//	}
		//}
		//赋值运算符重载
		vector& operator=(vector v)//能解决自己给自己赋值的问题
		{
			swap(v);
			return *this;
		}
		//析构函数
		~vector()
		{
			delete[] _start;
			_start = _finish = _end_of_storage = nullptr;
		}
		//迭代器
		typedef T* iterator;
		iterator begin()
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}
		const iterator begin()const
		{
			return _start;
		}
		const iterator end()const
		{
			return _finish;
		}
		T& operator[](size_t pos)
		{
			return _start[pos];
		}
		const T& operator[](size_t pos)const
		{
			return _start[pos];
		}
		//reserve接口
		void reserve(size_t n)
		{
			//扩容
			if (n > capacity())
			{
				size_t oldSize = size();//先记录下size,后续解决finish失效
				T* tmp = new T[n];
				if (_start != nullptr)
				{
					//memcpy(tmp, _start, sizeof(T) * oldSize);//浅拷贝
					for (size_t i = 0; i < oldSize; ++i)
					{
						tmp[i] = _start[i];//调用赋值运算符重载完成深拷贝
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + oldSize;//异地扩容后_finish失效，需重新设定_finish
				_end_of_storage = _start + n;
			}
		}
		//resize接口
		void resize(size_t n, T val = T())//val给T类型的缺省值
		{
			if (n > capacity())//n大于capacity，要扩容
			{
				reserve(n);
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else if (n > size())//n小于capacity但大于原size
			{
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else//缩size的情况
			{
				_finish = _start + n;
			}
		}
		//push_back/pop_back接口
		void push_back(const T& val)
		{
			if (_finish == _end_of_storage)
			{
				size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
				reserve(newCapacity);
			}
			*_finish = val;
			++_finish;
		}
		void pop_back()
		{
			assert(!empty());
			--_finish;
		}
		//insert和erase接口
		iterator insert(iterator pos, const T& val)
		{
			assert(pos >= _start && pos <= _finish);
			//判断扩容
			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;//需要处理pos迭代器失效问题，记录len
				size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
				reserve(newCapacity);//扩容后pos迭代器失效
				pos = _start + len;//重新设定pos
			}
			//挪动数据
			for (iterator i = _finish; i > pos; --i)
			{
				*i = *(i - 1);
			}
			//填入数据
			*pos = val;
			++_finish;
			return pos;
		}
		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			for (iterator i = pos; i < _finish - 1; ++i)
			{
				*i = *(i + 1);
			}
			--_finish;
			return pos;
		}
		//小接口
		size_t size()const
		{
			return _finish - _start;
		}
		size_t capacity()const
		{
			return _end_of_storage - _start;
		}
		bool empty()const
		{
			return _start == _finish;
		}
		void clear()
		{
			_finish = _start;
		}
	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
 
 
 
/测试部分
	void test()
	{
		vector<int> v(1, 5);
		vector<int> v1(v);
		for (auto e : v1)
		{
			cout << e << " ";
		}
	}
	class Solution {
	public:
		vectorint>> generate(int numRows) {
			vectorint>> vv;
			vv.resize(numRows);
			for (size_t i = 0; i < vv.size(); ++i)
			{
				vv[i].resize(i + 1, 0);
				vv[i][0] = 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)
					{
						vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
					}
				}
			}
			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;
			}
			return vv;
		}
	};
	void test_vector()
	{
		vectorint>> vv;
		vector<int> v(5, 1);
		vv.push_back(v);
		vv.push_back(v);
		vv.push_back(v);
		vv.push_back(v);
		vv.push_back(v);
 
		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;
	}
}