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

C++——list的简要介绍

7月前 作者：Nick-An 分类：Toy博客 阅读(53) 违法举报

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

list的介绍

详细请看（https://cplusplus.com/reference/list/list/?kw=list）

1.list是一个可以在常数范围内在任意位置，进行插入和删除的序列式容器，并且此容器可以前后双向迭代。

2.list的底层实质是一个双向链表结构，双向链表里每个元素的存放都互不相关，在节点中可以通过指针来指向前一个元素和后一个元素

3.相对于vector等序列式容器，list在任意位置上的插入、删除元素的效率会更高。

4.但是list与其他序列式容器相比，最大缺陷是不支持任意位置的随机访问，必须要从已知位置迭代到当前的位置，只有这样才可以进行数据的读取。

简要使用

建立及其数据的尾插

void test_list1()
{
	list<int> l1;
	l1.push_back(1);
	l1.push_back(2);
	l1.push_back(3);
	l1.push_back(4);
	l1.push_back(5);

	list<int>::iterator it = l1.begin();//读取需要用迭代器读取，不能用下标
	while (it != l1.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	for (auto e : l1)
	{
		cout << e << " ";
	}
	cout << endl;
}

排序

list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
l1.push_back(5);

l1.reverse();//进行了逆序
l1.sort();//默认升序

//降序
greater<int> gt;
l1.sort(gt);//传入这个即可

l1.sort(greater<int>());//也可以用匿名函数

//升序限定范围
sort(v.begin(), v.end());

数据的拷贝

lt2.assign(v.begin(), v.end());//粘贴

去重函数

list<int> L;
L.push_back(1);
L.push_back(4);
L.push_back(3);
L.push_back(3);

L.unique();
//但在注意的是，去重函数本质是用一个双指针进行删除，连续相同的会留下一个，若是多个重复数据，若不是连//续的，那么结果还是会出现重复的元素。
//——所以需要先进行排序sort

分割函数

list<int> l1, l2;
for (int i = 1; i <= 4; i++)
{
	l1.push_back(i);
}
for (int i = 5; i <= 8; i++)
{
	l2.push_back(i);
}

auto it = l1.begin();
l1.splice(it, l2);//将l2中的数据，全部插入到l1的it处

list的模拟实现

现在复现list类的简要底层代码——实现的结构体逻辑和用C实现相似。

namespace bit
{
	template<class T>
	struct list_node//节点的结构,并且对节点进行初始化
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& x = T())
//给缺省值，由于不知道是什么类型，所以用模板名T进行位置类型变量的初始化(作为缺省)->T()
			:_data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};
    
    template<class T>
	class list//链表的结构，需要一个头结点即可
	{
        typedef list_node<T> Node;
	public:
	private:
		Node* _head;
	};
}

构造函数

void empty_init()
{
    _head=new Node;
    _head->_next=_head;
    _head->_prev=_head;
}

list()
{
    empty_init();
}

尾插

void push_back(const T& x)
{
    Node*tail=_head->_prev;
    Node* newnode=new Node(x);//建立一个包含x的节点
    tail->_next=newnode;
    newnode->_prev=tail;
    newnode->_next=_head;
    _head->_prev=newnode;
    ++_size;
}

节点迭代器

倘若我们有以下的代码

list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
l1.push_back(5);

list<int>::iterator it = l1.begin();
while (it != l1.end())
{
	cout << *it << " ";
	++it;
}

这样子会显示报错？这是为什么？——结构体存放的是结点，解引用出来的是一整个结构体

而且节点存放的空间不是连续存放的，所以需要写一个结构体，进行对于' 节点的指针 '的封装。

template<class T>
struct _list_iterator
{    
    typedef _list_iterator<T> self;
    typedef list_node<T> Node;
    Node* _node;//结构体里存放的就是节点
}

迭代器的构造

_list_iterator(Node* node)//此迭代器的本质也就是用节点的指针
    :_node(node)
{}

节点指针++

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

解引用获取数据

T& operator*()//解引用也要进行一个函数的封装,要的是这个数据，所以用T
{
	return _node->_data;	
}

指针的比较

bool operator!=(const self& s)//结点之间比较，所以用迭代器的结构体名称
{
	return _node != s._node;
}

list类

有了迭代器之后，对于list类作补充

