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);

}

标签： #list #元素 #容器