vector

MySTL开发日志(一)

Date:2022.4.15
开发内容:vector基本组成、基本函数
实现了:vector的构造函数、push_back、pop_back、insert、
find、erase、clear、empty和迭代器等功能,
测试了基本功能,无bug
https://moonweb.top 版权所有

/*******************************************************
//
//    MySTL开发日志
//    Date:2022.4.15
//    开发内容:vector基本组成、基本函数
//    实现了:vector的构造函数、push_back、pop_back、insert、
//         find、erase、clear、empty和迭代器等功能,
//    测试了基本功能,无bug
//
//
//		https://moonweb.top 版权所有
//
********************************************************/
#pragma once
template <typename T>
class vector
{
private:
	typedef T* iterator;
	T* pointer_to_arr;
	size_t _capacity;
	size_t curSize;
	iterator _begin;
	iterator _finish;
	iterator _end_of_storage;


	void _resize()
	{
		size_t oldCapacity = _capacity;
		T* oldArr = pointer_to_arr;
		curSize = _capacity;
		if (oldCapacity == 0)		//如果当前无元素
		{																	 		
			_capacity = 1;		//扩容为1
		}																	 		
		else																 		
		{				//否则扩容为原来的2倍
			_capacity = 2 * oldCapacity;									 	
		}																	 
		T* newarr = new T[_capacity];										 
		for (int i = 0; i < _capacity; i++) newarr[i] = 0;	//把新数组初始化
		for (int i = 0; i < oldCapacity; i++) newarr[i] = oldArr[i];	 			//把原数组的数据拷贝到新数组中
		pointer_to_arr = newarr;	//数组指针指向新数组
		_begin = pointer_to_arr;	//更新迭代器
		_finish = pointer_to_arr + curSize;											
		_end_of_storage = pointer_to_arr + _capacity;
	}
		
	void _copy(iterator ite)		//把ite之后的元素向前移动一位,删除ite的元素
	{
		iterator iite = ite + 1;
		while (iite != end() + 1)	*ite++ = *iite++;
	}

	void move_behind(iterator ite)   	 //把ite及以后的元素向后移动
	{
		iterator tmp = end();
		while (tmp != ite)
		{
			*tmp = *(tmp - 1 );
			tmp--;
		}
	}

	void move_behind(iterator ite, size_t n)		//把ite及以后的元素向后移动
	{
		iterator tmp = end();
		while (n--)
		{
			*tmp = *(tmp - 1);
			tmp--;
		}
	}

public:

	vector()
	{							//初始化数组和迭代器
		pointer_to_arr = nullptr;														 
		_begin = pointer_to_arr;														 
		_finish = pointer_to_arr;														 
		_end_of_storage = pointer_to_arr;												 
		curSize = 0;																	 
		_capacity = 0;																	 
	}																					 
																						 
	vector(size_t cap)															 
	{																					 
		T* arr = new T[cap];		//初始化数组和迭代器
		for (int i = 0; i < cap; i++) arr[i] = 0;
		pointer_to_arr = arr;															 
		_begin = pointer_to_arr;														 
		_finish = pointer_to_arr+ cap;
		_end_of_storage = pointer_to_arr + cap;
		curSize = cap;
		_capacity = cap;
	}																					 
																						 
	vector(size_t cap, const T& value)
	{										//初始化数组和迭代器
		T* arr = new T[cap];
		pointer_to_arr = arr;															 
		for (int i = 0; i < cap; i++)	arr[i] = value;
		_begin = pointer_to_arr;														 
		_finish = pointer_to_arr + cap;
		_end_of_storage = pointer_to_arr + cap;
		curSize = cap;
		_capacity = cap;
	}


	void push_back(T val)
	{
		if (_finish == _end_of_storage)
		{
			_resize();
		}

		curSize++;
		*_finish = val;
		_finish++;
	}

	void pop_back()
	{
		if (_capacity > 0)
		{
			curSize--;
			_finish--;

		}
	}

