开发者

C++之list的使用与模拟实现过程

开发者 https://www.devze.com 2025-10-10 10:48 出处:网络 作者: 小苏兮
目录一、list的介绍与使用迭代器分类list的迭代器失效二、list的模拟实现三、list与vector的比较总结一、list的介绍与使用
目录
  • 一、list的介绍与使用
    • 迭代器分类
    • list的迭代器失效
  • 二、list的模拟实现
    • 三、list与vector的比较
      • 总结

        一、list的介绍与使用

        我们对于list的学习和前面string与vector类似,先看官方文档:【list的文档介绍】:

        C++之list的使用与模拟实现过程

        可见,list也是一个类模板。

        list的底层其实是一个带有头结点的双向循环链表

        C++之list的使用与模拟实现过程

        在有了前面string与vector的基础,我们这里对于list的学习就直接采用文档来学习,不在一一列举了。

        C++之list的使用与模拟实现过程

        示例:

        #include<list>
        #include<vector>
        using namespace std;
        
        int main()
        {
        	list<int> l1;       //不初始化
        
        	list<int> l2(5, 10);//用5个10来初始化
        
        	list<int> l3(l2);	//拷贝构造
        
        	vector<int> v = { 1,2,3,4,5,6 };
        	list<int> l4(v.begin(), v.end());//用迭代器区间来初始化
        
        	return 0;
        }
        

        调试:

        C++之list的使用与模拟实现过程

        C++之list的使用与模拟实现过程

        C++之list的使用与模拟实现过程

        用法与前面的容器基本相同,我们就不过多阐述了,这里主要对迭代器的分类说明一下,拓展:

        迭代器分类

        在list这里,我们就要对迭代器的分类有一定了解了,

        • 按功能分类:

        C++之list的使用与模拟实现过程

        这个我们都好理解,但是,今天,我们按性质分。

        • 按性质分类:

        C++之list的使用与模拟实现过程

        C++之list的使用与模拟实现过程

        可见,list为双向迭代器,vector为随机迭代器,那有什么区别呢,为什么会有这样的分类?

        迭代器按性质分有以下:

        C++之list的使用与模拟实现过程

        几者的关系为继承。先行了解就行。

        它们之间的区别为:

        C++之list的使用与模拟实现过程

        有区别的原因就在于其底层的实现不同,还会导致它们适用的算法不同:

        C++之list的使用与模拟实现过程

        C++之list的使用与模拟实现过程

        在 C++ 标准库的容器中,没有"纯 Input 迭代器"。至少都是 Forward 迭代器,后续随着对容器的学习会了解。

        C++之list的使用与模拟实现过程

        C++之list的使用与模拟实现过程

        C++之list的使用与模拟实现过程

        与vector相同, list的迭代器失效问题我们需要注意。

        list的迭代器失效

        前面说过,我们可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。

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

        void Test1()
        {
        	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 Test()
        {
        	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);
        	}
        }
        

        C++之list的使用与模拟实现过程

        对于list的使用,我们就到此为止,因为与string与vector相似,所以我们就简单的演示就没有做。

        我们重点来进行list的模拟实现。

        二、list的模拟实现

        list的底层:

        C++之list的使用与模拟实现过程

        首先我们先来对结点进行封装:

        //节点
        template<class T>
        struct list_node
        {
        	T _data;
        	list_node* _next;
        	list_node* _prev;
        
        	list_node(T data = T())
        	{
        		_data = data;
        		_next = _prev = this;
        	}
        };
        

        这里我们要说一个点:

        C++之list的使用与模拟实现过程

        答案是:int() = 0

        解释:对于用户自定义的类,如果定义了默认构造函数,调用 MyClass() 会初始化对象。对于基本类型,int() 可以看作是这种模式的一种延伸,将其初始化为一个合理的&ldquowww.devze.com;空”状态。这样就会使得自定义类型与内置类型共用同一个模版了。

        由于list的迭代器不再是原生指针,所以我们对list的迭代器进行封装,那么对于iterator与const_iterator我们岂不是要封装两次吗,但是,我们可以这样做,设置三个模板参数(结合最下面list的主框架实现来看)

        //迭代器
        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)
        	{
        	}
        
        	Ref operator*()
        	{
        		return _node->_data;
        	}
        
        	Ptr operator->()
        	{
        		return &(_node->_data);
        	}
        	//前置
        	Self& operator++()
        	{
        		_node = _node->_next;
        		return *this;
        	}
        	Self& operator--()
        	{
        		_node = _node->_prev;
        		return *this;
        	}
        	//后置
        	Self& operator++(int)
        	{
        		_node = _node->_next;
        		return _node->prev;
        	}
        	Self& operator--(int)
        	{
        		_node = _node->_prev;
        		return _node->_next;
        	}
        	bool operator!=(const Self& it)const
        	{
        		return _node != it._node;
        	}
        	bool operator==(const Self& it)const
        	{
        		return _node == it._node;
        	}
        };
        

        list主框架

        template<class T>
        class list
        {
        	typedef list_node<T> Node;
        public:
        	typedef list_iterator<T, T&, T*> iterator;
        	typedef list_iterator<T, const T&, const T*> const_iterator;
        
        	// List的构造
        	void init_head()
        	{
        		_head = new Node;
        	}
        	list()
        	{
        		init_head();
        	}
        	list(int n, const T& value = T())
        	{
        		init_head();
        		while (n--)
        		{
        			push_back(value);
        		}
        	}
        	template <class Iterator>
        	list(Iterator first, Iterator last)
        	{
        		init_head();
        		while (first != last)
        		{
        			push_back(*first);
        			++first;
        		}
        	}
        	list(list<T>& ls)
        		python:_head(new Node)
        	{
        		for (auto i : ls)
        		{
        编程客栈			push_back(i);
        		}
        	}
        	//赋值重载
        	/*list<T>& operator=(list<T>& ls)
        	{
        		for (iterator it = begin();it!=end();)
        		{
        			it = erase(it);
        		}
        		for (auto i :编程客栈 ls)
        		{
        			push_back(i);
        		}
        		return *this;
        	}*/
        	list<T>& operator=(list<T> ls)
        	{
        		swap(ls);
        		return *this;
        	}
        	~list()
        	{
        		clear();
        		delete _head;
        		_head = nullptr;
        	}
        
        
        	// List Iterator
        	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 iterator(_head);
        		return const_iterator(_head);
        	}
        
        	// List Capacity
        	size_t size()const
        	{
        		size_t cnt = 0;
        		for (auto i : *this)
        		{
        			++cnt;
        		}
        		return cnt;
        	}
        	bool empty()const
        	{
        		return _head->_next == _head;
        	}
        	// List Access
        	T& front()
        	{
        		return _head->_next->_data;
        	}
        	const T& front()const
        	{
        		return _head->_next->_data;
        	}
        	T& back()
        	{
        		return _head->_prev->_data;
        	}
        	const T& back()const
        	{
        		returnpython _head->_prev->_data;![请添加图片描述](https://i-blog.csdnimg.cn/direct/73edd14ebffb4fb8a9a82434243b58ca.jpg)
        
        	}
        	// List Modify
        	void push_back(T data)
        	{
        		/*Node* cur = new Node(data);
        		cur->_next = _head;
        		cur->_prev = _head->_prev;
        		_head->_prev = cur;
        		cur->_prev->_next = cur;*/
        		insert(end(), data);
        	}
        	void pop_back()
        	{
        		erase(--end());
        	}
        	void push_front(const T& val)
        	{
        		insert(begin(), val);
        	}
        	void pop_front()
        	{
        		erase(begin());
        	}
        	// 在pos位置前插入值为val的节点
        	iterator insert(iterator pos, const T& val)
        	{
        		Node* newnode = new Node(val);
        		newnode->_next = pos._node;
        		newnode->_prev = pos._node->_prev;
        		newnode->_next->_prev = newnode;
        		newnode->_prev->_next = newnode;
        		return newnode;
        	}
        	// 删除pos位置的节点,返回该节点的下一个位置
        	iterator erase(iterator pos)
        	{
        		//assert(end());
        		pos._node->_prev->_next = pos._node->_next;
        		pos._node->_next->_prev = pos._node->_prev;
        		iterator it = pos._node->_next;
        
        		delete pos._node;
        		return it;
        	}
        	void clear()
        	{
        		for (iterator it = begin(); it != end();)
        		{
        			it = erase(it);
        		}
        	}
        	void swap(list<T>& ls)
        	{
        		std::swap(this->_head, ls._head);
        	}
        
        
        private:
        	Node* _head;
        };
        
        

        iterator解释:

        C++之list的使用与模拟实现过程

        在三个模版参数的作用下,就会使得iterator与const_iterator共用同一个模版的情况下实现。当然,也可以写成两个模版,效果是一样的。

        还需注意:

        • 模板只有在被使用时才会实例化。
        • 单纯的typedef声明只是创建了一个类型别名,并不会触发实例化。

        我们这里只是实现正向迭代器,反向迭代器简单说明一下:

        反向迭代器的++就是正向迭代器的–,反向迭代器的–就是正向迭代器的++,因此反向迭代器的实现可以借助正向迭代器,即:反向迭代器内部可以包含一个正向迭代器,对正向迭代器的接口进行包装即可。

        三、list与vector的比较

        vector 与 list 都是 STL 中非常重要的序列式容器,由于两个容器的底层结构不同,导致其特性以及应用场景不同,其主要不同如下:

        特性vectorlist
        底层结构动态顺序表,一段连续空间带头结点的双向循环链表
        随机访问支持随机访问,访问某个元素效率 O(1)不支持随机访问,访问某个元素效率 O(N)
        插入和删除任意位置插入和删除效率低,需要搬移元素,时间复杂度为 O(N),插入时有可能需要增容,导致效率更低任意位置插入和删除效率高,不需要搬移元素,时间复杂度为 O(1)
        空间利用率底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高底层节点动态开辟,小节点容易造成内存碎片,空间利用率低,缓存利用率低
        迭代器原生态指针对原生态指针(节点指针)进行封装
        迭代器失效插入元素时,要给所有的迭代器重新赋值,因为插入元素有可能会导致重新扩容,致使原来迭代器失效;删除操作会使指向被删除元素及之后所有元素的迭代器失效。需要重新赋值插入元素不会导致迭代器失效,删除元素时,只会导致当前迭代器失效,其他迭代器不受影响
        使用场景需要高效存储,支持随机访问,不关心插入删除效率大量插入和删除操作,不关心随机访问

        总结

        以上为个人经验,希望能给大家一个参考,也希望大家多多支持编程客栈(www.devze.com)。 

        0

        精彩评论

        暂无评论...
        验证码 换一张
        取 消

        关注公众号