5、链表 list

List 是每个节点包含前驱指针、后继指针和数据域三个部分的双向链表。List 不提供随机存取,访问元素需要按顺序走到需存取的元素,时间复杂度为 O(n),在 list 的任何位置上执行插入或删除操作都非常迅速,只需在 list 内部调整一下指针。list 不仅是一个双向链表,而且还是一个环状双向链表。所以它只需要一个指针,便可以完整实现整个链表。(这里需要特别强调一下:list 到底是不是双向链表?有的书上说是,有的书上没说,所以大家注意一下,这里暂把 list 当作双向链表,等博主找到资料再做解释)
与向量 vector 相比,list 允许快速的插入和删除,且每次插入或删除一个元素,就配置或释放一个元素空间,对于任何位置的元素插入或元素移除,list 永远是常数时间。
List 不再能够像 vector 那样以普通指针作为迭代器,因为其节点不保证在储存空间中连续存在。list 迭代器必须有能力指向 list 的节点,并有能力进行正确的递增、递减、取值、成员存取等操作。所谓 list 迭代器正确的递增、递减、取值、成员取用操作是指,递增时指向下一个节点,递减时指向上一个节点,取值时取的是节点的数据值,成员取用时取用的是节点的成员。
List 有一个重要性质:插入操作(insert)和合并操作(splice)都不会造成原有的 list 迭代器失效。这在 vector 是不成立的,因为 vector 的插入操作可能造成记忆体重新配置,导致原有的迭代器全部失效。甚至 list 的元素删除操作(erase)也只有“指向被删除元素”的那个迭代器失效,其他迭代器不受任何影响。
在使用 list 类模版时,也必须包含相应的头文件:#include<list>,list 对象的声明与 vector 类似,这里仅仅介绍一下 list 的成员函数。

1、声明 list 容器

  1. list list1; // 声明一个空的 list1
  2. list list2 (4, 100); // 声明以个含 4 个 100 的 list2
  3. list list3 (list2.begin(), list2.end()); // 用 list2 的迭代器内容声明 list3
  4. list list4 (list3); // 声明 list4 为 list3 的一个副本
  5. list list5(size); // 声明一个含 size 个默认值为 0 的 list5
  6. list1.~list(); // 注销 list

2、list 与 vector 不相同的一些操作

List 与 vector 相同的一些操作,这里仅列出函数名,不再进行具体说明:Begin/end/rbegin/rend/empty/size/Max_size/resize/insert/erase/swap/clear。
以下这些函数是 list 与 vector 不同的函数:

list<int> list1;

1、访问 list 元素

  1. list1.front():返回第一个元素的值。
  2. list1.back():返回最后一个元素的值。

2、list 元素的插入与删除

  1. list1.push_front(x):把元素 x 插入到链表头部。
  2. list1.pop_front():删除第一个元素。
  3. list1.push_back(x):把元素 x 插入到链表尾部。
  4. list1.pop_back():删除最后一个元素。
  5. list1.remove(val):删除链表中所有值为 val 的元素。
  6. list1.remove_if(pred):删除链表中谓词 pred 为真的元素(谓词即为元素存储和检索的描述,如 std::less<>,std::greater<> 那么就按降序/升序排列,你也可以定义自己的谓词)。
  7. list1.unique():删除链表中所有重复的元素(这个函数博主在 VS 上测试的时候,并没有删除所有重复的元素,大家使用的时候最好也亲测一下。。。)。
  8. list1.unique(pred):根据谓词 pred 删除所有重复的元素,使链表中没有重复元素。

3、list 拼接操作

  1. splice():链表拼接,参数 position 是迭代器而不是下标。
  2. list1.splice ( position, list2 ):将 list2 中的所有元素插入到 list1 中 position 处,list2 会被清空,position 仍然指向 list1 中的那个元素。
  3. list1.splice ( position, list2, iter ):将 list2 中 iter 处的元素插入到 list1 中 position 处,list2 会将 iter 指向的元素删除,iter 失效。
  4. list1.splice ( position, list2, first, last ):将 list2 中[first,last)位置处的元素插入到 list1 的 position 处。

4、list 合并操作

  1. merge(listref):链表合并:把 listref 所引用的链表中的所有元素插入到链表中,可指定合并规则。
  2. OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
  3. OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); // 由于参数复杂,这里列出了 C++ 官网给出的原函数,具体的例子可以参考C++官网.

5、list 排序操作

  1. sort():根据默认的谓词对链表排序,默认升序。
  2. sort(pred):根据给定的谓词对链表排序。

3、vector 与 list 之间的区别

C++ 标准库中,容器 vector 和 list 都可以用来存放一组类型相同的数据。而且二者不同于数组的一点是,支持动态增长。但它们还是有几点不同:

  1. Vector 是顺序表,表示的是一块连续的内存,元素被顺序存储;list 是双向链表,在内存中不一定连续。
  2. 当数值内存不够时,vector 会重新申请一块足够大的连续内存,把原来的数据拷贝到新的内存里面,再释放旧空间;list 因为不用考虑内存的连续,因此新增开销比 vector 小。
  3. List 只能通过指针访问元素,随机访问元素的效率特别低,在需要频繁随机存取元素时,使用 vector 更加合适。
  4. 当向 vector 插入或者删除一个元素时,需要复制移动待插入元素右边的所有元素;因此在有频繁插入删除操作时,使用 list 更加合适。
  5. Vector 和 deque 支持随机访问,而 list 不支持随机访问,因此 list 不支持[ ]访问。