c++领域展开第十八幕——STL（list容器的了解和使用以及手撕模拟）超详细！！！！

06-01 996阅读

文章目录

前言
一、list的介绍和使用

1.1 list的介绍
1.2 list的使用

1.2.1 list的构造
1.2.2 list iterator的使用
1.2.3 list capacity
1.2.4 list element access
1.2.5 list modifiers
1.2.6 list的迭代器失效
二、list的模拟实现
list与vector的对比
总结

总结

前言

本专栏上一篇博客把vector的有关实现和细节问题都讲解完毕

今天我们来学习 stl 库的另外一个容器——list

从认识到使用到手撕实现，我来手把手教你

fellow me

一、list的介绍和使用

1.1 list的介绍

list文档

文档链接在上面啦，大家可以翻译看看

双向循环链表图，list就相当于我们数据结构学习的双向循环链表

只不过在stl库里面给它进行了封装

1.2 list的使用

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

1.2.1 list的构造

构造函数（(constructor))

list (size_type n, const value_type& val = value_type())——————构造的list中包含n个值为val的元素

list() ————————————构造空的list

list (const list& x) ——————拷贝构造函数

list (InputIterator first, InputIterator last)————用[first, last)区间中的元素构造list

代码展示

	list l1;                         // 构造空的l1
    list l2(4, 100);                 // l2中放4个值为100的元素
    list l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左闭右开的区间构造l3
    list l4(l3);                    // 用l3拷贝构造l4
    // 以数组为迭代器区间构造l5
    int array[] = { 16,2,77,29 };
    list l5(array, array + sizeof(array) / sizeof(int));
    // 列表格式初始化C++11
    list l6{ 1,2,3,4,5 };

1.2.2 list iterator的使用

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

函数声明——————接口说明

begin + end————返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器

rbegin + rend————返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

【注意】

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

代码展示

	// 注意这里调用的是list的 begin() const，返回list的const_iterator对象
    for (list::const_iterator it = l.begin(); it != l.end(); ++it)
    {
        cout  1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list
        cout 
        cout  1, 2, 3 };
    list 1, 2, 3 };
    list 7, 8, 9 };
    L.insert(pos, v.begin(), v.end());
    PrintList(L);
    // 删除pos位置上的元素
    L.erase(pos);
    PrintList(L);
    // 删除list中[begin, end)区间中的元素，即删除list中的所有元素
    L.erase(L.begin(), L.end());
    PrintList(L);
    
	// 用数组来构造list
    int array1[] = { 1, 2, 3 };
    list
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list
		// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
		l.erase(it);
		++it;
	}
}
// 改正
void TestListIterator()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list
		l.erase(it++); // it = l.erase(it);
	}
}

		typedef list_node}
		Ref operator*()
		{
			return _node-_data;
		}
		Ptr operator-()  
		{
			return &_node-_data;
		}
		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;
		}
		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}
		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
	};

		typedef list_node
			//return iterator(_head-_next);
			iterator it(_head-_next);
			return it;
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin() const
		{
			return const_iterator(_head-_next);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}
		void empty_init()  // 初始化
		{
			_head = new Node;
			_head-_next = _head;
			_head->_prev = _head;
			_size = 0;
		}
		list()   // 默认构造
		{
			empty_init();
		}
		list(initializer_list lt)   // c++11支持  {   }构造
		{
			empty_init();
			for (auto& e : lt)
			{
				push_back(e);
			}
		}
		// lt2(lt1)
		list(const list& lt)  // 拷贝构造
		{
			empty_init();
			for (auto& e : lt)
			{
				push_back(e);
			}
		}
		// lt1 = lt3
		list& operator=(list lt)  // 赋值重载
		{
			swap(lt);
			return *this;
		}
		void swap(list& lt)    // list内部的  swap
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		void clear()   // 清楚函数
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		size_t size() const
		{
			return _size;
		}
		void push_back(const T& x)
		{
			/*Node* newnode = new Node(x);
			Node* tail = _head->_prev;
			newnode->_prev = tail;
			tail->_next = newnode;
			newnode->_next = _head;
			_head->_prev = newnode;*/
			insert(end(), x);
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_front()
		{
			erase(begin());
		}
		void pop_back()
		{
			erase(--end());
		}
		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;
			++_size;
		}
		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* cur = pos._node;
			Node* nextNode = cur->_next;
			Node* prevNode = cur->_prev;
			prevNode->_next = nextNode;
			nextNode->_prev = prevNode;
			delete cur;
			--_size;
			return iterator(nextNode);
		}
	private:
		Node* _head;
		size_t _size;
	};

经过几次的模拟实现stl，发现stl的容器大多都是类似的，有点期待后面的map和set

list 的模拟实现就到这里啦

list与vector的对比

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

总结

C++ STL中的list是基于双向循环链表实现的序列容器，支持高效插入删除（O(1)时间复杂度），但随机访问效率较低。其核心特性包括：通过迭代器遍历元素（支持正向/反向迭代器）、插入操作不引发迭代器失效（删除仅影响被删节点迭代器）。模拟实现需封装节点结构体，设计泛型迭代器（重载++/--/*等操作），并实现深拷贝控制。与vector对比，list适合频繁增删场景，而vector更适合随机访问和内存连续需求。理解其底层实现有助于优化数据操作逻辑。

不要走开，小编持续更新中~~~~~

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们。

高速稳定云服务器9.9元起

一	二	三	四	五	六	日
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31