C++起始之路——list

👇作者其它专栏

《数据结构与算法》《算法》《C++起始之路》

目录

1.list的介绍及使用

2.list的模拟实现

3.list与vector的对比

1.list的介绍及使用

1.1list的介绍

list的文档介绍

1.2list的使用

list中的接口比较多，一下为一些常见的重要接口。

1.2.1list的构造

1.2.2list iterator的使用

可以暂时将迭代器理解成一个指针，该指针指向list中的某个结点。

【注意】

1.begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

2.rbegin（end）与rend（begin）为反向迭代器，对迭代器执行++操作，迭代器向前移动

1.2.3list capacity

1.2.4list element access

1.2.5list modifiers

1.2.6list的迭代器失效

上文提到，可以暂时将迭代器理解类似于指针，迭代器失效即迭代器所指向的结点无效，即该结点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除结点的迭代器，其他迭代器不会受到影响。

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()){ //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()){ l.erase(it++);//it=l.erase(it); } }

2.list的模拟实现

2.1模拟实现list

list的模拟实现

2.2list的反向迭代器

由上文可知，反向迭代器的++就是正向迭代器的--，反向迭代器的--就是正向迭代器的++，因此反向迭代器的实现可以借助正向迭代器，即：反向迭代器内部可以包含一个正向迭代器，对正向迭代器的接口进行包装即可。

template<class Iterator> class ReverseListIterator{ //注意： //此处typename的作用是明确告诉编译器，Ref是Iterator类中的类型，而不是静态成员变量 //否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量 //因为静态成员变量也是按照 类名::静态成员变量名 的放式访问的 public: typedef typename Iterator::Ref Ref; typedef typename Iterator::Ptr Ptr; typedef ReverseListIterator<Iterator> Self; //构造 ReverseListIterator(Iterator it):_it(it){} //具有指针类似行为 Ref operator*(){ Iterator tmp(_it); --tmp; return *tmp; } Ptr operator->(){ return &(operator*());} //迭代器支持移动 Self& operator++(){ --_it; return *this; } Self operator++(){ Self tmp(*this); --_it; return tmp; } Self& operator--(){ ++_it; return *this; } Self& operator--(int){ Self tmp(*this); ++_it; return tmp; } //迭代器支持比较 bool operator!=(const Self& l)const { return _it!=l.it; } bool operator==(const Self& l)const { return _it==l.it; }

3.list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不同，其主要不同如下：