list模拟实现

一. list的基本框架

template<class T>
struct list_node
{list_node<T>* _prev;T _data;list_node<T>* _next;
};template<class T>
class list
{typedef list_node<T> Node;
private:Node* _head;
}

---

使用库中的list类需要包含头文件#inlcude<list>，并且使用std::命名空间

list是一个带头结点的双向循环链表

_head：指向其头结点

二. list_node类

1.构造函数

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

每一个结点，创建时_data = val，并将 _prev和 _next置空(nullptr)。

其中如果没有传val参数，则使用缺省值T()：T类型的匿名对象（内置类型，如：int() = 0)

2.其他函数

其他成员函数使用编译器默认生成的函数就行，如：析构函数、拷贝构造、赋值运算符重载……

因为，如

1. 拷贝构造：内置类型是按照字节方式直接拷贝的；自定义类型是调用其拷贝构造函数完成拷贝的
2. 析构函数：无动态申请空间需要释放

三. 迭代器（iterator）

和string与vector的顺序存储不同，list存储是链式的。

所以list::iterator不能直接定义为元素指针，因为++、*(解引用)等对指针的操作在这里会出现问题

我们可以来封装原生指针(节点指针)成一个类，在类中完成运算符重载(operator 运算符)，使++、*(解引用)等能完成其功能。此时iterator就变成像指针一样的对象了。

1.结构

template<class T, class Refence, class Pointer>
struct _list_iterator
{typedef list_node<T> Node;Node* _node;
};

2. 构造函数

_list_iterator(Node* node = nullptr):_node(node)
{}

3. 运算符重载

//为书写方便，typedf
typedef _list_iterator<T, Refence, Pointer> iterator;

bool operator!=(const iterator& it)
{return _node != it._node;
}bool operator==(const iterator& it)
{return _node == it._node;
}Refence operator*()
{//返回节点的数据的引用return _node->_data;
}Pointer operator->()
{ //返回数据元素的指针return &(operator*());
}// ++it
iterator& operator++()
{//自增1位_node = _node->_next;return *this;
}// it++
//临时变量不能传引用
iterator operator++(int)
{//后置++，返回+1前的值iterator tmp(*this);_node = _node->_next;return tmp;
}// --it
iterator& operator--()
{_node = _node->_prev;return *this;
}// it--
//临时变量不能传引用
iterator operator--(int)
{iterator tmp(*this);_node = _node->_prev;return tmp;
}

operator->

---

->操作符：类对象指针访问其publibc成员

四.反向迭代器

反向迭代器与正向迭代器的区别主要是：移动方向不同。如：反向迭代器的++操作是向前走的

因此反向迭代器也需要重载运算符(operator 运算符)，我们可以沿用正向迭代器的实现方法：将反向迭代器封装成一个类。

同时我们可以使用正向迭代器来适配反向迭代器，即复用正向迭代器的代码

反向迭代器设计时，可以规定和正向迭代器相反：

因此*rbegin的操作应该是先让rbegin向前移动1位再 *(解引用)

1.结构

template<class Iterator, class Refence, class Pointer>
struct _reverse_iterator
{Iterator _rit;
}

反向迭代器类的成员变量是一个正向迭代器的对象（适配）

2.构造函数

_reverse_iterator(const Iterator& it = Iterator()):_it(it){}

3.运算符重载

//为书写方便，typedf
typedef _reverse_iterator<Iterator, Refence, Pointer> Self;

Refence operator*()
{Iterator tmp = _it;return *(--tmp);
}Pointer operator->()
{return &(operator*());
}Self& operator++()
{--_it;return *this;
}Self& operator--()
{++_it;return *this;
}bool operator!=(const Self& s)
{return _it != s._it;
}

五. list常用方法及实现

1. 默认构造函数

a.empty_init

void empty_init()
{// 创建并初始化哨兵位头结点_head = new Node;_head->_next = _head;_head->_prev = _head;
}

list()
{empty_init();
}

2.迭代器

//正向迭代器
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;

//反向迭代器
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

反向迭代器第一个模板参数传入的正向迭代器的类 类型

a. begin

iterator begin()
{//返回迭代器对象return iterator(_head->_next);
}
const_iterator begin() const
{return const_iterator(_head->_next);
}

返回首元素的位置（_head的下一个元素）

b. end

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

end()返回，尾元素的下一个位置(即 _head)

c.rbegin

