C++中的list

一丶 list的介绍和使用1. list的介绍2. list的使用I. list的构造II. list iterator的使用III.list capacityIV.list element accessV. list modifiers

VI. list迭代器失效的问题

二丶list的模拟实现三丶list与vector的对比

一丶 list的介绍和使用

1. list的介绍

1.list是可以在常数范围内任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，forward_lis已让其更简单高效。

4. 与其他的序列式容器相比(比方说array，vector，deque), list通常在任意位置进行插入丶移除元素的执行效率更好。

5. 与其他序列式容器相比，list和forward_list的最大缺陷是不支持任意位置的随机访问。这跟链表的随机访问是一致的，效率极低。

库中的list属于双向循环带头链表。

关于list的示意图如下：

2. list的使用

我们这里只叙述list常用的一些功能。

I. list的构造

构造函数(constructor)

1. list(size_type n, const value& val = value_type())

构造的list中含有n个值为val的元素

2. list()

构造空的list

3. list(const list& x)

拷贝构造函数

4. list(InputIterator first, InputIterator last)

用[first, last)区间中的元素构造list

II. list iterator的使用

我们可以把iterator暂时理解为指针，该指针指向list某个节点。

iterator

1. bgein+end

begin()返回第一个元素的迭代器，end()返回最后一个元素的下一个位置的迭代器。

2. rbegin+rend

rbegin()返回最后一个元素对应的反向迭代器，rend()返回第一个元素之前的反向迭代器。

关于正丶反迭代器指向的示意图：

这里对于正反向迭代器的++和–的移动方向进行说明：

begin()和end()都是正向迭代器，对迭代器执行++操作时，迭代器向后移动；执行- -操作则向前移动。rbegin()和rend()都是反向迭代器，对迭代器进行++操作时，迭代器是向前移动的；执行- -的操作时，则是向后移动。

III.list capacity

list中的容量问题。

1. empty

检测list是否为空，是返回true，否则返回false

2. size

返回list中有效节点的个数

IV.list element access

关于list中元素的访问

1. front

返回list的第一个节点中值的引用

2. back

返回list的最后一个节点中值的引用

V. list modifiers

关于list的修改操作

1. push_back

在list首元素前插入值为val的元素

2. pop_front

删除list中的第一个元素

3. push_back

在list尾部插入值为val的元素

4.pop_back

删除list中最后一个元素

5.insert

在list position位置中插入值为val的元素

6.erase

删除list position位置的元素

7. swap

交换两个list中的元素

8. clear

清空list中的有效元素

VI. list迭代器失效的问题

我们在前面说过，迭代器可以暂时理解为指针。list中的迭代器失效即迭代器指向的节点的无效，即该节点被删除了。因为list的底层结构是带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的；只有在删除时才会失效，而且失效的只是被删除的迭代器，其他位置的迭代器不会受到影响。

<code>void TestListIterator1()

{ -- -->

int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };

list<int> l(array, array + sizeof(array) / sizeof(array[0]));

auto it = l.begin();

while (it != l.end())

{

// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值

l.erase(it);

++it;

}

}

// 改正

void TestListIterator()

{

int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };

list<int> l(array, array + sizeof(array) / sizeof(array[0]));

auto it = l.begin();

while (it != l.end())

{

it = l.erase(it);

++it;

}

}

二丶list的模拟实现

声明一下，我们在List.h中实现各个功能，同时存放测试代码，并在List.cpp中直接测试。

List.h

#pragma once

#include <assert.h>

namespace bit

{

template<class T>

struct ListNode

{

//C++定义一个类 既可以用class 也可以用struct

//当有公有又有私有时 通常使用class

//当基本都是公有是 一般使用struct

ListNode<T>* _next;

ListNode<T>* _prev;

T _data;

ListNode(const T& data = T())//实现为匿名对象 确保其通用性

:_next(nullptr)

,_prev(nullptr)

,_data(data)

{ }

};

//将list的结点封装起来 重载++和--的方法

//使其结点通过++或--到达访问下一个或上一个结点的目的

//template<class T>

template<class T, class Ref, class Ptr>

struct ListIterator//此类作为迭代器 无需析构函数释放结点

{ //结点管理要在list中 不要越级管理

typedef ListNode<T> Node;

typedef ListIterator<T, Ref, Ptr> Self;

Node* _node;

ListIterator(Node* node)

:_node(node)

{ }

//不必重载+n或是-n

//因为这样效率太低了

//库中的迭代器也是不支持+n和-n的

//前置++

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;

}

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

bool operator!=(const Self& it)

{

return _node != it._node;

}

bool operator==(const Self& it)

{

return _node == it._node;

}

};

