当前位置： 首页 > article >正文

通过比较list与vector在简单模拟实现时的不同进一步理解STL的底层

article 2024/12/24 11:33:54

 cplusplus.com/reference/list/list/?kw=list

当我们大致阅读完list的cplusplus网站的文档时，我们会发现它提供的接口大致上与我们的vector相同。当然的，在常用接口的简单实现上它们也大体相同，但是它们的构造函数与迭代器的实现却大有不同。(食用本文时建议与文末的模拟实现代码一起食用，效果更佳)

一，list与vector在构造函数上的不同

 1.1成员封装的不同

我们在vector中，需要封装的成员只有我们顺序表的起始指针，有效元素的末尾指针，以及用来记录空间结束位置的指针：

如果我们在list中，便无法再这样封装，因为我们的list存放数据的内存并不连续，所以我们需要对链表的节点用额外的结构体封装，而在原本的list类里面我们封装的成员则是链表的头结点：

template<class T>
struct list_node
{
	T _data;
	list_node<T>* _next;
	list_node<T>* _prev;

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

1.2迭代器的封装的不同 

在vector中，迭代器可以直接简单的设置为我们存储数据类型的对应指针。但是在list中，我们发现迭代器需要指向的是一个节点，有人说那我直接照搬vector不也OK。但是这时候就会有个问题，因为我们的节点相当于一个自定义类型，后面在进行调用的时候不可避免的会去调用它的构造函数，同时我们迭代器又会有许多的函数去使用，所以迭代器也需要额外的用一个类来封装。

template<class T, class Ref, class Ptr>
struct list_iterator//tip
{
	typedef list_node<T> Node;
	typedef list_iterator<T, Ref, Ptr> Self;
};

TIPS:这里将迭代器与结点成员设置为公开是为了方便list类的调用，实际上我们在使用list时也无法直接调用这些成员，这也是对成员的保护方式。

二，list与vector在迭代器上的不同(重点) 

 2.1对迭代器的const修饰

在我们的vector中，由于我们的迭代器本身就是我们存储数据的类型的相应指针，所以我们可以通过直接加const的方式来实现我们的const_iterator。但是在list中，由于我们的迭代器是指向一个自定义类型的指针，而我们的自定义类型中存储数据。如果我们直接用const来修饰，会发现我们此时无法修改迭代器指向的结点，从而无法完成我们后续的遍历。如果我们要为const来再额外封装一个类，会使代码看上去非常冗余。

在stl的源码中有着这样的几行代码：

template <class T, class Ref, class Ptr>
struct __slist_iterator : public __slist_iterator_base
{
  typedef __slist_iterator<T, T&, T*>             iterator;
  typedef __slist_iterator<T, const T&, const T*> const_iterator;
  typedef __slist_iterator<T, Ref, Ptr>           self;

  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef __slist_node<T> list_node;

我们发现，它的模板参数有三个。其实由于我们的目的是为了源结点中的值无法被改变，只需要我们在返回结点中的值时加上const修饰，而我们获取存储数据的方式无非两种，一种是对迭代器解引用(其中_node是当前迭代器指向的结点)：

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

或者通过->来获取：

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

 所以我们只需要对T*与T&在模板实例化时用const修饰即可：

typedef list_iterator<T,T&,T*> iterator;//tip
typedef list_iterator<T,const T&,const T*> const_iterator;//tip

 TIP:在迭代器的类型中我们又分为随机，双向和单向迭代器，从左向右为父级关系。在使用库中的sort时对list无法使用快排，因为他是双向迭代器，而vector之所以可以使用是因为他是随机迭代器。

2.2list反向迭代器的实现

通过上面的多个模板参数的引出，我们可以对反向的迭代器Reverse_iterator来封装进行封装：

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

原理其实就是我们2.1中介绍到的，这里我们直接给出模拟实现代码。

三，list与vector其他方面不同的总结(不仅是模拟实现上)

附件：list的简单模拟实现代码(常用接口) 

/
#pragma once
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <list>
using namespace std;

namespace ELY {

	template<class T>
	struct list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		list_node(const T& x = T())
			:_data(x)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};

	template<class T,class Ref,class Ptr>
	struct list_iterator//tip
	{
		typedef list_node<T> Node;
		typedef list_iterator<T,Ref,Ptr> Self;
		Node* _node;
		list_iterator(Node* node)
			:_node(node)
		{}

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

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

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

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

		Self operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		Self operator++(int)
		{
			Self tmp(*this);
			_node = _node->_next;
			return tmp;
		}


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


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

	template<class T>
	class list
	{
		void empty_init()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}
	public:
		typedef list_node<T> Node;
		typedef list_iterator<T,T&,T*> iterator;//tip
		typedef list_iterator<T,const T&,const T*> const_iterator;//tip
		list()
		{
			empty_init();
		}

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

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

		list(size_t n, const T& val = T())
		{
			empty_init();
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		iterator begin()
		{
			return iterator(_head->_next);
		}

		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		iterator end() 
		{
			return iterator(_head);
		}

		const_iterator end() const
		{
			return const_iterator(_head);
		}


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

			newnode->_next = _head;
			newnode->_prev = tail;

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

		iterator insert(iterator pos, const T& val)//tip
		{
			Node* newnode = new Node(val);
			Node* cur = pos._node;

			cur->_prev->_next = newnode;
			newnode->_prev = cur->_prev;

			cur->_prev = newnode;
			newnode->_next = cur;
			return iterator(newnode);
		}

		iterator push_front(const T& val)
		{
			return insert(begin(), val);
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* cur = pos._node;

			cur->_next->_prev = cur->_prev;
			cur->_prev->_next = cur->_next;
			
			pos = cur->_next;
			delete cur;

			return pos;
		}

		iterator pop_front()
		{
			return erase(begin());
		}

		iterator pop_back()
		{
			return erase(--end());
		}

		void clear()
		{
			auto i = begin();
			while (i != end())
			{
				i = erase(i);
			}
		}

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

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

	private:
		Node* _head;
	};
}
/
mylist.h


http://www.kler.cn/a/355019.html

相关文章：

  • 问题解决：发现Excel中的部分内容有问题。是否让我们尽量尝试恢复? 如果您信任此工作簿的源，请单击“是”。
  • [Unity Shader][图形渲染] Shader数学基础11 - 复合变换详解
  • Ubuntu硬盘分区及挂载（命令行）
  • PostgreSQL标识符长度限制不能超过63字节
  • 条款33 对auto形参使用decltype以std::forward它们
  • ARP..
  • 标准C库总结
  • 第1节 入门
  • WLAN技术
  • 【前端】Matter：基础概念与入门
  • 基于51单片机的PID直流电机调速系统（程序+Proteus仿真+报告+原理图）
  • Rider + xmake DX12 开发环境
  • 【AAOS】Android Automotive 15模拟器源码下载及编译
  • tensorRT安装详解（linux与windows）
  • Redis总结（官方文档解读）
  • 【工具篇】MLU运行XInference部署手册
  • 安全见闻笔记
  • 春日学习伴侣：Spring Boot答疑平台
  • 03.顺序表实现
  • JS_用发布订阅模式解耦
  • 云手机：社交平台运营的热门工具
  • 王爽汇编语言第三版实验1
  • 基于springboot的学习平台系统
  • 两种常见的磁盘分区样式及它们的区别总结
  • HttpUtils 详解
  • k8s jenkins 2.421动态创建slave