企业官网建设流程全解析

list深度剖析

• 一、list介绍与使用
  • 1.关于list
  • 2.list的使用
    • 3.迭代器相关说明
• 二、list相关接口简述
  • 简要区分：emplace_back与push_back
  • 关于splice接口
  • 简述迭代器失效
• 三、源码剖析：根据源码重构list
  • 1.结构分析
  • 2.节点类实现
  • 3.迭代器类实现
    • 3.1 成员变量
    • 3.2 构造函数
    • 3.3 operator*
    • 3.4 operator++和operator- -
    • 3.5 operator==和operator!=
    • 3.6 operator->
  • 4.List实现
    • 4.1 成员变量
    • 4.2 构造函数
    • 4.3赋值重载
    • 4.4 析构函数
    • 4.5 插入删除
  • 5.const迭代器的实现
  • 6. 关于initializer_list

一、list介绍与使用

1.关于list

list即为链表，而且还是双向带头循环链表，其详细介绍参考C++官网
点我

2.list的使用

这里只介绍一下构造函数，其余函数参考官网

3.迭代器相关说明

list采用的是双向迭代器，而vector采用的是随机访问迭代器，因此list_iterator不支持 +/-，也不支持[]下标
我们来看看sort
显而易见，算法库的sort要的参数是随机访问迭代器，因此，list不能使用sort，但是list有它自己实现的sort

二、list相关接口简述

l.empty() // 是否为空 l.size() // 元素个数 l.max_size() // 最大容量（一般不用） l.front() // 第一个元素 l.back() // 最后一个元素 l.push_back(10) //尾插10 l.push_front(20) //头插20 l.pop_back() //尾删 l.pop_front() //头删

• insert:指定位置插入
• erase:指定位置删除
• remove:按值删除
• removeif:条件删除
• unique:去重
• reverse:翻转
• merge:合并链表，需要两链表有序，类似于归并
• splice:剪切链表

简要区分：emplace_back与push_back

list<A> lt; A aa(1,1); lt.push_back(aa); lt.push_back(A(2,1)); //lt.push_back(2,2); 这是错误的 lt.emplace_back(aa); lt.emplace_back(A(2,1)); lt.emplace_back(2,2); //没有问题

emplace_back和push_back前两种插入效率差不多，但是emplace_back可以进行第三种方式进行插入，且效率更高，因为它只进行了构造，而前两种进行了构造加拷贝

关于splice接口

splice就是把一个list的节点直接移动到另一个list

std::list<int> l1 = {1,2,3}; std::list<int> l2 = {4,5}; auto it = l1.begin(); ++it; l1.splice(it, l2);

结果：

l1: 1 4 5 2 3 l2: 空

vector的insert可能会导致迭代器失效，而splice并不会导致迭代器失效，因为splice只是移动指针，并没有发生扩容导致指针指向位置偏移，并不会导致迭代器失效

简述迭代器失效

链表插入数据后并不会发生迭代器失效，但在删除后可能发生

• 插入数据后，原来迭代器指向的位置不会发生改变，故不会发生迭代器失效
• 删除数据后，若删除的是迭代器指向的数据，那么该迭代器失效，其他的迭代器不会产生任何影响

三、源码剖析：根据源码重构list

1.结构分析

要实现list，必须包含三个类，分别是：节点类、迭代器类、链表类，以下list均用List表示

2.节点类实现

//List节点类 template<class T> struct ListNode { ListNode<T>* _prev; ListNode<T>* _next; T _data; };

list节点类包含指向前驱节点指针_prev、指向后继结点的指针_next、节点数据_data，节点使用struct进行封装，是因为后面的程序会频繁调用节点的成员

ListNode(const T& data = T()) :_prev(nullptr), _next(nullptr), _data(data) { }

这里需要一个节点的构造函数，我们可以将其全部置空，这里的data=T()，对于内置类型也是兼容的

3.迭代器类实现

3.1 成员变量

//List迭代器类 template<class T> struct ListIterator { typedef ListNode<T> Node; typedef ListIterator self; Node* _pnode; };

list的迭代器需要一个封装的指针，因为list的空间不是连续的，原生指针难以实现++,- -,解引用等操作，这些需要我们手动去执行

3.2 构造函数

ListIterator(Node* pnode = nullptr) :_pnode(pnode) { }

迭代器本身就是一个封装的指针，因此浅拷贝足够，不需要我们去实现