	void insert(iterator ite, T val)		//在ite之前插入元素val
	{
		iterator tmp = ite;
		size_t move_behind_nums = 0;	//记录有多少个元素需要向后移动
		size_t need_to_insert_index = 0;		//记录需要插入元素的下标
		for (auto i = ite; i != end(); i++) move_behind_nums++;
		for (auto i = begin(); i != ite; i++)	need_to_insert_index++;
		if (ite  != end())		 //如果不是在最后插入元素
		{
			if (_finish == _end_of_storage)		//如果空间不足需要扩容
			{
				_resize();		//扩容后迭代器失效,无法用迭代器判断位置,需要通过传入需要移动元素的数量来确定位置。
				move_behind(ite, move_behind_nums);
			}
			else move_behind(ite);		//不需要扩容则通过迭代器判断位置
			*(begin()+ need_to_insert_index) = val;		//插入元素
			curSize++;						//移动迭代器
			_finish++;					//移动迭代器
		}
		else
		{
			push_back(val);		
		}
	}

	void insert(iterator ite, size_t n, T val)
	{
		//TODO
	}
																						  //查找元素第一次出现的位置,返回迭代器
	iterator find(T&& val)
	{
		iterator ite = begin();
		while(ite != end())
		{
			if (*ite == val) return ite;
			ite++;
		}
		return end();
	}

	iterator erase(iterator ite)		//删除指定位置的元素
	{
		if (ite + 1 != end())	//如果当前不是最后一个元素
		{
			_copy(ite);		//把ite后面的元素向前移动一位
		}
		_finish--;			
		curSize--;
		return ite;
	}

	iterator erase(iterator beg, iterator end)
	{
		//TODO
	}


	void clear()				//清除所有元素
	{
		curSize = 0;
		_finish = _begin;
	}

	T front() const 
	{
		return *begin();
	}

	T back() 
	{
		return *(end()-1);
	}

	T operator[](const size_t idx)
	{
		return *(begin() + idx);
	}

	 

	size_t size() const 
	{
		return curSize;
	}

	size_t capacity() const 
	{
		return _capacity;
	}

	bool empty() const
	{
		return begin() == end();
	}

	iterator begin() const 
	{
		return _begin;
	}

	iterator end() const
	{
		return _finish;
	}
};

MySTL开发日志(二)

Date:2022.4.16
开发内容:vector基本组成、基本函数
实现了:vector的resize,reverse,reserve,at,data,erase等成员函数及其重载版本
修改了:size(),capacity()成员函数的实现方式,删除了两个成员变量。更加符合STL源码。
https://moonweb.top 版权所有

/*******************************************************
//
//    MySTL开发日志
//    Date:2022.4.16
//    开发内容:vector基本组成、基本函数
//    实现了:vector的resize,reverse,reserve,at,data,erase等成员函数及其重载版本
//    修改了:size(),capacity()成员函数的实现方式,删除了两个成员变量。更加符合STL源码。
//
//
//		https://moonweb.top 版权所有
//
********************************************************/
	inline iterator erase(iterator _beg, iterator _end)		//删除[_beg,_end) 范围内的所有元素
	{
		size_t num = _end - _beg;			//统计删除的元素个数
		iterator tmp = _beg;
		if (_end != end())
		{
			iterator ite = _end;			//将后续元素移动到前面
			while (ite != end())
			{
				*tmp++ = *ite++;
			}
			_finish = tmp;						//更改迭代器
			return _beg;						//返回删除元素的下一个元素的迭代器
		}
		else
		{
			_finish = _beg;
			return _end;
		}
	}

	inline void reverse(iterator _beg, iterator _end)	 //翻转[_beg,end)内的元素
	{
		if (_beg >= _end) return;
		auto i = _beg, j = _end - 1;
		while (i < j)
		{
			auto tmp = *i;
			*i = *j;
			*j = tmp;
			i++;
			j--;
		}
	}

	inline void resize(size_t& newsize)			//扩容
	{
		size_t curSize = size();																 
		if (newsize == curSize) return;			//如果容量相等则返回
		else if (newsize < curSize)				//如果容量变小则调用erase删除后续元素
		{
			erase(begin() + newsize, end());
			return;
		}
		else																				  //如果容量增加则扩容
		{
			_resize(newsize);
			return;
		}
	}


	inline void resize(size_t newsize,T&& val)		//扩容
	{
		size_t curSize = size();
		if (newsize == curSize) return;			//如果容量相等则返回
		else if (newsize < curSize)				//如果容量变小则调用erase删除后续元素
		{
			erase(begin() + newsize, end());
			return;
		}
		else								//如果容量增加则扩容
		{
			_resize(newsize,val);
			return;
		}
	}

	inline void reserve(size_t& newsize)
	{
		size_t curSize = size();
		if (newsize <= curSize) return;
		else
		{
			_reverse(newsize);
			return;
		}
	}

	inline T at(const size_t& idx) const
	{
		return *(begin() + idx);
	}


	inline T* data()	const		//返回数组第一个元素的指针
	{
		return begin();
	}

	inline size_t size() const
	{
		return _finish-_begin;
	}

	inline size_t capacity() const
	{
		return _end_of_storage-_begin;
	}

