1.list初始化

首先要有一个节点类

初始化列表进行nullptr的赋初值

然后就是链表的无参构造

双向链表,连接后要构成一个环,如上empty_init;

2.push_back

注意,双向链表,tail就是head的prev;

3.迭代器

之前模拟实现string和vector的时候,迭代器使用的是原生指针,那这里可以吗?因为要进行++操作,而原生指针++是物理结构上的++,不是逻辑结构上的++,所以不能使用原生指针,而要定义成一个结构体,其中存放指针域,从而实现逻辑上的++。

迭代器结构体如下:

迭代器要实现++、!=、解引用的重载函数

这样对吗?显然不对,迭代器加加后,返回的还是一个迭代器,所以应该返回迭代器对象,而++是自身++,所以应该this这个迭代器的node变成当前的下一个,如下:

下面是解引用:这样对吗?

返回值应该是T类型的引用,是正确的。

4.迭代器的begin end

这个函数应该写在哪里呢?写在list中,因为是list调用这两个函数

这个函数的返回值是一个结构体,所以可以像第一种方式一样,return iterator(_head->_next),但是c++支持单参数构造函数的隐式类型转换,所以可以直接使用第二种方式,它会饮食调用iterator的单参构造函数。但是,刚刚写的构造函数就不适用了:

这种写法的参数是一个node类型,但是begin和end返回的是指针类型,所以这个构造函数应该改成:

5.insert

有了迭代器就可以写insert了,使用迭代器定义起始值

6.erase

注意,node是new开辟的空间,所以一定要delete

测试一下insert和end:

当我们想erase第三个node时,发现+使用不了,因为他不是原生指针,所以要自己重写,进行运算符重载:

此时就可以用erase和insert实现pushback和popback:

7.clear

clear时清空链表,但不是销毁链表,所以表头要保留,如上。注意,释放当前节点之前,要记录下下一个节点,防止之后找不到下一个要释放的节点。

但是下面的程序崩溃了,按理说,空链表因该打印出来是空的,但是却崩溃了,为什么?

因为,clear之后,没有把head的next域和指针域改变,所以如下:

这样写clear太麻烦了,我们可以调用erase,如下:

但是注意,it已经释放掉了,再去加加,就会出问题,所以当erase之后,it应该指向被释放掉的元素的下一个位置,所以erase函数应该加上返回值

但是,这样的话,erase就不能简单地返回普通引用了,而要返回const引用,因为单参数构造函数的隐式类型转换要生成临时对象,临时对象具有常性

8.~list

首先清空链表,再将其头节点的空间释放掉并置为空,防止形成野指针!!!

10.->迭代器访问成员重载

现在有下面的情形:

A是一个自定义的类,想要使用list迭代器输出a的内容,但是<<不能使用,有下面的几种解决方法

1.让A自己实现流插入重载

2.*(it)._a进行输出,其中,*是迭代器重载的

3.it->_a想要这样实现,就需要让迭代器重载->运算符

如下:

注意,这里返回的是数据的地址,在这里就是A对象的地址,最后让A对象去访问它的_a成员。但是_a是私有的,所以可以将A类携程结构体。

10.const迭代器

什么是const迭代器呢?const迭代器等同于const T* 也就是说,const迭代器可以加加减减改变指向,但是其指向的了内容不能够改变,也就是说,list的const迭代器内部的_node指针指向的内容不能够改变。所以,对于那些重载的函数,++ --是针对迭代器本身进行操作的,不需要改,而对于解引用操作,由于解引用拿到的是node,不能对node进行修改,所以应该在解引用返回时返回const T*类型的

第一种方法就是再写一个const迭代器的结构体

template<class T>
struct __const_list_iterator
{
	typedef list_node<T> Node;
	typedef __const_list_iterator<T> self;
	const Node* _node;
	__const_list_iterator(Node* node)
		:_node(node)
	{}
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	self operator++(int)
	{
		self tmp(this->_node);
		_node = _node->_next;
		return tmp;
	}
	self operator--()
	{
		self tmp(this->_node);
		_node = _node->_prev;
		return tmp;
	}
	
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
	const T& operator*()
	{
		return _node->_data;
	}
	
	const T* operator->()
	{
		return &_node->_data;
	}
	
};

其实只有*和->重载函数的返回值变成了const T*。也就是将原来所有返回T*的都变成const T*

通过下面的打印函数测试一下:

但是发现,打印完之后,程序崩溃了。为什么呢?调试后得知是在main函数中对lt进行析构的时候崩溃的。再仔细调试可以看到在main函数析构之前lt已经被析构了。为什么呢???因为我们还没有进行拷贝构造的重载,所以在传参时变成了默认的浅拷贝,所以都指向了同一块空间,所以print函数中对形参进行析构的同时其实就是对lt进行了析构。

那该怎么办呢?当然是传递引用啦:

这回就对了,而且咱们写的const迭代器也被成功调用了

但是再写一个类太麻烦了,我们可以尝试使用之前写的迭代器。该怎么用呢?

根据上面写的两个iterator类的分析,可以看出来,只有operator*和operator->的返回值不一样,其他都一样,所以可以在类模板参数中加俩个参数,如果想要编译器生成const迭代器,就传入const有关的参数,如下:

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* node)
		:_node(node)
	{}
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}
	self& operator+(int i)
	{
		while (i > 0)
		{
			_node = _node->_next;
			i--;
		}
		return *this;
	}
	self& operator-(int i)
	{
		while (i > 0)
		{
			_node = _node->_prev;
			i--;
		}
		return *this;
	}
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	
};

主要就是最后两个函数,用到了Ref和Ptr

template<class T>
class list
{
	typedef struct list_node<T> Node;
	//typedef struct __list_iterator<T> iterator;//封装/接口的统一性,所有迭代器都这样表示
	//typedef struct __const_list_iterator<T> const_iterator;
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;
    iterator begin()
    {
	    return _head->_next;
    }
    iterator end()//end 返回的是最后一个节点的末尾,也就是head
    {
	    return _head;
    }

    const_iterator begin()const
    {
	    return _head->_next;
    }
    const_iterator end()const//end 返回的是最后一个节点的末尾,也就是head
    {
	    return _head;
    }
………………
}

这样就实现了类模板的复用

11.拷贝构造

这次有了const迭代器了,就可以进行范围for遍历const list了。

12.赋值重载

赋值重载要注意是对已有对象进行的,但是已有对象可能不是空链表,所以应该先进行clear,再插入元素

13.print_list

前面在测试const迭代器时,咱们写了print函数:

这里为什么无法访问const_iterator呢?因为typedef这一行没有写到public中,默认是私有的

所以应该将typedef写到public中

但如果想要打印list中的string呢?

所以它应该变成一个模板函数

但是运行时报错了:

为什么呢?

因为编译器编译时看不到模板,T还没有实例化,那么list类就还没有形成,编译器就无法到list里面取const_iterator,他就不知道这是个类型还是个静态成员变量,。所以要在这句代码之前加上一个typename关键字,来告诉编译器这个是一个类型。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部