STL之list的模拟实现

文章目录

STL之list的模拟实现

在学会了使用list之后，在使用过程中，难免会出现一些使用上的问题，为了更好地使用list，我们模仿STL源码，自己实现一个list容器

类的设计

节点类

首先，我们得有一个节点类，节点类中需要包含两个指针和一个值来保存数据。一个指针保存前一个节点地址，一个指针保存下一个节点地址。

template<class T>
	class ListNode {
	public:
		//把list和ListIterator类都声明为ListNode类的友元类
		friend class list<T>;
		friend class ListIterator<T, T&, T*>;
		friend class ListIterator<T, const T&, const T*>;
	public:
		ListNode(const T& val = T())
			:_val(val)
			, _pPrev(nullptr)
			, _pNext(nullptr)
		{}
	private:
        //定义前后两个节点的指针
		ListNode<T>* _pPrev;
		ListNode<T>* _pNext;
        //数据成员
		T _val;
	};

别的类要访问节点类的私有成员，就要把别的类设为节点类的友元类。

迭代器类

由于list是一个双向循环带头链表，我们不能用下标对节点进行访问，所以我们对指针进行封装，让这个迭代器对象可以象指针一样进行操作。

迭代器有两种实现方式，具体应根据容器底层数据结构实现：

原生态指针，比如：vector

将原生态指针进行封装，因迭代器使用形式与指针完全相同，因此在自定义的类中必须实现以下方法：

指针可以解引用，迭代器的类中必须重载operator*()
指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
至于operator–()/operator–(int)释放需要重载，根据具体的结构来抉择，双向链表可
以向前移动，所以需要重载，如果是forward_list就不需要重载–
迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()

我们使用了三个模板参数来实现一个模板类产生两个不同类型的迭代器

template<class T, class Ref, class Ptr>
	class ListIterator {
	public:
		friend class list<T>;
		typedef ListNode<T> Node;
		typedef Node* PNode;
		typedef ListIterator<T, Ref, Ptr> Self;
    public:
       //ref和ptr可以是T&和T* 也可以是const T&和const T*
        Ref operator*() {
			return _PNode->_val;
		}
        Ptr operator->() {
			return &(_PNode->_val);
		}
    }

list类

list类中要有一个成员变量，也就是头节点的指针，还要用到迭代器对象

template<class T>
	class list {
	public:
		typedef ListNode<T> Node;
		typedef Node* PNode;
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;
    private:
		PNode _pHead;
	};

list类的构造

要构造list类，我们就先得有一个头节点

我们动态申请一个头节点，我们写了一个方法来实现节点的申请，这里我们参照了STL的源码来实现，这里的实现很巧妙。
首先我们传入三个有缺省值的参数，分别是当前节点后一个节点的指针，前一个节点的指针，还有构造的val值。
如果我们不传参，全部按照缺省值来，那么这里就会申请一个值为类型默认值的节点，并且这个节点的前后指针都指向自己，可以用来申请头节点。
要是传入了前后指针和值，那么这个方法会把申请的这个新节点指向它的前后节点，减少我们连接的步骤。

PNode _BuyNode(PNode _Narg = 0, PNode _Parg = 0, const T& val = T()) {
	PNode _S = new Node(val);
	_S->_pNext = _Narg != 0 ? _Narg : _S;
	_S->_pPrev = _Parg != 0 ? _Parg : _S;
	return (_S);
}

不同的情况使用_BuyNode方法就可以创建出不同的节点

//无参构造
list()
	:_pHead(_BuyNode())
{}
//构造n个val值
list(int n, const T& val = T())
	:_pHead(_BuyNode())
{
	while (n--) {
		push_back(val);
	}
}
//构造一个区间
template <class Iterator>
list(Iterator first, Iterator last)
	:_pHead(_BuyNode())
{
	while (first != last) {
		push_back(*first);
		++first;
	}
}

list类的迭代器

实现两个方法分别返回list第一个节点的迭代器也就是头节点的下一个节点，最后一个节点的下一个节点的迭代器，还有它们的const版本

iterator begin();
iterator end();
const_iterator begin();
const_iterator end();

//返回的是节点的指针构造出来的迭代器临时对象
iterator begin() {
	return iterator(_pHead->_pNext);
}
iterator end() {
	return iterator(_pHead);
}

const_iterator cbegin() const {
	return const_iterator(_pHead->_pNext);
}
const_iterator cend() const {
	return const_iterator(_pHead);
}

