【STL】list的底层原理及其实现

文章目录

  • list的介绍
  • list的整体结构设计
  • list的构造
    • 代码模拟实现：
  • list节点类的实现
  • list 迭代器Iterator的使用以及实现
    • Iterator的使用
    • Iterator的底层实现
    • 反向迭代器
  • list与vector的比较
  • 实现list类

list的介绍

  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
  2. list的底层是用双向链表实现的（线性），每个元素都存在相互独立的节点中，每个节点都有一个指针分别指向前一个节点和后一个节点。
  3. 因为底层结构是链表，list的插入和删除操作是非常高效的，这与vector容器相反。但是由于链表的结构特点，list的各个节点之间的物理地址是不连续的，也就导致了任意访问某个节点的效率较低。
  4. list的空间消耗会比vector大（存储相同个数的元素），因为每个节点还需要给前后指针开空间。

在这里插入图片描述

list的整体结构设计

list可以分为三部分：一个是list类本身，一个是节点类，一个是迭代器类。

list类的成员变量一般只有头节点（哨兵），除了负责初始化以外还负责声明和定义插入删除功能。
ListNode节点类封装了list的元素以及前后节点的指针，还负责new出节点时的初始化。
Iterator迭代器类封装了指向节点的指针ListNode*,还负责重载++、–、！=等运算符。为什么要在迭代器内部重载呢？

跟vector不同的是，由于list迭代器指向的是一个节点，且节点间物理地址不连续，向前移动或者向后移动都不能用指针直接去加减。

在这里插入图片描述
list的节点类

 // List的节点类
 template<class T>
 struct ListNode
 {
     ListNode(const T& val = T());
     ListNode<T>* _pPre;
     ListNode<T>* _pNext;
     T _val;
 };

list的迭代器类

template<class T, class Ref, class Ptr>
class ListIterator
{
    typedef ListNode<T>* PNode;
    typedef ListIterator<T, Ref, Ptr> Self;
public:
    ListIterator(PNode pNode = nullptr);
    ListIterator(const Self& l);
    T& operator*();
    T* operator->();
    Self& operator++();
    Self operator++(int);
    Self& operator--();
    Self& operator--(int);
    bool operator!=(const Self& l);
    bool operator==(const Self& l);
private:
    PNode _pNode;
};

list类

template<class T>
class list
{
    typedef ListNode<T> Node;
    typedef Node* PNode;
public:
    typedef ListIterator<T, T&, T*> iterator;
    typedef ListIterator<T, const T&, const T&> const_iterator;
public:
    ///
    // List的构造
    list();
    list(int n, const T& value = T());
    template <class Iterator>
    list(Iterator first, Iterator last);
    list(const list<T>& l);
    list<T>& operator=(const list<T> l);
    ~list();

    ///
    // List Iterator
    iterator begin();
    iterator end();
    const_iterator begin();
    const_iterator end();
    ///
    // List Capacity
    size_t size()const;
    bool empty()const;

};

list的构造

list有四个构造函数：无参构造、拷贝构造、连续赋值构造、迭代器构造。

//构造的list中包含n个值为val的元素
list (size_type n, const value_type& val = value_type())
//构造空的list，初始化哨兵节点
list() 
//拷贝构造
list (const list& x)
//用[first, last)区间中的元素构造list
list (InputIterator first, InputIterator last)

代码模拟实现：

		void Empty_Init() {
			head = new Node;
			head->_pre = head;
			head->_next = head;
			head->_val = -1;
			sz = 0;
		}
		//构造
		list()
		{
			Empty_Init();
		}
		list(size_t n, const T& value = T())
		{
			Empty_Init();
			for (size_t i = 0; i < n; i++) {
				push_back(value);
			}
			sz = n;
		}
		//拷贝构造
		list(const list<T>& lt) {
			Empty_Init();
			for (auto& it : lt) {
				push_back(it);
			}
		}
		//迭代器构造
		template <class IIterator>
		list(IIterator first, IIterator last) {
			Empty_Init();
			while (first != last) {
				push_back(*first);
				first++;
			}
		}

list节点类的实现

节点类的成员变量就是前后指针以及节点的元素值。此外还需注意构造节点时的初始化工作。

