C++--list的使用及其模拟实现

list的使用及其模拟实现

1. list 的常用接口和使用

1.1 list 一般接口

list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，其底层是带头双向循环链表。

list 常用接口的使用和 string、vector 系列容器的接口使用一样，这里就不再详细介绍，具体使用细节可以查看 list 使用文档 – cplusplus.com。

1.1.1 构造函数

接口说明	构造函数说明
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list()	构造空的list
list (const list& x)	拷贝构造函
list (InputIterator first, InputIterator last)	用[first, last]区间中的元素构造list

1.1.2 Capacity

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

1.1.3 Element access

函数声明	接口说明
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用函数声明

1.1.4 Modifiers

函数声明	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list position 位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

1.1.5 注意事项

• 由于 list 的物理结构是非连续的，前一个节点地址和后一个节点地址的位置关系是随机的，所以 list 不支持随机访问，自然也就不支持 [] 操作。
• list 不支持 reserve操作，因为 list 的节点是使用时开辟，使用完销毁，不能预留空间。

1.2 list 特殊接口

除了上述 STL 容器基本都有的一般接口外，list 还提供一些独有的特殊操作接口，如下：

函数声明	接口说明
splice	将 list1 中的元素转移到 list2 中
remove	移除 list 中的指定元素
unique	链表去重
merge	合并两个链表
sort	链表排序
reverse	链表逆置

1.2.1 注意事项

• 链表排序只能使用 list 提供的 sort 接口，而不能使用 algorithm 提供的 sort 接口。

  因为链表（list）物理地址不连续，迭代器为双向迭代器，不支持 + - 操作，而算法库中的 sort 函数需要支持 + - 的随机迭代器。有关迭代器种类的详细介绍，请继续阅读。

• 链表去重之前必须保证链表有序，否则去重不完全。

• 两个有序链表合并之后仍然保存有序。

最后，虽然 list 提供了这些具有特殊功能的接口，它们也确实有一定的作用，但是实际上这些特殊接口使用频率非常低，包括 sort 接口 (链表排序的效率太低)，下面会进行详细介绍。

1.3 list 排序的性能分析

虽然链表排序只能使用 list 提供的 sort 接口，而不能使用 algorithm 提供的 sort 接口，但是其使用频率仍然非常低，这是由于链表排序的效率太低了，可以通过对比两组测试数据来直观的感受链表排序的效率。

1.3.1 测试一：vector 排序与 list 排序性能对比

