【c++】:list模拟实现“任意位置插入删除我最强ƪ(˘⌣˘)ʃ“

这篇具有很好参考价值的文章主要介绍了【c++】:list模拟实现“任意位置插入删除我最强ƪ(˘⌣˘)ʃ“。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 文章来源地址https://www.toymoban.com/news/detail-797891.html

 

文章目录

  • 前言
  • 一.list的基本功能的使用
  • 二.list的模拟实现
  • 总结

 


前言

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

 

 

一、list的基本功能的使用

我们先看看list有哪些接口:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

其实list的接口并不多,对于链表而言我们在数据结构中就学过,无非就是头插尾插,头删尾删以及任意位置的插入删除等,下面我们就讲解一下一些常用的接口该如何使用:

首先要注意包list的头文件#include <list>

void test1()
{
	list<int> ls;
	ls.push_back(1);
	ls.push_back(2);
	ls.push_back(3);
	ls.push_back(4);
	list<int>::iterator it = ls.begin();
	while (it != ls.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}
int main()
{
	test1();
	return 0;
}

 上面是尾插push_back接口的使用和迭代器的使用,迭代器还是与前面的容器一样都是这样的用法,但是他们的底层实现已经天差万别了,我们模拟的时候会详细的介绍。

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

接下来我们头插一个99.

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio size是链表中的元素个数,empty是判断链表是否为空:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

front返回链表中第一个节点值的引用,back返回链表中最后一个节点的引用。

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

void test2()
{
	list<int> ls;
	ls.push_back(1);
	ls.push_back(2);
	ls.push_back(3);
	ls.push_back(4);
	for (auto e : ls)
	{
		cout << e << " ";
	}
	cout << endl;
	ls.pop_back();
	ls.pop_front();
	for (auto e : ls)
	{
		cout << e << " ";
	}
	cout << endl;
}
int main()
{
	//test1();
	test2();
	return 0;
}

 pop_back是尾删,pop_front是头删。接下来我们再演示一下插入,删除,清空就结束。

clear():将list中的有效元素清空:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 insert():

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 我们已经学过vector,可以发现这里insert接口参数都是一样的用迭代器进行插入:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

erase也是同理:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio 在这里我们为什么--了一下end()才删掉最后一个元素呢?因为end()是哨兵位的头结点,我们不能将头结点删除:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 由于list底层是双向带头循环链表,所以头结点的前一个就是最后一个元素。

 我们之前讲过vector的迭代器失效问题,那么erase会导致迭代器失效吗?答案是一定会失效,因为pos位置都被删掉了,要解决这个办法我们只需要把pos后的迭代器给it即可,如下图:

void test3()
{
	list<int> ls;
	ls.push_back(1);
	ls.push_back(2);
	ls.push_back(3);
	ls.push_back(4);
	list<int>::iterator it = ls.begin();
	while (it != ls.end())
	{
		ls.erase(it);
		++it;
	}
	cout << endl;
}
int main()
{
	//test1();
	//test2();
	test3();
	return 0;
}

我们的目的是依次删除链表中的元素,然后当我们运行起来:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

这时候我们像刚刚将的那样解决一下:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio 这也证明了在erase一个pos位置后,这个位置的迭代器会失效。

当然还有一些功能对我们刷题很有用,如下:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 这些功能有链表的拼接,合并,反转等大家刷题的时候想用可直接查看原文档。

接下来我们就进入模拟list的环节。

 二、list的模拟实现

同样我们先看一下STL源码:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 我们可以看到对于单个节点的实现源码中用了struct,对于c++中是用struct还是用class是视情况而定的,如果你想要这个类里面的东西全部公开那就用struct,因为struct中的成员默认就是公有的。

下面的迭代器我们可以看到很复杂,这就与我们刚开始所说的迭代器的底层实现已经发生了巨大改变,我们讲到迭代器会详细的介绍,这里就先讲解list中的成员:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio 我们可以看到库中对于list也是用空间配置器开空间的与vector一样,然后在list中有一个node的成员,这个是什么呢?看下图:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 link_type其实就是list_node*的重命名,也就是说实际上是一个链表节点的指针。然后通过我们之前对双向带头循环链表的知识不难判断这里就是哨兵位头结点,接下来我们看一下list的构造函数:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

这个empty_initialize是什么呢?看下图:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

原来这就是一个对头节点进行初始化的函数,先开一个头结点,然后让这个头结点的前后指针都指向自己。

看完了源码现在我们就正式的开始模拟实现:

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

namespace sxy
{
	template<class T>
	struct list_node
	{

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

	}
}

 首先我们为了防止和库中命名冲突将要写的list放入命名空间,因为list要容纳任意类型所以我们必须用模板参数,对于一个链表节点我们和库中一样都用struct,有一个该类型的prev指针和一个next指针,然后还有一个模板类型的data变量。接下来我们创建list类,由于要经常用到节点指针所以我们直接将节点重命名为node,然后创建一个哨兵位的头结点_head,我们也像库中实现的那样专门用一个函数去初始化这个头节点,初始化头结点的步骤是:先给_head指针开一个节点空间,然后将这个节点的前后两个指针都指向自己。

对于构造函数,我们直接初始化一下头结点即可:

        list()
		{
			empty_init();
		}

 接下来我们直接写一个push_back接口:

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

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 对于尾插来说,就是将最后一个节点的next连接新节点,新节点的prev连上前一个节点,然后再将新节点与头结点相连形成循环即可。我们可以看到给newnode开空间的时候我们初始化为x,那么这个时候一定要想到list_node的构造函数是否写了,因为我们没写所以给list_node写一个带缺省值的构造函数:

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

		}
		list_node<T>* _prev;
		list_node<T>* _next;
		T _data;
	};

