【C++】list的使用与模拟实现

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

目录

一、list介绍

二、list的使用 

1、list的构造

2、list capacity

3、list element access

4、list iterator

5、list modifiers

5.1、insert

6、list Operations

6.1、sort

7、list的迭代器失效

三、list模拟实现

1、push_back

2、iterator

3、const iterator

4、Ptr

5、insert 及其复用

6、erase 及其复用

7、clear

8、构造函数

8.1、默认构造

8.2、迭代器构造

9、拷贝构造函数

10、析构函数

11、operator=


一、list介绍

【C++】list的使用与模拟实现

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

【C++】list的使用与模拟实现

二、list的使用 

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

【C++】list的使用与模拟实现

2、list capacity

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

3、list element access

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

4、list iterator

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

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

【C++】list的使用与模拟实现

注意:

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

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中的有效元素

5.1、insert

使用方法如下:

【C++】list的使用与模拟实现

6、list Operations

函数声明

接口说明
splice 将元素从一个列表传输到另一个列表
remove 删除具有特定值的元素
unique 删除重复值
merge 合并排序列表
sort 对容器中的元素进行排序
reverse 反转元素的顺序

6.1、sort

list无法使用算法库里的 sort 函数,因为算法库里的 sort 函数底层实现如下图所示:

【C++】list的使用与模拟实现

 这里使用了减法运算,而list各个节点的地址都是不连续的,于是就发生了错误。除此之外,算法库里的 sort 函数底层使用快排实现,而快排有一个重要的组成部分:三数取中,也不适用于list。

文档里关于 sort 函数的说明,也暗示使用算法库里的 sort 函数时要传随机迭代器:

【C++】list的使用与模拟实现


 list中的 sort 用法如下:

【C++】list的使用与模拟实现

 功能没有任何问题,但是list的 sort 函数我们很少使用,因为它的效率非常的低。

我们使用如下代码进行证明:

【C++】list的使用与模拟实现

 可以看到,把相同的数据先拷贝到 vector 中排序,排好了之后再拷贝回来,都要比直接使用 list 排序要快。

7、list的迭代器失效

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

三、list模拟实现

我们先来搭一个list的基本框架:

namespace bin
{
	template<class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;
		
		list_node(const T& x = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}
	};

	template<class T>
	class list
	{
		typedef list_node<T> node;
	public:
		list()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}
	private:
		node* _head;
	};
}

【C++】list的使用与模拟实现

 需要注意:在 list 类中定义私有成员变量时,一定要注意成员变量类型为类名 + 模板参数

1、push_back