MySTL开发日志(三)

Date:2022.4.17
开发内容:vector基本组成
实现了:vector的拷贝构造函数和赋值运算符,实现了vector的深拷贝。
修改了:修复了某些情况会导致内存泄漏的bug,将类成员函数的实现放在类外
https://moonweb.top 版权所有

/*******************************************************
//
//    MySTL开发日志
//    Date:2022.4.17
//    开发内容:vector基本组成、基本函数
//    实现了:vector的拷贝构造函数和赋值运算符,实现了vector的深拷贝。将类成员函数的实现放在类外
//    修改了:修复了某些情况会导致内存泄漏的bug。
//
//
//		https://moonweb.top 版权所有
//
********************************************************/
template <typename T>
vector<T>& vector<T>::operator=(vector<T>& vec)
{
	if (this != &vec)
	{
		T* p = new T[vec.size()];
		this->pointer_to_arr = p;
		for (int i = 0; i < vec.size(); i++) p[i] = vec[i];
		_begin = this->pointer_to_arr;
		_finish = _begin + vec.size();
		_end_of_storage = _finish;
	}
	return *this;
}

template <typename T>
vector<T>::vector(vector& vec)
{
	T* p = new T[vec.size()];
	this->pointer_to_arr = p;
	for (int i = 0; i < vec.size(); i++) p[i] = vec[i];
	_begin = this->pointer_to_arr;
	_finish = _begin + vec.size();
	_end_of_storage = _finish;
}

list

MySTL开发日志(四)

Date:2022.4.18
开发内容:list基本组成,list迭代器类、list节点类。
实现了:list的节点类的实现、迭代器类的构造函数、重载操作符、list类的insert,push_back,begin,end等函数

https://moonweb.top 版权所有

/*******************************************************
//
//    
//    Date:2022.4.18
//    开发内容:list基本组成,list迭代器类、list节点类。
//    实现了:list的节点类的实现、迭代器类的构造函数、重载操作符、
//    	      list类的insert,push_back,begin,end等函数
//    https://moonweb.top 版权所有
//
//		
//
********************************************************/
 #pragma once
#include<iostream>
using namespace std;

template <class T>
struct _list_Node
{
public:

	_list_Node<T>* next;
	_list_Node<T>* pre;
	T val;

	friend ostream& operator<<(ostream& out,_list_Node<T>& node)	//重载输出节点值
	{
		out << (&node)->val;
		return out;
	}
};

template<class T>
class _list_iterator
{
public:
	typedef T value_type;
	typedef _list_Node<T>* node_type;
	typedef _list_iterator<T> self;

	node_type node;					//指向节点的指针

	_list_iterator(node_type x) :node(x) {}
	_list_iterator(const _list_iterator& x) :node(x.node){}//重载<<输出地址
	friend ostream& operator<<(ostream& os,self ite)
	{
		os << &ite;
		return os;
	}

	bool operator==(self x)			 //重载迭代器==
	{
		return node == x.node;
	}

	bool operator!=(self x)														   //重载迭代器!=
	{
		return node != x.node;
	}

	value_type operator *()		//重载迭代器*ite
	{
		return node->val;
	}

	self& operator++()		 //重载++ite
	{
		node =node->next;
		return *this;
	}

	self operator++(int)	//重载ite++
	{
		auto tmp = *this;
		++* this;
		return tmp;
	}
	self& operator--() 		 //重载--ite
	{
		node = node->pre;
		return *this;
	}

	self operator--(int) 	//重载ite--
	{
		auto tmp = *this;
		--* this;
		return tmp;
	}
};
 

template <class T>
class list
{
public:
	typedef _list_Node<T>		node_type;	 //指向尾结点后的空白节点的指针
	typedef _list_Node<T>*		pointer;
	typedef T					value_type;
	typedef _list_iterator<T>	iterator;

	node_type* node;

private:
 