在这里缺省值一定是T类型的匿名对象,因为list是针对任何类型的,用匿名对象做缺省值会去调用其类型的默认构造。 

这样我们的尾插应该是成功了,如下图:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 下面我们开始实现迭代器:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

如上图,对于list的迭代器我们不能再像vector一样简单的让指针加加减减了,因为链表中每个节点的地址是不连续的,指针++并不是下一个节点的地址,这个时候我们看看库中是如果搞定迭代器的:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio 通过源码我们发现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& it)
		{
			return _node != it._node;
		}
		bool operator==(const self& it)
		{
			return _node == it._node;
		}
	};

 我们首先从迭代器的构造函数开始讲解:

        list_iterator(node* n)
			:_node(n)
		{

		}

 因为我们的迭代器本质是一个链表的节点,所以我们的构造函数的参数也是一个节点,初始化就是用这个节点初始化即可。

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

 解引用符号本质就是找到其节点所保存的数据,所以返回data即可,返回类型用T&可以减少拷贝。

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

 前置加加就比较简单了,对于迭代器的++其实就是指向下一个节点,所以我们让节点变成next即可,由于这里++后还是个迭代器我们必须返回其迭代器,而迭代器类型为list_iterator<T>太过繁琐我们直接typedef为self,所以返回self&即可。

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

对于后置++而言我们要用一个tmp变量,tmp是此迭代器的拷贝构造,虽然我们没有写拷贝构造但是编译器默认生成的拷贝构造完全可以完成拷贝一个节点的任务,对于一个节点浅拷贝就刚好满足我们的需求。

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

 前置--和后置--与++同理。

对于迭代器来说,我们需要判断两个迭代器是否相等是否不相等:

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

 判断是否相等很简单,直接判断两个迭代器所在的节点是否相等。

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

 解决完迭代器后一定要在list类中重新定义一下迭代器,不然名字太长了,如下:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

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

 因为我们的迭代器实现是用struct重新创建的,所以返回的时候我们不能像之前那样直接返回头结点,我们返回的类型必须是迭代器,所以对于begin我们返回一个匿名对象并且用头结点的下一个节点初始化。而end就用头结点即可,如下图:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

下面我们试试迭代器是否能正常使用:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio 很明显是可以使用的,我们之前实现过string,vector,迭代器都有相应的const版本,那么我们这个迭代器如何实现const版本呢?

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 我们看到对于const对象现在确实不能使用迭代器,我们可以这样吗?

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

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 我们看到确实能正常编译了,但是对于const迭代器而言我们的目的是不可以修改迭代器所指向的内容,而迭代器本身可以++ --等,那么现在符合我们的预期吗,如下图:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 对于const对象来讲现在竟然可以修改其内容了,所以上面我们写的const迭代器一定是错误的,那么该怎么办呢?

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 同样上图中对于const迭代器的使用也是不正确的,如果将const位于迭代器之前这样迭代器就无法++ --了,也是达不到我们的预期的。

所以我们给出第一种解决办法:

    template<class T>
	struct list_const_iterator
	{
		typedef list_node<T> node;
		typedef list_const_iterator<T> self;
		node* _node;
		list_const_iterator(node* n)
			:_node(n)
		{

		}
		const 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& it)
		{
			return _node != it._node;
		}
		bool operator==(const self& it)
		{
			return _node == it._node;
		}
	};

