C++初阶（list容器+模拟实现）

list介绍

list的本质是一个带头的双向循环链表。

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另 一个是存储下一个结点地址的指针域。

​ 相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就只配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准， 一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list永远是常数时间。

​ List和vector是两个最常被使用的容器。 List容器是一个双向链表。

• 采用动态存储分配，不会造成内存浪费和溢出
• 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
• 链表灵活，但是空间和时间额外耗费较大
• list有一个重要的性质，插入和删除操作都不会造成原有的list迭代器失效

概述

list容器

• 数据结构：双向循环链表
• 迭代器：双向迭代器
• 常用API
  • 构造
  • 数据元素的插入和删除
  • 容器大小操作
  • 赋值操作
  • 数据的存取
  • 反转和排序
• 动态存储分配（链表的插入和删除）
• 注意：list容器不能使用常用的sort，只能使用自己的sort
• list容器插入和删除很方便，但是不支持任意位置的随机访问

list常见的接口

list的构造函数

list<T> lstT;//list采用采用模板类实现,对象的默认构造形式 list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身 list(n,elem);//构造函数将n个elem拷贝给本身 list(const list &lst);//拷贝构造函数 

void test() { 	list<int> lt1;// 无参构造 	list<int> lt2(10, 5);// 用n个val构造一个list对象 	list<int> lt3(lt2);// 拷贝构造 	list<int> lt4(lt2.begin(), lt2.end());// 用一段区间的元素构造list } 

list中的迭代器

• begin + end： 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator(最后一个数据的下一个位置就是第一个数据的位置)
• rbegin + rend： 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator（第一个数据的前一个位置就是最后一个数据的位置）
• list容器是一个双向的循环链表

list的迭代器遍历

1.迭代器遍历正向遍历

void test01() { 	list<int> lt; 	//尾插 	lt.push_back(1); 	lt.push_back(2); 	lt.push_back(3); 	//头插 	lt.push_front(0); 	lt.push_front(-1); 	lt.push_front(-2); 	list<int>::iterator it = lt.begin(); 	while (it != lt.end()) 	{ 		cout << *it << " "; 		++it; 	} 	cout << endl; } 

2.范围for

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

3.迭代器反向遍历

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

输出结果如下：

list的增删改查

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身 assign(n, elem);//将n个elem拷贝赋值给本身 push_back(elem);//在容器尾部加入一个元素 pop_back();//删除容器中最后一个元素 push_front(elem);//在容器开头插入一个元素 pop_front();//从容器开头移除第一个元素 insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置 insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值 insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值 clear();//移除容器的所有数据 erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置 erase(pos);//删除pos位置的数据，返回下一个数据的位置 remove(elem);//删除容器中所有与elem值匹配的元素 swap(lst);//将lst与本身的元素互换 

list<int> mylist; mylist.push_back(19); mylist.push_back(29); mylist.push_back(39); mylist.push_back(49); mylist.push_back(59); mylist.push_front(100); mylist.push_front(200); mylist.push_front(300); mylist.push_front(400);  vector<int> v; v.push_back(1000); v.push_back(2000); v.push_back(3000);  mylist.insert(mylist.begin(), v.begin(), v.end()); printList(mylist); 	 mylist.remove(300); //删除大于300的数据 mylist.remove_if(myfunc); 

list的大小和头尾元素的读取

size();//返回容器中元素的个数 empty();//判断容器是否为空 resize(num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除 resize(num, elem);//重新指定容器的长度为num，若容器变长，则以值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除 

list迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

第一种情况：插入

list<int> mylist; mylist.push_back(19); mylist.push_back(29); mylist.push_back(39); mylist.push_back(49); mylist.push_back(59); list<int>::iterator it = mylist.begin(); mylist.insert(it,3); 

运行结果没有问题，不会报错

第二种情况：删除

list<int> mylist; mylist.push_back(19); mylist.push_back(29); mylist.push_back(39); mylist.push_back(49); mylist.push_back(59); list<int>::iterator it = mylist.begin(); while( it! = mylist.end()) { 	mylist.erase(it); 	++it; } 

总结：插入数据不会导致迭代器失效，删除数据会导致迭代器失效。相比vector容器，vector容器插入数据是会导致迭代器失效，因为vector涉及增容问题，而list却不存在增容问题，所以迭代器指向的位置是有效的。删除数据会导致迭代器指向的位置是无效的，所以迭代器会失效。

解决方法：和vector一样，对迭代器进行赋值

list<int> mylist; mylist.push_back(19); mylist.push_back(29); mylist.push_back(39); mylist.push_back(49); mylist.push_back(59); list<int>::iterator it = mylist.begin(); while( it! = mylist.end()) { 	it = mylist.erase(it);//erase()返回值是指向被删元素的下一元素的指针(也就是迭代器) } 

list模拟实现

list整体框架

list是由节点组成，所以定义一个节点的类，然后list的类中成员只需要一个头结点的指针即可。

template<class T> struct __list_node { 	__list_node<T>* _prev; 	__list_node<T>* _next; 	T _data; 	__list_node(const T& x = T()) 		:_next(nullptr) 		, _prev(nullptr) 		, _data(x) 	{} }; template<class T> class list { 	typedef __list_node<T> Node; public: private: 	Node* _head; }; 

list的构造函数

构造函数要做的任务就是开一个头结点，所以我们可以封装出一个具体的函数来实现创建头结点的这个过程

创建头结点：

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

构造函数的实现：

list() { 	CreatHead(); } 

list迭代器的实现

list相比vector的迭代器而言，不再是一个简单的指针，它相对而言更复杂一些，list的迭代器为了实现一些简单的功能，我们把它封装成了一个类。看下面源码实现：

我们自己来模拟实现一下简单的。
迭代器的小框架（里面有一个成员变量——节点指针）

struct __list_iterator { 	typedef __list_node<T> Node; 	__list_iterator(Node* node = nullptr) 		:_node(node) 	{} 	Node* _node; } 

由于迭代器分普通迭代器和const 迭代器，为了不造成代码冗余，我们设计出来三个模板参数，根据传入的模板参数确定是那种迭代器。

// __list_iterator<T, T&, T*>  ->  普通迭代器 // __list_iterator<T, const T&, const T*>  ->  const迭代器 template<class T, class Ref, class Ptr> struct __list_iterator { 	typedef __list_node<T> Node; 	typedef __list_iterator<T, Ref, Ptr> Self; 	Node* _node; 	__list_iterator(Node* node = nullptr) 		:_node(node) 	{} 	__list_iterator(const Self& l) 		:_node(l._node) 	{} 	// *it  T& 	Ref operator*() 	{ 		return _node->_data; 	} 	// it->  T* 	Ptr operator->() 	{ 		return &_node->_data; 	} 	Self& operator++() 	{ 		_node = _node->_next; 		return *this; 	} 	Self& operator--() 	{ 		_node = _node->_prev; 		return *this; 	} 	Self operator++(int) 	{ 		Self tmp(*this); 		//_node = _node->_next; 		++(*this);  		return tmp; 	} 	Self operator--(int) 	{ 		Self tmp(*this); 		//_node = _node->_prev; 		--(*this);  		return tmp; 	} 	Self operator+(int count) 	{ 		Self tmp(*this); 		while (count--) 		{ 			++tmp; 		}  		return tmp; 	} 	Self operator-(int count) 	{ 		Self tmp(*this); 		while (count--) 		{ 			--tmp; 		}  		return tmp; 	} 	bool operator!=(const Self& it) 	{ 		return _node != it._node; 	} }; 

我们还要在list里面做这样一个操作（堆两种迭代器进行重命名，方便我们认识）：

typedef list_iterator<T, T&, T*> iterator;// 普通迭代器 typedef list_iterator<T, const T&, const T*> const_iterator;// const迭代器 

list内部begin()和end()的实现（普通迭代器调用前两个，const迭代器调用后两个）

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

list的增删查改的实现

void push_back(const T& x) { 	Node* newnode = new Node(x); 	Node* tail = _head->_prev;  	tail->_next = newnode; 	newnode->_prev = tail; 	newnode->_next = _head; 	_head->_prev = newnode; }   void pop_back() { 	assert(head != head->_next); 	Node* tail = head->_prev; 	Node* prevTail = tail->_prev; 	delete tail; 	tail = prevTail;  	tail->_next = head; 	head->_prev = tail; }  void push_front(const T& x) { 	Node* newnode = new Node(x); 	Node* firstNode = head->_next;  	head->_next = newnode; 	newnode->_prev = head; 	newnode->_next = firstNode; 	firstNode->_prev = newnode; }  void pop_front() { 	assert(head->_next != head); 	Node* firstNode = head->_next; 	Node* secondNode = firstNode->_next;  	delete firstNode; 	firstNode = nullptr;  	head->_next = secondNode; 	secondNode->_prev = head; }  void insert(iterator pos, const T& x) { 	Node* cur = pos._node; 	Node* prev = cur->_prev;  	Node* newnode = new Node(x);  	prev->_next = newnode; 	newnode->_prev = prev; 	newnode->_next = cur; 	cur->_prev = newnode; }  iterator erase(iterator pos) { 	assert(head->_next != head); 	assert(pos != end());  	Node* node = pos._node; 	Node* prev = node->_prev; 	Node* next = node->_next;  	delete node; 	node = nullptr;  	prev->_next = next; 	next->_prev = prev;  	return iterator(next); }  T front() { 	assert(head->_next != head); 	return head->_next->data; }  T back() { 	assert(head->_next != head); 	return head->_prev->data; }  

list中的析构函数和clear

1.clear 通过迭代器遍历，一个一个的删除节点

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

2.析构函数 可以先调用clear函数清理空间，然后再delete掉头结点

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

拷贝构造和operator=赋值重载

1.拷贝构造

list(const list<T>& lt) { 	CreatHead(); 	/*const_iterator it = lt.begin(); 	while (it != lt.end()) 	{ 		push_back(*it); 		++it; 	}*/ 	for (auto e : lt) 		push_back(e); } 

2.operator= 直接利用swap和形参交换，形参会自己调用析构函数清理空间

list<T>& operator=(list<T> lt) { 	if (this != &lt)// 防止自己给自己赋值 	{ 		swap(lt); 	}  	return *this; } 

swap函数实现如下：

void swap(list<T>& lt) { 	::swap(head, lt.head); }