C++——list-开发者社区

一、基本概念

list就是带头的循环双向链表模板类。它的迭代器是双向迭代器，不支持[ ]的重载和用+/-随机访问数据。

（1）

三、常用接口

构造、迭代器、empty、size、front、back、不支持[ ]重载、assign、push_front、pop_front、push_back、pop_back、insert、erase、swap、resize、clear、、、、、、

迭代器不是原生指针，由于物理上内存不是连续的，所以不能通过迭代器 + e 来访问下一个位置的元素

二、迭代器的分类

（1）按照性质进行分类

①输入/只读迭代器（Input Iterator）

输入迭代器又叫只读迭代器。类似于一个只能读数据，不能修改数据，仅支持++，不支持--的指针。通常用于单向向后遍历。

②输出/只写迭代器（Output Iterator）

输出迭代器又叫只写迭代器。类似于一个只能写数据，不能读取数据，仅支持++，不支持--的指针。通常用于从单向向后写入。

③前向迭代器/单向(读写)迭代器（Forward Iterator）

输出迭代器又叫只写迭代器。类似于一个可以读可写数据，仅支持++，不支持--的指针。通常用于从单向向后遍历写入。（和只读迭代器一样，要想修改某个位置的数据，只能通过遍历去修改）

这里以forward_list(不带头的不循环的单向链表类模板)。由于单链表在物理结构上不是连续的(遍历时不能使用+/-，不能通过下标访问某个节点的数据)，而且不能往回遍历(不能使用--)。所以在设计它的迭代器时也就设计成了前向迭代器。

下面用具体的代码感受一下：

#include<iostream> #include<forward_list> using namespace std; //单向迭代器 int main() { forward_list<int> f{1,2,3}; forward_list<int>::iterator it = f.begin(); cout << *it << endl;//可读 ++it;//仅支持++ cout << *it << endl;//可写 //--it;//不支持--会报错 }

④双向迭代器/双向读写迭代器(Bidirectional Iterator)

双向迭代器又叫做双向读写迭代器。类似于一个可以读可写数据，支持++/--的指针。通常用于从双向遍历和写入。（和只读迭代器一样，要想修改某个位置的数据，只能通过遍历去修改）

由于list带头双向循环链表的设计，所以它的迭代器也就设计成了双向迭代器。

⑤随机访问迭代器(Random Access Iterator)

随机访问迭代器又叫做随机读写迭代器。类似于一个可以读可写数据，既支持++、--，还支持加减整数、下标访问、大小比较的指针。即能双向遍历，也可以通过下标随机访问数据，类似于顺序表。

string和vector的底层是数组。根据这种结构string和vector的迭代器就被设计成了随机访问迭代器。

string迭代器

vector迭代器

（2）迭代器按照功能进行分类

迭代器按照功能共有四种。分别是普通迭代器和反向迭代器以及他们的const版本——普通只读迭代器，普通反向迭代器。

三、list常用接口

（1）构造

①无参的默认构造

创建一个空的list(仅带哨兵位)。