template<class T>
class list
{
public:
    typedef _list_iterator<T> iterator;
    iterator begin()
    {
        return _head->_next;
    }
    iterator end()
    {
        return _head;
    }

}

插入

iterator insert(iterator pos, const T& val)//由于插入是利用节点之间的连接进行的，且需要用迭代器
{
    Node* cur=pos._node;
    Node* newnode=new Node(val);
    Node* prev=cur->_prev;
       
    prev->_next=newnode;
    newnode->_prev=prev;
    newnode->_next=cur;
    cur->_prev=newnode;
    ++_size;
    return iterator(newnode);//insert插入函数的结果会返回插入节点的位置
}

删除

iterator erase(iterator pos)
{
    Node* cur=pos._node;
    Node* prev=cur->_prev;
    Node* next=cur->_next;
    
    delete cur;
    prev->_next=next;
    next->_prev=prev;
    --_size;
    return iterator(next);//erase要返回下一个元素的指针
}

有了insert和erase后，可以方便地实现其他函数

void push_front(const T& x)//头插
{
	insert(begin(), x);
}
void pops_front(const T& x)//头删
{
	erase(begin());
}
void pops_back(const T& x)//尾删
{
	erase(end());
}

清理函数

void clear()
{
    iterator it=begin();
    while(it!=end())
    {
        it=erase(it);//erase会返回一个指向下一个位置的地址，用erase可以减少代码量
    }
}

拷贝重载/赋值拷贝

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;
}

list(const list<T>& lt)
{
	empty_init();
	for (auto e : lt)
	{
		push_back(e);//直接用push_back进行数据的插入即可，不需要再作拷贝结点
	}
}

析构函数

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

完善节点指针的结构体

template<class T>//用一个迭代器的结构体进行结点的封装 ++
//struct 默认公有，但是class类需要做些声明
struct _list_iterator
{
	typedef list_node<T> Node;
	typedef _list_iterator<T> self;
	Node* _node;//创造一个结点

	_list_iterator(Node* node)//用一个结点的指针就能够造出一个迭代器
		:_node(node)//传入begin，就会有对应位置的一个初始化结点出来
	{}

	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*()//解引用也要进行一个函数的封装,要的是这个数据，所以用T
	{
		return _node->_data;
	}
	T* operator->()
	{
		return &_node->_data;
	}
	bool operator!=(const self& s)//结点之间比较，所以用迭代器的结构体名称
	{
		return _node != s._node;
	}
	bool operator==(const self& s)//结点之间比较，所以用迭代器的结构体名称
	{
		return _node == s._node;
	}
};

const迭代器

我们知道，若无const修饰，那么就可以进行' 读写 '，若有const修饰，那么就只能进行' 读 '。

倘若用const修饰迭代器呢？(const iterator)——err，这样子会是迭代器本身不能修改，那么应该怎么表示？

——const_iterator 重新定义的一个类型，这样本身可以修改，指向的内容不能修改。

那么可以在迭代器基础上进行修改，成为const迭代器

template<class T>//用一个迭代器的结构体进行结点的封装 ++
//struct 默认公有，但是class类需要做些声明
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修改后，迭代器里的内容就不能被修改
	const T& operator*()//解引用也要进行一个函数的封装,要的是这个数据，所以用T
	{
		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;//模板中的类型T，可以用Ref和Ptr来分别取代
	//其中，T& 又可以被Ref代替  T* 可以被Ptr代替
	Node* _node;//创造一个结点
	_list_iterator(Node* node)//用一个结点的指针就能够造出一个迭代器
		:_node(node)//传入begin，就会有对应位置的一个初始化结点出来
	{}

	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;
	}
};

那么对于list类，要通过两个模板参数进行相关的控制文章来源地址https://www.toymoban.com/news/detail-650720.html

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;

    iterator begin()
	{
		return iterator(_head->_next);//两种写法
	}
	iterator end()
	{
		return _head;
	}
	const_iterator begin()const
	{
		return const_iterator(_head->_next);
	}
	const_iterator end()const
	{
		return _head;
	}
....//
}

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

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

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

