C++：vector的模拟实现

hello，各位小伙伴，本篇文章跟大家一起学习《C++：vector的模拟实现》，感谢大家对我上一篇的支持，如有什么问题，还请多多指教 ！
如果本篇文章对你有帮助，还请各位点点赞！！！

话不多说，开始进入正题

🍁全代码

#pragma once
#include<iostream>
#include <assert.h>
#include <stdbool.h>

using namespace std;

namespace My_vector
{

	// 适配器 -- 复用
	template<class Iterator, class Ref, class Ptr>
	struct Reverse_iterator
	{
		Iterator _it;
		typedef Reverse_iterator<Iterator, Ref, Ptr> Self;

		Reverse_iterator(Iterator it)
			:_it(it)
		{}

		Ref operator*()
		{
			Iterator tmp = _it;
			return *(--tmp);
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		Self& operator++()
		{
			--_it;
			return *this;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		bool operator!=(const Self& s)
		{
			return _it != s._it;
		}
	};

	template <class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

		reverse_iterator rbegin()
		{
			return iterator(end());
		}

		reverse_iterator rend()
		{
			return iterator(begin());
		}

		const_reverse_iterator rbegin()
		{
			return const_iterator(end());
		}

		const_reverse_iterator rend()
		{
			return const_iterator(begin());
		}

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

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

		vector<T>& operator=(vector<T> v)//c = a;
		{					// 直接崩掉就是因为现代的赋值运算符重载是传值传参,会调用拷贝构造构造个临时变量,拷贝构造也需要初始化
			swap(v);
			return *this;
		}
		
		vector(const vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _endOfStorage(nullptr)
		{
			reserve(v.capacity());
			for (auto e : v)
			{
				push_back(e);
			}
		}

		template<class InPutIterator>
		vector(InPutIterator first, InPutIterator last)
		{
			while (first != last)
			{
				push_back((*first));
				++first;
			}
		}

		vector(initializer_list<T> a)
		{
			reserve(a.size());
			for (auto e : a)
			{
				push_back(e);
			}
		}
		

		vector(size_t n, const T& val = T())
		{
			reserve(n);
			for (int i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}

		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _endOfStorage = nullptr;
			}
		}

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

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin()const
		{
			return _start;
		}

		const_iterator end()const
		{
			return _finish;
		}

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

		size_t capacity()const
		{
			return _endOfStorage - _start;
		}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t oldsize = size();
				T* tmp = new T[n];
				if (_start)
				{
					for (size_t i = 0; i < oldsize; ++i)
						tmp[i] = _start[i];

					// 3. 释放旧空间
					delete[] _start;
				}

				_start = tmp;
				_finish = _start + oldsize;
				_endOfStorage = _start + n;
			}
		}

		void resize(size_t n, const T& value = T())
		{
			if (n <= size())
			{
				_finish = _start + n;
				return;
			}

			if (n > capacity())
			{
				reserve(n);
			}
			iterator lt = _finish;
			_finish = _start + n;
			while (lt != _finish)
			{
				*lt = value;
				++lt;
			}
		}

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

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

		void push_back(const T& t)
		{
			/*if (_finish == _endOfStorage)
			{
				size_t newcapacity = (capacity() == 0) ? 4 : 2 * capacity();
				reserve(newcapacity);
			}
			*_finish = t;
			++_finish;*/

			insert(end(), t);
		}
		void popback()
		{
			assert(_start != _finish);
			--_finish;
		}

		void erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);

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

			--_finish;
		}

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

			// 空间不够先进行增容
			if (_finish == _endOfStorage)
			{
				//size_t size = size();
				size_t len = pos - _start;
				size_t newCapacity = (0 == capacity()) ? 4 : capacity() * 2;
				reserve(newCapacity);

				// 如果发生了增容，需要重置pos
				pos = _start + len;
			}

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

			return pos;
		}
		iterator insert(iterator pos,size_t n ,const T& t)
		{
			assert(pos >= _start);
			assert(pos <= _finish);

			// 空间不够先进行增容
			while (_finish + n >= _endOfStorage)
			{
				//size_t size = size();
				size_t len = pos - _start;
				size_t newCapacity = (0 == capacity()) ? 4 : capacity() * 2;
				reserve(newCapacity);

				// 如果发生了增容，需要重置pos
				pos = _start + len;
			}

			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + n) = *end;
				--end;
			}
			int cnt = 0;
			while (cnt < n)
			{
				*pos = t;
				++pos;
				++cnt;
			}
			_finish += n;

			return pos;
		}

	private:
		iterator _start;		// 指向数据块的开始
		iterator _finish;		// 指向有效数据的尾
		iterator _endOfStorage;  // 指向存储容量的尾
	};
}

🍁讲解

🍃一个类vector和一个结构体Reverse_iterator

类vector里私有成员变量有：

iterator _start;		// 指向数据块的开始
iterator _finish;		// 指向有效数据的尾
iterator _endOfStorage; // 指向所开空间的尾

结构体Reverse_iterator成员变量有：

Iterator _it;// 迭代器，因为对于反向迭代器我们可以复用正向迭代器

🍃vector的迭代器

由于迭代器类似于指针，所以我们在这里用指针代替：

// 正向迭代器
typedef T* iterator;
typedef const T* const_iterator;

// 反向迭代器
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

🍃vector的成员函数

• 1.默认构造函数：

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

• 2.传参构造函数

传元素个数和值（可不写，调用该类型的构造函数）
由于此原因，所以内置类型也就有了自己的默认构造函数

vector(size_t n, const T& val = T())
{
	reserve(n);
	for (int i = 0; i < n; ++i)
	{
		push_back(val);// vector的尾插成员函数
	}
}