const迭代器的不同点就是对于*解引用的内容不可以被修改,所以我们将operator*的返回值设为const T&,这样是可以的。

        typedef list_node<T> node;
		typedef list_iterator<T> iterator;
		typedef list_const_iterator<T> const_iterator;
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

但是这样实现会不会太浪费了呢?const与普通迭代器的区别只是operator的返回值不同,其他的函数都是一样的,有什么办法可以只用普通迭代器就能既完成普通的又完成const迭代器呢?答案是有的,我们之前看源码可以看到源码中的迭代器的模板参数比我们多了两个,这就是解决这类问题的。如下:

    template<class T,class Ref>
	struct list_iterator
	{
		typedef list_node<T> node;
		typedef list_iterator<T,Ref> self;
		node* _node;
		list_iterator(node* n)
			:_node(n)
		{

		}
		Ref 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& it)
		{
			return _node != it._node;
		}
		bool operator==(const self& it)
		{
			return _node == it._node;
		}
	};
        typedef list_node<T> node;
		typedef list_iterator<T,T&> iterator;
		typedef list_iterator<T,const T&> const_iterator;
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 我们直接多给一个模板参数Ref,让operator *的返回值为Ref,然后我们在list中typedef的时候将list_iterator<T,T&>为普通迭代器,list_iterator<T,const T&>为const迭代器,这样一来一旦有const对象调用迭代器就会调用这个const T&的参数,然后普通迭代器中operator *的返回值就变成了constT&.对于迭代器来说,要么是原生指针,要么是自定义类型对原生指针的封装,模拟指针的行为。

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 对于上图中这样的自定义类型我们是无法去直接打印链表中的值的,如下图:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

当然也确实可以打印,但是会比较麻烦,比如下面这样:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio 所以我们想要让自定义类型的访问也方便应该让迭代器重载->操作符,不然就会像上图中圈出来的那样访问太过麻烦,而库中对于这方面的解决办法也是多加一个模板参数,如下:

    template<class T,class Ref,class Ptr>
	struct list_iterator
	{
		typedef list_node<T> node;
		typedef list_iterator<T,Ref,Ptr> self;
		node* _node;
		list_iterator(node* n)
			:_node(n)
		{

		}
		Ref 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;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		bool operator!=(const self& it)
		{
			return _node != it._node;
		}
		bool operator==(const self& it)
		{
			return _node == it._node;
		}
	};
        typedef list_node<T> node;
		typedef list_iterator<T,T&,T*> iterator;
		typedef list_iterator<T,const T&,const T*> const_iterator;

这样就解决了上述我们所说的问题。

接下来我们实现insert接口:

        void insert(iterator pos, const T& x)
		{
			node* cur = pos._node;
			node* prev = cur->_prev;
			node* newnode = new node(x);
			newnode->_next = cur;
			cur->_prev = newnode;
			newnode->_prev = prev;
			prev->_next = newnode;
		}

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

对于插入我们并不陌生,只需要将新节点插入到pos的前一个节点和pos位置中间即可,让新节点的next连接pos位置的节点,pos位置的节点的prev连接新节点,再将新节点与prev节点相连即可。

实现了insert,我们就可以复用实现头插尾插了:

        void push_back(const T& x)
		{
			insert(end(), x);
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}

 接下来我们实现erase接口:

        iterator erase(iterator pos)
		{
            assert(pos!=end());
			node* prev = pos._node->_prev;
			node* tail = pos._node->_next;
			prev->_next = tail;
			tail->_prev = prev;
			delete pos._node;
			return iterator(tail);
		}

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

 对于erase,首先我们是不可以删除哨兵位的头结点的,所以我们断言一下,end()的位置就是头结点的位置。删除pos位置就是将pos 的前一个节点和pos的后一个节点相互连接即可。然后delete掉pos位置的节点,前面我们讲过为了防止erase后迭代器失效我们要返回pos位置节点的下一个节点,所以我们返回一个迭代器的匿名对象,用pos的下一个节点初始化即可。

有了erase接口我们就可以复用头删,尾删了:

        void pop_front()
		{
			erase(begin());
		}
		void pop_back()
		{
			erase(_head->_prev);
		}

下面实现一下clear()接口:

        void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

在这个接口就体现出我们实现erase让其返回下一个节点的重要性了,如果不这样做这里迭代器失效是无法持续删除的。

        void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				//it = erase(it);
				erase(it++);
			}
		}

 当然我们也可以用后置++,也可以完成c连续删除的任务。

接下来是析构函数:

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

 析构函数和clear的区别在于析构函数要释放哨兵位的头结点,释放后将头结点置为空。

