1. Toy模板网首页
  2. > Toy博客

【C++心愿便利店】No.14---C++之探索list底层原理

9月前 作者：小沈YO. 分类：Toy博客 阅读(54) 违法举报

这篇具有很好参考价值的文章主要介绍了【C++心愿便利店】No.14---C++之探索list底层原理。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

【C++心愿便利店】No.14---C++之探索list底层原理,《C++ 心愿便利店》,c++,list,开发语言

👧个人主页：@小沈YO.
😚小编介绍：欢迎来到我的乱七八糟小星球🌝
📋专栏：C++ 心愿便利店
🔑本章内容：list
记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~

提示：以下是本篇文章正文内容，下面案例可供参考

一、list的介绍及使用

list的文档介绍

1.1 list的介绍

  • list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
  • list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
  • list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
  • 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
  • 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

1.2 list的使用

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展
的能力。以下为list中一些常见的重要接口

1.2.1 list的构造

构造函数（ (constructor)） 接口说明
list() 构造空的list
list (size_type n, const value_type& val = value_type()) 构造的list中包含n个值为val的元素
list (InputIterator first, InputIterator last) 用[first, last)区间中的元素构造list
list (const list& x) 拷贝构造函数 
void test_list1()
{
	list<int> l1;//构造空的list
	list<int>l2(6, 6);//构造的list中包含n个值为val的元素
	list<int>l3(l2.begin(), l2.end());//用[first, last)区间中的元素构造list
	list<int>l4(l3);//拷贝构造函数
	list<int>::iterator it = l2.begin();
	while (it != l2.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	for (auto e : l3)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : l4)
	{
		cout << e << " ";
	}
	cout << endl;
}

1.2.2 list iterator的使用

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

函数声明 接口说明
begin + end 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置 
void test_list2()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	// 使用正向迭代器遍历打印lt中的元素
	// list<int>::iterator it = l.begin();   //两种写法都对
	auto it = lt.begin();                    
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	// 使用反向迭代器遍历打印lt中的元素
	// list<int>::reverse_iterator rit = l.rbegin();
	auto rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
}

【注意】

  1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
  2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
  3. 遍历链表只能使用迭代器和范围 for。

1.2.3 list capacity

函数声明 接口说明
empty 检测list是否为空，是返回true，否则返回false
size 返回list中有效节点的个数

1.2.4 list element access

函数声明 接口说明
front 返回list的第一个节点中值的引用
back 返回list的最后一个节点中值的引用

1.2.5 list modifiers

函数声明 接口说明
push_front 在list首元素前插入值为val的元素
pop_front 删除list中第一个元素
push_back 在list尾部插入值为val的元素
pop_back 删除list中最后一个元素
insert 在list position 位置中插入值为val的元素
erase 删除list position位置的元素
swap 交换两个list中的元素
clear 清空list中的有效元素

1.2.6 list operations

函数声明 接口说明
splice 实现list拼接的功能，将源list的内容部分或全部元素删除，拼插入到目的list。
remove 删除特定值节点
unique 对链表中的元素去重，要求必须有序
merge 对两个有序的链表进行归并，得到一个有序的链表
sort 对链表中的元素进行排序
reverse 逆置

注意：链表排序只能使用 list 自身的 sort() 接口（其底层是利用归并排序原理），不能使用算法库的 sort，因为算法库中的 sort 底层是通过快排来实现的，快排涉及到三数取中，需要迭代器 - 迭代器，链表不能很好的支持。

void test_list3()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	lt.reverse();链表逆置可以使用 list 自身的接口，也可以使用算法库中的 reverse
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//sort(lt.begin(), lt.end());
	lt.sort();//默认升序< less
	//降序> greater
	
	//greater<int> gt;lt.sort(gt);
	lt.sort(greater<int>());
	//上面的两种写法都可以
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}
————————————————————————————————————————————————————————————————————————————————
unique  ---	去重（一定要记得有序）
void test_list4()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(3);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(2);
	lt.push_back(5);
	lt.push_back(5);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	lt.unique();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

【C++心愿便利店】No.14---C++之探索list底层原理,《C++ 心愿便利店》,c++,list,开发语言

虽然链表提供了排序接口，但是用链表对数据排序意义不大（当数据比较大时），效率太低了，更希望用 vector 来对数据进行排序 — 如下（具体可以通过对两者进行效率比对），但是数据较小时sort还是很有用的