	pointer create_node(value_type val);
	pointer create_node();
	void empty_initialize();
 
public:
	list();
	iterator begin();
	iterator end();
	bool empty() const;

	void push_back(value_type val);
	iterator insert(iterator pos, value_type v); 
 
};

template<class T>			 //创建一个空节点
typename list<T>::pointer list<T>::create_node(value_type v)									 
{																								 
	node_type* p = new node_type;																 
	p->val = v;																					 
	p->next = p;																				 
	p->pre = p;																					 
	return p;																					 
}																								 
																								 
template<class T>																				 
typename list<T>::pointer list<T>::create_node() //创建一个空节点
{
	node_type* p = new node_type;
	p->val = 0;
	p->next = p;
	p->pre = p;
	return p;
}

template<class T>
inline void list<T>::empty_initialize()
{
	node_type* p = new node_type;
	p->next = p;
	p->pre = p;
	node = p;
}


template<class T>		 //无参构造函数
list<T>::list()
{
	empty_initialize();
}


template<class T>
typename list<T>::iterator list<T>::begin()
{
	return iterator(node->next);	//返回构造的迭代器类对象
}

template<class T>
typename list<T>::iterator list<T>::end()//返回构造的迭代器类对象
{
	return iterator(node);
}

template<class T>
bool list<T>::empty() const
{
	return node->next == node;
}


template<class T>
inline typename list<T>::iterator list<T>::insert(iterator pos, value_type v)				 //在pos前面插入v节点
{
	pointer tmp = create_node(v);
	tmp->next = pos.node;
	tmp->pre = pos.node->pre;
	(pos.node->pre)->next = tmp;
	pos.node->pre = tmp;
	return iterator(tmp);
}

template<class T>
void list<T>::push_back(value_type val)
{
	insert(end(), val);
}

MySTL开发日志(五)

Date:2022.4.19
开发内容:list成员函数
实现了:list的push_front,push_back,pop_front,
pop_back,front,back,size,clear,remove等函数
https://moonweb.top 版权所有

/*******************************************************
//
//    
//    Date:2022.4.19
//    开发内容:list成员函数
//    实现了:list的push_front,push_back,pop_front,
//    pop_back,front,back,size,clear,remove等函数
//    
//
//    https://moonweb.top 版权所有
//
//		
//
********************************************************/
template<class T>
inline typename list<T>::reference list<T>::front()
{
	return  *begin();
}

template<class T>
inline typename list<T>::reference list<T>::back()
{
	iterator tmp = end();
	--tmp;
	return  *tmp;
}


template<class T>
inline void list<T>::push_back(value_type val)
{
	insert(end(), val);
}

template<class T>
inline void list<T>::push_front(value_type val)
{
	insert(begin(), val);
}

template<class T>
inline void list<T>::pop_back()
{
	iterator tmp = end();
	erase(--tmp);
}

template<class T>
inline void list<T>::pop_front()
{
	erase(begin());
}

template<class T>
inline typename list<T>::value_type list<T>::size()
{
	iterator _begin = begin();
	value_type num = 0;
	while (_begin != end())
	{
		num++;
		_begin++;
	}
	return num;
}

template<class T>
inline void list<T>::clear()
{
	pointer cur = node->next;											   //找到begin迭代器
	while (cur!=node)													   //遍历所有节点
	{																	   
		pointer tmp = cur;												   
		cur = cur->next;												   
		destroy_node(tmp);												   //释放所有节点
	}																	    
																		    
	node->next = node;													   //恢复初始状态
	node->pre = node;													  
}

template<class T>
inline void list<T>::remove(value_type val)								   //移除所有值为val的节点
{
	iterator cur = begin();
	while (cur != end())
	{
		iterator tmp = cur;
		cur++;
		if (*tmp == val) erase(tmp);
	}

}

MySTL开发日志(六)

Date:2022.4.20
开发内容:list成员函数,vector的列表初始化
实现了:list的 merge,sort,splice,swap,resize,reverse等函数,
list的列表初始化和vector的列表初始化

https://moonweb.top 版权所有