接下来是用迭代器区间构造:

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

 首先我们用迭代器区间构造是一个个push_back,而我们要用push_back()必须得有哨兵位的头结点,所以我们先对空初始化然后依次push_back()即可。对于迭代器区间构造我们之前说过,这里的迭代器可以是任意类型的比如string,vector,所以我们必须用一个模板参数Iterator。

拷贝构造函数:

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

 对于拷贝构造函数,我们先讲头结点初始化,然后依次尾插ls的节点即可。

当然还有一种现代写法的拷贝构造函数:

        list(const list<T>& ls)
		{
            empty_init();
			list<T> tmp(ls.begin(), ls.end());
			swap(tmp);
		}
		void swap(list<T>& ls)
		{
			std::swap(_head, ls._head);
		}

 我们先开一个头结点然后初始化,用迭代器区间构造一个与ls对象一样的tmp链表,然后再将tmp和*this交换交换指针指向即可。

接下来是赋值重载:

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

赋值重载就很简单了,首先我们是传值传参,ls是一份临时拷贝,我们直接用这个临时变量和*this交换即可,然后返回*this.

 以上就是list的完整模拟实现了。

下面我们放一张vector与list的对比图:

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio

c++ list指定位置插入,c++,后端,c++,链表,数据结构,visualstudio 

 


总结

list的模拟实现中最难理解的就是迭代器的构造,对于list的迭代器我们一定要多练习才能真正的掌握。

 

到了这里,关于【c++】:list模拟实现“任意位置插入删除我最强ƪ(˘⌣˘)ʃ“的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • STL--list如何实现元素的插入和删除

    在C++标准模板库(STL)中,std::list 是一个双向链表。由于它的双向链表特性,std::list 支持在任何位置高效地插入和删除元素。 元素插入: ●使用 push_back() 在列表尾部添加元素; ●使用 push_front() 在列表头部添加元素; ●使用 insert() 在指定位置插入元素。这需要一个迭代器

    2024年04月12日
    浏览(37)
  • Mybatis 中传入List实现 批量插入、批量更新、批量删除

    个人收藏使用 文章来自Mybatis 中传入List实现 批量插入、批量更新、批量删除 - chelsey3tsf - 博客园 (cnblogs.com) 1. 批量插入 : Mapper层: 对应的mapper.xml: 如果List数据量比较大,可以考虑将List分批次插入 2. 批量更新: 批量更新只提供更新单个字段的,因为更新多个字段无论哪种

    2024年02月11日
    浏览(58)
  • 【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)
  • C++ list模拟实现

    源码中的list实现为 带头双向链表   list类的对象有两个成员:指向头结点的指针_head,统计数据个数的_size 在模拟实现list之前,需要先模拟实现 结点类,迭代器类 结点类:三个成员,_data _prev _next , 实现成struct (也是类,不过与class不同的是,它的成员都是公开的,都可以

    2024年02月11日
    浏览(47)
  • (C++) list底层模拟实现

     个人主页:Lei宝啊  愿所有美好如期而遇 首先,list底层是一个带头双向循环链表,再一个,我们还要解决一个问题,list的迭代器,vector和string的迭代器可以直接++,是因为他们的地址空间是连续的,而链表不是,所以链表的迭代器封装的不是原生指针,我们需要想办法解决

    2024年01月21日
    浏览(45)
  • [C++]:12:模拟实现list

    1.节点结构: 1.SGI下的节点通过两个结构体实现。 2.基础的链表节点只包括前驱指针和后继指针。 3.链表节点去继承基础链表节点,新增节点数据。 4.优化掉指针类型带模板参数。 2.节点构造函数: 1.节点本身在这个地方是没有构造函数的。 2.观察下面的链表的结构和链表的

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

    list为任意位置插入删除的容器,底层为带头双向循环链表 begin() 代表第一个结点,end()代表最后一个结点的下一个 1. list_node 类设计 C++中,Listnode作为类名,而next和prev都是类指针,指针引用成员时使用-,而对象引用成员时使用 . 通过显示实例化,将两个类指针指定类型为T

    2024年02月02日
    浏览(44)
  • 《C++ list的模拟实现》

    本文主要介绍list容器的模拟实现 list示意图: 首先需要定义一个节点 的结构体 我们之前所理解的是:迭代器理解为像指针一样的东西,但是在list中有些不同 我们可以来观察一下STL源码中大佬是怎么封装的: 我们可以看到,只有一个成员,那就是一个结点的指针node,link_

    2024年02月07日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包