//将li中的数据拷贝到vector
vector<int> v(lt.begin(),lt.end());
for (auto e : v)
{
	cout << e << " ";
}
cout << endl;
//排序
sort(v.begin(), v.end());
for (auto e : v)
{
	cout << e << " ";
}
cout << endl;
//拷贝回lt
lt.assign(v.begin(), v.end());
for (auto e : lt)
{
	cout << e << " ";
}
cout << endl;

——————————————————————————————————————————————————————————————————————————————————————————
//对两者进行效率比对
void TestSort()
{
    srand(time(0));
    const int N = 5000000;
    vector<int> v;
    list<int> lt;

    v.reserve(N);//提前开好空间

    for (int i = 0; i < N; i++)
    {
        auto e = rand();
        v.push_back(e);
        lt.push_back(e);
    }

    比较vector 和 list 的排序
    
    int begin1 = clock();
    sort(v.begin(), v.end());
    int end1 = clock();

    int begin2 = clock();
    lt.sort();
    int end2 = clock();

    printf("vector sort:%d\n", end1 - begin1);
    printf("list sort:%d\n", end2 - begin2);
}

迭代器的这种分类方式，是由容器的底层结构来决定的

迭代器类型（性质上分类） 功能 及 示例
单向（InputIterator） 支持 ++ （单链表、哈希表）
双向（BidirectionalItreator） 支持 ++/- - （双向链表、红黑树（map和set））
随机（RandomAccessIterator） 支持 ++ / - - / + / - （vector、string、deque）

可以看到算法库里面的sort：迭代器类型是随机（RandomAccessIterator）类型的所以不可以用算法库中的sort，以list中的reverse为例：迭代器是双向（BidirectionalItreator）类型的。
【C++心愿便利店】No.14---C++之探索list底层原理,《C++ 心愿便利店》,c++,list,开发语言

1.2.7 list的迭代器失效

list中insert 插入元素并不会导致迭代器失效， vector 中的 insert插入元素导致迭代器失效是因为，vector 中的 insert 会去扩容挪动数据，而 list 中的 insert 不会进行扩容挪动数据
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响

void TestListIterator1()
{
 	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 	list<int> l(array, array+sizeof(array)/sizeof(array[0]));
 	auto it = l.begin();
 	while (it != l.end())
 	{
 	
 		//erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
 	
 		l.erase(it); 
		 ++it;
	 }
}
——————————————————————————————————————————————————————————————————————————————
// 改正
void TestListIterator()
{
 	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 	list<int> l(array, array+sizeof(array)/sizeof(array[0]));
 	auto it = l.begin();
 	while (it != l.end())
 	{
	 	l.erase(it++); // it = l.erase(it);
 	}
}

二、list的模拟实现

2.1 定义一个结构体实现list的节点

template<class T>
struct list_node//struct默认是公有的不受访问限定符限制
{
	T _data;
	list_node<T>*_next;
	list_node<T>*_prev;

	list_node(const T& x=T())//拷贝构造
		:_data(x)
		,_next(nullptr)
		,_prev(nullptr)
	{}
};

2.2 list的成员变量

template<class T>
class list
{
	typedef list_node<T> Node;
public:
		
private:
	Node* _head;
};

2.3 list迭代器的封装实现

list 的迭代器不再使用原生指针因为：

  • 首先如果list 的迭代器使用原生指针，那对迭代器解引用得到的是一个节点，但是我们是希望对迭代器解引用可以得到节点里面存储的元素数据
  • 其次 list 在底层的物理空间并不连续，如果使用原生指针作为 list 的迭代器，那对迭代器执行 ++ 操作，并不会让迭代器指向下一个节点。
    所以需要对 list 的迭代器进行封装并对一些运算符进行重载以实现迭代器的效果。

2.3.1 普通迭代器

//迭代器的封装和运算符重载
template<class T>
struct __list_iterator
{
	typedef list_node<T>Node;
	typedef __list_iterator<T> self;
	Node* _node;
	
	__list_iterator(Node* node)//构造
		:_node(node)
	{}

	self& operator++()//前置++
	{
		_node = _node->_next;
		return *this;
	}

	self operator++(int)//后置++
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

	self& operator--()//前置--
	{
		_node = _node->_prev;
		return *this;
	}

	self& operator--(int)//后置--
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

	T& operator*()//因为要修改数据所以返回数据的&
	{
		return _node->_data;
	}

	bool operator==(const self& s)
	{
		return _node == s._node;
	}

	bool operator!=(const self& s)
	{
		return _node !=s._node ;
	}
};

迭代器不需要实现析构函数、拷贝构造函数、赋值运算符重载函数，直接使用默认生成的就可以（所以浅拷贝就足够了不需要深拷贝）

2.3.2 const迭代器

