C++初阶(list容器+模拟实现)

时间:2022-11-21 22:03:51

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

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

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

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

C++初阶(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容器是一个双向的循环链表
C++初阶(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;
}

输出结果如下:

C++初阶(list容器+模拟实现)

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;
}
C++初阶(list容器+模拟实现)

总结:插入数据不会导致迭代器失效,删除数据会导致迭代器失效。相比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的迭代器为了实现一些简单的功能,我们把它封装成了一个类。看下面源码实现:C++初阶(list容器+模拟实现)

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

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

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

C++初阶(list容器+模拟实现)
// __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);
}