3.3 operator*

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

迭代器就是一个封装的指针，解引用需要返回指针指向的数据

3.4 operator++和operator- -

self& operator++() { _pnode = _pnode->_next; return *this; } self operator++(int) { auto tmp = *this; _pnode = _pnode->_next; return tmp; } self& operator--() { _pnode = _pnode->_prev; return *this; } self& operator--(int) { auto tmp = *this; _pnode = _pnode->_prev; return tmp; }

这里是前置++、后置++、前置- -、后置- -

3.5 operator==和operator!=

bool operator==(const self& s) const { return s._pnode == _pnode; } bool operator!=(const self& s) const { return s._pnode != _pnode; }

直接比较指针是否相等

3.6 operator->

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

既然这个迭代器是指针，那就有指针->的方式去访问节点数据
举一个简单的例子：

class A { public: int _a; int _b; }; List<A> lt; List<A>::iterator it=lt.begin(); //取it指向节点的_b元素 cout<<it->_b<<endl;

取_b元素实际上是

it.operator->()->_b

4.List实现

4.1 成员变量

//List类 template<class T> class List { public: typedef ListNode<T> Node; private: Node* _head; size_t _size; };

List需要一个指向头结点的指针_head和一个_size便于统计长度

4.2 构造函数

接下来，我们需要一个构造函数，因为后面链表各种构造方式都需要一个空链表，所以我们先实现一个空链表的构造：先构造一个哨兵头结点，将头结点的前驱和后继都指向自己，将_size置零即可

//空构造 void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; } //构造 List(){ empty_init(); } //拷贝构造 list(const list<T>& lt){ empty_init(); for (auto& e : lt) push_back(e); }

4.3赋值重载

复制重载可以使用swap的方式完成，这是一种经典且高效的写法，它避免了一个个拷贝的时间消耗，而是在自己的swap中调用库里的swap

void swap(List<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } List<T>& operator=(List<T> lt) { swap(lt); return *this; }

4.4 析构函数

先写一个clear函数清除节点，再去实现析构，注意：析构要删除头结点，clear不用

void clear() { auto it = begin(); while (it != end()) { it = erase(it); } _size=0; } ~List() { clear(); delete _head; _head = nullptr; }

4.5 插入删除

插入删除注意要保持双向链表的结构

void insert(iterator pos,const T& val) { Node* cur = pos._pnode; Node* prev = cur->_prev; Node* newnode = new Node(val); newnode->_next = cur; cur->_prev = newnode; newnode->_prev = prev; prev->_next = newnode; ++_size; } void erase(iterator pos) { Node* node = pos._pnode; if (node == _head) return; Node* prev = node->_prev; Node* next = node->_next; prev->_next = next; next->_prev = prev; delete node; --_size; } void push_back(const T& val) { insert(end(), val); } void pop_back() { if (!empty()) erase(--end()); } void push_front(const T& val) { insert(begin(), val); } void pop_front() { if (!empty()) erase(begin()); }

5.const迭代器的实现

要实现const迭代器可以采用复制一份普通迭代器的方法来实现，但是这样代码长度太长了，接下来，我们看一种stl库里实现的方法
看ListIterator类，我们对它的模板参数进行修改，传三个参数，第一个是类型，第二、三个分别是类型的引用和指针，将ListIterator<T, T&, T*>定义为iterator，而const ListIterator<T, const T&, const T*>定义为const_iterator，接下来把之后T&改成Ref，T*改成Ptr即可，这样编译器就能自动识别你要的是iterator还是const_iterator了

//List迭代器类 template<class T,class Ref,class Ptr> struct ListIterator { typedef ListIterator<T, T&, T*> iterator; typedef const ListIterator<T, const T&, const T*> const_iterator; typedef ListNode<T> Node; typedef ListIterator<T, Ref, Ptr> self; Node* _pnode; }

6. 关于initializer_list

stl库支持这样的初始化：

list<int> lt={1,2,3,4,5};

这是C++11新增的初始化方式：初始化列表初始化

看看initializer_list是怎样的

看看它的底层：可见，它的底层是_First和_Last两个指针，_First指向第一个元素，_Last指向最后一个元素的下一个位置

因此，我们可以写一个用initializer_list初始化的构造函数

List(std::initializer_list<T> il) { empty_init(); for (auto i : il) { push_back(i); } } List<int> lt({1,2,3,4}); //lt: 1->2->3->4