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

  • 开发
  • 37

文章目录

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;
	};
}
阅读全部

相关推荐

  5. 【Vue】实现的底层原理

    2024-04-08 13:38:01       41 阅读

  7. C#面：AJAX的底层实现原理

    2024-04-08 13:38:01       31 阅读

  9. DNS负载均衡的底层实现原理

    2024-04-08 13:38:01       36 阅读

  10. Mysql事务隔离级别及其底层原理

    2024-04-08 13:38:01       64 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-08 13:38:01       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-08 13:38:01       100 阅读

  9. 在Django里面运行非项目文件

    2024-04-08 13:38:01       82 阅读

  19. Python语言-面向对象

    2024-04-08 13:38:01       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-04-08 13:38:01       85 阅读

热门阅读

  8. 利用hdfs gateway挂载NFS到本地

    2024-04-08 13:38:01       37 阅读

  9. GitOps是DevOps的下一个风口吗？

    2024-04-08 13:38:01       39 阅读

  10. FDA 上市库 Mini | 药物筛选 | MCE

    2024-04-08 13:38:01       36 阅读

  11. HyperBus协议--HyperFLASH中Program Suspend 功能的理解

    2024-04-08 13:38:01       33 阅读

  21. 3.9 Python格式化字符串

    2024-04-08 13:38:01       31 阅读

  22. 蓝桥杯练习题 —— 圆的面积（python）

    2024-04-08 13:38:01       35 阅读

  27. abc348 D~F题解

    2024-04-08 13:38:01       39 阅读

  28. wpf Validation.ErrorTemplate

    2024-04-08 13:38:01       33 阅读