个人主页

文章目录

🎄一、前言🏠二、基本框架🎡三、list节点类的实现🎉四、list迭代器类1.Ref operator*()2.Ptr operator->()3.Self& operator++()前置和Self& operator--()前置4.Self operator++(int)后置和Self operator--(int)后置5.bool operator!=(const Self& s) const和bool operator==(const Self& s) const

⭐五、list类1.初始化2.构造函数4.析构函数和clear函数5.深拷贝6.深赋值7.头插和头删函数8.尾插和尾删函数9.insert和erase函数10.迭代器的实现（普通和const)11.判空12.size()函数

🚀六、vector和list函数的区别🏝️七、源代码

🎄一、前言

list是一个双向链表的容器，它可以在其内部中存储各种类型的元素，并且支持动态地添加、删除和修改元素。

🏠二、基本框架

list可以分为三部分：一个是list节点类，一个是迭代器类，还有一个是list类本身。

它们三个类底层的成员变量又分别代表不同的功能。

其中list节点类封装了list的元素以及前后指针，且完成了节点的初始化。

迭代器类封装了指向节点的指针，还负责重载++、–等运算符。

list类本身负责初始化以及负责插入和删除等功能。

🎡三、list节点类的实现

链表中数据以及前后指针的类型都是由模板自动生成的，可以为内置类型或自定义类型。

<code>template<class T>

struct list_node

{ -- -->

T _data;

list_node<T>* _next;

list_node<T>* _prev;

//构造

list_node(const T& data = T())

:_data(data)

, _next(nullptr)

, _prev(nullptr)

{ };

};

🎉四、list迭代器类

因为迭代器涉及普通迭代器和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* _node;

};

迭代器的默认构造函数因为支持基本的隐式类型转换，因此实现起来也很简单。

list_iterator(Node* node)

:_node(node)

{ }

1.Ref operator*()

负责重载迭代器的解引用，直接返回当前该迭代器指向的节点数据即可。

Ref operator*()

{

return _node->_data;

}

2.Ptr operator->()

由于我们想把迭代器当成指针使用，因此重载->是必要的，其返回值为节点元素的地址。为什么是返回地址呢？这是因为在使用迭代器->时，编译器会自动优化成->->。

Ptr operator->()

{

return &_node->_data;

}

3.Self& operator++()前置和Self& operator–()前置

直接让节点指向下一个和前一个即可。

//前置++

Self& operator++()

{

_node = _node->_next;

return *this;

}

//前置--

Self& operator--()

{

_node = _node->_prev;

return *this;

}

4.Self operator++(int)后置和Self operator–(int)后置

我们只需把当前迭代器实例化的对象拷贝给一个新的迭代器对象tmp，然后把当前的数据进行处理，最后将tmp进行返回即可。

//后置++

Self operator++(int)

{

Self tmp(*this);

_node = _node->_next;

return tmp;

}

//后置--

Self& operator--(int)

{

Self tmp(*this);

_node = _node->_prev;

return tmp;

}

5.bool operator!=(const Self& s) const和bool operator==(const Self& s) const

判断节点是否相等不能只判断值是否相等，因为不同的节点可以存放相同的值，因此需要比较其节点是否相等即可。

bool operator!=(const Self& s) const

{

return _node != s._node;

}

bool operator==(const Self& s) const

{

return _node == s._node;

}

⭐五、list类

1.初始化

初始化只需初始化头结点即可。

//无参初始化

list()

{

//通过调用这一函数来创建头节点

empty_init();

}

//空初始化

void empty_init()

{

_head = new Node;

_head->_next = _head;

_head->_prev = _head;

_size = 0;

}

2.构造函数

当链表为空时，_head节点的头和尾都指向它自己，因此在后续有节点插入时，只需改变一下prev和next指向的位置即可。

list()

{

_head = new Node<T>();

_head->next = _head;

_head->prev = _head;

}

4.析构函数和clear函数

析构函数是用来释放节点空间的，因此需要先定义一个clear函数用来释放所有的有效节点，确保没有有效节点后再把哨兵位的_head进行删除，然后将_head置为空。

//析构

~list()

{

clear();

delete _head;

_head = nullptr;

}

void clear()

{

auto it = begin();

while (it != end())

{

it = erase(it);

}

}

5.深拷贝

先对其进行空初始化操作，然后用迭代器依次对其进行访问然后插入即可。

//深拷贝

list(const list<T>& lt)

{

empty_init();

for (auto& e : lt)

{

push_back(e);

}

}

6.深赋值

我们可以调用swap函数将两者数据进行交换即可。

//深赋值

void swap(list<int>& lt)

{

std::swap(_head, lt._head);

std::swap(_size, lt._size);

}

list<T>& operator=(list<T> lt)

{

swap(lt);

return *this;

}

7.头插和头删函数

头插函数就是每次在begin位置之前进行插入，因为begin是第一个有效的元素；而头删就是每次在begin位置进行删除。

void push_front(const T& x)

