＜C++＞ list容器本质|常用接口|自定义排序规则（上）

1、list 容器本质与特点

本质：

list 容器可以看做一个双向循环链表，用于存储的每个结点包含数据域和指针域

示意图：

名词解释：

begin和end都是迭代器，可以看成指针来操作

begin 对应的是容器首个元素，而end 对应容器最后一个元素的下一个位置

prev和next代表前驱指针和后继指针，并不是 list容器的接口

指针域用来存储下一个结点的地址

front和back分别是第一个和最后一个结点的数据域

push_back、push_front、pop_back、pop_front代表尾插、头插、尾删、头删

通过前驱后继指针可以将每个结点连接起来，头结点的前驱与尾结点后继指针都指向null

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器

list 特点：

优点：可以对任意位置快速插入删除，动态分配存储，不会造成内存浪费和溢出

缺点：遍历速度比数组慢，占用空间比数组大

list 有一个重要的性质，插入和删除操作都不会造成原有 list迭代器的失效

2、list 基本操作与常用接口

包含 list容器的构造、赋值交换、插入删除、数据存取、空间大小、反转、排序。

2.1、list 构造函数

用于创建list容器

函数原型：

list<T> lst;

采用模板类实现,对象的默认构造形式

list(beg,end);

构造函数将[beg, end)区间中的元素拷贝给本身。

list(n,elem);

构造函数将n个elem拷贝给本身。

list(const list &lst);

拷贝构造函数

示例：

#include<iostream>
#include <list>
using namespace std;
void printList(const list<int>& L) {
  for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
    cout << *it << " ";
  }
  cout << endl;
}
void test()
{
  //默认构造
  list<int>L1;
  L1.push_back(10);
  L1.push_back(20);
  L1.push_back(30);
  printList(L1);
    //区间构造
  list<int>L2(L1.begin(),L1.end());
  printList(L2);
  //拷贝构造
  list<int>L3(L2);
  printList(L3);
  //相同值构造
  list<int>L4(10, 1000);
  printList(L4);
}

2.2、list 赋值和交换

用于给list容器进行赋值，以及交换list容器

函数原型：

assign(beg, end);

将[beg, end)区间中的数据拷贝赋值给本身

assign(n, elem);

将n个elem拷贝赋值给本身

list& operator=(const list &lst);

重载等号操作符

swap(lst);

将lst与本身的元素互换

示例：

//赋值和交换
void test01()
{
  list<int>L1;
  L1.push_back(10);
  L1.push_back(20);
  L1.push_back(30);
  //赋值
  list<int>L2;
  L2 = L1;
  list<int>L3;
  L3.assign(L2.begin(), L2.end());
  list<int>L4;
  L4.assign(10, 100);
}
//交换
void test02()
{
  list<int>L1;
  L1.push_back(10);
  L1.push_back(20);
  L1.push_back(30);
  list<int>L2;
  L2.assign(10, 100);
  cout << "交换前： " << endl;
  printList(L1);
  printList(L2);
  L1.swap(L2);
  cout << "交换后： " << endl;
  printList(L1);
  printList(L2);
}

2.3、list 大小操作

用于对list容器的大小进行操作

函数原型：

size();

返回容器中元素的个数

empty();

判断容器是否为空

resize(num);

重新指定容器的长度为num，若容器变长，则以默认值填充新位置。

如果容器变短，则末尾超出容器长度的元素被删除。

resize(num, elem);

与resize(num)的区别是默认值变为elem

示例：