list常见接口

list的文档介绍
list的底层结构为带头结点的双向循环链表

构造

iterator迭代器

容量

元素访问

增删查改

list模拟实现

list迭代器失效

在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响

void TestListIterator1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array+sizeof(array)/sizeof(array[0]));
    auto it = l.begin();
    while (it != l.end())
   {
   //erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给
   //其赋值
    l.erase(it);  
    ++it;
   }
}
// 改正
void TestListIterator()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array+sizeof(array)/sizeof(array[0]));
    auto it = l.begin();
    while (it != l.end())
   {
    //l.erase(it++);    
    //让erase函数有返回值，返回指向（被删除位置）新节点的迭代器
   it = l.erase(it);
   }
}

模拟实现

• list.h

#pragma once
#include<iostream>
#include<assert.h>
#include<list>
using namespace std;

namespace high_cool
{
	template<class T>
	struct list_node
	{
		T _date;
		list_node<T>* _prev;
		list_node<T>* _next;

		list_node(const T date=T())
			:_date(date)
			,_prev(nullptr)
			,_next(nullptr)
		{ }
	};

	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_iterator(Node* pnode)
			:_pnode(pnode)
		{}

		Ref operator*()
		{
			return _pnode->_date;
		}
		Ptr operator->()
		{
			return &(_pnode->_date);
		}

		Self operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}
		Self operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}
		Self operator++(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}
		Self operator--(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}
		bool operator!=(const Self& s) const
		{
			return _pnode != s._pnode;
		}
		bool operator==(const Self& s) const
		{
			return _pnode == s._pnode;
		}
	};

	/*template<class T>
	struct list_const_iterator
	{
		typedef list_node<T> Node;
		Node* _pnode;

		list_const_iterator(Node* pnode)
			:_pnode(pnode)
		{
		}

		const T& operator*()
		{
			return _pnode->_date;
		}
		const T* operator->()
		{
			return &(_pnode->_date);
		}

		list_const_iterator operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}
		list_const_iterator operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}
		list_const_iterator operator++(int)
		{
			list_const_iterator tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}
		list_const_iterator operator--(int)
		{
			list_const_iterator tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}
		bool operator!=(const list_const_iterator& s) const
		{
			return _pnode != s._pnode;
		}
		bool operator==(const list_const_iterator& s) const
		{
			return _pnode == s._pnode;
		}
	};*/

	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		/*typedef list_iterator<T> iterator;
		typedef list_const_iterator<T> const_iterator;*/
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;

		void empty_init()
		{
			_head= new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
		list()
		{
			empty_init();
		}
		list(const list<T>& lt)
		{
			empty_init();
			for (auto e : lt)
			{
				push_back(e);
			}
		}
		void swap(list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		list<T> operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}
		void clear()
		{
			auto it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		size_t size() const
		{
			return _size;
		}
		bool empty() const
		{
			return _size == 0;
		}
		iterator begin()
		{
			return _head->_next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator begin() const
		{
			return _head->_next;
		}
		const_iterator end() const
		{
			return _head;
		}

		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._pnode;
			Node* newnode = new Node(x);
			newnode->_next = cur;
			newnode->_prev = cur->_prev;
			cur->_prev = newnode;
			newnode->_prev->_next = newnode;
			++_size;
			return newnode;
		}
		void push_back(const T& x)
		{
			insert(end(), x);
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}

		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 next;
		}
		void pop_back()
		{
			erase(--end());
		}
        void pop_front()
		{
			erase(begin());
		}
		
	private:
		Node* _head;
		size_t _size;
	};

	template<class Container>
	void print_container(const Container con)
	{
		typename Container::const_iterator it = con.begin();
		while (it != con.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
}

• test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"
namespace high_cool
{
	void test1()
	{

		struct AA
		{
			int _a1 = 1;
			int _a2 = 1;
		};

		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			*it += 10;

			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		print_container(lt);

		list<AA> lta;
		lta.push_back(AA());
		lta.push_back(AA());
		lta.push_back(AA());
		lta.push_back(AA());
		list<AA>::iterator ita = lta.begin();
		while (ita != lta.end())
		{
			//cout << (*ita)._a1 << ":" << (*ita)._a2 << endl;
			// 特殊处理，本来应该是两个->才合理，为了可读性，省略了一个->
			cout << ita->_a1 << ":" << ita->_a2 << endl;
			cout << ita.operator->()->_a1 << ":" << ita.operator->()->_a2 << endl;

			++ita;
		}
		cout << endl;
	}

	void test2()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);

		list<int> lt2(lt1);

		print_container(lt1);
		print_container(lt2);

		list<int> lt3;
		lt3.push_back(10);
		lt3.push_back(20);
		lt3.push_back(30);
		lt3.push_back(40);

		lt1 = lt3;
		print_container(lt1);
		print_container(lt3);
	}
}


int main()
{
	//high_cool::test1();
	high_cool::test2();
	return 0;
}