C++中vector的模拟实现实例详解

目录

• vector接口总览
• 默认成员函数

• 构造函数
• 拷贝构造
• 赋值重载
• 析构函数

• begin和end

• size和capacity
• reserve
• resize
• empty

• push_back
• pop_back
• insert
• erase
• swap

• operator[ ]

namespace nzb
{
	//模拟实现vector
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		//默认成员函数
		vector();                                           //构造函数
		vector(size_t n, const T& val);                     //构造函数
		template<class InputIterator>
		vector(InputIterator first, InputIterator last);    //构造函数
		vector(const vector<T>& v);                         //拷贝构造函数
		vector<T>& operator=(const vector<T>& v);           //赋值重载
		~vector();                                          //析构函数
		//迭代器相关函数
		iterator begin();
		iterator end();
		const_iterator begin()const;
		const_iterator end()const;
		//容量相关函数
		size_t size()const;
		size_t capacity()const;
		void reserve(size_t n);
		void resize(size_t n, const T& val = T());
		bool empty()const;
		//修改容器相关函数
		void push_back(const T& x);
		void pop_back();
		void insert(iterator pos, const T& x);
		iterator erase(iterator pos);
		void swap(vector<T>& v);
		//访问容器相关函数
		T& operator[](size_t i);
		const T& operator[](size_t i)const;
	private:
		iterator _start;        //指向容器的头
		iterator _finish;       //指向有效数据的尾
		iterator _endofstorage; //指向容器的尾
	};
}

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

vector(size_t n, const T& val)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstorage(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)
	, _endofstorage(nullptr)
{
	while (first != last)
	{
			push_back(*first);
			first++;
	}
}

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

		vector(const vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
			vector<T> tmp(v.begin(), v.end());
			swap(tmp);
		}

vector<T>& operator=(const vector<T>& v)
{
	if (this != &v)
	{
		delete[] _start;
		_start = _finish = _endofstorage = nullptr;
		reserve(v.capacity());
		for (const auto& e : v)
		{
			push_back(e);
		}
	}	
	return *this;
}

vector<T>& operator=(vector<T> v)
{
	swap(v);
	return *this;
}

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

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

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

void reserve(size_t n)
{
	if (n > capacity()) 
	{
		size_t sz = size(); // 记录原容器中数据个数
		T* tmp = new T[n]; // 开辟一块容量为n的空间
		if (_start) //判空
		{
			for (size_t i = 0; i < sz; i++) // 拷贝数据
			{
				tmp[i] = _start[i];
			}
			delete[] _start; // 释放原容器中的数据
		}
		_start = tmp; // 调整指针
		_finish = _start + sz; 
		_endofstorage = _start + n; 
	}
}

void resize(size_t n, const T& val = T())
{
	if (n <= size())// 当n小于当前的size时
	{
		_finish = n + _start;// 将size缩小到n
	}
	else // 当n大于当前的size时
	{
		if (n > capacity())// 当n大于容量时，扩容
		{
			reserve(n);
		}
		while (_finish < _start + n)// 给size到容器结尾赋值
		{
			*_finish = val;
			_finish++;
		}
	}
}

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

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

void pop_back()
{
	assert(!empty());// 判空
	--_finish;
}

iterator insert(iterator pos, const T& x)
{
	assert(pos >= _start&&pos <= _finish);// 判断传入数据的合法性
	if (_finish == _endofstorage)// 扩容
	{
		size_t len = pos - _start;// 记录pos的位置
		size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapacity);
		pos = _start + len;
	}
	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 it = pos + 1;// 利用迭代器记录pos的后一位
	while (it != _finish)// 将pos后的数据往前挪动一位
	{
		*(it - 1) = *it;
		it++;
	}
	_finish--;
	return pos;
}

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

T& operator[](size_t i)// 可读可写
{
	assert(i < size());
	return _start[i];
}
const T& operator[](size_t i) const// 只能读
{
	assert(i<size());
	return _start[i];
}