list类的容量实现

int size()const {
	int sz = 0;
	PNode _S = _pHead->_pNext;
	while (_S != _pHead) {
		sz++;
		_S = _S->_pNext;
	}
	return sz;
}
bool empty()const {
	return _pHead->_pNext == _pHead;	
}

list类的访问实现

T& front() {
	assert(!empty());
	return _pHead->_pNext->_val;
}
const T& front()const {
	assert(!empty());
	return _pHead->_pNext->_val;
}
T& back() {
	assert(!empty());
	return _pHead->_pPrev->_val;
}
const T& back()const {
	assert(!empty());
	return _pHead->_pPrev->_val;
}

list类的操作实现

push_back()
pop_back()
push_front()
pop_front()
insert()
erase()
clear()
swap()

要实现这么多方法，看似很多，很复杂，其实我们只要完成insert和erase方法，其他方法就可以通过这两个方法复用适配实现

iterator insert(iterator pos, const T& val = T()) {
    //先定义一个节点指针指向当前节点
	PNode _S = pos._PNode;
    //当前节点的prev更新为新申请的节点，也急就是把新申请的节点放在了当前节点的前面，并且当前节点的prev指针指向了这个新节点
    //调用_BuyNode方法时我们传入了当前节点的指针和当前节点的前一个节点的指针，节点创建完成时，新节点就分别指向这两个节点
  	//可以说这条语句是一箭三雕
	_S->_pPrev = _BuyNode(_S, _S->_pPrev, val);
    //这时更新_S的位置为新节点
	_S = _S->_pPrev;
    //只剩下一条链接，用新节点的前一个节点的后向指针指向新节点
	_S->_pPrev->_pNext = _S;
    //返回新节点的指针
	return iterator(_S);
}

iterator erase(iterator pos) {
    //创建一个_S节点指针指向当前节点
	PNode _S = pos._PNode;
    //pos迭代器更新到下一个位置，也就是当前节点的下一个节点位置
	pos++;
    //更新节点指向
	_S->_pPrev->_pNext = _S->_pNext;
	_S->_pNext->_pPrev = _S->_pPrev;
    //删除当前节点
	delete _S;
    //返回已删除节点下一个节点
	return pos;
}

其他的操作实现

void push_back(const T& val) {
	insert(end(), val);
}
void push_front(const T& val) {
	insert(begin(), val);
}
void pop_back() {
	erase(--end());
}
void pop_front() {
	erase(begin());
}

void clear() {
	int sz = size();
	for (int i = 0; i < sz; ++i) {
		erase(begin());
	}
}
//交换两个链表也就是交换两个链表头节点的指针
void swap(list<T>& l) {
	std::swap(_pHead, l._pHead);
}

list的拷贝

list(const list<T>& l)
	:_pHead(_BuyNode())
{
     //用l的区间构造临时对象
	list<T> temp(l.cbegin(), l.cend());
     //交换新对象和临时对象
	swap(temp);
}

list<T>& operator=(const list<T> l) {
	if (this != &l) {
       	//原理和拷贝构造类似
		list<T> temp(l);
		swap(temp);
	}
	return *this;
}

list的销毁

~list() {
	clear();
	delete _pHead;
	_pHead = nullptr;
}

完整代码实现

#include<iostream>
namespace xiaomage {
	///
	//前向声明
	template<class T>
	class list;
	template<class T, class Ref, class Ptr>
	class ListIterator;
	///
	//节点类
	template<class T>
	class ListNode {
	public:
		//把list和ListIterator类都声明为ListNode类的友元类
		friend class list<T>;
		friend class ListIterator<T, T&, T*>;
		friend class ListIterator<T, const T&, const T*>;
	public:
		ListNode(const T& val = T())
			:_val(val)
			, _pPrev(nullptr)
			, _pNext(nullptr)
		{}
	private:
		ListNode<T>* _pPrev;
		ListNode<T>* _pNext;
		T _val;
	};
	///
	//迭代器类
	//这里给了Ref和Ptr两个模板参数用来实现在一个类实现普通迭代器和const迭代器
	template<class T, class Ref, class Ptr>
	class ListIterator {
	public:
		friend class list<T>;
		typedef ListNode<T> Node;
		typedef Node* PNode;
		typedef ListIterator<T, Ref, Ptr> Self;
	public:
		
