一、list的结构

1. list的节点

list的底层是一个带头双向循环链表但list本身和list的节点是不同的结构需要分开实现。

list节点的结构

template<class T>
struct list_node
{
	list_node<T>* _next;
	list_node<T>* _prev;
	T _data;
	//构造使用x初始化节点的数据
	list_node(const T& x)
		:_next(nullptr)
		, _prev(nullptr)
		, _data(x)
	{}
};

2. list的结构

class list
{
	typedef list_node<T> node;
	//……
private:
	node* _head;
	size_t _size;
};

---

二、list的迭代器

list的迭代器不能再像vector一样用普通指针作为迭代器因为存储节点的空间不保证连续。

list迭代器必须有能力指向list的节点并能够正确的进行++、--、*、->等操作所谓正确是指++时指向下一个节点--时指向上一个节点*取的是节点的数据值->取的是节点数据成员的地址。

list的迭代器使用封装 + 操作符重载以达到在使用方式上如同指针一样的目的。

list是一个双向链表迭代器必须具有前移++、后移- -所以list的迭代器是一个双向迭代器。

1. 正向迭代器

template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef list_node<T> node;
	typedef __list_iterator<T, Ref, Ptr> Self;
	node* _pnode;//迭代器内部要有一个指针指向list的节点
	
	//constructor
	__list_iterator(node* p)
		:_pnode(p)
	{}
	
	Ptr operator->()
	{
		//return &_pnode->_data;
		return &(operator*());//标准做法
	}

	// iterator it
	// *it
	// ++it;
	// 解引用取到的是节点的数据值
	Ref operator*()
	{
		return _pnode->_data;
	}

	const T& operator*() const
	{
		return _pnode->_data;
	}
	
	// ++it
	Self& operator++()
	{
		_pnode = _pnode->_next;
		return *this;
	}

	// it++
	Self operator++(int)//返回类型为迭代器自己
	{
		//拷贝构造这里只需要浅拷贝使用系统生成的即可满足需求
		Self tmp(*this);
		_pnode = _pnode->_next;
		return tmp;
	}
	//--it
	Self& operator--()
	{
		_pnode = _pnode->_prev;
		return *this;
	}
	//it--
	Self operator--(int)
	{
		Self tmp(*this);
		_pnode = _pnode->_prev;
		return tmp;
	}
	//比较指向节点的指针即节点的地址
	bool operator!=(const Self& it) const
	{
		return _pnode != it._pnode;
	}

	bool operator==(const Self& it) const
	{
		return _pnode == it._pnode;
	}
};

---

2. 反向迭代器

反向迭代器的实现体现了泛型思维。反向迭代器是正向迭代器的封装内部有一个正向迭代器成员

模板参数Iterator给我不同容器的正向迭代器适配出对应的这个容器需要的反向迭代器。比如要实现vector的反向迭代器只需将其正向迭代器作为参数传入即可。

// 适配器 -- 复用
template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
	typedef ReverseIterator<Iterator, Ref, Ptr> Self;
private:
	Iterator _it;
public:
	ReverseIterator(Iterator it)
		:_it(it)
	{}
	Ref operator* ()
	{
		Iterator tmp = _it;
		return *(--tmp);//先--再解引用原因是用正向迭代器的end构造了rbegin
	}
	Ptr operator-> ()
	{
		return &(operator*());//显示调解引用再取地址
	}
	//前置++
	Self& operator++ ()
	{
		--_it;//反向迭代器的++是正向迭代器的--
		return *this;
	}
	//后置++
	Self operator++ (int)
	{
		ReverseIterator tmp(_it);
		--_it;
		return tmp;
	}
	//前置--
	Self& operator-- ()
	{
		++_it;
		return *this;
	}
	//后置--
	Self operator-- (int)
	{
		ReverseIterator tmp(_it);
		++_it;
		return tmp;
	}
	bool operator!= (const Self& s)
	{
		return _it != s._it;
	}
};

