创作初心：在加深个人对知识系统理解的同时希望可以帮助到更多需要的同学
😄柯一梦的专栏系列
🚀柯一梦的gitee
🛠️柯一梦的CSDN主页
座右铭：功不唐捐，玉汝于成
在这里插入图片描述

list的大体框架，三个类及其主要的成员函数总览

结点类的实现

要学习list，我们可以从vector入手，vector是一个顺序表，而list只不过就是把每个结点分散开来。如果list要想像vector靠拢，我们只需要保存每一个结点的地址，通过地址来进行节点之间的访问
在这里插入图片描述
对于节点类的构造：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)
	{
	}
};

有些同学肯定会有这样的疑问：为什么结点的构造函数要传一个缺省值？

  • 我们在哪些情况下会使用到这个缺省值呢？

    1.我们在初始化list的时候，可以直接通过new一个node从而实现哨兵结点的无参构造
    2.在实现push_back的时候，它的底层我们可以使用new node并且直接传入缺省值

llist迭代器的封装

我们在实现vector，string的时候都没有进行iterator的封装，而是直接使用typedef 将原生指针重命名为迭代器，为什么偏偏到了list就要开始封装迭代器了呢？要回答这个问题我们就要了解一下迭代器的作用。在进行迭代器遍历的时候，我们需要使用iterator类型的变量进行±，还有解引用得到每个迭代器指向的空间里的值。但是如果我们直接使用node的结点指针作为迭代器可以吗？当然不行，我们没办法实现±法，也没办法实现解引用，所以我们要封装一个类。

迭代器的类模版参数说明

这个类有三个模版参数
在这里插入图片描述
因为我们重定义了两个迭代器，分别是const迭代器和普通迭代器
在这里插入图片描述
因为const迭代器和普通迭代器的唯二区别就是解引用运算符重载和->运算符重载的返回值的类型的不同。

构造函数

这个类构造出来的对象相当于指向每个节点的指针，所以它唯一的成员变量就是一个node*。我们在写构造函数的时候缺省值要写成一个nullptr这样我们的代码会更健壮

1
2
3
4
__list_iterator(Node* node = nullptr)
	:_node(node)
{
}

++运算符重载

++运算符重载分为前置++和后置++（参数部位需要添加int进行区分）

前置++

我们返回的是++对象本身，所以我们的返回值是一个类型的引用，因为iterator对象李爱你存放的是ndoe指针，我们在更改——iterator指向的时候，只需要_node = _node->_next

1
2
3
4
5
6
self& operator++()//前置++
{
	_node = _node->_next;
	return *this;
}

后置++

后置++的返回值就是值返回了，我们要先拷贝构造一个iterator（在这里我们不需要单独去写一个，我们可以直接使用编译器生成的拷贝构造）

1
2
3
4
5
6
self operator++(int)//后置++
{
    self temp(*this);
    _node = _node->_next;
    return temp;
}

–运算符重载

和++运算符同理，这里不展开介绍

前置–
1
2
3
4
5
self& operator--()//前置--
{
    _node = _node->_prev;
    return *this;
}
后置–
1
2
3
4
5
6
self operator--(int)//后置--
{
    self temp(*this);
    _node = _node->_prev;
    return temp;
}

*运算符重载

返回值：我们解引用得到的就是node节点里面存放的Data元素，并且是可以修改的，所以是引用返回。但是我们为什么要将返回值弄成模版参数呢？答案是如果我们不这样写成模版参数，我们只能写两个类。

  • 1、我们为什么不直接在将普通迭代前面加上一个const使其变成const迭代器呢？

因为const迭代器修饰的是指向的内容本身不能修改【因为我们封装的是迭代器，我们能访问内容的唯一途径就是通过解引用的引用返回，我们只要在这里实现封装，也就是加上一个const就好】，而不是迭代器本身，迭代器本身还要能够实现+±-功能.

  • 2.我们可以使用函数重载（参数的个数，顺序，类型不同）来实现目的吗？

有的同学希望使用const T& operator*(const)来实现不同的调用，但是const修饰的是*this指针，也就是iterator，这样的话就又转回到第一个问题了。所以我们无法通过函数重载，来实现const迭代器与普通迭代器对*的调用

1
2
3
4
Ref operator*()
{
   return (_node->data);
}

==运算符重载

1
2
3
4
bool operator==(const self& it)
{
    return _node == it._node;
}

!=运算符重载

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

->运算符重载

