list 容器（链表）

hello-205112 / 2023-08-14 / 原文

1.list基本概念

链表（list）是一种物理存储单元上的非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的；将数据进行链式存储。

　　　　是一个双向循环链表；

　　链表由一系列结点组成；

　　结点的组成：一个是存储数据元素的数据域，另一个是存储下一个结点的指针域；

优点：可以对任意位置快速插入或删除元素；

缺点：遍历速度没有数组快，占用空间比数组大；

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

list有个重要的性质，插入操作和删除操作都不会造成原有list迭代器失效，这在vector是不成立的；

2.list构造函数

3.list赋值和交换

4.list大小操作

5.list插入和删除

函数原型:

push_back ( elem );//在容器尾部加入一个元元素
pop _ back();//除容器中最后一个元素
push _ front ( elem )/在容器开头播入一个元素
pop _ front ();//从容器开头移除第一个元素
insert ( pos , elem )://在 pos 位置插 elem 元素的的拷贝,返回新数据的位置。
insert ( pos , n , elem )://在 pos 位置插入 n 个 elelem 数据,无返回值。
insert ( pos , beg , end )// 在 pos 位置插入[ beg , end )区间的数据,无返回值。
cleart （）；//移除容器的所有数抵
erase ( beg , end )://删除[ beg，end )区间的数据据,返回下一个数据的位置,
erase ( pos )；//除 pos 位置的故据,返回下一个数据的位置。
remove ( elem )//删除容器中所有与 elem 值值匹配的元素。

6.list数据存取

front（）；
back（）；

不可以用中括号和at来访问list里的元素，原因是list空间不是连续的；

7.list反转和排序

reverse（）；//反转链表
sort（）；//排序

如果想要降序的话，重载一个函数：

 1 #include<iostream>
 2 #include<list>
 3 #include<string>
 4 using namespace std;
 5 
 6 //案例：将person自定义类型进行排序，person中属性有姓名，年龄，身高，按照年龄进行升序，若年龄相同，按身高；
 7 
 8 class Person
 9 {
10 public:
11     Person(string n, int a, int h)
12     {
13         this->m_name = n;
14         this->m_age = a;
15         this->m_height = h;
16     }
17 
18     string m_name;
19     int m_age;
20     int m_height;
21 };
22 
23 void myprint(list<Person> l)
24 {
25     for (list<Person>::iterator it = l.begin(); it != l.end(); it++)
26     {
27         cout << (*it).m_name << "\t" << (*it).m_age << "\t" << (*it).m_height << endl;
28     }
29 
30 }
31 
32 //指定排序规则
33 bool compare(Person p1,Person p2)
34 {
35     //按照年龄升序
36     if (p1.m_age == p2.m_age)
37     {
38         return p1.m_height < p2.m_height;
39     }
40     else { return p1.m_age < p2.m_age; }
41 }
42 
43 void test01()
44 {
45     list<Person> L;
46     Person p1("aa", 20, 180);
47     Person p2("bb", 35, 178);
48     Person p3("cc", 34, 180);
49     Person p4("dd", 20, 165);
50     Person p5("ee", 35, 185);
51     L.push_back(p1);
52     L.push_back(p2);
53     L.push_back(p3);
54     L.push_back(p4);
55     L.push_back(p5);
56 
57     L.sort(compare);
58     myprint(L);
59 }
60 
61 int main()
62 {
63     test01();
64 }