List常用接口

insert

list<int>::iterator pos = find(lt.begin(), lt.end(), 3);
if (pos != lt.end())
	lt.insert(pos, 30);
for (auto e : lt)
	cout << e << " ";
cout << endl;

list的不会失效，而vector会失效。

erase后均会失效。

解决迭代器失效问题

list<int>::iterator it = lt.begin();
while (it != lt.end())
{
	if (*it % 2 == 0)
		it = lt.erase(it);
	else
		it++;
}

核心 erase会返回以删除位置的下一个位置。

清空列表的两种方式

while (it != lt.end())
{
	lt.erase(it++);
}
lt.clear();

模拟实现list

模拟node节点

template<class T>
struct __list_node
{
	__list_node<T>* _next;
	__list_node<T>* _prev;
	T _data;
	__list_node(const T& x=T())
		:_data(x)
		,_next(nullptr)
		,_prev(nullptr)
	{}
};

模拟构造迭代器

template<typename T>
struct __list_iterator
{
	typedef __list_node<T> Node;
	Node* _node;
	__list_iterator(Node* node)
		:_node(node)
	{}
	//*it;
	T& operator*()
	{
		return _node->_data;
	}
	//++it
	__list_iterator<T> operator++()
	{
		_node = _node->_next;
		return *this;
	}
	//it!=end()
	bool operator!=(__list_iterator<T>& it)
	{
		return _node != it->_node;

	}
};

 按照STL原码模拟实现list的结构

template<class T>
class list
{
	typedef struct __list_node<T> Node;
	typedef __list_iterator<T> iterator;
public:
	iterator begin()
	{
		return iterator(_head->_next);
	}
	iterator end()
	{
		return iterator(_head);
	}
	//带头双向循环列表
	list()
	{
		_head = new node;
		_head->_next = _head;
		_head->_prev = _head;
	}
	void push_back(const T& x)
	{
		Node* tail = _head->_prev;
		Node* newnode = new Node(x);
		
		tail->_next = newnode;
		newnode->_prev = tail;
		_head->_prev = newnode;
		newnode->_next = _head;

	}
private:
	Node* _head;
};

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

有了迭代器就可以使用范围for 

T* operator->()
{
	return &_node->_data;
}

struct Date
{
	int _year = 0;
	int _mouth = 1;
	int _day = 1;
};
void test_list()
{
	list<Date> lt;
	lt.push_back(Date());
	lt.push_back(Date());
	list<Date>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << it->_year << it->_mouth << it->_day << endl;
		++it;
	}
}

while (it != lt.end())
{
	//cout << it->_year << it->_mouth << it->_day << endl;
	cout << (*it)._year << (*it)._mouth << (*it)._day << endl;
	++it;
}

前后置++ 

//++it
__list_iterator<T>& operator++()
{
	_node = _node->_next;
	return *this;
}
__list_iterator<T>& operator++()
{
	_node = _node->_prev;
	return *this;
}
//it++	 
__list_iterator<T> operator++(int)
{
	__list_iterator<T> tmp(*this);
	_node = _node->_next;
	return tmp;
}

//it++	 
__list_iterator<T> operator++(int)
{
	__list_iterator<T> tmp(*this);
	_node = _node->_next;
	//(*this)++;
	return tmp;
}