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

c++中的list容器讲解

10月前 作者：槛外长江__自流 分类：Toy博客 阅读(47) 违法举报

这篇具有很好参考价值的文章主要介绍了c++中的list容器讲解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. list的介绍及使用

1.1 list的介绍

list的文档介绍

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

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

1.2.2 list iterator的使用

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

函数声明 接口说明
begin +end 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rebegin +rend 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

【注意】:

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

1.2.3 list capacity

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

1.2.4 list element access

函数说明 接口说明
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中的有效元素

list中还有一些操作，需要用到时大家可参阅list的文档说明。

1.2.6 list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节
点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代
器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
list的各个接口代码，演示：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
#include<vector>

using namespace std;

//list的构造
void constructor()
{
	/*list<int> l1();*/
	list<int> l2(4, 100);
	list<int> l3(l2.begin(), l2.end());
	list<int> l4(l3);
	int array[5] = { 1,2,3,4,5 };
	list<int> l5(array, array+sizeof(array) / sizeof(array[0]));
	list<int> l6{ 9,8,7,6,5,4 };
	
	// 用迭代器方式打印l5中的元素
	list<int>::iterator it = l5.begin();
	for (; it != l5.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;

	for (auto e : l5)
	{
		cout << e << " ";
	}
	cout << endl;
}


// list迭代器的使用
// 注意：遍历链表只能用迭代器和范围for

void Printlist(const list<int>& l)
{
	// 注意这里调用的是list的 begin() const，返回list的const_iterator对象
	for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
	/*std::list<int> mylist;
	for (int i = 1; i <= 5; ++i) mylist.push_back(i);

	std::cout << "mylist backwards:";
	for (std::list<int>::reverse_iterator rit = mylist.rbegin(); rit != mylist.rend(); ++rit)
		std::cout << ' ' << *rit;

	std::cout << '\n';*/

}

void TestList2()
{
	int array[10] = { 1,2,3,4,5,6,7,8,9,10 };
	list<int> ls(array, array + sizeof(array) / sizeof(array[0]));
	for (auto e : ls)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test3()
{
	
	list<int> lt{ 9,8,7,6,5,4 };
	int sz = lt.size();
	list<int>::iterator it = lt.begin();
	for (int i = 0; i < sz; ++i)
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList3()
{
	int array[] = { 1,2,3 };
	list<int> L(array, array + sizeof(array) / sizeof(array[0]));

	L.push_back(4);
	L.push_front(0);
	Printlist(L);
	L.pop_back();
	L.pop_front();
	Printlist(L);
}

void TestList4()
{
	int array1[] = { 1,2,3 };
	list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));
	auto pos = ++L.begin();
	cout << *pos << endl;

	L.insert(pos, 5, 5);
	Printlist(L);

	vector<int> v{ 7,8,9 };
	L.insert(pos, v.begin(), v.end());
	Printlist(L);

	L.erase(pos);
	Printlist(L);
	L.erase(L.begin(), L.end());
	Printlist(L);
}

void TestList5()
{
	// 用数组来构造list
	int array1[] = { 1, 2, 3 };
	list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
	Printlist(l1);

	// 交换l1和l2中的元素
	list<int> l2;
	l1.swap(l2);
	Printlist(l1);
	Printlist(l2);

	// 将l2中的元素清空
	l2.clear();
	cout << l2.size() << endl;
}

void Testiterator()
{
	int array[10] = { 1,2,3,4,5,6,7,8,9,10 };
	list<int> l1(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l1.begin();
	while (it != l1.end())
	{
		l1.erase(it);
		++it;
	}
}

// 改正
void TestListIterator()
{
	int array[] = { 1,2,3,4,5,6,7,8 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		l.erase(it++);//erase后it的所指的被删除位置的迭代器失效，通过it++来解决，
		//因为失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响
	}
}

int main()
{
	constructor();
	cout << endl;
	list<int> l1{ 1,2,3,45 };
	Printlist(l1);
	cout << endl;
	TestList2();
	cout << endl;
	test3();
	cout << endl;
	TestList3();
	cout << endl;
	TestList4();
	cout << endl;
	TestList5();
	cout << endl;
	//Testiterator();
	//cout << endl;
	TestListIterator();
	cout << endl;

	return 0;
}

c++中的list容器讲解,c++,c++,list,开发语言

2. list的模拟实现

2.1 模拟实现list

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现
在我们来模拟实现list。
list.h

#pragma once
#include<iostream>
#include<assert.h>

using namespace std;

namespace hcm
{
	template<class T>
	struct ListNode
	{
		ListNode(const T& val = T())
			:_prev(nullptr)
			, _next(nullptr)
			, _val(val)
		{}

		ListNode<T>* _prev;
		ListNode<T>* _next;
		T _val;
	};

	template<class T,class Ref,class Ptr>
	class ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;
	public:
		typedef Ref Ref;
		typedef Ptr Ptr;
	public:
		//
		// 构造
		ListIterator(Node* node = nullptr)
			:_node(node)
		{}
		// 具有指针类似行为
		Ref operator*()
		{
			return _node->_val;
		}
		Ptr operator->()
		{
			return &(operator*());
		}
		// 迭代器支持移动
		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& l) const
		{
			return _node != l._node;
		}
		bool operator == (const Self& l) const
		{
			return _node == l._node;
		}

		Node* _node;
	};
	template<class Iterator>
	class ReverseListIterator
	{
// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的一个类型，
// 而不是静态成员变量
// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
	public:
		typedef typename Iterator::Ref Ref;
		typedef typename Iterator::Ptr Ptr;
		typedef ReverseListIterator<Iterator> Self;
	public:
		ReverseListIterator(Iterator it)
			:_it(it)
		{}
		// 具有指针类似行为
		Ref operator*()
		{
			Iterator temp(_it);
			--temp;
			return *temp;
		}
		Ptr operator->()
		{
			return &(operator*());
		}
		// 迭代器支持移动
		Self& operator++()
		{
			--_it;
			return *this;
		}
		Self& operator++(int)
		{
			Self temp(*this);
			--_it;
			return temp;
		}
		Self& operator--()
		{
			++_it;
			return *this;
		}
		Self& operator--(int)
		{
			Self temp(*this);
			++_it;
			return temp;
		}
		// 迭代器支持比较
		bool operator!=(const Self& l)const
		{
			return _it != l._it;
		}
		bool operator ==(const Self& l) const
		{
			return _it == l._it;
		}

		Iterator _it;
	};

	template<class T>
	class list
	{
		typedef ListNode<T> Node;

	public:
		// 正向迭代器
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T&> const_iterator;

		// 反向迭代器
		typedef ReverseListIterator<iterator> reverse_iterator;
		typedef ReverseListIterator<const_iterator> const_reverse_iterator;
	public:
		///
		// List的构造
		list()
		{
			CreateHead();
		}

		list(int n, const T& value = T())
		{
			CreateHead();
			for (int i = 0; i < n; ++i)
				push_back(value);
		}

		template <class Iterator>
		list(Iterator first, Iterator last)
		{
			CreateHead();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		list(const list<T>& l)
		{
			CreateHead();

			// 用l中的元素构造临时的temp,然后与当前对象交换
			list<T> temp(l.begin(), l.end());
			this->swap(temp);
		}

		list<T>& operator=(list<T> l)
		{
			this->swap(l);
			return *this;
		}

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

		///
		// List的迭代器
		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);
		}

		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}

		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin()const
		{
			return const_reverse_iterator(end());
		}

		const_reverse_iterator rend()const
		{
			return const_reverse_iterator(begin());
		}

		///
		// List的容量相关
		size_t size()const
		{
			Node* cur = _head->_next;
			size_t count = 0;
			while (cur != _head)
			{
				count++;
				cur = cur->_next;
			}

			return count;
		}

		bool empty()const
		{
			return _head->_next == _head;
		}

		void resize(size_t newsize, const T& data = T())
		{
			size_t oldsize = size();
			if (newsize <= oldsize)
			{
				// 有效元素个数减少到newsize
				while (newsize < oldsize)
				{
					pop_back();
					oldsize--;
				}
			}
			else
			{
				while (oldsize < newsize)
				{
					push_back(data);
					oldsize++;
				}
			}
		}
		
		// List的元素访问操作
		// 注意：List不支持operator[]
		T& front()
		{
			return _head->_next->_val;
		}

		const T& front()const
		{
			return _head->_next->_val;
		}

		T& back()
		{
			return _head->_prev->_val;
		}

		const T& back()const
		{
			return _head->_prev->_val;
		}

		
		// List的插入和删除
		void push_back(const T& val)
		{
			insert(end(), val);
		}

		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* pNewNode = new Node(val);
			Node* pCur = pos._node;
			// 先将新节点插入
			pNewNode->_prev = pCur->_prev;
			pNewNode->_next = pCur;
			pNewNode->_prev->_next = pNewNode;
			pCur->_prev = pNewNode;
			return iterator(pNewNode);
		}

		// 删除pos位置的节点，返回该节点的下一个位置
		iterator erase(iterator pos)
		{
			// 找到待删除的节点
			Node* pDel = pos._node;
			Node* pRet = pDel->_next;

			// 将该节点从链表中拆下来并删除
			pDel->_prev->_next = pDel->_next;
			pDel->_next->_prev = pDel->_prev;
			delete pDel;

			return iterator(pRet);
		}

		void clear()
		{
			Node* cur = _head->_next;

			// 采用头删除删除
			while (cur != _head)
			{
				_head->_next = cur->_next;
				delete cur;
				cur = _head->_next;
			}

			_head->_next = _head->_prev = _head;
		}

		void swap(hcm::list<T>& l)
		{
			std::swap(_head, l._head);
		}

	private:
		void CreateHead()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}
	private:
		Node* _head;
	};

}

