STL——List常用接口模拟实现及其使用

认识list

list的介绍

• 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
• 2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
• 3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
• 4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
• 5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

list和vector的对比

基本框架

单个节点构建

	template<class T>
	class list_node {
	public:
		list_node<T>* _next;//后继指针
		list_node<T> *_prev;//前驱指针
		T _data;//节点的值
		list_node(const T& data = T())
			:_data(data)
			, _next(nullptr)
			,_prev(nullptr)
		{}
	};

List结构构建

class List {
		typedef list_node<T> Node;
	public:
		List(){
			_pHead = new Node();
			_pHead->_next = _pHead;
			_pHead->_prev = _pHead;
		}
};

push_back尾插

实现

void push_back(const T& data) {
			Node* newnode = new Node(data);
			Node* pTail = _pHead->_prev;//最后一个节点

			pTail->_next = newnode;
			newnode->_prev = pTail;//连接最后一个节点和新节点

			newnode->_next = _pHead;
			_pHead->_prev = newnode;//处理最后一个节点和第一个节点		}

使用

mylist::List<int> A;
	A.push_back(1);
	A.push_back(2);
	A.push_back(3);
	A.push_back(4);
	A.print();//这个是方便调试观察结果写出来的函数

迭代器的实现

在之前的容器string和vector的实现中，迭代器都是以指针的形式实现，但是在List模拟实现中又不是指针，因为List是一个链表，空间并不连续，指针的+或-并不能移动到数据的下一个位置。

迭代器的构造

	template <class T>
	class list_iterator {
		typedef list_node<T> Node;
	public:
		Node* _node
		list_iterator(Node* x): _node(x){}
	};

operator++

//前置++   (++it)
		iterator<T>& operator++() {
			_node = _node->_next;
			return *this;
		}
//后置++  (it++)
		iterator<T> operator++(int) {
			list_iterator<T> tmp(*this);
			_node = _node->_next;
			return tmp;
		}

operator*

//解引用
		T& operator*() {
			return _node->_data;
		}

operator !=

bool operator !=(const iterator& it) {
			return _node != it._node;
		}

const迭代器实现

如果这里要实现const迭代器，将之前的的代码复用再写一个const_list_iterator,然后在List再写一个const 的begin()和end()就可以了，但是这里有更优的写法，可以解决这些不必要的代码冗余

	class List {
	public:
		typedef list_node<T> Node;
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;
		const_iterator begin() const {
			return const_iterator(_pHead->_next);
		}
		const_iterator end() const {
			return cosnt_iterator(_pHead);
		}
		.......
}
struct list_iterator {
		typedef list_node<T> Node;
		typedef list_iterator<T, Ref, Ptr> self;
		Ref& operator*() {
			return _node->_data;
		}
}

迭代器对List初始化

template<class Iterator>
		List(Iterator first, Iterator last) {
			_pHead = new Node();
			_pHead->_next = _pHead;
			_pHead->_prev = _pHead;

			while (first != last) {
				push_back(*first);
				first++;
			}
		}

增删查改

在 pos 位置前插入 - insert

	void insert(iterator pos, const T& x) {
			Node* cur = pos._node;     // 找到pos位置的结点
			Node* cur_prev = cur->_prev;     // 当前pos位置的前一个结点
			Node* new_node = new Node(x);  // 创建新节点

			cur_prev->_next = new_node;
			new_node->_prev = cur_prev;
			new_node->_next = cur;
			cur->_prev = new_node;
		}

push_front 头插

void push_front(const T& x) {
			insert(begin(), x); 
		}

删除 pos 位置的结点 erase

iterator erase(iterator pos) {
			assert(pos != end());   // 防止头结点被删除

			Node* cur = pos._node;   // pos
			Node* cur_prev = cur->_prev;   // pos的前驱
			Node* cur_next = cur->_next;   // pos的后继

			// 删除pos
			delete cur;
			cur_prev->_next = cur_next;
			cur_next->_prev = cur_prev;

			return iterator(cur_next);
		}

pop_back 尾删

void pop_back() {
	erase(_pHead->_prev);  // 删除最后一个元素
}

pop_front 头删

void pop_front() {
			erase(begin());  // 删除头结点的下一个结点->begin所指的位置
		}

clear 删除链表所有数据

void clear() {
			iterator cur = begin();
			while (cur != end()) {
				iterator del = cur++;
				delete del._node; 
			}
			//处理哨兵节点
			_pHead->_next = _pHead;
			_pHead->_prev = _pHead;
		}

析构函数和拷贝构造

默认的拷贝构造是浅拷贝，在这里是行不通的，万一调用析构函数，同一个空间就被释放两次了所以要对拷贝构造设计一下让其成为深拷贝的形式

析构

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

拷贝构造

list(const list<T>& L) {
    _pHead = new Node();
	_pHead->_next = _pHead;
	_pHead->_prev = _pHead;
	List<T> tmp(L.begin(), L.end());
	swap(_pHead, tmp._pHead);  
}