相关文章

  • 【C++】list的介绍及使用 | 模拟实现list（万字详解）

    【C++】list的介绍及使用 | 模拟实现list（万字详解）

    目录 一、list的介绍及使用 什么是list？ list的基本操作 增删查改 获取list元素 不常见操作的使用说明 ​编辑 接合splice ​编辑 移除remove 去重unique 二、模拟实现list 大框架 构造函数 尾插push_back 迭代器__list_iterator list的迭代器要如何跑起来 iterator的构造函数 begin()与end() opera

    2024年02月06日
    浏览(36)
  • 【C++】STL---list基本用法介绍

    【C++】STL---list基本用法介绍

    个人主页：平行线也会相交💪 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【C++之路】💌 本专栏旨在记录C++的学习路线，望对大家有所帮助🙇‍ 希望我们一起努力、成长，共同进步。🍓 list 是STL中的一种 容器 ，底层其实就是一个 双向链

    2024年02月16日
    浏览(33)
  • 【C++】——list的介绍及模拟实现

    【C++】——list的介绍及模拟实现

    我们之前已经学习了string和vector，今天我们来学习C++中的另一个容器——list，list的底层是带头双向循环链表。 1.list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。 2.list的底层是双向链表结构，双向链表中每个元素存储在互不相

    2024年02月08日
    浏览(31)
  • 【C++】STL——list介绍及使用

    【C++】STL——list介绍及使用

    🚀 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。 🚁 个人主页：不 良 🔥 系列专栏：🛸C++  🛹Linux 📕 学习格言：博观而约取，厚积而薄发 🌹 欢迎进来的小伙伴，如果小伙伴们在学习的过程中，发现有需要纠正的地方，烦请指正，希望能够与诸君一同

    2024年02月12日
    浏览(69)

  • C++面试：向量vector和列表list介绍

    目录 vector list  list和vector的区别 1. 底层实现： 2. 动态性和静态性： 3. 内存管理： 4. 迭代器和指针： 5. 访问效率： 6. 适用场景：   std::vector 是 C++ STL 提供的动态数组容器，提供了多种操作。以下是一些常见的 std::vector 操作，一一列举出来 初始化和基本操作 插入和删除元

    2024年01月22日
    浏览(27)
  • 【C++初阶】STL详解（五）List的介绍与使用

    【C++初阶】STL详解（五）List的介绍与使用

    本专栏内容为：C++学习专栏，分为初阶和进阶两部分。 通过本专栏的深入学习，你可以了解并掌握C++。 💓博主csdn个人主页：小小unicorn ⏩专栏分类：C++ 🚚代码仓库：小小unicorn的代码仓库🚚 🌹🌹🌹关注我带你学习编程知识 1.list是一种可以在常数范围内在任意位置进行插

    2024年02月04日
    浏览(36)
  • 【C++从0到王者】第十四站：list基本使用及其介绍

    【C++从0到王者】第十四站：list基本使用及其介绍

    如下所示，是库里面对list的基本介绍 链表是序列容器，允许在序列内的任何位置进行常量时间的插入和擦除操作，以及两个方向的迭代。 链表容器被实现为双链表;双链表可以将它们包含的每个元素存储在不同且不相关的存储位置。排序是通过与前面元素的链接和后面元素的

    2024年02月14日
    浏览(37)
  • 【C++】STL——list的介绍和使用、list增删查改函数的介绍和使用、push_back、pop_back

    【C++】STL——list的介绍和使用、list增删查改函数的介绍和使用、push_back、pop_back

    list构造函数的介绍和使用      push_front()函数用于将一个新的元素插入到链表的开头位置。 通过调用push_front()函数并将待插入的元素作为参数传递给该函数，即可实现在链表开头插入新元素的操作。   和链表的插入一样，push_front()函数的时间复杂度为O(1)，因为在双向链

    2024年02月15日
    浏览(43)

  • 目标检测简要介绍

    目标检测是计算机视觉领域的一项重要任务，其目的是在图像或视频中自动识别和定位特定目标。本教程将介绍目标检测的基础知识和常用算法，旨在帮助读者快速掌握目标检测的核心概念和实现方法。 目标检测基础知识 图像表示和处理 目标检测的定义和分类 目标检测的评

    2024年02月01日
    浏览(32)
  • Socket简要介绍

    Socket简要介绍

    简介 Socket作为计算机术语翻译为“套接字”，而它更常见的含义是：插座。 Socket就像一个电话插座，负责连通两端的电话，进行点对点通信，让电话可以进行通信，端口就像插座上的孔，端口不能同时被其他进程占用。而我们建立连接就像把插头插在这个插座上，创建一个

    2024年02月06日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包