//vector sort 和 list sort 性能对比 -- release 版本下
void test_op1() {srand((size_t)time(0));const int N = 1000000;  //100万个数据vector<int> v;v.reserve(N);list<int> lt;for (int i = 0; i < N; ++i){auto e = rand();v.push_back(e);lt.push_back(e);}//vector sortint begin1 = clock();sort(v.begin(), v.end());int end1 = clock();//list sortint begin2 = clock();lt.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}

1.3.2 测试二：list 直接进行排序与将数据拷贝到 vector 中使用 vector 排序后再将数据拷回 list 中性能对比

//list sort 与 将数据转移到 vector 中进行排序后拷贝回来性能对比 -- release 版本下
void test_op2()
{srand(time(0));const int N = 1000000;  //100万个数据list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){auto e = rand();lt1.push_back(e);lt2.push_back(e);}//list sort -- lt1int begin1 = clock();lt1.sort();int end1 = clock();// 将数据拷贝到vector中排序，排完以后再拷贝回来 -- lt2int begin2 = clock();vector<int> v;v.reserve(N);for (auto e : lt2)  //拷贝{v.push_back(e);}sort(v.begin(), v.end());  //排序lt2.assign(v.begin(), v.end());  //拷贝int end2 = clock();printf("list1 sort:%d\n", end1 - begin1);printf("list2 sort:%d\n", end2 - begin2);
}

1.3.3 总结

可以看到，list sort 的效率远低于 vector sort，甚至于说，直接使用 list sort 的效率都不如先将数据拷贝到 vector 中，然后使用 vector sort，排序之后再将数据拷贝回 list 中快。至此也能明白为什么 list sort 接口使用的非常少了。

**注意：**在 release 版本下测试软件或算法性能得到的结果要比在 debug 版本下得到的结果具有参考意义。

2. list 迭代器的实现

2.1 迭代器的分类

按照迭代器的功能，迭代器一共可以分为以下三类：

• 单向迭代器：迭代器仅仅支持 ++ 和解引用操作，单链表（ forword_list ）的迭代器是典型的单向迭代器。

• 双向迭代器：迭代器支持 ++、– 和解引用操作，但不支持 +、- 操作，list (双向带头循环链表) 是典型的双向迭代器。

• 随机迭代器：迭代器不仅支持 ++、– 和解引用操作，还支持 +、- 操作，即迭代器能够随机访问，前面学习的 string 和 vector 的迭代器是典型的随机迭代器。

2.2 迭代器失效问题

和 vector 不同，list 进行 insert 操作后并不会产生迭代器失效问题，因为 list 插入的新节点是动态开辟的，同时由于 list 每个节点的物理地址是不相关的，所以插入的新节点并不会影响原来其他节点的地址。

但是 list erase 之后会发生迭代器失效，因为 list 删除节点会直接将该节点释放掉，此时如果再访问该节点就会造成越界访问。

2.3 迭代器类实现的意义

之前模拟实现 string 和 vector 时都没有说要实现一个迭代器类，为什么实现 list 的时候就需要实现一个迭代器类了呢？

因为 string 和 vector 对象都将其数据存储在了一块连续的内存空间，可以通过指针进行自增、自减以及解引用等操作，就可以对相应位置的数据进行一系列操作，因此 string 和 vector 当中的迭代器就是原生指针。

但是对于 list 来说，其各个结点在内存当中的位置是随机的，并不是连续的，不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作。

而迭代器的意义就是，让使用者可以不必关心容器的底层实现，可以用简单统一的方式对容器内的数据进行访问。

既然 list 的结点指针的行为不满足迭代器定义，那么可以对这个结点指针进行封装，对结点指针的各种运算符操作进行重载，使得可以用和 string 和 vector 当中的迭代器一样的方式使用 list 当中的迭代器。例如，当使用 list 当中的迭代器进行自增操作时，实际上执行了 p = p->next 语句，只是使用者不知道而已。

总结：

• list 迭代器类，实际上就是对结点指针进行了封装，对其各种运算符进行了重载，使得结点指针的各种行为看起来和普通指针一样。（例如，对结点指针自增就能指向下一个结点）
• 所以所有迭代器存在的意义就是提供一种统一的方式去访问、修改底层结构存在差异的不同的容器。使得不同的容器可以使用同一套方法去访问、修改其中的数据，使用者不用关心容器底层的结构是什么。
• 迭代器的设计思路体现了封装，屏蔽了底层实现细节，屏蔽了各容器结构的差异，本质封装底层细节和差异，提供统一的访问方式。

2.4 迭代器模拟实现

根据前面 string 和 vector 中迭代器的了解可以知道，迭代器也分为普通迭代器和const迭代器。可以通过模版参数进行合理区分，分别实现出不同类型的迭代器。

2.4.1 普通迭代器

list 普通迭代器的实现比较简单，只需要一个模板参数 T 来代表数据类型，然后通过运算符重载来实现迭代器的各种操作即可：

//typedef __list_iterator<T> iterator -- 普通迭代器
template<class T>
struct list_iterator
{typedef list_node<T> Node;	//将list节点重命名为Nodetypedef list_iterator<T> Self;	//将list迭代器重命名为SelfNode* _node;	//节点指针作为类的唯一成员变量list_iterator(Node* node)	//默认构造:_node(node){}T& operator*()	//解引用{return _node->_data;}T* operator->()	//->{return &_node->_data;}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;}bool operator!=(const Self& s)	//!={return _node != s._node;}bool operator==(const Self& s)	//=={return _node == s._node;}
};

2.4.2 const迭代器

上面的迭代器是普通迭代器，那么如何实现 const 迭代器呢？

const 迭代器与普通迭代器的区别在于const 迭代器不能修改解引用后节点中的数据，即 operator*() 函数的返回值应该是 const T& 类型的。

错误思路：

那么可能有人会这样来实现 const 迭代器，即在上面实现的普通迭代器的 list_iterator 类中重载一个返回值为 const T& 的 operator*() 函数，如下：

//typedef list_iterator<T> iterator -- 迭代器
//typedef const list_iterator<T> const_iterator  -- const 迭代器
template<class T>
struct list_iterator 
{//普通迭代器T& operator*()  {return _pnode->_data;}//const迭代器const T& operator*() const{return _pnode->_data;}
};

但是是不行的，因为 const list_iterator<T> const_iterator 中 const 修饰的是 const_iterator 本身，即限制 const_iterator 不能改变，这样会导致 const_iterator 不能进行 ++ 等操，而迭代器被解引用后节点数据仍可以改变，这并不符合 const 迭代器的要求。

正确思路：

应该为 const 迭代器设计一个单独的类 list_const_iterator：

//typedef __list_const_iterator<T> const_iterator -- const迭代器
template<class T>
struct list_const_iterator
{typedef list_node<T> Node;	//将list节点重命名为nodetypedef list_const_iterator<T> Self;	//将const list迭代器重命名为SelfNode* _node;	//节点指针作为类的唯一成员变量list_const_iterator(Node* node)	//默认构造:_node(node){}const T& operator*()	 //解引用{return _node->_data;}const T* operator->()	//->{return &_node->_data;}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;}bool operator!=(const Self& s)	//!={return _node != s._node;}
};

可以看到，list_iterator 类和 list_const_iterator 类除了类名和 operator*() 函数和 operator->() 的返回值不同以外，其他地方完全相同，这就会造成严重的代码冗余。

大佬显然是不会运行这种冗余存在的，所以想到了另一种办法来解决 const 迭代器的问题，那就是向 list_iterator 中增加一个模板参数，通过模版参数来控制模版生成所需要的类是 list_iterator 还是 list_const_iterator ，如下：

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--(){_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;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};

迭代器类的模板参数列表当中的 Ref 和 Ptr 分别代表的是引用类型和指针类型。

//使用者
list<int, T&， T*>::iterator it;  //普通迭代器
list<int, const T&, const T*>::iterator cit;  //const 迭代器

3. list 的模拟实现

和 vector 一样，类模版不支持分离成多个文件，这里 list 的模拟实现也都是在 list.h 的头文件中实现。

3.1 list 的基本结构

//list.h
namespace tcq
{//利用模版先构造出一个节点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){}};//list类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;//成员函数private://成员变量Node* _head;	//哨兵位头结点
}

• list 的基本结构是根据一个个节点组成，所以在实现 list 基本结构的时候，需要先通过模版实现出 list_node 。

• 内部类 Node

  这里在 list 类中，利用 typdef 的 Node 相当于一个内部类，这里的 Node 是收到了 list 这个类的类域限制的。并且由于没有使用访问限定符修饰也就表示这个 Node 是私有的，只能在类的内部用，在 list 类外不可用。

• struct 和 class 的区别

  基本没有区别。但是注意，在 struct 中没有使用访问限定符的成员默认会是共有的，可以在 struct 外使用；但是在 class 中没有使用访问限定符的成员默认会是私有的，不可以在 class 外使用。

  **惯例：**一个类既有公有也有私有，就用 class；一个类如果全是公有，就用 struct。

• 重定义迭代器

  这里使用 typedef 重定义了 iterator 和 const_iterator，便于后续模拟实现 list 中的成员函数。

3.2 list 的构造和析构

3.2.1 构造函数

list是一个带头双向循环链表，在构造一个list对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己即可。

3.2.1.1 默认构造

//list.h
list()
{_head = new Node; //申请一个头结点_head->_next = _head; //头结点的后继指针指向自己_head->_prev = _head; //头结点的前驱指针指向自己
}

3.2.1.2 n个val构造

//list.h
list(size_t n, const T& val = T())
{_head = new Node; //申请一个头结点_head->_next = _head; //头结点的后继指针指向自己_head->_prev = _head; //头结点的前驱指针指向自己for(size_t i = 0; i < n; i++)	//循环插入数据{push_back(val);}
}

3.2.1.3 拷贝构造

//list.h
list(const list<T>& lt)
{_head = new node; //申请一个头结点_head->_next = _head; //头结点的后继指针指向自己_head->_prev = _head; //头结点的前驱指针指向自己for (const auto& e : lt){push_back(e); //将容器lt当中的数据一个个尾插到新构造的容器后面}
}

3.2.2 析构函数

//list.h
~list()
{clear(); //清理容器delete _head; //释放头结点_head = nullptr; //头指针置空
}

3.3 list 迭代器相关函数

3.3.1 begin和end

首先应该明确的是：begin函数返回的是第一个有效数据的迭代器，end函数返回的是最后一个有效数据的下一个位置的迭代器。

对于 list 这个带头双向循环链表来说，其第一个有效数据的迭代器就是使用头结点后一个结点的地址构造出来的迭代器，而其最后一个有效数据的下一个位置的迭代器就是使用头结点的地址构造出来的迭代器。（最后一个结点的下一个结点就是头结点）

//list.h
iterator begin()
{//返回使用头结点后一个结点的地址构造出来的普通迭代器return iterator(_head->_next);
}
iterator end()
{//返回使用头结点的地址构造出来的普通迭代器return iterator(_head);
}

当然，还需要重载一对用于const对象的begin函数和end函数。

const_iterator begin() const
{//返回使用头结点后一个结点的地址构造出来的const迭代器return const_iterator(_head->_next);
}
const_iterator end() const
{//返回使用头结点的地址构造出来的普通const迭代器return const_iterator(_head);
}

3.4 list 的插入和删除

3.4.1 insert

insert函数可以在所给迭代器之前插入一个新结点。

先根据所给迭代器得到该位置处的结点指针 cur，然后通过 cur 指针找到前一个位置的结点指针 prev，接着根据所给数据 x 构造一个待插入结点，之后再建立新结点与 cur 之间的双向关系，最后建立新结点与 prev 之间的双向关系即可。

//插入函数
iterator insert(iterator pos, const T& x)
{assert(pos._pnode); //检测pos的合法性node* cur = pos._pnode; //迭代器pos处的结点指针node* prev = cur->_prev; //迭代器pos前一个位置的结点指针node* newnode = new node(x); //根据所给数据x构造一个待插入结点//建立newnode与cur之间的双向关系newnode->_next = cur;cur->_prev = newnode;//建立newnode与prev之间的双向关系newnode->_prev = prev;prev->_next = newnode;return iterator(newnode);
}

同时因为这里的 list 不涉及扩容之类的情况，所以也就不存在和 vector 中一样的迭代器失效问题。

3.4.2 erase

erase函数可以删除所给迭代器位置的结点。

先根据所给迭代器得到该位置处的结点指针 cur ，然后通过 cur 指针找到前一个位置的结点指针 prev ，以及后一个位置的结点指针 next ，紧接着释放 cur 结点，最后建立 prev 和 next 之间的双向关系即可。

//删除函数
iterator erase(iterator pos)
{assert(pos._pnode); //检测pos的合法性assert(pos != end()); //删除的结点不能是头结点node* cur = pos._pnode; //迭代器pos处的结点指针node* prev = cur->_prev; //迭代器pos前一个位置的结点指针node* next = cur->_next; //迭代器pos后一个位置的结点指针delete cur; //释放cur结点//建立prev与next之间的双向关系prev->_next = next;next->_prev = prev;return iterator(next); //返回所给迭代器pos的下一个迭代器
}

同时因为这里的 list 不涉及扩容之类的情况，所以也就不存在和 vector 中一样的迭代器失效问题。

3.4.3 push_back和pop_back

push_back和pop_back函数分别用于 list 的尾插和尾删，在已经实现了 insert 和 erase 函数的情况下，可以通过复用函数来实现 push_back 和 pop_back 函数。

push_back 函数就是在头结点前插入结点，而 pop_back 就是删除头结点的前一个结点。

//尾插
void push_back(const T& x)
{insert(end(), x); //在头结点前插入结点
}
//尾删
void pop_back()
{erase(--end()); //删除头结点的前一个结点
}

3.4.3 push_front和pop_front

当然，用于头插和头删的 push_front 和 pop_front 函数也可以复用 insert 和 erase 函数来实现。

push_front 函数就是在第一个有效结点前插入结点，而 pop_front 就是删除第一个有效结点。

//头插
void push_front(const T& x)
{insert(begin(), x); //在第一个有效结点前插入结点
}
//头删
void pop_front()
{erase(begin()); //删除第一个有效结点
}

3.5 list 的其他函数

3.5.1 clear

clear函数用于清空容器，通过遍历的方式，逐个删除结点，只保留头结点即可。

void clear()
{auto it = begin();while (it != end())	 //逐个删除结点，只保留哨兵位头结点{it = erase(it);}
}

3.5.2 operator =

对于赋值运算符的重载，这里提供两种写法：

写法一：传统写法

传统写法是一种比较容易理解的写法，先调用 clear 函数将原容器清空，然后将容器 lt 当中的数据，通过遍历的方式一个个尾插到清空后的容器当中即可。

//operator=传统写法
list<T>& operator=(const list<T>& lt)
{if (this != &lt) //避免自己给自己赋值{clear(); //清空容器for (const auto& e : lt){push_back(e); //将容器lt当中的数据一个个尾插到链表后面}}return *this; //支持连续赋值
}

写法二：现代写法

现代写法的代码量较少，首先利用编译器机制，故意不使用引用接收参数，通过编译器自动调用list的拷贝构造函数构造出来一个 list 对象，然后调用 swap 函数将原容器与该 list 对象进行交换即可。

//operator=现代写法
list<T>& operator=(list<T> lt) //编译器接收右值的时候自动调用其拷贝构造函数
{swap(lt); //交换这两个对象return *this; //支持连续赋值
}

这样做相当于将应该用 clear 清理的数据，通过交换函数交给了容器 lt ，而当该赋值运算符重载函数调用结束时，容器 lt 为栈上的局部变量会自动销毁，并调用其析构函数进行清理。

3.5.3 size

size 函数用于获取当前容器当中的有效数据个数，因为 list 是链表，所以只能通过遍历的方式逐个统计有效数据的个数。

//list.h
size_t size() const
{size_t sz = 0; //统计有效数据个数const_iterator it = begin(); //获取第一个有效数据的迭代器while (it != end()) //通过遍历统计有效数据个数{sz++;it++;}return sz; //返回有效数据个数
}

**补充：**其实也可以给 list 多设置一个成员变量 size ，用于记录当前容器内的有效数据个数。这种方法更加高效。

3.5.4 swap

swap函数用于交换两个容器，list容器当中存储的实际上就只有链表的头指针，将这两个容器当中的头指针交换即可。

//list.h
void swap(list<T>& lt)
{std::swap(_head, lt._head); //交换两个容器当中的头指针即可
}

补充：

在此处调用库当中的 swap 函数需要在 swap 之前加上“::”（作用域限定符），告诉编译器这里优先在全局范围寻找 swap 函数，否则编译器会认为你调用的就是你正在实现的 swap 函数（就近原则）。

实现这个 swap 的目的是因为标准库中的 swap 使用的是深拷贝，生成出新的临时对象再使用拷贝构造进行交换，会浪费大量资源，十分低效。然而在 list 中实现的 swap 可以直接交换 list 类中的唯一成员变量，也就是头结点指针即可。这样更加节省资源，更加高效。

3.5.5 resize

resize函数的规则：

1. 若当前容器的 size 小于所给 n ，则尾插结点，直到 size 等于 n 为止。
2. 若当前容器的 size 大于所给 n ，则只保留前 n 个有效数据。

实现 resize 函数时，不要直接调用 size 函数获取当前容器的有效数据个数，因为当调用 size 函数后就已经遍历了一次容器了，而如果结果是 size 大于 n ，那么还需要遍历容器，找到第 n 个有效结点并释放之后的结点。

这里实现 resize 的方法是，设置一个变量 len ，用于记录当前所遍历的数据个数，然后开始变量容器，在遍历过程中：

1. 当 len 大于或是等于 n 时遍历结束，此时说明该结点后的结点都应该被释放，将之后的结点释放即可。
2. 当容器遍历完毕时遍历结束，此时说明容器当中的有效数据个数小于 n ，则需要尾插结点，直到容器当中的有效数据个数为 n 时停止尾插即可。

//list.h
void resize(size_t n, const T& val = T())
{iterator i = begin(); //获取第一个有效数据的迭代器size_t len = 0; //记录当前所遍历的数据个数while (len < n&&i != end()){len++;i++;}if (len == n) //说明容器当中的有效数据个数大于或是等于n{while (i != end()) //只保留前n个有效数据{i = erase(i); //每次删除后接收下一个数据的迭代器}}else //说明容器当中的有效数据个数小于n{while (len < n) //尾插数据为val的结点，直到容器当中的有效数据个数为n{push_back(val);len++;}}
}

4. vector 和 list 的区别

vector 和 list 的区别其实就是顺序表和带头双向链表的区别，但是由于相较于数据结构初阶又增添了 C++ 的相关知识，所以这里还是重新列举一下二者的异同与优缺：

	vector	list
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素时间复杂度O(1)	不支持随机访问，访问某个元素时间复杂度O(N)
插入和删除	任意位置插入和删除效率低，需要移动元素，时间复杂度O(N)，插入时有可能需要额外扩容，导致效率更低	任意位置插入和删除效率高，不需要移动元素，时间复杂度为O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层节点为分块存储，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	插入元素时，可能会导致所有迭代器失效，因为插入元素有可能会导致底层结构重新分配空间	插入元素不会导致迭代器失效，删除元素时，只会导致指向被删除元素的迭代器失效
使用场景	需要高效存储，支持随机访问，不关心插入删除效率	大量插入和删除操作，不关心随机访问