目录

一.List定义

二.List的使用

（1）push_back后的遍历

​编辑

（2）erase，insert那些跟vector一样用法，没什么好说的

（3）sort（List支持排序，但效率低）

【1】简介 List::sort

【2】库里面的sort不支持List的原因(三类迭代器)：

【3】std::sort 与 List::sort 比较，List::sort就是 "飞屋"

三.List模拟实现

重点：

（1）return iterator(_head->_next); 是返回了匿名对象

（2）begin()迭代器能否直接返回  _head->_next ？——可以

（3）it->_a1 解释

（4）为什么list要封装新的iterator，而不能用原生指针？vector却可以

（5）const迭代器

（6）erase迭代器失效

1.第一阶段

List.h

Test.cpp

2.第二阶段 const迭代器

List.h

3.第三阶段

易错点：

四.list 相关题目

一.List定义

Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.

List是一个顺序容器，这个顺序容器允许O(1)的时间复杂度任意插入和删除，还支持双向迭代器。（List底层是双向带头链表）

二.List的使用

（1）push_back后的遍历

List底层是链表，链表空间不连续，就舍弃的[]+下标的遍历方法，通常使用迭代器遍历。

void test_list1()
	{
		list lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		list::iterator it = lt.begin();
		while (it != lt.end())        //迭代器遍历
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
    
		for (auto e : lt)            //范围for遍历
		{
			cout << e << " ";
		}
		cout << endl;

		//list::reverse_iterator rit = lt.rbegin();
		auto rit = lt.rbegin();
		while (rit != lt.rend())
		{
			cout << *rit << " ";
			++rit;
		}
		cout << endl;

	}

（2）erase，insert那些跟vector一样用法，没什么好说的

（3）sort（List支持排序，但效率低）

【1】简介 List::sort

库里面的sort不支持List，所以List要有自己的sort（原因在下面），因为结构问题，List::sort效率很低，vector用 std::sort 排序会很快，不建议用List::sort。

void test_list3()
	{
		list lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_front(10);
		lt.push_front(20);
		lt.push_front(30);
		lt.push_front(40);

		lt.push_back(1);
		lt.push_back(1);
		lt.push_back(1);

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

		lt.sort();
		lt.unique();

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

【2】库里面的sort不支持List的原因(三类迭代器)：

实现结构的角度，迭代器再实际中分为三类:
1、单向。
2、双向。
3、随机。

随机迭代器属于单向迭代器也属于双向迭代器，即：单向迭代器包含随机迭代器，双向迭代器也包含随机迭代器。

库里面的sort是随机迭代器

List是双向迭代器

双向包含随机，但随机不包含双向，所以std::sort的使用不能包含双向

【3】std::sort 与 List::sort 比较，List::sort就是 "飞屋"

std::sort 底层是快排（要包含头文件）

List::sort 底层是归并排序

 

总结：短数据情况下（1w个数据以内）List::sort是有价值可以用，大数据就要用vector排序了，连续空间的优势 

三.List模拟实现

重点：

（1）return iterator(_head->_next); 是返回了匿名对象

iterator()是匿名对象，匿名对象只存在于构造该对象的那行代码，离开构造匿名对象的那行代码后立即调用析构函数。

①return iterator(_head->_next); 这一句等价于：②先构造一个iterator类的 it对象，因为不是引用返回，所以需要返回it的临时拷贝，临时拷贝又是it拷贝构造得到的。

②iterator it( head-> next);     
    return it;

对比：②经历了构造对象it，然后拷贝构造一个临时变量；①利用匿名对象优化：把构造匿名对象+拷贝构造临时变量 优化成了 直接构造一个对象并返回。

        iterator begin()
		{
			return iterator(_head->_next);    //iterator()是匿名对象，详情看（1）
			//return _head->_next;
		}

		iterator end()
		{
			return iterator(_head);      //iterator()是匿名对象，详情看（1）
		}

（2）begin()迭代器能否直接返回  _head->_next ？——可以

单参数的构造函数支持隐式类型转换：返回值是iterator，原本是先构造iterator类的对象，再拷贝构造出一个临时变量，通过编译器优化就成了直接构造一个对象并返回。

        iterator begin()
		{
			return iterator(_head->_next);    //iterator()是匿名对象，详情看（1）
			//return _head->_next; //能否直接返回  _head->_next ？——可以,详情看（2）
		}

（3）it->_a1 解释

cout << (*it)._a1 << "-"<< (*it)._a2 <<" "; 访问AA中的数据是正常操作，也可以指针指向的写法访问 it->_a1 。因为 *it 返回的是 _node->_data ，所以 it-> 返回的是 &_node->_data，按理来说指针指向方式 访问AA数据元素写法应该是 it->->_a1 编译器为了可读性进行优化处理，优化以后，省略了一个->，成为it->_a1。

struct __list_iterator中：
        T& operator*()
		{
			return _node->_data;
		}

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

	void test_list2()
	{
		list lt;
		lt.push_back(AA(1, 1));
		lt.push_back(AA(2, 2));
		lt.push_back(AA(3, 3));
		lt.push_back(AA(4, 4));

		// 迭代器模拟的是指针行为
		// int* it  *it
		// AA*  it  *it  it->
		list::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << (*it)._a1 << "-"<< (*it)._a2 <<" ";
			cout << it->_a1 << "-" << it->_a2 << " ";    //it->_a1解释，详情见(3)
			++it;
		}
		cout << endl;
	}