/*******************************************************
//
//    
//    Date:2022.4.20
//    开发内容:list成员函数,vector的列表初始化
//    实现了:list的 merge,sort,splice,swap,resize,reverse等函数,
//    list的列表初始化和vector的列表初始化
//   
//
//     https://moonweb.top 版权所有
//
//		
//
********************************************************/
template<class T>
inline void list<T>::merge(list<T>& x)		//将两个有序链表合并
{
	iterator first1 = begin(); 
	iterator last1 = end(); 
	iterator first2 = x.begin(); 
	iterator last2 = x.end();
	while(first1 != last1 && first2 != last2)
		if (*first2 < *first1)
		{
			iterator next = first2;
			transfer(first1, first2, ++next);
			first2 = next;
		}
		else
		{	++first1;
		}
	if (first2 != last2) transfer(last1, first2, last2);

}

template<class T>
inline void list<T>::splice(iterator pos, list<T>& x, iterator first, iterator last)				   //将[first,last)的元素移动到pos之前
{
	if (first != last)
	{
		transfer(pos, first, last);
	}
}

template<class T>
inline void list<T>::splice(iterator pos, list<T>& x, iterator i)									  //将i之前的元素移动到pos之前
{
	iterator j = i;
	++j;
	if (pos == i || pos == j)
	{
		return; 
	}
	transfer(pos, i, j);
}

template<class T>
inline void list<T>::splice(iterator pos, list<T>& x)												 //将x移动到pos之前
{
	if (!x.empty)
	{
		transfer(pos, x.begin(), x.end());
	}
}

template<class T>
inline void list<T>::swap(list<T>& x)
{
	list<T> t;
	t.splice(t.end(),x, x.begin(), x.end());
	x.clear();
	x.splice(x.end(),*this, this->begin(), this->end());
	this->clear();
	this->splice(this->end(),t, t.begin(), t.end());

}

template<class T>
inline void list<T>::resize(value_type n)
{
	resize(n, 0);
}

template<class T>
inline void list<T>::resize(value_type n, value_type val)
{
	size_t size = this->size();
	if (n == size) return;
	else if (n < size)
	{
		while (n != size)
		{
			pop_back();
			size--;
		}
	}
	else if (n > size)
	{
		while (n != size)
		{
			push_back(val);
			size++;
		}
	}
}

deque

MySTL开发日志(七)

Date:2022.4.22
开发内容:deque容器迭代器
实现了:deque的迭代器类的自增自减,随机访问,大小比较等重载运算符,缓冲区等相关函数及成员。

https://moonweb.top 版权所有

/*******************************************************
//
//    
//      Date:2022.4.22
//	开发内容:deque容器迭代器
//	实现了:deque的迭代器类的自增自减,随机访问,大小比较等重载运算
//	符,缓冲区等相关函数及成员
//   
//
//      https://moonweb.top 版权所有
//
//		
//
********************************************************/
template <class T>
class _deque_iterator
{
public:
	typedef _deque_iterator<T>		self;
	typedef T**				map_pointer;
	typedef T				value_type;
	typedef T&				reference;
	typedef T*				pointer;
   

	pointer cur;													    //指向缓冲区内的当前元素
	pointer first;														//指向缓冲区内的首个元素
	pointer last;														//指向缓冲区内的最后元素
	map_pointer node;													//指向中控器的节点的指针

	size_t _deque_buf_size(size_t n, size_t sz)
	{
		if (n != 0) return n;
		else if (sizeof(value_type) < 512) return 512 / sz;
		else return 1;
	}

	size_t buf_size()													 //获得缓冲区大小
	{
		return _deque_buf_size(32, sizeof(value_type));
	}

	void set_node(map_pointer new_node)									 //指向下一个缓冲区
	{
		node = new_node;
		first = *new_node;
		last = first + buf_size();
	}

	reference operator*() const											 //获取迭代器指向的元素
	{
		return *cur;
	}

	pointer operator->() const
	{
		return &(*operator());
	}

	self& operator++()
	{
		++cur;
		if (cur == last)
		{
			set_node(node + 1);
			cur = first;
		}
		return* this;
	}

	self operator++(int)
	{
		self tmp = *this;
		++* this;
		return tmp;
	}

	self& operator--()
	{
		--cur;
		if (cur == first)
		{
			set_node(node - 1);
			cur = last;
		}
		return*this;
	}

	self operator--(int)
	{
		self tmp = *this;
		--* this;
		return tmp;
	}