//为何要采用封装Node的写法呢？

//我们实现的是list 双向链表

//既然是链表 那么个节点的物理地址是不连续的

//仅仅++或-- 是获取不到下一个或上一个结点的

//因此必须封装结点 并为其重载++和--操作符

//在重载中实现对应的功能

//list的反向迭代器

//反向迭代器的++就是正向迭代器的--，反向迭代器的--就是

//正向迭代器的++。因此反向迭代器的实现可以借助正向迭代器。即：

//反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口

//进行包装即可。

template<class T, class Ref, class Ptr>

struct ReverseListIterator//此类作为迭代器 无需析构函数释放结点

{ //结点管理要在list中 不要越级管理

typedef ListNode<T> Node;

typedef ReverseListIterator<T, Ref, Ptr> Self;

Node* _node;

ReverseListIterator(Node* node)

:_node(node)

{ }

//不必重载+n或是-n

//因为这样效率太低了

//库中的迭代器也是不支持+n和-n的

//前置++

Self& operator++()

{

_node = _node->_prev;

return *this;

}

//前置--

Self& operator--()

{

_node = _node->_next;

return *this;

}

//后置++

Self operator++(int)

{

Self tmp(*this);

_node = _node->_prev;

return tmp;

}

//后置--

Self operator--(int)

{

Self tmp(*this);

_node = _node->_next;

return tmp;

}

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

bool operator!=(const Self& it)

{

return _node != it._node;

}

bool operator==(const Self& it)

{

return _node == it._node;

}

};

//template<class T>

//class ListConstIterator//此类作为迭代器 无需析构函数释放结点

//{//结点管理要在list中 不要越级管理

//typedef ListNode<T> Node;

//typedef ListConstIterator<T> Self;

//Node* _node;

//public:

//ListConstIterator(Node* node)

//:_node(node)

//{}

////不必重载+n或是-n

////因为这样效率太低了

////库中的迭代器也是不支持+n和-n的

////前置++

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

//}

//const T& operator*() const

//{

//return _node->_data;

//}

//const T* operator->() const

//{

//return &_node->_data;

//}

//bool operator!=(const Self& it)

//{

//return _node != it._node;

//}

//bool operator==(const Self& it)

//{

//return _node == it._node;

//}

//};

template<class T>

class list

{

typedef ListNode<T> Node;

public:

/*typedef ListIterator<T> iterator;

typedef ListConstIterator<T> const_iterator;*/

//注意：不能写成下面这种形式

//typedef ListConstIterator<const T> const_iterator;

//如果这样实现 那么在实例化的时候

//迭代器的类型为const 而Node的类型不是const

//那么类型就会不统一

//鉴于ListIterator和ListConstIterator内部都有很多

//重复的功能 因此我们把它们实现在同一个类中

//这样可以减少代码的冗余程度

typedef ListIterator<T, T&, T*> iterator;//常规迭代器

typedef ListIterator<T, const T&, const T*> const_iterator;//const迭代器

typedef ReverseListIterator<T, T&, T*> reverse_iterator;

typedef ReverseListIterator<T, const T&, const T*> const_reverse_iterator;

reverse_iterator rbegin()

{

//iterator it(_head->_next);

//return it;

return reverse_iterator(_head->_prev);

}

reverse_iterator rend()

{

return reverse_iterator(_head);

}

const_reverse_iterator crbegin() const

{

//iterator it(_head->_next);

//return it;

return const_reverse_iterator(_head->_next);

}

const_reverse_iterator crend() const

{

return const_reverse_iterator(_head);

}

iterator begin()

{

//iterator it(_head->_next);

//return it;

return iterator(_head->_next);

}

iterator end()

{

return iterator(_head);

}

const_iterator cbegin() const

{

//iterator it(_head->_next);

//return it;

return const_iterator(_head->_next);

}

const_iterator cend() const

{

return const_iterator(_head);

}

//empty_init 用于开辟_head结点 因为各个拷贝构造

//都需要先开辟_head结点 因此将此功能提取封装出来

void empty_init()

{

_head = new Node();

_head->_next = _head;

_head->_prev = _head;

}

list()

{ //_head作为哨兵位

/*_head = new Node();

_head->_next = _head;

_head->_prev = _head;*/

empty_init();

}

//拷贝构造

//拷贝构造的具体实现是这样的：

//首先先开辟_head结点 之后再不断地尾插

//push_back内部完成了结点链接操作的封装

// 因此可以直接复用尾插操作

list(const list<T>& lt)

{

empty_init();

auto it1 = lt.cbegin();

while(it1!=lt.cend())

{

//list<T>& lt中的每个结点进行插入

//通过迭代器 来拿到每个结点对应的数据域 插入到this中

push_back(it1._node->_data);

it1++;

}

//由于实现的迭代器begin的问题

//若想运行这里的for循环必须去掉参数中的const

//因为这里的范围for只会获取const_iterator

//而begin是iterator

//造成const_iterator到iterator的转换问题

/*for (const auto& e : lt)

{

push_back(e);

}*/

}

list(initializer_list<T> il)

{

empty_init();

for (const auto& e : il)

{

push_back(e);

}

}

//传值传参功能实现是这样的：

//直接利用swap函数进行交换

//注意这里的参数不是引用类型

//也就是说 这里会调用拷贝构造生成一个局部的临时对象lt

//然后 我们直接将*this和lt进行一个swap操作的值交换

//交换其中的_head _head是头结点

//拿到了它 就等于拿到了整个链表

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

{

swap(_head, lt._head);

return *this;

}

//~list的功能是这样的：

//先清理各个结点 最后把_head清理了 让整个链表都清理干净

~list()

{

clear();

delete _head;

_head = nullptr;

}

//clear的功能是将每个结点的清理掉 除了_head结点

void clear()

{

auto it = begin();

while (it != end())

{

it = erase(it);

}

}

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;*/

insert(end(), x);

}

