模拟实现vector

文章目录

1.模拟实现前须知知识点

1.1普通类和模板类的良好编写习惯

1.模板类
使用类模板时,声明和定义不要分离,分离也要放在同一个文件,否则会导致链接错误
由于声明和定义必须放在同一文件,所以很多时候都将.h文件写成.hpp文件,表示我使用的是模板类,并且声明和定义都不会分离

2.普通类
平时我们应该将声明和定义分离,这样可以更好的看见类的整体框架
并且我们可以将代码短小的函数放在类里面,让它默认成为内联函数

1.2vector中的参数含义

模拟实现vector

1.3空间的开辟注意事项

1.3.1开空间不能用malloc/realloc

模拟实现vector

1.3.2注意深浅拷贝

模拟实现vector

1.4巧妙利用{}作用域,调用析构函数

模拟实现vector

1.5迭代器失效场景

模拟实现vector
模拟实现vector

2.实现过程

一个类的默认有六种成员函数,我们模拟实现的时候一般都是实现它的构造、拷贝构造、赋值运算符重载、析构函数,取地址重载默认的就够用了;

在实现了基本的成员函数之后,应该转移到增删查改的思路上面去模拟实现,像vector的增有push_back和insert删有erase和push_pop,查是库里面公用的find,改则是重载[]

在实现上述过程之中,会发现容量也需要改变,因此我们还需要实现reserve和resize,同时也需要将迭代器进行重定义,vector的迭代器就是它的原生指针

在此在之外,我们通常会需要获得空间内部的大小和有效元素的个数,因此需要size和capacity接口。在外部的时候我们很有可能需要访问私有成员变量,因此又可以提供begin和end接口

在上述实现中,如果不需要改变的地方尽量的使用const,扩大接收范围。如果可以场景使用引用的话,尽量使用引用,降低拷贝的消耗

3.代码

#pragma once
#include <assert.h>
#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
#include <string>

namespace mv
{
	template<class T>
	class vector
	{
	public:

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


		vector()//构造函数说明,vector出来一个对象之后,第一件就是给它开空间
			:_start(nullptr),
			_finish(nullptr),
			_end_of_storge(nullptr)
		{}

		template<class InputIterator>//模板函数
		vector(InputIterator first, InputIterator last)
			: _start(nullptr),
			_finish(nullptr),
			_end_of_storge(nullptr)
		{
			reserve(last - first);//开辟空间
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

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

		vector(const vector<T> &x)
			:_start(nullptr),
			_finish(nullptr),
			_end_of_storge(nullptr)
		{
			vector<T> temp(x.begin(), x.end());
			swap(temp);
		}

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

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

		T &operator[](size_t index)const//const类型调用const
		{
			assert(index<size());
			return _start[index];
		}

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

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

		//void reserve(size_t n) //浅拷贝,只适用于内置
		//{
		//	if (n>capacity())
		//	{
		//						
		//		T *temp = new T[n];
		//		size_t old_size = size();//临时保存一份,避免失效

		//		memcpy(temp, _start, size()*sizeof(T));

		//		//delete[] _start;
		//		_start = temp;
		//		_finish = _start + old_size;
		//		_end_of_storge = _start + n;
		//		temp = nullptr;
		//	}

		//}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				 iterator temp = new T[n];
				size_t old_size = size();//大小临时记录一下

				iterator begin_start = _start;
				iterator begin_temp=temp;

				while (begin_start != _finish)
				{
					*begin_temp= *begin_start;//深拷贝一份
					//往后挪动
					begin_start++;
					begin_temp++;
				}

				delete[] _start;//释放原来的空间
				_start = temp;//指向新的空间
				temp = nullptr;//防止析构自定义类型
				
				_finish = _start + old_size;//不直接使用size是因为防止迭代器失效
				_end_of_storge = _start + n;
				
			}
		}

		void check_capacity()
		{
			if (_finish >= _end_of_storge)
			{
				size_t newsize = capacity() == 0 ? 4 : 2 * capacity();//如果为0,则扩容4个,否则扩容2倍
				reserve(newsize);
			}
		}

		void  push_back(const T &x)
		{
			check_capacity();
			*_finish = x;
			_finish++;
		}

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

		void resize(size_t newsize, const T &x=T())//调用匿名对象,具有常性,需要加上const
		{
			if (newsize>capacity())
			{
				reserve(newsize);//扩容
			}

			if (newsize<size())
				_finish = _start + newsize;

			else
			{
				while (_finish != _start + newsize)
				{
					*_finish = x;
					_finish++;
				}
			}
		}

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

			size_t inpos = pos - _start;//保存一份相对位置,防止迭代器失效
			check_capacity();

			pos = _start + inpos;
			iterator last = _finish;

			while (last != pos)//往后挪动
			{
				*last = *(last - 1);
				last--;
			}
			*pos = x;
			_finish++;

			return pos;//结局和迭代器失效问题
		}

		void Print()
		{
			iterator start = _start;
			while (start != _finish)
			{
				cout << *start << " ";
				start++;
			}
			cout << endl;
		}
		
		iterator erase(iterator pos)
		{
			assert(pos >= _start&&pos < _finish);

			iterator temp_pos = pos;

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

			return temp_pos;
		}

	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storge;

	};
}

上一篇:Eclipse错误:The superclass "javax.servlet.http.HttpServlet" was not found on the Java Build


下一篇:如何使用diea创建一个空的java项目