STL之list容器-蒲公英云

摘要：本文主要介绍了list容器的相关内容。

1、基本概念

1.1 链表的简单介绍

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

相较于vector的连续线性空间，list就显得复杂许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list都是可以做到的。

1.2 链表的特点

采用动态存储分配，不会造成内存浪费和溢出
链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
链表灵活，但是空间和时间额外耗费较大

2、list容器的迭代器

List容器不能像vector一样以普通指针作为迭代器，因为其节点不能保证在同一块连续的内存空间上。List迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list正确的递增，递减、取值、成员取用”是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员。

由于list是一个双向链表，迭代器必须能够具备前移、后移的能力，所以list容器提供的是Bidirectional Iterators.

List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效。这在vector是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效，甚至List元素的删除，也只有被删除的那个元素的迭代器失效，其他迭代器不受任何影响。

3、常用API

	API	意义
构造函数	list<T> lstT	采用采用模板类实现,对象的默认构造形式
list(beg,end)	构造函数将[beg, end]区间中的元素拷贝给本身
list(n,elem)	构造函数将n个elem拷贝给本身
list(const list &lst)	拷贝构造函数
数据元素插入和删除操作	push_back(elem)	在容器尾部加入一个元素
pop_back()	删除容器中最后一个元素
push_front(elem)	在容器开头插入一个元素
pop_front()	从容器开头移除第一个元素
insert(pos,elem)	在pos位置插elem元素的拷贝，返回新数据的位置
insert(pos,n,elem)	在pos位置插入n个elem数据，无返回值
insert(pos,beg,end)	在pos位置插入[beg,end)区间的数据，无返回值
clear()	移除容器的所有数据
erase(beg,end)	删除[beg,end)区间的数据，返回下一个数据的位置
erase(pos)	删除pos位置的数据，返回下一个数据的位置
remove(elem)	删除容器中所有与elem值匹配的元素
大小操作	size()	返回容器中元素的个数
empty()	判断容器是否为空
resize(num)	重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除
resize(num, elem)	重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除
赋值操作	assign(beg, end);	将[beg, end)区间中的数据拷贝赋值给本身
assign(n, elem)	将n个elem拷贝赋值给本身
list& operator=(const list &lst)	重载等号操作符
swap(lst)	将lst与本身的元素互换
数据的存取	front()	返回第一个元素
back()	返回最后一个元素
反转排序	reverse()	反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素
sort()	list排序

4、代码示例

1 #define _CRT_SECURE_NO_WARNINGS
  2 #include<iostream>
  3 #include<list>
  4 #include <algorithm>
  5 #include <string>
  6 
  7 using namespace std;
  8 
  9 void printList(list<int>&L) {
 10     for (list<int>::iterator it = L.begin(); it != L.end();it++) {
 11         cout << *it << " ";
 12     }
 13     cout << endl;
 14 }
 15 
 16 void test01() {    //初始化，打印
 17     list<int>L1(10,10);
 18     list<int>L2(L1.begin(),L1.end());
 19     printList(L1);
 20     printList(L2);
 21     L2.push_back(100);
 22     printList(L2);
 23 
 24     //逆序打印
 25     for (list<int>::reverse_iterator it=L2.rbegin();it!=L2.rend();it++)
 26     {
 27         cout << *it <<" ";
 28     }
 29        cout << endl;
 30 
 31        list<int>L3; //首尾插入元素
 32        L3.push_back(10);
 33        L3.push_back(20);
 34        L3.push_back(30);
 35        L3.push_front(100);
 36        L3.push_front(200);
 37        L3.push_front(300);
 38 
 39        printList(L3);
 40        L3.pop_front();  //删除头部和尾部
 41        L3.pop_back();
 42        printList(L3);
 43 
 44        L3.insert(L3.begin(), 1000);  //指定位置插入
 45        printList(L3);
 46 
 47        L3.remove(10);  //去除10这个元素
 48        printList(L3);
 49 }
 50 
 51 void test02() {    //容量大小的改变
 52     list<int>L4;
 53     L4.push_back(10);
 54     L4.push_back(20);
 55     L4.push_back(30);
 56     L4.push_front(100);
 57     L4.push_front(200);
 58     L4.push_front(300);
 59     cout << L4.size() << endl;  //输出大小
 60     if (L4.empty())
 61     {
 62         cout << "链表为空" << endl;
 63     }
 64     else {
 65         cout << "链表不为空" << endl;
 66     }
 67 
 68     L4.resize(10);   //扩充补0
 69     printList(L4);
 70 
 71     L4.resize(3);    //只留3个
 72     printList(L4);
 73 
 74     list<int>L5;
 75     L5.assign(L4.begin(), L4.end());
 76     printList(L5);
 77 
 78     cout << L5.front() << endl;
 79     cout << L5.back() << endl;
 80 }
 81 
 82 bool mycompare(int v1,int v2) {
 83     return v1 > v2;
 84 }
 85 
 86 void test03() {   //反转、排序
 87     list<int>L;
 88     L.push_back(10);
 89     L.push_back(50);
 90     L.push_back(20);
 91     L.push_back(60);
 92 
 93     L.reverse();  //进行了反转
 94     printList(L);
 95 
 96     L.sort();  //进行了从小到大的排列
 97     printList(L);
 98 
 99     L.sort(mycompare);  //进行了从大到小的排列
100     printList(L);
101 }
102 
103 class Person {
104 public:
105     string m_name;
106     int m_age;
107     int m_height;
108     Person(string name,int age,int height):m_name(name),m_age(age),m_height(height) {}
109     
110     //重载 == 让remove 可以删除自定义的person类型
111     bool operator==(const  Person & p)
112     {
113         if (this->m_name == p.m_name && this->m_age == p.m_age && this->m_height == p.m_height)
114         {
115             return true;
116         }
117         return false;
118     }
119 };
120 
121 bool mycompareperson(Person &p1,Person &p2) {
122   if (p1.m_age==p2.m_age)
123   {
124       return p1.m_height < p2.m_height;
125   }
126   else {
127       return p1.m_age > p2.m_age;
128   }
129 }
130 
131 void test04(){
132     list<Person>L;
133     Person p1("火男",20,165);
134     Person p2("亚瑟", 26, 170);
135     Person p3("诸葛亮", 29, 175);
136     Person p4("周瑜", 26, 176);
137     Person p5("李典", 35, 180);
138     Person p6("不知火舞", 19, 172);
139     Person p7("后羿", 39, 188);
140 
141     L.push_back(p1);
142     L.push_back(p2);
143     L.push_back(p3);
144     L.push_back(p4);
145     L.push_back(p5);
146     L.push_back(p6);
147     L.push_back(p7);
148 
149     L.sort(mycompareperson);
150     for (list<Person>::iterator it=L.begin();it!=L.end();it++)
151     {
152         cout << "姓名:  "<< it->m_name <<"年龄：  "<<(*it).m_age<<"身高：  "<<it->m_height<< endl;
153     }
154 
155     L.remove(p6);
156     for (list<Person>::iterator it = L.begin(); it != L.end(); it++)
157     {
158         cout << "姓名:  " << it->m_name << "年龄：  " << (*it).m_age << "身高：  " << it->m_height << endl;
159     }
160 }
161 
162 int main() {
163     //test01();
164     //test02();
165     //test03();
166     test04();
167     system("pause");
168     return 0;
169 }