上述实现了普通迭代器，那 const 迭代器该怎样实现呢？
所谓const 迭代器本质：是限制迭代器指向的内容不能修改，而 const 迭代器自身可以修改，它可以指向其他节点。
const iterator这种写法，const 限制的就是迭代器本身，会让迭代器无法实现 ++ 等操作(所以const迭代器不是对普通迭代器＋const修饰)。

为了实现const迭代器有两种方式：

  • 单独写一个 _list_const_iterator 的类
template<class T>
struct __list_const_iterator
{
	typedef list_node<T>Node;
	typedef __list_const_iterator<T> self;
	Node* _node;
	
	__list_const_iterator(Node* node)
		:_node(node)
	{}

	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	self& operator--(int)
	{			
		self tmp(*this);			
		_node = _node->_prev;
		return tmp;
	}

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

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

	bool operator==(const self& s)
	{
		return _node == s._node;
	}

	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
};
  • 在普通迭代器的基础上，再传递一个模板参数，让编译器来生成
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)
		:_node(node)
	{}
	
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}

	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	self& operator--(int)
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}

	Ref operator*()
	{
		return _node->_data;
	}

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

	bool operator==(const self& s) 
	{
		return _node == s._node;
	}

	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
};

2.4 list成员函数

2.4.1 构造函数

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

void empty_init()
{
	_head = new Node;//这里需要传个值所以在拷贝构造的地方给个匿名对象
	_head->_next = _head;
	_head->_prev = _head;
}
list()
{
	empty_init();
}

2.4.2 拷贝构造函数

list(const list<T>& lt)//--->lt是一个const类型的
{
	empty_init();
	for (auto e : lt)
	{
		push_back(e);
	}
}

2.4.3 赋值运算符重载

//两种写法：
list<int>& operator=(const list<int>& lt)
{
	if(this!=&lt)
	{
		clear();//释放lt3;--->不清哨兵位的头结点可以继续插入
		for (auto e : lt)//遍历lt1
		{
			push_back(e);//把lt1中的数据插入到lt3
		}
	}
	return *this;
}
____________________________________________________________________________________
void swap(list<T>& lt)
{
	std::swap(_head,lt._head);//交换头指针
	std::swap(_size, lt._size);
}
list<int>& operator=(list<int>& lt)
{
	swap(lt);
	return *this;
}

2.4.4 迭代器相关

//普通迭代器：
iterator begin()
{
	return _head->_next;
}
iterator end()
{
	return _head;
}
//const迭代器：
const_iterator begin()const
{
	return _head->_next;
}
const_iterator end()const 
{
	return _head;
}

2.4.5 insert

iterator insert(iterator pos, const T& val)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
			 
	Node* newnode = new Node(val);
	prev->_next = newnode;
	newnode->_prev = prev;

	newnode->_next = cur;
	cur->_prev = newnode;

	_size++;
	return iterator(newnode);
}

2.4.6 erase

iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	delete cur;
	cur = nullptr;

	prev->_next = next;
	next->_prev = prev;

	_size--;
	return iterator(next);//返回pos的下一个位置
}

2.4.7 push_back()

void push_back(const T& x)
{
//找尾
	Node* tail = _head->_prev;
//插入节点	
	Node* newnode = new Node(x);
	tail->_next = newnode;
	newnode->_prev = tail;
	
	newnode->_next = _head;
	_head->_prev = newnode;
}
————————————————————————————————————————————————————————————————————————————————
//直接复用insert
void push_back(const T& x)
{
	insert(end(),x);
}

2.4.8 push_front()

void push_front(const T& x)
{
	insert(begin(), x);
}

2.4.9 pop_back()

void pop_back(const T& x)
{
	erase(--end());
}

2.4.10 pop_front()

void pop_front(const T& x)
{
	erase(begin());
}

2.4.11 size()

size_t size()
{
	return _size;
}

2.4.12 clear()

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);//返回下一个位置的迭代器
	}
}

2.4.13 析构函数

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

三、list与vector的对比

【C++心愿便利店】No.14---C++之探索list底层原理,《C++ 心愿便利店》,c++,list,开发语言文章来源地址https://www.toymoban.com/news/detail-755444.html