{

Insert(begin(), x);

}

void pop_front()

{

erase(--begin());

8.尾插和尾删函数

尾插就是每次在end()位置进行插入，因为end是最后一个有效的元素；而尾删则是在end()的位置上进行删除。

由于我们实现了insert函数，因此就可以调用insert函数在其尾部插入数据即可。

void push_back(const T& x)

{

Insert(end(), x);

++_size;

}

void pop_back()

{

erase(--end());

}

9.insert和erase函数

insert函数就是在pos位置插入值。

iterator Insert(iterator pos, const T& x)

{

//取到pos位置的节点

Node* cur = pos._node;

//保留之前的节点

Node* prev = cur->_prev;

//创建新节点

Node* newnode = new Node(x);

//改变指向，最后更新一下_size

newnode->_next = cur;

cur->_prev = newnode;

newnode->_prev = prev;

prev->_next = newnode;

++_size;

return newnode;

}

erase函数首先要进行断言，防止删除哨兵位。然后将pos位置节点的前和后进行连接，最后删除pos位置的节点，更新一下_size的大小。

iterator erase(iterator pos)

{

assert(pos != end());

Node* prev = pos._node->_prev;

Node* next = pos._node->_next;

prev->_next = next;

next->_prev = prev;

delete pos._node;

--_size;

return next;

}

10.迭代器的实现（普通和const)

由于存在普通成员变量和const成员变量的调用，因此需要实现两个迭代器。

begin迭代器是返回第一个有效位置，由于哨兵位_head并没有数据，因此返回哨兵位的下一个位置。end迭代器是返回最后一个元素的下一个位置，而这个位置是无效的，双向链表无效的位置就只有哨兵位这一个位置，因此返回哨兵位即可。

iterator begin()

{

return _head->_next;

}

iterator end()

{

return _head;

}

//const迭代器

const_iterator begin() const

{

return _head->_next;

}

const_iterator end() const

{

return _head;

}

11.判空

直接判断_size是否为空即可。

//判空

bool empty() const

{

return _size == 0;

}

12.size()函数

直接返回_size即可。

size_t size() const

{

return _size;

}

🚀六、vector和list函数的区别

首先，vector是一个动态数组，在插入和删除数据的时候会挪动后面的元素，这就有可能会导致迭代器失效；而list则为链表，它可以在任意位置进行插入和删除，因此迭代器的稳定性就更高。

其次，vector的迭代器通常为随机访问迭代器，允许向前向后访问元素，而list迭代器可能为双向迭代器，只能向前或向后移动。

最后，vector的随机访问速度快，因此在查找元素时的效率高，但如果频繁的插入或者删除元素时，list通常会更快，因为它不需要移动大量的元素。

🏝️七、源代码

#include<iostream>

#include<assert.h>

#include<list>

using namespace std;

namespace bit

{

template<class T>

struct list_node

{

T _data;

list_node<T>* _next;

list_node<T>* _prev;

//构造

list_node(const T& data = T())

:_data(data)

, _next(nullptr)

, _prev(nullptr)

{ };

};

//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)

{ }

Ref operator*()

{

return _node->_data;

}

Ptr 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& s) const

{

return _node != s._node;

}

bool operator==(const Self& s) const

{

return _node == s._node;

}

};

template<class T>

class list

{

typedef list_node<T> Node;

public:

typedef list_iterator<T,T&,T*> iterator;

typedef list_iterator<T,const T&,const T*> const_iterator;

iterator begin()

{

return _head->_next;

}

iterator end()

{

return _head;

}

//const迭代器

const_iterator begin() const

{

return _head->_next;

}

const_iterator end() const

{

return _head;

}

//空初始化

void empty_init()

{

_head = new Node;

_head->_next = _head;

_head->_prev = _head;

_size = 0;

}

//无参初始化

list()

{

empty_init();

}

//析构

~list()

{

clear();

delete _head;

_head = nullptr;

}

void clear()

{

auto it = begin();

while (it != end())

{

it = erase(it);

}

}

//深拷贝

list(const list<T>& lt)

{

empty_init();

for (auto& e : lt)

{

push_back(e);

}

}

//深赋值

void swap(list<int>& lt)

{

std::swap(_head, lt._head);

std::swap(_size, lt._size);

}

list<T>& operator=(list<T> lt)

{

swap(lt);

return *this;

}

size_t size() const

{

return _size;

}

void push_back(const T& x)

{

Insert(end(), x);

++_size;

}

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

++_size;

return newnode;

}

void pop_back()

{

erase(--end());

}

void pop_front()

{

erase(--begin());

}

iterator erase(iterator pos)

{

assert(pos != end());

Node* prev = pos._node->_prev;

Node* next = pos._node->_next;

prev->_next = next;

next->_prev = prev;

delete pos._node;

--_size;

return next;

}

void push_front(const T& x)

{

Insert(begin(), x);

}

//判空

bool empty() const

{

return _size == 0;

}

private:

Node* _head;

size_t _size;

};

}