template<class T>
class ListNode {
public:
	ListNode(const T& val = T())
		:_val(val)
		, _pre(nullptr)
		, _next(nullptr)
	{

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

list 迭代器Iterator的使用以及实现

Iterator的使用

在上面iterator类的声明中我们可以看到，不同的容器其迭代器的实现方式是不一样的。在string和vector中的iterator本质是一个指针。但是list的迭代器是一个像指针的类。

//返回第一个元素或最后一个的迭代器
begin()
end()

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

在这里插入图片描述

  1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
  2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
    代码演示：
    在这里插入图片描述

Iterator的底层实现

先实现一个正向的迭代器类。因为涉及到存在const修饰迭代器指向的节点，所以在设计迭代器的时候需要同时设计出const版本（const是修饰节点，不是迭代器本身）。这里我们可以使用模板，模板里面有三个类型：节点数据类型、引用类型、指针类型。
在这里插入图片描述
值得注意的是，由于我们需要在迭代器类里访问节点Node类型的成员变量，所以可以将Iterator设为Node类的友元类，或者开放Node类的权限。

迭代器的构造函数的实现：

ListIterator(Node* node)
	:_node(node)
{}

我这里设计的比较简单，只实现了单参的构造函数，可以支持基本的隐式类型转换。

重载*:

Ref operator* () {
	return _node->_val;
}

重载迭代器的移动操作符++、--:

Self& operator++() {
	_node = _node->_next;
	return *this;
}
Self& operator++(int) {//后置++
	Self temp(*this);
	_node = _node->_next;
	return temp;
}

Self& operator--() {
	_node = _node->_pre;
	return *this;
}

Self& operator--(int) {//后置--
	Self temp(_node);
	_node = _node->_pre;
	return temp;
}

重载->：

Ptr operator ->() {
	return &_node->_val;
}

由于我们想把迭代器当指针使用，重载->是必要的，那么为什么是返回节点元素的地址呢？其实当我们在使用迭代器->时，编译器会自动优化成->->。比如我们的节点元素类型是一个类，我们有时需要访问节点元素类中的成员变量，此时希望通过迭代器->能直接访问到。
观察以下代码：
在这里插入图片描述
其中t是一个结构体类型，当我们用list存这样的节点并试图遍历节点中的a1的值时，(*it)得到的是t类型，如果我们想要输出t中的a1，就必须写成（*it）.a1。
我们希望迭代器能像指针一样，it->a1这样就能直接访问a1的元素，于是我们重载一个->,这个->的作用其实等价于it->->a1也就是it.operator->()->a1。这是编译器帮我们优化了。
在这里插入图片描述

反向迭代器

方向迭代器和普通的迭代器功能基本一致，只不过由于起始位置是在哨兵位，解引用时需要先往前面移动一个节点再返回其节点元素值

Ref operator* () {
	Self temp(_node);
	temp++;
	return temp._node->_val;
}

此外移动的方向也和普通迭代器相反，是向节点的前一个节点方向移动。

	Self& operator--() {
		_node = _node->_next;
		return *this;
	}
	Self& operator--(int) {//后置--
		Self temp(*this);
		_node = _node->_next;
		return temp;
	}

	Self& operator++() {
		_node = _node->_pre;
		return *this;
	}

	Self& operator++(int) {//后置++
		Self temp(_node);
		_node = _node->_pre;
		return temp;
	}

其它功能和普通迭代器几乎一致。

list与vector的比较

list和vector各种代表着的是链表和数组。它们之间的具体区别其实在前面已经讲过了。
链表的优缺点
顺序表的优缺点
迭代器的区别：

vector的迭代器是原生态指针，list的迭代器是对原生态指针(节点指针)进行封装。
vector在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效。
而list插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响

实现list类

#define _CRT_SECURE_NO_WARNINGS 1
#include<assert.h>
#include<iostream>

namespace bite {

	//节点
	template<class T>
	class ListNode {
	public:
		ListNode(const T& val = T())
			:_val(val)
			, _pre(nullptr)
			, _next(nullptr)
		{

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


	//反向迭代器
	template<class T, class Ref, class Ptr>
	class ReserveListIterator {
	public:
		typedef ListNode<T> Node;
		typedef ReserveListIterator<T, Ref, Ptr> Self;

		ReserveListIterator(Node* node)
			:_node(node)
		{}
		//重载
		Ref operator* () {
			Self temp(_node);
			temp++;
			return temp._node->_val;
		}

		Self& operator--() {
			_node = _node->_next;
			return *this;
		}
		Self& operator--(int) {//后置--
			Self temp(*this);
			_node = _node->_next;
			return temp;
		}

		Self& operator++() {
			_node = _node->_pre;
			return *this;
		}

		Self& operator++(int) {//后置++
			Self temp(_node);
			_node = _node->_pre;
			return temp;
		}

		bool operator!=(const Self& p) {
			return _node != p._node;
		}
		//T*/const T*
		Ptr operator ->() {
			return &_node->_val;
		}
		bool operator==(const Self& p) {
			return _node == p._node;
		}
		Node* _node;
	};


	//迭代器
	template<class T, class Ref, class Ptr>//T表示节点数据类型，Ref表示T&、Ptr表示T*类型
	class ListIterator {
	public:
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;

		ListIterator(Node* node)
			:_node(node)
		{}
		//重载
		Ref operator* () {
			return _node->_val;
		}

		Self& operator++() {
			_node = _node->_next;
			return *this;
		}
		Self& operator++(int) {//后置++
			Self temp(*this);
			_node = _node->_next;
			return temp;
		}

		Self& operator--() {
			_node = _node->_pre;
			return *this;
		}

		Self& operator--(int) {//后置--
			Self temp(_node);
			_node = _node->_pre;
			return temp;
		}

		bool operator!=(const Self& p) {
			return _node != p._node;
		}
		//T*/const T*
		Ptr operator ->() {
			return &_node->_val;
		}
		bool operator==(const Self& p) {
			return _node == p._node;
		}
		Node* _node;
	};

	template<class T>
	class list {
	public:
		//节点
		typedef ListNode<T> Node;
		typedef Node* pNode;

		//迭代器
		typedef ListIterator<T, T&, T*> Iterator;
		typedef ListIterator<T, const T&, const T*> const_Iterator;
		typedef ReserveListIterator<T, T&, T*> Reserve_Iterator;
		typedef ReserveListIterator<T, const T&, const T*> const_Reserve_Iterator;
		

	public:

		void Empty_Init() {
			head = new Node;
			head->_pre = head;
			head->_next = head;
			head->_val = -1;
			sz = 0;
		}

		//构造
		list()
		{
			Empty_Init();
		}

		list(size_t n, const T& value = T())
		{
			Empty_Init();
			for (size_t i = 0; i < n; i++) {
				push_back(value);
			}
			sz = n;
		}

		//拷贝构造
		list(const list<T>& lt) {
			Empty_Init();
			for (auto& it : lt) {
				push_back(it);
			}
		}

		//迭代器构造
		template <class IIterator>
		list(IIterator first, IIterator last) {
			Empty_Init();
			while (first != last) {
				push_back(*first);
				first++;
			}
		}

		//析构
		~list() {
			Iterator it = begin();
			while (it != end()) {
				it = erase(it);
			}
			delete head;
			sz = 0;
		}

		void swap(list<T> lt) {
			std::swap(lt.head, head);
			std::swap(sz, lt.sz);
		}


		//普通迭代器
		Iterator begin() {
			return head->_next;
		}
		Iterator end() {
			return head;
		}
		//const迭代器
		const_Iterator begin() const {
			return head->_next;
		}
		const_Iterator end() const {
			return head;
		}
		//反向迭代器
		 Reserve_Iterator  rbegin() {
			 return head;
		 }
		 Reserve_Iterator  rend() {
			 return head->_next;
		 }

		 const_Reserve_Iterator rbegin() const {
			 return head;
		 }
		 const_Reserve_Iterator rend() const {
			 return head->_next;
		 }

		//插入
		void insert(Iterator pos, const T& val) {
			Node* newnode = new Node(val);
			Node* cur = pos._node;

			newnode->_pre = cur->_pre;
			newnode->_next = cur;
			cur->_pre->_next = newnode;
			cur->_pre = newnode;
			sz++;
		}
		//删除
		Iterator erase(Iterator pos) {
			assert(sz > 0);
			Node* cur = pos._node;
			Node* t = cur->_next;
			cur->_pre->_next = cur->_next;
			cur->_next->_pre = cur->_pre;
			delete cur;
			sz--;
			return t;
		}
		//尾插
		void push_back(const T& val) {
			insert(end(), val);
			//size++;
		}


		//操作符重载
		list<T>& operator = (list<T> lt) {
			swap(lt);
			return *this;
		}


		// List Capacity
		size_t size()const {
			return sz;
		}
		bool empty()const {
			return sz == 0;
		}

	private:
		pNode head;
		size_t sz;
	};
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/524582.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux中shell脚本的学习第一天，编写脚本的规范，脚本注释、变量，特殊变量的使用等，包含面试题

Linux中shell脚本的学习第一天，编写脚本的规范，脚本注释、变量，特殊变量的使用等，包含面试题

4月7日没参加体侧的我自学shell的第一天 Shebang 计算机程序中&#xff0c;shebang指的是出现在文本文件的第一行前两个字符 #&#xff01; 1)以#!/bin/sh 开头的文件&#xff0c;程序在执行的时候会调用/bin/sh, 也就是bash解释器 2)以#!/usr/bin/python 开头的文件&#…
阅读更多...
科研学习|研究方法——扎根理论三阶段编码如何做？

科研学习|研究方法——扎根理论三阶段编码如何做？

一、背景介绍 “主题标引”意指对文献内容进行分析, 然后对文献所表达的中心思想、所讨论的基本问题以及研究的对象等进行提取, 以形成主题概念, 然后在此基础上把可检索的主题词表示出来, 再将这些主题词按一定顺序 (如字顺) 排列, 对论述相同主题内容的文献加以集中, 从而提高…
阅读更多...
vmware和ubuntu的问题与解决

vmware和ubuntu的问题与解决

1.问题与对策 最近使用vmware安装ubuntu16和ubuntu20&#xff0c;遇到了挺多的问题&#xff0c;如下 ubuntu在用过多次后&#xff0c;重启后登录用户名后会出现花屏的现象。 解决方案如下 在键盘上同时按键&#xff1a;Ctrl Alt F4&#xff0c;进入命令行模式&#xff0c;…
阅读更多...
Hive3.0.0建库表命令测试

Hive3.0.0建库表命令测试

Hive创建表格格式如下&#xff1a; create [external] table [if not exists] table_name [(col_name data_type [comment col_comment],)] [comment table_comment] [partitioned by(col_name data_type [comment col_comment],)] [clustered by (col_name,col_name,...)…
阅读更多...
三防平板定制服务：亿道信息与个性化生产的紧密结合

三防平板定制服务：亿道信息与个性化生产的紧密结合

在当今数字化时代&#xff0c;个性化定制已经成为了市场的一大趋势&#xff0c;而三防平板定制服务作为其中的一部分&#xff0c;展现了数字化技术与个性化需求之间的紧密结合。这种服务是通过亿道信息所提供的技术支持&#xff0c;为用户提供了满足特定需求的定制化三防平板&a…
阅读更多...
leetcode代码记录（下一个更大元素 I

leetcode代码记录（下一个更大元素 I

目录 1. 题目&#xff1a;2. 我的代码&#xff1a;小结&#xff1a; 1. 题目&#xff1a; nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。 给你两个 没有重复元素 的数组 nums1 和 nums2 &#xff0c;下标从 0 开始计数&#x…
阅读更多...
Severt和tomcat的使用(补充）

Severt和tomcat的使用(补充）

打包程序 在pom.xml中添加上述代码之后打包时会生成war包并且包的名称是test 默认情况打的是jar包.jar里量但是tomcat要求的是war包. war包Tomcat专属的压缩包. war里面不光有.class还有一些tomcat要求的配置文件(web.xml等)还有前端的一些代码(html, css, js) 点击其右边的m…
阅读更多...
【大数据】安装hive-3.1.2

【大数据】安装hive-3.1.2

1、上传HIVE包到/opt/software目录并解压到/opt/modules/ tar -zxvf apache-hive-3.1.2-bin.tar.gz -C /opt/modules/ 2、修改路径 mv /opt/modules/apache-hive-3.1.2-bin/ /opt/modules/hive 3、将hIVE下的bin目录加入到/etc/profile中 export HIVE_HOME/opt/module…
阅读更多...
机器学习（30）

机器学习（30）

文章目录 摘要一、文献阅读1. 题目2. abstract3. 网络架构3.1 Sequence Generative Adversarial Nets3.2 SeqGAN via Policy Gradient3.3 The Generative Model for Sequences3.4 The Discriminative Model for Sequences(CNN) 4. 文献解读4.1 Introduction4.2 创新点4.3 实验过…
阅读更多...
Svg Flow Editor 原生svg流程图编辑器（五）

Svg Flow Editor 原生svg流程图编辑器（五）

系列文章 Svg Flow Editor 原生svg流程图编辑器&#xff08;一&#xff09; Svg Flow Editor 原生svg流程图编辑器&#xff08;二&#xff09; Svg Flow Editor 原生svg流程图编辑器&#xff08;三&#xff09; Svg Flow Editor 原生svg流程图编辑器&#xff08;四&#xf…
阅读更多...
如何自定义项目启动时的图案

如何自定义项目启动时的图案

说明&#xff1a;有的项目启动时&#xff0c;会在控制台输出下面的图案。本文介绍Spring Boot项目如何自定义项目启动时的图案&#xff1b; 生成字符图案 首先&#xff0c;找到一张需要设置的图片&#xff0c;使用下面的代码&#xff0c;将图片转为字符文件&#xff1b; impo…
阅读更多...
蓝桥杯练习系统（算法训练）ALGO-957 P0703反置数

蓝桥杯练习系统（算法训练）ALGO-957 P0703反置数

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 一个整数的反置数指的是把该整数的每一位数字的顺序颠倒过来所得到的另一个整数。如果一个整数的末尾是以0结尾&#xff0c;那么在它的…
阅读更多...
Java: LinkedList的模拟实现

Java: LinkedList的模拟实现

一、双向链表简介 上一篇文章我介绍了单向链表的实现&#xff0c;单向链表的特点是&#xff1a;可以根据上一个节点访问下一个节点&#xff01;但是&#xff0c;它有个缺点&#xff0c;无法通过下一个节点访问上一个节点&#xff01;这也是它称为单向链表的原因。 那么&#x…
阅读更多...
Codigger Desktop：用户体验与获得收益双赢的革新之作（一）

Codigger Desktop：用户体验与获得收益双赢的革新之作（一）

上周&#xff0c;我们介绍了Codigger Desktop凭借其强大的功能、稳定的性能以及人性化的设计&#xff0c;成为了广大开发者的得力助手。Codigger Desktop除了是开发者的利器外&#xff0c;它以其出色的用户体验和创新的收益模式&#xff0c;为用户提供了一个全新的选择。Codigg…
阅读更多...
leetcode代码记录（下一个更大元素 II

leetcode代码记录（下一个更大元素 II

目录 1. 题目&#xff1a;2. 我的代码&#xff1a;小结&#xff1a; 1. 题目&#xff1a; 给定一个循环数组 nums &#xff08; nums[nums.length - 1] 的下一个元素是 nums[0] &#xff09;&#xff0c;返回 nums 中每个元素的 下一个更大元素 。 数字 x 的 下一个更大的元素…
阅读更多...
微信小程序真机无法下载文件

微信小程序真机无法下载文件

问题&#xff1a; 1、真机无法展示加了防盗链的图片 2、真机无法下载pdf等文件 文件服务器供应商&#xff1a;腾讯 解决&#xff1a; 1、在文件服务器控制台加上微信小程序的域名白名单&#xff1a;servicewechat.com 具体可查看&#xff1a;对象存储 设置防盗链-控制台指…
阅读更多...
mysql结构与sql执行流程

mysql结构与sql执行流程

Mysql的大体结构 客户端&#xff1a;用于链接mysql的软件 连接池&#xff1a; sql接口&#xff1a; 查询解析器&#xff1a; MySQL连接层 连接层&#xff1a; 应用程序通过接口&#xff08;如odbc,jdbc&#xff09;来连接mysql&#xff0c;最先连接处理的是连接层。 连接层…
阅读更多...
STM32CubeMX+MDK通过I2S接口进行音频输入输出（全双工读写一个DMA回调）

STM32CubeMX+MDK通过I2S接口进行音频输入输出（全双工读写一个DMA回调）

一、前言 目前有一个关于通过STM32F411CEUx的I2S总线接口控制SSS1700芯片进行音频输入输出的研究。 SSS1700 是具有片上振荡器的 3S 高度集成的USB音频控制器芯片 。 SSS1700 功能支持96 KHz 24 位采样率&#xff0c;带外部音频编解码器&#xff08;24 位/96KHz I2S 输入和输出…
阅读更多...
Java常用API_正则表达式_检验字符串是否满足规则——基础使用方法及综合练习

Java常用API_正则表达式_检验字符串是否满足规则——基础使用方法及综合练习

正则表达式可以校验字符串是否满足一定的规则&#xff0c;并用来校验数据格式的合法性。 简单举例&#xff1a; 校验一个qq号是否符合要求 要求&#xff1a;6位到20位之内&#xff0c;不能以0开头&#xff0c;必须全是数字 代码演示&#xff1a; public class Test1 {public…
阅读更多...
【CicadaPlayer】视频切换/音视频同时切换

【CicadaPlayer】视频切换/音视频同时切换

G:\CDN\all_players\CicadaPlayer-github-0.44\mediaPlayer\SuperMediaPlayer.hCicadaPlayer https://github.com/alibaba/CicadaPlayer可以clone 整个仓库的历史 git clone --bare https://github.com/username/project.git整体架构 ：根据这个更容易理解：切换就是judgeFunc…
阅读更多...
最新文章

Copyright @ 2022~2023