	self& operator+=(size_t n)
	{
		size_t offset = n + (cur - first);
		if (offset >= 0 && offset <= buf_size())								//目标在同一缓冲区内
		{
			cur += n;
		}
		else
		{
			size_t t = offset>0?offset/buf_size():-(-offset-1)/buf_size()-1;
			set_node(node + t);
			cur = first + (offset - t * buf_size());
		}
		return *this;
	}

	self operator+(size_t n)
	{
		self tmp = *this;
		return tmp += n;
	}

	self& operator-=(size_t n)
	{																			 //调用operator+= 实现operator-=
		return *this += -n;
	}

	self operator-(size_t n)
	{
		self tmp = *this;
		return tmp -= n;
	}
																				 
	reference operator[](size_t n)												  //随机访问
	{
		return *(*this + n);
	}

	bool operator==(const self& x)
	{
		return this->cur == x.cur;
	}

	bool operator!=(const self& x)
	{
		return this->cur != x.cur;
	}

	bool operator<(const self& x)
	{
		return node == x.node ? (cur < x.cur) : (node < x.node);
	}

	bool operator>(const self x)
	{
		return node == x.node ? (cur > x.cur) : (node > x.node);
	}
};

MySTL开发日志(八)

Date:2022.4.25
开发内容:deque容器
实现了:deque的begin,end,front,back,下标访问操作符,empty和中控器的空间配置等功能。

https://moonweb.top 版权所有

/*******************************************************
//
//    
//      Date:2022.4.25
//	开发内容:deque容器
//	实现了:deque的begin,end,front,back,下标访问操作符,
//      empty和中控器的空间配置等功能。
//   
//
//      https://moonweb.top 版权所有
//
//		
//
********************************************************/
 template<class T>
inline typename deque<T>::iterator deque<T>::begin()
{
	return start;
}

template<class T>
inline typename deque<T>::iterator deque<T>::end()
{
	return finish;
}

template<class T>
inline typename deque<T>::reference deque<T>::operator[](size_t n)
{
	return start[n];
}

template<class T>
inline typename deque<T>::reference deque<T>::front()
{
	return *start;
}

template<class T>
inline typename deque<T>::reference deque<T>::back()
{
	auto tmp = finish;
	tmp--;
	return *tmp;
}

template<class T>
inline typename deque<T>::value_type deque<T>::size()
{
	return (finish - start);
}

template<class T>
inline bool deque<T>::empty()
{
	return start == finish;
}

template<class T>
inline typename deque<T>::map_pointer deque<T>::_allocate_map(int map_size)
{
	pointer *t = new pointer[map_size];
	std::memcpy(t, map, sizeof(map));
	map = t;
	return map;
}

template<class T>
inline void deque<T>::create_map_and_nodes(int n)
{
	size_t nodeNums = n / buf_size() + 1;										//需要节点数=元素个数/每个缓冲区内的元素数量 + 1,非空节点数
	map_size = nodeNums + 2;													//前后各保留两个空节点,在扩容时使用。
	map = _allocate_map(map_size);												//创建map中控器节点
	map_pointer newstart = map + (map_size - nodeNums) / 2;
	map_pointer newfinish = newstart + nodeNums - 1;
	map_pointer cur;

	for (cur = newstart; cur <= newfinish; cur++)
	{
		*cur = allocate_buf();	//TODO												  //为每个中控器节点配置缓冲区
		
	}
	start.set_node(newstart);
	finish.set_node(newfinish);
	start.cur = start.first;
	finish.cur = finish.first + n % buf_size();

}

MySTL开发日志(九)

Date:2022.4.26
开发内容:deque容器
实现了:deque的默认构造函数,push_back,push_back_aux,迭代器重载运算符等
修复了:当扩容时忽略边界问题导致的元素丢失的问题

https://moonweb.top 版权所有

/*******************************************************
//
//    
//      Date:2022.4.26
//	开发内容:deque容器
//	实现了:deque的默认构造函数,push_back,push_back_aux,迭代器重载运算符等
//	修复了:当扩容时忽略边界问题导致的元素丢失的问题
//
//      https://moonweb.top 版权所有
//
//		
//
********************************************************/
  template<class T>
inline void deque<T>::push_back(const value_type& val)
{
	if (finish.cur != finish.last - 1)									//如果缓冲区还有空间,则直接原地构造
	{
		*finish.cur = val;
		finish.cur++;
	}
	else
	{
		push_back_aux(val);											  //否则调用辅助函数
	}
}