void pop_back()

{

erase(--end());

}

void push_front(const T& x)

{

insert(begin(), x);

}

void pop_front()

{

erase(begin());

}

//insert操作鉴于没有扩容缩容的操作

//因此不存在迭代器失效的问题

iterator insert(iterator pos, const T& x)

{

Node* cur = pos._node;

Node* newnode = new Node(x);

Node* prev = cur->_prev;

prev->_next = newnode;

newnode->_next = cur;

cur->_prev = newnode;

newnode->_prev = prev;

//返回新插入的结点迭代器

return iterator(newnode);

}

//erase要对pos结点进行delete操作

//那么必然会出现pos迭代器失效的问题

iterator erase(iterator pos)

{

assert(pos != end());

Node* cur = pos._node;

Node* prev = cur->_prev;

Node* next = cur->_next;

prev->_next = next;

next->_prev = prev;

delete cur;

return iterator(next);

}

private:

Node* _head;

};

//const迭代器 可以修改迭代器的指向 但不能修改迭代器指向的空间内容

void Func(const list<int>& lt)

{

list<int>::const_iterator it = lt.cbegin();

//const迭代器 可以修改迭代器的指向 但不能修改指向的内容

while (it != lt.cend())

{

//*it += 10;//const属性 不允许修改的操作

cout << *it << " ";

++it;

}

cout << endl;

}

void test_list1()

{

list<int> lt1;

lt1.push_back(1);

lt1.push_back(2);

lt1.push_back(3);

lt1.push_back(4);

lt1.push_back(5);

list<int>::iterator it = lt1.begin();

while (it != lt1.end())

{

cout << *it << " ";

cout << endl;

cout << it.operator->() << endl;

//当T为内置类型时 it和it.operator->()是没有区别的

//当T为自定义类型时 it-> 等价于 it.operator->()->

++it;

}

cout << endl;

}

struct Pos

{

Pos(int row = 0, int col = 0)

:_row(row)

,_col(col)

{ }

int _row;

int _col;

};

void test_list2()

{

list<Pos> lt1;

lt1.push_back(Pos(100, 100));

lt1.push_back(Pos(200, 200));

lt1.push_back(Pos(300, 300));

list<Pos>::iterator it = lt1.begin();

while (it != lt1.end())

{

//cout << (*it)._row << ":" << (*it)._col << endl;

//这种写法只是为了通用性和可读性

cout << it->_row << ":" << it->_col << endl;

//这里是如何通过->进行调用的呢？

//上面的原型是这样的：

cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;

//首先我们重载了->。 它的功能是这样的：返回数据域的指针

//第一次it->operator() 我们拿到了数据域的指针

//然后因为这里的数据是一个名为Pos的结构体 结构体本身满足使用->来访问成员

//因此第二次-> 来拿到各项成员

//上面的一行 使用一个-> 是一种简写的方法

it++;

}

cout << endl;

}

void test_list3()