传迭代器区间

template<class InPutIterator>
vector(InPutIterator first, InPutIterator last)
{
	while (first != last)
	{
		push_back((*first));
		++first;
	}
}

传初始化列表

vector(initializer_list<T> a)
{
	reserve(a.size());
	for (auto e : a)
	{
		push_back(e);
	}
}

• 3.拷贝构造函数

vector(const vector<T>& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _endOfStorage(nullptr)
{
	reserve(v.capacity());
	for (auto e : v)
	{
		push_back(e);
	}
}

🍃析构函数

~vector()
{
	if (_start)
	{
		delete[] _start;
		_start = _finish = _endOfStorage = nullptr;
	}
}

🍃迭代器

// 正向迭代器
iterator begin()
{
	return _start;
}

iterator end()
{
	return _finish;
}

const_iterator begin()const
{
	return _start;
}

const_iterator end()const
{
	return _finish;
}

// 反向迭代器
reverse_iterator rbegin()
{
	return iterator(end());// 复用正向迭代器
}

reverse_iterator rend()
{
	return iterator(begin());// 复用正向迭代器
}

const_reverse_iterator rbegin()
{
	return const_iterator(end());// 复用正向迭代器
}

const_reverse_iterator rend()
{
	return const_iterator(begin());// 复用正向迭代器
}

🍃交换函数

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

🍃赋值重载函数

vector<T>& operator=(vector<T> v)//c = a;
{
	swap(v);// 复用交换函数
	return *this;
}

🍃vector相关的容器函数

• 判断是否为空

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

• 返回vrctor的大小

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

• 返回该vector所开的空间

size_t capacity()const
{
	return _endOfStorage - _start;
}

🍃reserve函数

预留空间，大大降低了数组需要被重新分配大小为了增加存储空间所用的时间，提高了效率

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t oldsize = size();
		T* tmp = new T[n];
		if (_start)
		{
			for (size_t i = 0; i < oldsize; ++i)
				tmp[i] = _start[i];

			// 3. 释放旧空间
			delete[] _start;
		}

		_start = tmp;
		_finish = _start + oldsize;
		_endOfStorage = _start + n;
	}
}

由于重新分配空间会导致指针_start，_finish，_endOfStorage失效，所以使用了oldsize记录_start和_finish的距离。

🍃resize函数

// 扩容时可以传第二个参数value来对后面的空间初始化

void resize(size_t n, const T& value = T())
{
	// 缩容的情况
	if (n <= size())
	{
		_finish = _start + n;
		return;
	}
	
	// 扩容的情况
	if (n > capacity())
	{
		reserve(n);// 开空间
	}
	iterator lt = _finish;
	_finish = _start + n;
	while (lt != _finish)
	{
		*lt = value;
		++lt;
	}
}

🍃[]重载函数

T& operator[](size_t i)
{
	assert(i < size());// 检查是否越界访问
	return _start[i];
}

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

🍃尾插函数和尾删函数

• 尾插函数

void push_back(const T& t)
{
	if (_finish == _endOfStorage)// 判断是否需要扩容
	{
		size_t newcapacity = (capacity() == 0) ? 4 : 2 * capacity();
		reserve(newcapacity);
	}
	*_finish = t;
	++_finish;

	// insert(end(), t);// 复用插入函数
}

• 尾删函数

void popback()
{
	assert(_start != _finish);
	--_finish;
}

🍃erase函数

• 销毁函数

void erase(iterator pos)
{
	assert(pos >= _start);// 判断是否越界
	assert(pos < _finish);// 判断是否越界

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

	--_finish;
}

🍃插入函数

• 插入一个元素

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

	// 空间不够先进行增容
	if (_finish == _endOfStorage)
	{
		//size_t size = size();
		size_t len = pos - _start;
		size_t newCapacity = (0 == capacity()) ? 4 : capacity() * 2;
		reserve(newCapacity);

		// 如果发生了增容，需要重置pos，迭代器失效问题
		pos = _start + len;
	}

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

	return pos;
}

• 插入多个元素

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

	// 空间不够先进行增容
	while (_finish + n >= _endOfStorage)
	{
		//size_t size = size();
		size_t len = pos - _start;
		size_t newCapacity = (0 == capacity()) ? 4 : capacity() * 2;
		reserve(newCapacity);

		// 如果发生了增容，需要重置pos，迭代器失效问题
		pos = _start + len;
	}

	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + n) = *end;
		--end;
	}
	int cnt = 0;
	while (cnt < n)
	{
		*pos = t;
		++pos;
		++cnt;
	}
	_finish += n;

	return pos;
}

🍁反向迭代器对正向迭代器的复用

这里3个模板参数，就是为了让编译器去判断该调用什么类型返回值的成员函数

// 适配器 -- 复用
//             迭代器           引用        指针
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
	Iterator _it;// 成员变量，正向迭代器
	typedef Reverse_iterator<Iterator, Ref, Ptr> Self;

	// 构造函数
	Reverse_iterator(Iterator it)
		:_it(it)
	{}

	Ref operator*()
	{
		Iterator tmp = _it;
		return *(--tmp);
	}

	Ptr operator->()
	{
		return &(operator*());
	}

	Self& operator++()
	{
		--_it;
		return *this;
	}

	Self& operator--()
	{
		++_it;
		return *this;
	}

	bool operator!=(const Self& s)
	{
		return _it != s._it;
	}
};

你学会了吗？
好啦，本章对于《C++：vector的模拟实现》的学习就先到这里，如果有什么问题，还请指教指教，希望本篇文章能够对你有所帮助，我们下一篇见！！！

如你喜欢，点点赞就是对我的支持，感谢感谢！！！