template<class T>
inline void deque<T>::push_back_aux(const value_type& n)
{
	value_type t = n;
	*(finish.node + 1) = allocate_buf();										  //配置新的缓冲区
	*finish.cur = t;															  //push_back元素
	finish.set_node(finish.node + 1);											  //更改指针指向
	finish.cur = finish.first;													  //更改指针指向
}

template<class T>
inline deque<T>::deque()														   //默认构造函数
{
	map = nullptr;
	fill_initialize(0,0);	
	map_size = 0;
}

int operator-(self& x)
{
	return buf_size() * (node - x.node - 1) + (cur - first) + x.last - x.cur;
}

MySTL开发日志(十)

Date:2022.5.1
开发内容:deque容器
实现了:deque的析构函数,clear,pop_back,pop_front、pop_back_aux,push_back_aux等函数

https://moonweb.top 版权所有

/*******************************************************
//
//    
//      Date:2022.5.1
//	开发内容:deque容器
//	实现了:deque的析构函数,clear,pop_back,pop_front、
//	pop_back_aux,push_back_aux等函数
//	
//
//      https://moonweb.top 版权所有
//
//		
//
********************************************************/

template<class T>
inline void deque<T>::pop_back()
{
	if (finish.cur != finish.first)											  //如果有一个以上剩余元素
	{
		finish.cur--;														  //直接移动指针
	}
	else
	{																		  //否则调用辅助函数
		pop_back_aux();
	}
}

template<class T>
inline void deque<T>::pop_front()
{
	if (start.cur != start.last-1)											    //如果有一个以上剩余元素
	{
		start.cur++;														    //直接移动指针
	}
	else
	{
		pop_front_aux();														//否则调用辅助函数
	}
}

template<class T>
inline void deque<T>::clear()													//调用析构函数再调用构造函数
{
	if (map != nullptr)
	{
		for (int i = 0; i < map_size; i++)
		{
			auto idx = map + i;
			delete[] idx;
			idx = nullptr;
		}
	}
	
	map = nullptr;
	fill_initialize(0, 0);
	map_size = 0;
}

template<class T>
inline void deque<T>::pop_back_aux()
{
	finish.set_node(finish.node - 1);														 //调整指针指向
	destroy(finish.cur);
	finish.cur = finish.last - 1;
	
}

template<class T>
inline void deque<T>::pop_front_aux()
{
	start.set_node(start.node + 1);															  //调整指针指向
	destroy(start.cur);
	start.cur = start.first;
}

MySTL开发日志(十一)

Date:2022.5.3
开发内容:deque容器
实现了:deque的insert,insert_aux等函数
修复了:在调用erase等函数需要移动元素时,在某些时候会移动失败的情况

https://moonweb.top 版权所有

/*******************************************************
//
//  
//  	Date:2022.5.3
//	开发内容:deque容器
//	实现了:deque的insert,insert_aux等函数
//	修复了:在调用erase等函数需要移动元素时,在某些时候会移动
// 	败的情况
//	 
//	
//
//      https://moonweb.top 版权所有
//
//		
//
********************************************************/
template<class T>
inline typename deque<T>::iterator deque<T>::insert(iterator ite, value_type val)
{
	if (ite.cur == start.cur)
	{
		push_front(val);
		return start;
	}
	else if (ite.cur == finish.cur)
	{
		push_back(val);
		iterator tmp = finish;
		tmp--;
		return tmp;
	}
	return insert_aux(ite, val);
}
	
   template<class T>
inline typename deque<T>::iterator deque<T>::insert_aux(iterator ite, value_type& val)
{
	int idx = ite - start;																	   //插入点之前的元素个数
	value_type xx = val;
	if (idx < size() / 2)
	{
		push_front(front());
		iterator front1 = start;
		front1++;
		iterator front2 = front1;
		front2++;
		ite = start + idx;
		iterator ite1 = ite;
		ite1++;
		copy(front2, ite1, front1);
	}
	else
	{
		push_back(back());
		iterator back1 = finish;
		back1--;
		iterator back2 = back1;
		back2--;
		ite = start + idx;
		copy_backward(ite, back2, back1);
	}
	*ite = xx;
	return ite;
}

MySTL开发日志(十二)

Date:2022.5.5
开发内容:deque容器
实现了:deque的构造函数,带参构造函数
修复了:带参构造函数的非正常初始化的问题

https://moonweb.top 版权所有

