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

list介绍

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

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

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

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

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

概述

list容器

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

list常见的接口

list的构造函数

list 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 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::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 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 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 mylist;
mylist.push_back(19);
mylist.push_back(29);
mylist.push_back(39);
mylist.push_back(49);
mylist.push_back(59);
list::iterator it = mylist.begin();
mylist.insert(it,3);

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

第二种情况：删除

list mylist;
mylist.push_back(19);
mylist.push_back(29);
mylist.push_back(39);
mylist.push_back(49);
mylist.push_back(59);
list::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* _prev;
	__list_node* _next;
	T _data;
	__list_node(const T& x = T())
		:_next(nullptr)
		, _prev(nullptr)
		, _data(x)
	{}
};
template<class T>
class list
{
	typedef __list_node 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 Node;
	__list_iterator(Node* node = nullptr)
		:_node(node)
	{}
	Node* _node;
}

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

// __list_iterator  ->  普通迭代器
// __list_iterator  ->  const迭代器
template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef __list_node Node;
	typedef __list_iterator 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 iterator;// 普通迭代器
typedef list_iteratorconst 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& 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& operator=(list lt)
{
	if (this != <)// 防止自己给自己赋值
	{
		swap(lt);
	}

	return *this;
}

swap函数实现如下：

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