reverse_iterator rbegin()
{return reverse_iterator(end());
}
const_reverse_iterator rbegin() const
{return const_reverse_iterator(cend());
}

d.rend

reverse_iterator rend()
{return reverse_iterator(begin());
}
const_reverse_iterator rend() const
{return const_reverse_iterator(cbegin());
}

3.数据访问

a. size

size_t size() const
{size_t count = 0;iterator cur = begin();while (cur != end()){++count;}return count;
}

遍历计数

b. empty

void empty() const
{return begin() == end();
}

c. front

T& front()
{return *begin();
}
const T& front() const
{return *begin();
}

返回首元素的引用

d. back

T& back()
{return *(--end());
}
const T& back() const
{return *(--end());
}

返回尾元素的引用

4.增删操作

a. insert

iterator insert(iterator pos, const T& val)
{//断言处理，避免pos指向一个空指针assert(pos._node);Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;Node* next = cur;//|prev| |newnode| |next|newnode->_prev = prev;prev->_next = newnode;newnode->_next = next;next->_prev = newnode;return iterator(newnode);
}

在pos前 插入一个值为val的结点

b. push_back

void push_back(const T& val)
{insert(end(), val);
}

在尾元素的下一个位置前，插入值为val的结点

c. push_front

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

在首元素的位置前，插入值为val的结点

d. erase

iterator erase(iterator pos)
{assert(pos._node);//pos指向的非空指针assert(pos != end());//删除的不是尾元素的下一个位置Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;//|prev| |cur| |next|prev->_next = next;next->_prev = prev;delete cur;return iterator(next);
}

删除pos指向的元素，并返回删除位置的下一个位置的迭代器

e. pop_front

void pop_front()
{erase(begin());
}

删除首元素

f. pop_back

void pop_back()
{erase(--end());
}

删除尾元素

g.clear

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

迭代释放所有节点空间（除头节点外）

5.初始化和清理

a. 析构函数

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

释放所有节点空间

b. n个val的构造

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

c. 迭代器区间构造

template <class InputIterator>  
list(InputIterator first, InputIterator last)
{empty_init();//创建头结点while (first != last){push_back(*first);++first;}
}

d. swap

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

e. 拷贝构造

传统写法：

list(const list<T>& lt)
{empty_init();//创建头结点for (const auto& e : lt){push_back(e);}
}

现代写法：

通过一个局部对象，和swap来完成

list(const list<T>& lt)
{empty_init();//创建头结点list<T> temp(lt.begin(), lt.end());swap(temp);
}

通过empty_init，对成员变量_head进行初始化，然后和经迭代器区间构造函数得到的temp对象进行交换内容，完成拷贝构造。该函数执行结束，局部对象temp会自动调用析构函数，并销毁。

f. operator=

传统写法：

list<T>& operator=(const list<T> lt)
{//如果是自己给自己赋值则不操作if (lt != this){clear();for (const auto& e : lt){push_back(e);}}return *this;
}

现代写法：

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

传参时，会调用拷贝构造函数完成对局部对象lt的初始化，然后交换*this和lt的内容，完成对自身对象的赋值。

六.小结

1.代码结构

可以将模拟实现的代码放在自己的命名空间中，避免冲突

#include <iostream>
#include <assert.h>namespace yyjs
{template<class T>struct list_node{};template<class T, class Refence, class Pointer>struct _list_iterator{};template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{};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;typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;};
}

2.迭代器失效

插入元素时不会导致迭代器失效

iterator insert(iterator pos, const T& x);

在pos结点前插入一个元素，pos指向并未改变。

删除时迭代器会失效

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

对于上例中clear()函数中，每次进行删除操作后，it就是失效的迭代器(原先指向的空间被释放了)，所以需要重新对it进行赋值(erase函数返回的是下一个位置的迭代器)。

3. 反向迭代器

由于list底层是一个双向链表，因此可以实现反向遍历等操作(–)，所有可以实现其反向迭代器。

关于迭代器可以发现，对于客户(使用者)而言，不需要过多的了解使用的某个容器的底层实现原理，对于如string、vector与list，都提供了一个迭代器(iterator)，我们甚至不需要考虑iterator具体是什么：是一个指针还是一个类？

在使用时，auto it = lti.begin()，然后就可以遍历容器的元素，并且他们的操作方法都相同，如it++、*it……

---

    🦀🦀观看~~