/*******************************************************
//
//  
//  	2022.5.5
//	开发内容:deque容器
//	实现了:deque的构造函数,带参构造函数
//	修复了:带参构造函数的非正常初始化的问题
//	 
//	
//
//      https://moonweb.top 版权所有
//
//		
//
********************************************************/
template<class T>
inline deque<T>::deque(int n, const value_type& val)							  //有参构造函数
{
	map = nullptr;
	fill_initialize(0, val);
	map_size = 0;
	for (int i = 0; i < n; i++)
	{
		push_back(val);
	}
}

template<class T>
inline deque<T>::deque(int n)
{
	map = nullptr;
	fill_initialize(0, 0);
	map_size = 0;
	for (int i = 0; i < n; i++)
	{
		push_back(0);
	}
}

template<class T>
inline deque<T>::deque()														   //默认构造函数
{
	map = nullptr;
	fill_initialize(0,0);	
	map_size = 0;
}

stack

MySTL开发日志(十三)

Date:2022.5.7
开发内容:deque、stack
实现了:stack的push,pop,size,top,empty等成员函数
修复了:deque的push_back方法的底层实现,修复了在无元素时调用push_back会导致崩溃的情况,修改了部分容器的size函数的返回值类型
https://moonweb.top 版权所有

/*******************************************************
//
//    MySTL开发日志
//    Date:2022.5.7
//    开发内容:deque、stack
//    实现了:stack的push,pop,size,top,empty等成员函数
//    修复了:deque的push_back方法的底层实现,
//    修复了在无元素时调用push_back会导致崩溃的情况 
//	 修改了部分容器的size函数的返回值类型
//
//
//		https://moonweb.top 版权所有
//
********************************************************/
#pragma once
#include"deque.h"

template<class T,class sequence=deque<T>>
class stack
{
public:
	typedef T					value_type;
	typedef T*					pointer;	 
	typedef value_type&				reference;


	sequence c;					//底层容器

public:
	stack() :c() {}					//默认构造函数
	bool empty();
	void push(value_type x);
	void pop();
	size_t size();
	reference top();
 
};
 


template<class T, class sequence>
inline bool stack<T, sequence>::empty()
{
	return c.empty();
}


template<class T, class sequence>
inline void stack<T, sequence>::push(value_type x)
{
	c.push_back(x);
}

template<class T, class sequence>
inline void stack<T, sequence>::pop()
{
	c.pop_back();
}

template<class T, class sequence>
inline size_t stack<T, sequence>::size()
{
	return c.size();
}

template<class T, class sequence>
inline typename  stack<T, sequence>::reference stack<T, sequence>::top()
{
	return c.back();
}

queue

MySTL开发日志(十四)

Date:2022.5.8
开发内容:queue
实现了:stack的push,pop,size,empty,back,front等成员函数
https://moonweb.top 版权所有

/*******************************************************
//
//    
//      Date:2022.5.8
//	开发内容:queue
//	实现了:stack的push,pop,size,empty,back,front等成员函数
//    
//    
//    
//
//		https://moonweb.top 版权所有
//
********************************************************/
#pragma once
#include"deque.h"
using namespace std;


template <class T,class sequence=deque<T>>
class queue
{
public:
	typedef T					value_type;
	typedef T*					pointer;
	typedef value_type&				reference;

protected:
	sequence c;			//底层容器

public:
	queue() :c() {}
	queue(initializer_list<T> x) :c()
	{
		for (auto ite = x.begin(); ite != x.end(); ite++)
		{
			push(*ite);
		}
	}
	bool empty();
	void push(value_type x);
	void pop();
	size_t size();
	reference back();
	reference front();
};



template<class T, class sequence>
inline bool queue<T, sequence>::empty()
{
	return c.empty();
}

template<class T, class sequence>
inline void queue<T, sequence>::push(value_type x)
{
	c.push_back(x);
}

template<class T, class sequence>
inline void queue<T, sequence>::pop()
{
	c.pop_front();
}

template<class T, class sequence>
inline size_t queue<T, sequence>::size()
{
	return c.size();
}

template<class T, class sequence>
inline typename queue<T, sequence>::reference queue<T, sequence>::back()
{
	return c.back();
}

template<class T, class sequence>
inline typename queue<T, sequence>::reference queue<T, sequence>::front()
{
	return c.front();
}

Q.E.D.