void push_back(const T& x)
{
	node* tail = _head->_prev;
	node* new_node = new node(x);

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

【C++】list的使用与模拟实现

具体底层逻辑可以参照文章《双向链表》 。

2、iterator

 list的底层物理空间是不连续的,所以模拟实现迭代器时,就不能直接让指针 "++" "--" 了,而应该实现迭代器 "++" "--" 的重载:

template<class T>
struct __list_iterator
	{
	typedef list_node<T> node;
	typedef __list_iterator<T> self;
	node* _node;

	__list_iterator(node* n)
		:_node(n)
	{}

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

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

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

【C++】list的使用与模拟实现

 因为我们模拟实现的list类中的迭代器是使用原生指针实现的,且原生指针的类型为 _node* ,没办法直接实现,所以又定义了一个 __list_iterator 类进行封装。

 实验运行结果正确:

【C++】list的使用与模拟实现

 红框框起的部分调用了一次拷贝构造,由于我们没有自己实现拷贝构造函数,所以这里是一次浅拷贝,而我们想要的就是浅拷贝。

 这里浅拷贝之所以没有报错,是因为我们封装的迭代器类中没有实现析构函数,因为迭代器仅仅是使用list对象节点,而不是拥有list对象节点,它没有权利释放list的对象。

 我们再来完善一下迭代器的其他功能:

template<class T>
	struct __list_iterator
	{
		typedef list_node<T> node;
		typedef __list_iterator<T> self;
		node* _node;

		__list_iterator(node* n)
			:_node(n)
		{}

		T& 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& s)
		{
			return _node != s._node;
		}
	};

3、const iterator

先来看一下错误的写法:
【C++】list的使用与模拟实现

 直接在list类中定义 const 类型的成员函数。这种写法的错误之处在于,这些 const 类型成员函数所针对的是list类中的成员变量 _head ,虽然 _head const 限制无法更改,但是 _head 所指向的 _data 仍然可以更改,即数据仍然可以被更改,不符合我们的预期。

 我们较为容易想到的写法是直接再另外定义一个类,在这个新类中封装 const 类型的迭代器:

【C++】list的使用与模拟实现

 虽然这种写法可以实现功能且完全满足需求,但是代码太过于冗余,接下来我们来学习一种新的写法:

【C++】list的使用与模拟实现

在迭代器模板中多增加了一个模板参数 Ref ,用于满足不同的调用需求。

4、Ptr

观察如下代码:

【C++】list的使用与模拟实现

 编译器报错,因为我们没有为自定义类型 AA 实现流插入重载,所以需要写成这种形式:

【C++】list的使用与模拟实现

 但是我们在写 C++ 代码时,一般没有写成这种形式的习惯,大多数都是通过 "->" 来实现解引用操作的,所以我们可以改变写法:

【C++】list的使用与模拟实现

 这种写法乍一看非常难以理解,这时因为为了增强可读性的缘故,在这里少写了一个 "->"

【C++】list的使用与模拟实现

 大家看一下完整版的写法就一定能够理解:

【C++】list的使用与模拟实现

 同理,为了满足不同的调用需求,应该为list类重载一个 const 类型的成员函数,为了不造成代码冗余,同样只需要为list类模板增加一个模板参数就可以了:

【C++】list的使用与模拟实现

5、insert 及其复用

具体实现如下: 

【C++】list的使用与模拟实现

 list的 insert 不会导致迭代器失效。

可以使用 insert 函数的复用来实现 push_back push_front

【C++】list的使用与模拟实现

6、erase 及其复用

具体实现如下:

【C++】list的使用与模拟实现

  list的 erase 导致迭代器失效。

为了在使用 erase 函数后仍然可以找到该节点的下一个节点,我们使用返回值来返回需要的信息:

【C++】list的使用与模拟实现

 可以使用 erase 函数的复用来实现 pop_back pop_front

【C++】list的使用与模拟实现

7、clear

具体实现方法如下:

【C++】list的使用与模拟实现

 也可以使用下面这种写法:

【C++】list的使用与模拟实现

8、构造函数

8.1、默认构造

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

list()
{
	empty_init();
}

8.2、迭代器构造

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

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

 扩展内容:

 const 类型的对象是无法调用 empty_init() 函数的,因为这属于权限放大。那么为什么我们写如下 const 类型对象的实例化不会报错呢?

【C++】list的使用与模拟实现

 这是因为该 const 对象在定义的时候并没有 const 属性,在该对象定义完成后,才被赋予了 const 属性,否则就没有办法对对象进行初始化操作了。

9、拷贝构造函数

传统写法如下:

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

list(const list<T>& lt)
{
	empty_init();
	for ( auto e : lt)
	{
		push_back(e);
	}
}

这里再提供一份现代写法:

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

list(const list<T>& lt)
{
	empty_init();

	list<T> tmp(lt.begin(), lt.end());
	swap(tmp);
}

10、析构函数

实现代码如下:

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

11、operator=

实现代码如下:

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

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

【C++】list的使用与模拟实现

注意:这里的传参没有使用传引用传参,而是采用了传值传参。这是因为我们本来就期望在传参时发生一次拷贝构造,并把拷贝构造出的临时变量与 this 进行交换,这样不会影响到赋值运算符重载的右值本身。


关于list的使用和模拟实现的相关内容就讲到这里,欢迎同学们多多支持,如果有不对的地方欢迎大佬指正,谢谢!文章来源地址https://www.toymoban.com/news/detail-425508.html

到了这里,关于【C++】list的使用与模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】list的使用与模拟实现

    目录 一、list介绍 二、list的使用  1、list的构造 2、list capacity 3、list element access 4、list iterator 5、list modifiers 5.1、insert 6、list Operations 6.1、sort 7、list的迭代器失效 三、list模拟实现 1、push_back 2、iterator 3、const iterator 4、Ptr 5、insert 及其复用 6、erase 及其复用 7、clear 8、构造函

    2023年04月26日
    浏览(40)
  • 【C++】list的使用和模拟实现

    list的底层是一个双向带头循环链表,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素,其遍历只能通过迭代器来实现,范围for的底层也是迭代器。 迭代器是所有容器都可以使用的迭代方式。 与list类似的还有forward_list,底

    2024年02月09日
    浏览(49)
  • C++:List的使用和模拟实现

                                                            创作不易,感谢三连!! list的文档介绍 1. list是可以 在常数范围内在任意位置进行插入和删除的序列式容器 ,并且该容器 可以前后双向迭代。 2. list的 底层是双向链表结构, 双向链表中每个元素存储在互不相

    2024年03月25日
    浏览(40)
  • [C++入门]---List的使用及模拟实现

    list 是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list 的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向 其前一个元素和后一个元素。 list 与 forward_list 非常相似:最主要的不

    2024年02月07日
    浏览(35)
  • 【C++干货铺】list的使用 | 模拟实现

    ========================================================================= 个人主页点击直达: 小白不是程序媛 C++专栏: C++干货铺 代码仓库: Gitee ========================================================================= 目录 list的介绍及使用 list的介绍 list的使用 list的构造 list迭代器的使用 list的增删查改

    2024年02月04日
    浏览(37)
  • 【C++初阶】11. list的使用及模拟实现

    list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。 list与forward_list非常相似:最主要的不同在

    2024年02月12日
    浏览(42)
  • C++ STL之list的使用及模拟实现

    英文解释: 也就是说: list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。 list与forward_list非常

    2024年01月24日
    浏览(81)
  • 【C++模拟实现】list的模拟实现

    作者:爱写代码的刚子 时间:2023.9.3 前言:本篇博客关于list的模拟实现和模拟实现中遇到的问题 list模拟实现的部分代码 list模拟实现中的要点 const_iterator的实现 我们选择使用模版参数,复用iterator的类,设置三个模版参数: templateclass T,class Ref,class Ptr 并且 typedef __list_iter

    2024年02月09日
    浏览(55)
  • 【C++】list模拟实现

    个人主页 : zxctscl 如有转载请先通知 在前面一篇博客中分享了list的相关介绍 【C++】list介绍,这次来模拟实现一下list。 成员变量: 无参构造: 插入: 在库里面定义节点需要全部公有时用到的就是struct: 这里我们也用相同方法自己定义出一个节点: 然后在写list类时候就要

    2024年04月11日
    浏览(38)
  • C++ list 模拟实现

      目录 1. 基本结构的实现 2.  list() 3. void push_back(const T val) 4. 非 const 迭代器 4.1 基本结构  4.2 构造函数  4.3 T operator*() 4.4  __list_iterator operator++() 4.5 bool operator!=(const __list_iterator it) 4.6 T* operator-() 5. const 迭代器  6. begin()  end() ​编辑 7. iterator insert(iterator pos, const T v

    2024年02月08日
    浏览(51)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包