【C++ STL】探索STL的奥秘——vector底层的深度剖析和模拟实现！

#include<iostream>
using namespace std;
namespace my_vector
{
	template<class T>
	class vector
	{
	public:
	//vector的迭代器使用的是一个原生指针，因为原生指针本身就能完成迭代器相关的++ * --等这些操作
		typedef T* iterator;
		typedef const T* const_iterator
	private:
		iterator _start;//指向空间头部的指针
		iterator _finish;//指向最后一个有效数据的下一个位置
		iterator _endofstorage;//指向空间的末尾
};

//vector的默认构造
	vector()
	:_start(nullptr)
	,_finish(nullptr)
	,_endofstorage(nullptr)
{}

//使用n个val初始化
//这里的T()是调用T对应的构造 是为了能够让任意类型都能够调用 如果T是内置类型 就会调用内置类型的构造 如果T是自定义类型就调用自定义类型自己的默认构造
	vector(size_t n, T val = T())
	{
		resize(n, val);//resize接口后面会讲
	}

//拷贝构造

```cpp
//拷贝构造 v2(v1)
vector(const vector<T>& v)
{
	//开与v1一样大的空间
	reserve(v.size());//reserve接口后面会介绍
	//底层也是调用push_back
	for (auto e : v)
	{
		push_back(e);//尾插，后面会介绍
	}
}

//使用初始化列表构造 示例:vector<int> v1={1,2,3,4,5}; 花括号的内容其实是转化成了initializer_list对象 这里不理解的可以看上一篇文章！
vector(initializer_list<T> il) 
{
	//根据所给的对象il开空间然后调用push_back
	reserve(il.size());
	for (auto e : il)
	{
		//底层是this指针调用的pus_back this指针存的是要构造的vector对象的地址
		push_back(e);
	}
}


//迭代器区间构造 搞成函数模板支持泛型 形参可以是任意容器的迭代器
template<class Inputiterator>
vector(Inputiterator first, Inputiterator last)
{
	//底层调的还是push_back
	while (first != last)
	{
		push_back(*(first));
		first++;
	}
}


//赋值重载 底层使用交换函数交换底层的成员变量
vector operator=(const vector<T>& v)
{
	swap(v);
	return *this;
}

void swap(const vector<T>& v)
{
	std::swap(_start,v._start);
	std::swap(_finish,v._finish);
	std::swap(_endofstorage,v._endofstorage);
}

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

//普通迭代器
iterator begin()
{
	return _start;
}
iterator end()
{
	//返回的是finish不是endofstorage
	return _finish;
}
//const迭代器
const_iterator begin() const
{
	return _start;
}
const_iterator end() const
{
	//返回的是finish不是endofstorage
	return _finish;
}

//size和capacity通过两个指针相减可以计算它们之间的数据个数
size_t size() const
{
	return _finish - _start;
}

size_t capacity()
{
	return _endofstorage - _start;
}

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

void resize(size_t n, T val = T())
{
	if (n > size())
	{
		reserve(n);
		//n>size后面的n-size个空间使用val来填充
		while (_finish != _start + n)
		{
			*_finish = val;
			++_finish;
		}
	}
	else//n<size 缩容影响size 有效数据直接缩到n处
	{
		_finish = _start + n;
	}
}


void reserve(size_t n)
{
	//在start更新前要保存一下size
	auto oldsize = size();
	if (n > size())
	{
		//开辟新空间 拷贝旧数据
		iterator tmp = new T[n];
		//拷贝旧数据
		if (_start)
		{
			//memcpy深层次的拷贝问题 原因对于自定义类型是浅拷贝 delete的时候析构两次
			//memcpy(tmp, _start, size()*sizeof(T));
			//使用赋值重载来避免这种问题！！！
			for (size_t i = 0; i < old_size; i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}
		_start = tmp;
		//更新有效数据个数
		_finish = _start + oldsize;
		_endofstorage = _start + n;
	}
}

//支持读和写操作
const T& operator[](size_t i)
{
//判断下标是否合法
	assert(i < size());
	return _start[i];//实际上转化为指针的解引用: *(_start+i)
}

//加上const后只读
const T& operator[](size_t i) const
{
	assert(i < size());

	return _start[i];
}

//尾插
void push_back(const T& x)
{
	//插入要考虑空间是否足够
	if (_finish == _endofstorage)
	{
		reserve(capacity() == 0 ? 4 : 2 * capacity());
	}
	*_finish = x;
	++_finish;
}
//尾删
void pop_back()
{
	assert(!empty());
	--_finish;
}


iterator insert(iterator pos, const T& x)
{
	assert(pos <= _finish);
	assert(pos >= _start);

	//插入首先判断空间是否足够
	if (_finish == _endofstorage)
	{
		//法一 计算相对位置    
		size_t n = pos - _start;
		//扩容 异地扩容会导致迭代器失效 在这里就是野指针
		reserve(capacity() == 0 ? 4 : 2 * capacity());
		//扩容后更新pos
		pos = _start + n;
	}
	//挪动数据
	iterator end = _finish;
	while (end >= pos)
	{
		*(end + 1) = *(end);
		end--;
	}
	*(pos) = x;
	_finish++;

	return pos;
}


//版本二 返回迭代器
iterator erase(iterator pos)
{
	//检查pos的合法性
	assert(pos <= _finish);
	assert(pos >= _start);

	//删除要判断容器是否为空
	if (!empty())
	{
		//删除也会引发迭代器失效
		iterator it = pos;
		while (it < _finish)
		{
			//
			*(it) = *(it + 1);
			++it;
		}
		--_finish;
	}

	return pos;
}

void test_vector9()
{
	my_vector::vector<int> v{ 1,2,3,4};
	auto it = v.begin();
	v.push_back(5);                   //这里会扩容
	while (it != v.end())
	{
		cout << *it << " ";
		*it = 100;
		++it;
	}
	cout << endl;

}

void test_vector10()
{
//删除v中所有的偶数 
	my_vector::vector<int> v{1,2,3,4,5,6};
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		v.erase(it);
		++it;//erase删除的迭代器如果是最后一个元素++it导致程序崩溃
	} 
	for (auto e : v)
		cout << e << " ";
	cout << endl;
	return 0;
}