->运算符编译器会进行一些优化，也就是会对返回值进行->，简单的说，我们要实现->运算符的返回值是节点所存内容的地址：

1
2
3
4
ptr operator->()
{
    return &(_node->data);
}

如果我们存入的是一自定义类型pos，这个自定义类型pos有两个成员变量，row和col，iterator里面存放的是node的指针，我们使用迭代器it->row的时候编译器会自动调用两次->，编译器会先调用我们自定义的 operator->，得到一个普通指针，然后再对这个指针使用内置的 -> 运算符。

list类的实现

首先我们要在list里面对node以及iterator的两个类进行重定义，而且node与iterator两个类都用Struct来写，方便我们调用node和iterator里面的东西

默认成员函数

构造函数
  • 1、默认构造
    默认构造函数就是生成一个节点，并且让这个节点形成循环，但由于考虑到很多场景下都会用到这个默认构造，所以我们干脆直接生成一个函数empty_init
1
2
3
4
5
6
void empty_init()
{
    _head = new Node;
    _head->next = _head;
    _head->prev = _head;
}

所以默认构造函数就是：

1
2
3
4
5
6
7
8
9
10
void empty_init()
{
    _head = new Node;
    _head->next = _head;
    _head->prev = _head;
}
list()
{
    empty_init();
}
  • 2、initializer_list构造
    initializer_list的写法和vector的一样，形参是一个initializer_list类，然后使用for循环和push_back将initializer_list里面的值赋到使用empty_list初始化了的对象之中
1
2
3
4
5
6
7
8
list(initializer_list<T> li)
{
   empty_init();
   for (const auto& e : li)
   {
   push_back(e);
   }
}
拷贝构造函数

拷贝构造函数就是使用empty_init构造一个新的对象，然后使用for循环和push_back将元素插入构造的对象中

1
2
3
4
5
6
7
8
list(const list<T>& lt)
{
    empty_init();
    for (const auto& e : lt)
    {
        push_back(e);
    }
}
赋值运算符重载函数

有传统写法和现代写法两种，和之前的类似
传统写法

1
2
3
4
5
6
7
8
9
10
11
12
13
list<T>& operator=(const list<T>& lt)
{
	if (this!= &lt)//防止自己给自己赋值
	{
		clear();
		for (const auto& e : lt)
		{
			push_back(e);
		}
	}
	return *this;
}

现代写法

1
2
3
4
5
6
7
8
9
10
11
void swap(list<T>& lt)
{
	std::swap(this->_head,lt._head);
	std::swap(this->_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
	swap(lt);
	return *this;
}

析构函数

先使用clear释放除头结点外的所有节点空间，然后再释放头结点

1
2
3
4
5
6
7
8
9
void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = Erase(it);
	}
}

迭代器相关函数

begin和end、cosnt_begin与const_end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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);
}

插入与删除函数

push_back与pop_back
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void push_back(const T& x)
{
	Node* newnode = new Node(x);
	Node* tail = _head->_prev;

	tail->_next = newnode;
	newnode->_prev = tail;
	newnode->_next = _head;
	_head->_prev = newnode;
	++_size;
}
void pop_back()
{
	Erase(--end());
}

Insert函数

insert函数里重要的一点就是我们传入的是一个迭代器，要使用.得到node节点，然后我们使用Node*类型的变量来接收

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
iterator Insert(iterator pos,const T& val)
{
	Node* cur = pos._node;
	Node* newnode = new Node(val);
	Node* prev = cur->_prev;


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

Erase函数

重要的是我们要判断删除的是否是空链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
iterator Erase(iterator pos)
{
	if (pos == end())
	{
		return pos;
	}
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	prev->_next = next;
	next->_prev = prev;
	delete cur;
	--_size;
	return iterator(next);
}

其他函数

clear

在这里我们使用的是Erase去进行挨个删除

1
2
3
4
5
6
7
8
9
void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = Erase(it);
	}
}

swap
1
2
3
4
5
6
void swap(list<T>& lt)
{
	std::swap(this->_head,lt._head);
	std::swap(this->_size, lt._size);
}

size
1
2
3
4
size_t size()const
{
	return _size;
}

最后一个函数Print
在我们使用类里面的类型的时候，我们需要在前面加上一个typename，告诉编译器，这个不是成员变量，而是一个类型

1
2
3
4
5
6
7
8
9
void Print(const list<T>& lt)
{
	typename list<T>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << endl;
		++it;
	}
}