template<class T>
void PrintList(const hcm::list<T>& l)
{
	auto it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

list.cpp

#include"list.h"

// 测试List的构造
void TestList1()
{
	hcm::list<int> l1;
	hcm::list<int> l2(10, 5);
	PrintList(l2);
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	hcm::list<int> l3(array, array + sizeof(array) / sizeof(array[0]));
	PrintList(l3);
	hcm::list<int> l4(l3);
	PrintList(l4);

	l1 = l4;
	PrintList(l1);

}
// PushBack()/PopBack()/PushFront()/PopFront()
void TestBiteList2()
{
	hcm::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(10);
	PrintList(lt);
	lt.pop_back();
	PrintList(lt);
	lt.push_front(0);
	PrintList(lt);
	lt.pop_front();
	PrintList(lt);

}

// 测试insert和erase
void TestBiteList3()
{
	int array[] = { 1, 2, 3, 4, 5 };
	hcm::list<int> l(array, array + sizeof(array) / sizeof(array[0]));

	auto pos = l.begin();
	l.insert(l.begin(), 0);
	PrintList(l);

	++pos;
	l.insert(pos, 2);
	PrintList(l);

	l.erase(l.begin());
	l.erase(pos);
	PrintList(l);

	// pos指向的节点已经被删除，pos迭代器失效
	cout << *pos << endl;

	auto it = l.begin();
	while (it != l.end())
	{
		it = l.erase(it);
	}
	cout << l.size() << endl;
}

// 测试反向迭代器
void TestBiteList4()
{
	int array[] = { 1, 2, 3, 4, 5 };
	hcm::list<int> l(array, array + sizeof(array) / sizeof(array[0]));

	auto rit = l.rbegin();
	while (rit != l.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;

	const hcm::list<int> cl(l);
	auto crit = l.rbegin();
	while (crit != l.rend())
	{
		cout << *crit << " ";
		++crit;
	}
	cout << endl;
}

int main()
{
	TestList1();
	TestBiteList2();
	TestBiteList3();
	TestBiteList4();

	return 0;
}

运行结果如下：
c++中的list容器讲解,c++,c++,list,开发语言

3. list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不
同，其主要不同如下：文章来源地址https://www.toymoban.com/news/detail-699866.html

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

到了这里，关于c++中的list容器讲解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

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

相关文章

  • 【C++】list容器功能模拟实现

    【C++】list容器功能模拟实现

            上一次介绍了list队容器的迭代器模拟，这次模拟实现list的简单功能，尤其要注意 构造函数、析构函数、以及赋值运算符重载 的实现。         list容器需要接纳所有类型的数据，因此，结构设置与迭代器设置同理，需要引入结点，数据。     //结点结构     templ

    2024年01月24日
    浏览(56)
  • 【C++学习】STL容器——list

    【C++学习】STL容器——list

    目录 一、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的模拟实现 2.1 模拟实现list 三、list和vector的对比 一、list的介绍及使用 1.1 list的介绍 list的文档介绍

    2024年02月14日
    浏览(40)

  • C++高级编程——STL：list容器、set容器和map容器

    本专栏记录C++学习过程包括C++基础以及数据结构和算法，其中第一部分计划时间一个月，主要跟着黑马视频教程，学习路线如下， 不定时更新，欢迎关注 。 当前章节处于： ---------第1阶段-C++基础入门 ---------第2阶段实战-通讯录管理系统， ---------第3阶段-C++核心编程， -----

    2024年01月25日
    浏览(47)
  • 【C++杂货铺】详解list容器

    【C++杂货铺】详解list容器

    目录 🌈前言🌈 📁 介绍 📁 使用  📂 构造  📂 迭代器iterator  📂 capacity  📂 modifiers  📂 迭代器失效 📁 模拟实现  📂 迭代器的实现 📂 代码展示 📁 和vector的区别 📁 总结         欢迎收看本期【C++杂货铺】，本期内容将讲解STL中关于list的内容，会分为一下几个方

    2024年04月14日
    浏览(52)
  • C++ ——STL容器【list】模拟实现

    C++ ——STL容器【list】模拟实现

    代码仓库： list模拟实现 list源码 数据结构——双向链表 源码的list是双向带头循环链表，所以我们定义两个节点，一个指向下一个，一个指向前一个 list类包含一个 _head 头节点，然后为了方便查出当前有多少个节点，还能多定义一个 _size 源码的迭代器设置了三个模板参数：

    2024年02月15日
    浏览(46)

  • 【C++】list链表容器功能模拟实现

    目录 介绍 一，容器的结构设计 二，构造函数与赋值运算符 三，析构函数 四，list容器接口 1，begin和end 2，insert和erase 3，其它常用接口函数         上一次介绍了list双向链表容器的迭代器模拟，这次模拟实现list的简单功能，尤其要注意 构造函数、析构函数、以及赋值运算

    2024年02月20日
    浏览(41)

  • [开发语言][python][c++]：C++中的this指针和Python中的Self -- 26岁生日

    以朋友的新岁祝福开篇，祝笔者也祝大家☺️： 之前一直对 C++ 中的 this 和 python 中的 self 到底是什么关系，为什么 C++ 要显式的写出来，python 则不需要？ 模糊不清，趁着周末整理一下相关结论，希望本篇文章可以解答这些问题，同时对C++和Python中的类加深些理解。 python 当

    2024年01月24日
    浏览(71)
  • C++容器（vector、deque、list、map）

    C++容器（vector、deque、list、map）

    数组尾部添加或删除元素非常迅速。但在中部或头部就比较费时。 *代码演示：* 取： at在下标越界时会抛出异常，我们能捕获异常进行处理；而[]下标越界会让程序直接终止； 构造函数： cbegin, cend, crbegin, crend返回的是常量迭代器，不能通过迭代器修改vector元素的值。 插入（

    2024年02月02日
    浏览(54)
  • C++——STL标准模板库——容器详解——list

    C++——STL标准模板库——容器详解——list

    list：双向链表。list是一种分布式存储的线性表，每个节点分为数据域和指针域，其中指针域中包含一个指向前驱节点的指针和一个指向后续节点的指针，基本模型如下： 1、双向链表：每个元素都有一个前驱和一个后继，这种结构允许在链表的任何位置实现快速的插入和删除

    2024年01月16日
    浏览(47)
  • 【C++】STL之list容器的模拟实现

    【C++】STL之list容器的模拟实现

    个人主页：🍝在肯德基吃麻辣烫 分享一句喜欢的话：热烈的火焰，冰封在最沉默的火山深处。 本文章进入C++STL之list的模拟实现。 在STL标准库实现的list中，这个链表是一个== 双向带头循环链表==。 说明： list是一个类，成员变量为_head 节点类node，是每一个节点。 list的迭代

    2024年02月17日
    浏览(52)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包