		ListIterator(PNode pNode = nullptr)
			:_PNode(pNode)
		{}
		ListIterator(const Self& LI)
			:_PNode(LI._PNode)
		{}
		Ref operator*() {
			return _PNode->_val;
		}
		Ptr operator->() {
			return &(_PNode->_val);
		}
		Self& operator++() {
			_PNode = _PNode->_pNext;
			return *this;
		}
		Self operator++(int) {
			Self temp(*this);
			_PNode = _PNode->_pNext;
			return temp;
		}
		Self& operator--() {
			_PNode = _PNode->_pPrev;
			return *this;
		}
		Self operator--(int) {
			Self temp(*this);
			_PNode = _PNode->_pPrev;
			return temp;
		}
		bool operator!=(const Self& LI) {
			return _PNode != LI._PNode;
		}
		bool operator==(const Self& LI) {
			return !((*this) != LI);
		}
	private:
		PNode _PNode;
	};


	
	//链表类
	template<class T>
	class list {
	public:
		typedef ListNode<T> Node;
		typedef Node* PNode;
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;
	public:
		
		/// list构造
		list()
			:_pHead(_BuyNode())
		{}
		list(int n, const T& val = T())
			:_pHead(_BuyNode())
		{
			while (n--) {
				push_back(val);
			}
		}
		template <class Iterator>
		list(Iterator first, Iterator last)
			:_pHead(_BuyNode())
		{
			while (first != last) {
				push_back(*first);
				++first;
			}
		}

		/
		//list拷贝
		list(const list<T>& l)
			:_pHead(_BuyNode())
		{
			list<T> temp(l.cbegin(), l.cend());
			swap(temp);
		}

		list<T>& operator=(const list<T> l) {
			if (this != &l) {
				list<T> temp(l);
				swap(temp);
			}
			return *this;
		}
		
		//list迭代器
		iterator begin() {
			return iterator(_pHead->_pNext);
		}
		iterator end() {
			return iterator(_pHead);
		}

		const_iterator cbegin() const {
			return const_iterator(_pHead->_pNext);
		}
		const_iterator cend() const {
			return const_iterator(_pHead);
		}

		

		
		//list操作

		iterator insert(iterator pos, const T& val = T()) {
			PNode _S = pos._PNode;
			_S->_pPrev = _BuyNode(_S, _S->_pPrev, val);
			_S = _S->_pPrev;
			_S->_pPrev->_pNext = _S;
			return iterator(_S);
		}
		iterator erase(iterator pos) {
			PNode _S = pos._PNode;
			pos++;
			_S->_pPrev->_pNext = _S->_pNext;
			_S->_pNext->_pPrev = _S->_pPrev;
			delete _S;
			return pos;
		}
		void push_back(const T& val) {
			insert(end(), val);
		}
		void push_front(const T& val) {
			insert(begin(), val);
		}
		void pop_back() {
			erase(--end());
		}
		void pop_front() {
			erase(begin());
		}
		
		
		void clear() {
			int sz = size();
			for (int i = 0; i < sz; ++i) {
				erase(begin());
			}
		}
		void swap(list<T>& l) {
			std::swap(_pHead, l._pHead);
		}

		//
		//list容量
		int size()const {
			int sz = 0;
			PNode _S = _pHead->_pNext;
			while (_S != _pHead) {
				sz++;
				_S = _S->_pNext;
			}
			return sz;
		}
		bool empty()const {
			return _pHead->_pNext == _pHead;
		}
		/
		//list访问
		T& front() {
			assert(!empty());
			return _pHead->_pNext->_val;
		}
		const T& front()const {
			assert(!empty());
			return _pHead->_pNext->_val;
		}
		T& back() {
			assert(!empty());
			return _pHead->_pPrev->_val;
		}
		const T& back()const {
			assert(!empty());
			return _pHead->_pPrev->_val;
		}
		//
		//list销毁
		~list() {
			clear();
			delete _pHead;
			_pHead = nullptr;
		}
	private:
		/
		//节点申请
		PNode _BuyNode(PNode _Narg = 0, PNode _Parg = 0, const T& val = T()) {
			PNode _S = new Node(val);
			_S->_pNext = _Narg != 0 ? _Narg : _S;
			_S->_pPrev = _Parg != 0 ? _Parg : _S;
			return (_S);
		}
	private:
		PNode _pHead;
	};
}