到了这里，关于【C++心愿便利店】No.14---C++之探索list底层原理的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【C++心愿便利店】No.9---C++之内存管理

    【C++心愿便利店】No.9---C++之内存管理

    👧个人主页：@小沈YO. 😚小编介绍：欢迎来到我的乱七八糟小星球🌝 📋专栏：C++ 心愿便利店 🔑本章内容：内存管理 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示：以下是本篇文章正文内容，下面案例可供参考 【说明】 栈 又叫堆栈–非静态局部变量/函数参数/返回值

    2024年02月08日
    浏览(44)
  • 【C++心愿便利店】No.11---C++之string语法指南

    【C++心愿便利店】No.11---C++之string语法指南

    👧个人主页：@小沈YO. 😚小编介绍：欢迎来到我的乱七八糟小星球🌝 📋专栏：C++ 心愿便利店 🔑本章内容：string 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示：以下是本篇文章正文内容，下面案例可供参考 C语言中，字符串是以’\\0’结尾的一些字符的集合，为了操作方

    2024年02月05日
    浏览(48)
  • 【C++心愿便利店】No.4---C++初谈类和对象

    【C++心愿便利店】No.4---C++初谈类和对象

    👧个人主页：@小沈YO. 😚小编介绍：欢迎来到我的乱七八糟小星球🌝 📋专栏：C++ 心愿便利店 🔑本章内容：类和对象 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示：以下是本篇文章正文内容，下面案例可供参考 C语言是面向过程的，关注的是过程，分析出求解问题的步

    2024年02月10日
    浏览(36)
  • 【C++心愿便利店】No.7---C++之运算符重载

    【C++心愿便利店】No.7---C++之运算符重载

    👧个人主页：@小沈YO. 😚小编介绍：欢迎来到我的乱七八糟小星球🌝 📋专栏：C++ 心愿便利店 🔑本章内容：运算符重载 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示：以下是本篇文章正文内容，下面案例可供参考 通常比较两个操作数的大小，会写成下述方式： 但是对

    2024年02月08日
    浏览(43)
  • 【C++心愿便利店】No.5---构造函数和析构函数

    【C++心愿便利店】No.5---构造函数和析构函数

    👧个人主页：@小沈YO. 😚小编介绍：欢迎来到我的乱七八糟小星球🌝 📋专栏：C++ 心愿便利店 🔑本章内容：类和对象 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示：以下是本篇文章正文内容，下面案例可供参考 如果一个类中什么成员都没有，简称为空类。 空类中真的

    2024年02月09日
    浏览(50)
  • 【C++心愿便利店】No.1---C++入门（命名空间、缺省参数）

    【C++心愿便利店】No.1---C++入门（命名空间、缺省参数）

    👧个人主页：@小沈YO. 😚小编介绍：欢迎来到我的乱七八糟小星球🌝 📋专栏：C++ 心愿便利店 🔑本章内容：命名空间、缺省参数 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ C语言最初由 Dennis Ritchie 于 1969 年到 1973 年在 ATT 贝尔实验室里开发出来，主要用于重新实现 Unix 操作

    2024年02月11日
    浏览(37)
  • 【C++心愿便利店】No.8---C++之重识类和对象

    【C++心愿便利店】No.8---C++之重识类和对象

    👧个人主页：@小沈YO. 😚小编介绍：欢迎来到我的乱七八糟小星球🌝 📋专栏：C++ 心愿便利店 🔑本章内容：再谈构造函数、Static成员、友元、内部类、匿名对象、再次理解封装 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 在创建对象时，编译器通过调用构造函数，给对象中

    2024年02月08日
    浏览(40)
  • 【C++心愿便利店】No.3---内联函数、auto、范围for、nullptr

    【C++心愿便利店】No.3---内联函数、auto、范围for、nullptr

    👧个人主页：@小沈YO. 😚小编介绍：欢迎来到我的乱七八糟小星球🌝 📋专栏：C++ 心愿便利店 🔑本章内容：内联函数、auto、范围for、nullptr 记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~ 提示：以下是本篇文章正文内容，下面案例可供参考 通过对C语言的学习，对于宏有了一定

    2024年02月11日
    浏览(42)
  • 社区便利店选址五要素，真实案例分析便利店选址步骤分享！

    社区便利店选址五要素，真实案例分析便利店选址步骤分享！

    顺为城市地图：www.data-dance.com  近年来，各地政府陆续出台了具体的政策指标，以推动城乡社区便利店的建设，随着中国城镇化率和城市人口密度逐年提升，也将带动便利店经济的发展。 数据显示，2021年中国便利店行业市场规模，达 2988亿元 ，门店数量达 15.7万家 。 中国不

    2024年02月05日
    浏览(45)
  • 基于SSM的便利店系统

    基于SSM的便利店系统

    ✌全网粉丝20W+,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅 文末获取项目下载方式 🍅 一、项目背景介绍： 基于SSH的便利店系统是为了满足顾客、店长和管理者

    2024年02月08日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包