目录

前言

一、list

1.1 list的介绍

1.2 list的使用

1.2.1 list的构造

1.2.2 list iterator的使用

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

1.2.6 list的迭代器失效

二、list的模拟实现

2.1 模拟实现list

三、list与vector的对比

总结

1.2 list的使用

1.2.1 list的构造

void TestList1()
{
    list<int> l1;                         // 构造空的l1
    list<int> l2(4, 100);                 // l2中放4个值为100的元素
    list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3
    list<int> l4(l3);                    // 用l3拷贝构造l4

    // 以数组为迭代器区间构造l5
    int array[] = { 16,2,77,29 };
    list<int> l5(array, array + sizeof(array) / sizeof(int));

    // 列表格式初始化C++11
    list<int> l6{ 1,2,3,4,5 };

    // 用迭代器方式打印l5中的元素
    list<int>::iterator it = l5.begin();
    while (it != l5.end())
    {
        cout << *it << " ";
        ++it;
    }       
    cout << endl;

    // C++11范围for的方式遍历
    for (auto& e : l5)
        cout << e << " ";

    cout << endl;
}

1.2.2 list iterator的使用

1.2.6 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++); // it = l.erase(it);
         }
}

二、list的模拟实现

2.1 模拟实现list

namespace bit {
	template<class T>
	struct ListNode {
		ListNode<T>* _prev;//前驱节点
		ListNode<T>* _next;//后继节点
		T _date;//数据

		//节点的构造
		ListNode(const T& date = T())
			:_prev(nullptr)
			, _next(nullptr)
			,_date(date)
		{}
	};

	/*template<class T>
	struct ListConstIterator {
		typedef ListNode<T> Node;
		typedef ListConstIterator<T> Self;
		Node* _node;

		ListConstIterator(Node* node)
			:_node(node)
		{}

		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self operator++(int)
		{
			Self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		Self& operator--()
		{
			_node = _node->_prev;
		}

		Self& operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;

			return tmp;
		}

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

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

		bool operator!=(const Self& l)
		{
			return _node != l._node;
		}
		bool operator==(const Self& l)
		{
			return _node == l.node;
		}

	};*/

	template<class Iterator, class Ref, class Ptr>
	struct reverse_iterator
	{

		Iterator _it;

		reverse_iterator(Iterator it)
			:_it(it)
		{}

		Iterator& operator++()
		{
			--_it;
			return _it;
		}

		Iterator operator++(int)
		{
			Iterator temp = _it;
			--_it;
			return temp;
		}

		Iterator& operator--()
		{
			++_it;
			return _it;
		}

		Iterator& operator--(int)
		{
			Iterator temp = _it;;
			++_it;

			return temp;
		}

		Ref operator*()
		{
			Iterator tmp = _it;
			return *tmp;
		}

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

		bool operator!=(const reverse_iterator& l)
		{
			return _it !=l._it;
		}
		bool operator==(const reverse_iterator& l)
		{
			return _it !=l._it;
		}
	};

	template<class T, class Ref, class Ptr>
	struct ListIterator {
		typedef ListNode<T> Node;
		typedef ListIterator<T,Ref,Ptr> Self;
		Node* _node;

		ListIterator(Node* node)
			:_node(node)
		{}

		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self operator++(int)
		{
			Self tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		Self& operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;

			return tmp;
		}

		Ref operator*()
		{
			return _node->_date;
		}

		Ptr operator->()
		{
			return &_node->_date;
		}

		bool operator!=(const Self& l)
		{
			return _node != l._node;
		}
		bool operator==(const Self& l)
		{
			return _node == l.node;
		}

	};


	template<class T>
	class list {
	public:
		typedef ListNode<T> Node;
		//写两个不同的模板
	/*	typedef ListIterator<T> iterator;
		typedef ListConstIterator<T> const_iterator;*/

		//传不同的类型
		typedef ListIterator<T,T&,T*> iterator;
		typedef ListIterator<T,const T&,const T*> const_iterator;

        //反向迭代器
		typedef reverse_iterator<iterator, T&, T*> reverse_iterator;
		
		iterator begin()
		{
			return iterator(_head->_next);
		}

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

		reverse_iterator rbegin()
		{
			return reverse_iterator(_head->_prev);
		}

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

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

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

		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		list()
		{
			empty_init();
		}

		list(const list<T>& l)
		{
			empty_init();
			for (const auto& e: l)
			{
				push_back(e);
			}
		}

		list(initializer_list<T> l)
		{
			empty_init();
			for (const auto& e : l)
			{
				push_back(e);
			}

		}

		list<T>& operator=(list<T> l)
		{
			swap(_head, l._head);

			return *this;
		}

		void Clear()
		{
			auto it1 = begin();
			while (it1 != end())
			{
				it1=erase(it1);
			}
		}

		~list()
		{
			Clear();
			delete _head;
			_head = nullptr;
		}

		void push_back(const T& date)
		{
			Node* newnode = new Node(date);
			Node* tail = _head->_prev;

			//newnode head tail;
			_head->_prev = newnode;
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
		}

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

		// 在pos位置前插入值为val的节点
		iterator insert(iterator pos, const T& date)
		{
			Node* newnode = new Node(date);
			Node* cur = pos._node;
			Node* prev = cur->_prev;

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

			return iterator(newnode);

		}
		// 删除pos位置的节点，返回该节点的下一个位置
		iterator erase(iterator pos)
		{
			assert(pos != end());
			
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			delete[] cur;

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

			return iterator(next);

		}
	private:
		Node* _head;
	};

三、list与vector的对比