（4）为什么list要封装新的iterator，而不能用原生指针？vector却可以

template
	struct __list_iterator  //详情见（3），list为什么不能用原生指针？因为物理空间不连续
	{……}

 vector相当于家里有矿的孩子，不用努力，家里给（系统支持原生指针做迭代器的++--等）。

list 相当于普通家庭，需要自己努力（自己写自定义类型支持迭代器__list_iterator，还要重载运算符）

两者外表（调用）看起来一模一样，实际底层完全不同

（5）const迭代器

为了支持像printf这样形参传的是const对象，正常思路是再复制一遍__list_iterator类，然后全部改成const做成__list_const_iterator类，但是这样复用性不好，不便于维护，所以我们采用模板控制const类型参数：反正是对 operator* 和 -> 返回值的改变，不如直接添加两个模板参数T&和T*，分成const和非const两种模板 。lt对象带const时，就用const_iterator模板；对象是非const时就用iterator模板，就用。调用 lt.begin()时，begin()返回的临时对象类型是const_iterator，则__list_iterator 传入的3个模板类型是const_iterator，

也就是__list_iterator

	template
	struct __list_iterator
	{
		// *it
		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{ 
			//return &(operator*());
			return &_node->_data;
		}	
        ……

    template
	class list
	{
		typedef list_node Node;
	public:
		typedef __list_iterator iterator;
		typedef __list_iterator const_iterator;

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

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

	void print_list(const list& lt)
	{
		list::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			/

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

		template 
		list(InputIterator first, InputIterator last)
		{
			empty_init();

			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		// 17:00 继续
		void swap(list& lt)
		{
			std::swap(_head, lt._head);
		}

		// lt2(lt1) -- 现代写法
		list(const list& lt)
		{
			empty_init();
			list tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		// lt2 = lt1
		list& operator=(list lt)
		{
			swap(lt);
			return *this;
		}

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

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

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

			 _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_back()
		{
			erase(--end());
		}

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

		// 插入在pos位置之前
		iterator insert(iterator pos, const T& x)
		{
			Node* newNode = new Node(x);
			Node* cur = pos._node;
			Node* prev = cur->_prev;

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

			return iterator(newNode);
		}

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

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			// prev  next
			prev->_next = next;
			next->_prev = prev;
			delete cur;

			return iterator(next);
		}

	private:
		Node* _head;
	};

	void print_list(const list& lt)
	{
		list::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			/

		// 17:00 继续
		void swap(list& lt)    //不能加const，要不然修改不了了
		{
			std::swap(_head, lt._head);
		}

		// lt2(lt1) -- 拷贝构造现代写法
//链表的拷贝构造要深拷贝，如果浅拷贝就会导致两个链表的头结点_head指向同一个链表
		list(const list& lt)
		{
			empty_init();
			list tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		// lt2 = lt1
		list& operator=(list lt)
		{
			swap(lt);
			return *this;
		}

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

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

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

			 _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_back()
		{
			erase(--end());
		}

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

		// 插入在pos位置之前
		iterator insert(iterator pos, const T& x)
		{
			Node* newNode = new Node(x);
			Node* cur = pos._node;
			Node* prev = cur->_prev;

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

			return iterator(newNode);
		}

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

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			// prev  next
			prev->_next = next;
			next->_prev = prev;
			delete cur;

			return iterator(next);
		}

	private:
		Node* _head;
	};

	void print_list(const list& lt)
	{
		list::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			/

		auto it1 = lt.begin();
		while (it1 != lt.end())
		{
			if (*it1 % 2 == 0)
			{
				it1 = lt.erase(it1);
			}
			else
			{
				++it1;
			}
		}

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

		lt.clear();

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

		lt.push_back(10);
		lt.push_back(20);
		lt.push_back(30);

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

	void test_list6()
	{
		list lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		lt.push_back(6);

		list lt1(lt);

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

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

		list lt2;
		lt2.push_back(10);
		lt2.push_back(20);
		lt1 = lt2;
		for (auto e : lt2)
		{
			cout << e << " ";
		}
		cout << endl;

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

四.list 相关题目

for (int i=1; i<10; ++i) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9

std::reverse(myvector.begin(),myvector.end());    // 9 8 7 6 5 4 3 2 1

可知std::reserve 是将包括begin迭代器开始到end前一个位置进行逆置