{

使用常规迭代器访问常规对象

//list<int> lt1;

//lt1.push_back(1);

//lt1.push_back(2);

//lt1.push_back(3);

//lt1.push_back(4);

//lt1.push_back(5);

//list<int>::iterator it1 = lt1.begin();

//while (it1 != lt1.end())

//{

//*it1 += 10;

//cout << *it1 << " ";

//it1++;

//}

//cout << endl;

//Func(lt1);

//使用const型迭代器访问const型对象

//list<int>::const_iterator it2 = lt2.begin();

//while (it2 != lt2.end())

//{

////*it2 += 10;

//cout << *it2 << " ";

//it2++;

//}

//cout << endl;

}

void test_list4()

{

list<int> lt1;

lt1.push_back(1);

lt1.push_back(2);

lt1.push_back(3);

lt1.push_back(4);

lt1.push_back(5);

Func(lt1);

lt1.push_front(10);

lt1.push_front(20);

lt1.push_front(30);

Func(lt1);

lt1.pop_front();

lt1.pop_front();

Func(lt1);

lt1.pop_back();

lt1.pop_back();

Func(lt1);

}

void test_list5()

{

list<int> lt1;

lt1.push_back(1);

lt1.push_back(2);

lt1.push_back(3);

lt1.push_back(4);

lt1.push_back(5);

Func(lt1);

list<int>::reverse_iterator it = lt1.rbegin();

while (it != lt1.rend())

{

cout << *it << " ";

it++;

}

cout << endl;

}

void test_list6()

{

list<int> lt1;

lt1.push_back(1);

lt1.push_back(2);

lt1.push_back(3);

lt1.push_back(4);

lt1.push_back(5);

list<int> lt2(lt1);

Func(lt1);

Func(lt2);

lt1.push_back(6);

Func(lt1);

Func(lt2);

}

void test_list7()

{

list<int> lt1;

lt1.push_back(1);

lt1.push_back(2);

lt1.push_back(3);

lt1.push_back(4);

lt1.push_back(5);

list<int> lt3;

lt3.push_back(10);

lt3.push_back(20);

lt3.push_back(30);

Func(lt1);

Func(lt3);

lt1 = lt3;

Func(lt1);

Func(lt3);

}

void test_list8()

{

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

Func(lt1);

}

}

List.cpp

list中是双向迭代器，而不是随机迭代器

因此不允许使用sort全局方法 list在内部实现了自己的sort方法

此外 list的迭代器允许++ -- 但不允许+n -n

list为双向链表

//

//#include <iostream>

//#include <list>

//

//using namespace std;

//

//void test_list1()

//{

//list<int> lt1 = { 10,2,3,3,5,5,4,5,6 };

//list<int>::iterator it = lt1.begin();

//

//while (it != lt1.end())

//{

//cout << *it << " ";

//++it;

//}

//cout << endl;

//

//lt1.unique();//去重 不是有序的情况下 去重去除的不干净 因为它要求相同值必须都挨在一起

//

//for (auto e : lt1)

//{

//cout << e << " ";

//}

//cout << endl;

//

////sort(lt1.begin(), lt1.end());//不行 因为只有随机迭代器才能使用sort全局方法

//lt1.sort();//默认升序

//for (auto e : lt1)

//{

//cout << e << " ";

//}

//cout << endl;

//

//lt1.sort(greater<int>()); //利用仿函数实现降序

//for (auto e : lt1)

//{

//cout << e << " ";

//}

//cout << endl;

//

////去重

//lt1.unique();//该方法的使用前提是：list必须是有序的

//for (auto e : lt1)

//{

//cout << e << " ";

//}

//cout << endl;

//}

//

//void test_list2()

//{

////list.sort()的底层是归并排序 用处不大

////在数据量较大时 list的sort效率极低 远不如sort vector

////全局中的sort使用的是快排

//}

//

//int main()

//{

//test_list1();

//

//return 0;

//}

#include <iostream>

using namespace std;

#include "List.h"

int main()

{

/*bit::test_list1();*/

//bit::test_list2();

//bit::test_list3();

//bit::test_list4();

/*bit::test_list5();*/

/*bit::test_list6();*/

/*bit::test_list7();*/

bit::test_list8();

return 0;

}

三丶list与vector的对比

vector和list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，下面我们来阐述一下他们的不同点：

	vector	list
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素的效率为O(1)	不支持随机访问，访问某个元素的效率为O(N)
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容。增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层结点动态开辟，小结点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针(结点指针进行封装)
迭代器失效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值，否则会失效	插入元素不会导致迭代器失效；删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景	需要高效存储，支持随机访问，不关心插入和删除效率	大量插入和删除操作，不关心随机访问

---

本博客仅供个人参考，如有错误请多多包含。

---

Aruinsches-C++日志-5/30/2024

---