3. 迭代器失效问题

list的一个性质插入操作不会造成原迭代器失效。删除操作也只有”指向“被删除元素的迭代器失效其他不受影响。

4. 具体实现

template<class T>
class list
{
	typedef list_node<T> node;
private:
	node* _head;
	size_t _size;
	//……
public:
	//前面使用模板参数是为了根据传入参数不同实现不同迭代器
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;

	typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
	typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

	//反向迭代器
	reverse_iterator rbegin()
	{
		return reverse_iterator(end());
	}

	reverse_iterator rend()
	{
		return reverse_iterator(begin());
	}

	const_reverse_iterator rbegin() const
	{
		return const_reverse_iterator(end());
	}

	const_reverse_iterator rend() const
	{
		return const_reverse_iterator(begin());
	}

	const_iterator begin() const
	{
		return const_iterator(_head->_next);
	}

	const_iterator end() const
	{
		return const_iterator(_head);
	}

	iterator begin()
	{
		return iterator(_head->_next);
	}

	iterator end()
	{
		//iterator it(_head);
		//return it;
		return iterator(_head);
	}
};

可以发现正向迭代器和反向迭代器是对称的这也是为什么在反向迭代器实现中会有如下代码

Ref operator* ()
{
	Iterator tmp = _it;
	return *(--tmp);//先--再解引用原因是用正向迭代器的end构造了rbegin
}

---

三、构造和析构

• 构造一个空链表

void empty_initialize()
{
	_head = new node(T());
	_head->_next = _head;
	_head->_prev = _head;
	_size = 0;
}
list() { empty_initialize(); }//生成一个空链表

• 区间构造

template <class InputIterator>
list(InputIterator first, InputIterator last)
{
	empty_initialize();
	while (first != last)
	{
		push_back(*first);
		++first;
	}
}

• 拷贝构造和赋值运算符重载

//传统写法
// lt2(lt1)
//list(const list<T>& lt)
//{
//	empty_initialize();

//	for (const auto& e : lt)
//	{
//		push_back(e);
//	}
//}

 lt1 = lt3
//list<T>& operator=(const list<T>& lt)
//{
//	if (this != &lt)
//	{
//		clear();
//		for (const auto& e : lt)
//		{
//			push_back(e);
//		}
//	}

//	return *this;
//}
void swap(list<T>& lt)
{
	std::swap(_head, lt._head);
	std::swap(_size, lt._size);
}
// lt2(lt1)
list(const list<T>& lt)
//list(const list& lt) //虽然C++语法支持类名作为类型但是不建议
{
	empty_initialize();

	list<T> tmp(lt.begin(), lt.end());
	swap(tmp);
}

// lt3 = lt1
list<T>& operator=(list<T> lt)
//list& operator=(list lt) // 不建议
{
	swap(lt);
	return *this;
}

• 析构

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}
~list()
{
	clear();//clear完成除头节点外其他节点的销毁工作
	delete _head;
	_head = nullptr;
}

---

四、insert和erase

//在pos前插入
iterator insert(iterator pos, const T& x)
{
	node* newnode = new node(x);
	node* cur = pos._pnode;
	node* prev = cur->_prev;

	// prev newnode cur
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;

	++_size;

	return iterator(newnode);
}

iterator erase(iterator pos)
{
	assert(pos != end());

	node* prev = pos._pnode->_prev;
	node* next = pos._pnode->_next;

	prev->_next = next;
	next->_prev = prev;

	delete pos._pnode;
	--_size;

	return iterator(next);
}

---

五、其他元素操作

void push_back(const T& x)
{
	//node* newnode = new node(x);
	//node* tail = _head->_prev;
	 _head         tail   newnode
	//tail->_next = newnode;
	//newnode->_prev = tail;
	//newnode->_next = _head;
	//_head->_prev = newnode;

	insert(end(), x);
}

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

void pop_front()
{
	erase(begin());
}

void pop_back()
{
	erase(--end());
}

---