int main() { list<int> l;//调用默认构造 }

②填充构造

创建n个值为val的list。

int main() { list<int> l(5,0);//填充构造 for (auto e : l) { cout << e << "->"; } cout << endl; }

③迭代器范围构造

用迭代器进行构造，但是需要注意list的迭代器是双向迭代器。不支持+/-，仅支持++/--

int main() { list<int> l1(10,0);//填充构造 //list<int> l2(l1.begin(),l1.begin() + 3);//错误写法，list迭代器是双向读写迭代器 auto last = l1.begin(); ++last; ++last; ++last; list<int> l2(l1.begin(), last);//迭代器构造 for (auto e : l2) { cout << e << "->"; } cout << endl; }

④拷贝构造

用另一个list实例化对象实例化另一个对象。

int main() { list<int> l1(5, 1); list<int> l2(l1);//拷贝构造 for (auto e : l2) { cout << e << "->"; } cout << endl; }

（2）empty

判断链表是否为空链表；为空，输出1；不为空，输出0

int main() { list<int> l1; list<int> l2(5, 0); cout << l1.empty() << endl; cout << l2.empty() << endl; }

（3）size

计算链表中的节点个数。

int main() { list<int> l(100, 0); cout << l.size() << endl; }

（4）front和back

①front

返回list中的第一个元素的引用。reference是list中节点的引用。

②back

返回list中最后一个元素的引用。

int main() { list<int> l{10,20,30}; cout << l.front() << endl; cout << l.back() << endl; }

（5）assign

清空原list并重新对它进行初始化工作。可以形象的理解为先调clear，再调对应的构造。

int main() { list<int> l1(3, 0); list<int> l2{1,2,3,4,5}; l1.assign(l2.begin(), l2.end());//使用迭代器范围接口 Print(l1); l1.assign(5,0);//使用填充接口 Print(l1); l1.assign({10,20,30});//使用初始化列表接口C++11引入 Print(l1); }

（6）push_front/pop_front

头插和头删。

void Print(list<int> l) { for (auto e : l) { cout << e << "->"; } cout << endl; } int main() { list<int> l(3, 0); l.push_front(100);//头插 Print(l); l.pop_front();//头删 Print(l); }

（7）push_back/pop_back

尾插和尾删

void Print(list<int> l) { for (auto e : l) { cout << e << "->"; } cout << endl; } int main() { list<int> l(3, 0); l.push_back(100);//尾插 Print(l); l.pop_back();//尾删 Print(l); }

（8）insert

①next(C++11引入)

使用时必须包含头文件iterator

功能：list的迭代器是一个双向迭代器，无法直接访问某个数据，只能一步步的++或者--。而设计next就是实现了多次的++。

函数原型解释：它有两个参数，第一个参数是当前位置的迭代器，第二个参数是要移动的步数，缺省值为1。返回值类型为当前迭代器的类型

#include<iostream> #include<list> #include<iterator> using namespace std; int main() { list<int> l1{10,20,30,40,50}; list<int> l2(l1.begin(),next(l1.begin(),3));//迭代器构造 for (auto e : l2) { cout << e << "->"; } cout << endl; }

②insert

在指定位置插入之前数据。（在迭代器指向的元素之前插入数据）

void Print(list<int> l) { for (auto e : l) { cout << e << "->"; } cout << endl; } int main() { list<int> l1{10,20,30,40,50}; l1.insert(next(l1.begin(),2),100);//在某个位置插入单个元素，迭代器指向的是30这个节点，100在30之前插入 Print(l1); list<int> l2{ 10,20,30,40,50 }; l2.insert(++l2.begin(),3,100);//在某个位置插入n个val，迭代器指向的是20这个节点，100在20之前插入 Print(l2); list<int> l3{ 10,20,30,40,50 }; list<int> l4(3,0); l3.insert(++l3.begin(),l4.begin(),l4.end());//迭代器插入 Print(l3); list<int> l5{ 10,20,30,40,50 }; l5.insert(l5.begin(), {666,666,666});//初始化列表插入 Print(l5); }

（9）erase

删除指定位置的节点。

void Print(list<int> l) { for (auto e : l) { cout << e << "->"; } cout << endl; } int main() { list<int> l1{10,20,30,40,50}; l1.erase(next(l1.begin(),2));//删除单个元素 Print(l1); list<int> l2{ 10,20,30,40,50 }; l2.erase(++l2.begin(),--l2.end());//删除迭代器范围内的节点 Print(l2); }

（10）swap

交换两个实例化后list对象的内容。

int main() { list<int> l1(5, 0); list<int> l2(5, 1); cout << "l1交换前："; Print(l1); cout << "l2交换前："; Print(l2); l1.swap(l2); cout << "l1交换后："; Print(l1); cout << "l2交换后："; Print(l2); }

（11）resize

调整有效元素的个数。

（12）clear

清理节点空间。

C++——list