Wiki
list 容器
約 5 分鐘閱讀
本文由簡體中文內容確定性轉換，並受版本化術語表保護。
1.list容器
1.1.list基本概念
**功能：**將資料進行鏈式儲存
連結串列（list）是一種物理儲存單元上非連續的儲存結構，資料元素的邏輯順序是通過連結串列中的指標連結實現的
連結串列的組成：連結串列由一系列結點組成
結點的組成：一個是儲存資料元素的資料域，另一個是儲存下一個結點地址的指標域
STL中的連結串列是一個雙向迴圈連結串列
由於連結串列的儲存方式並不是連續的記憶體空間，因此連結串列list中的迭代器只支援前移和後移，屬於雙向迭代器
list的優點：
- 採用動態儲存分配，不會造成記憶體浪費和溢位
- 連結串列執行插入和刪除操作十分方便，修改指標即可，不需要移動大量元素
list的缺點：
- 連結串列靈活，但是空間(指標域) 和 時間（遍歷）額外耗費較大
List有一個重要的性質，插入操作和刪除操作都不會造成原有list迭代器的失效，這在vector是不成立的。
總結：STL中List和vector是兩個最常被使用的容器，各有優缺點
1.2.list建構函式
功能描述：
- 建立list容器
函式原型：
list<T> lst;//list採用採用模板類實現,物件的預設構造形式：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 test01()
{
list<int>L1;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
printList(L1);
list<int>L2(L1.begin(),L1.end());
printList(L2);
list<int>L3(L2);
printList(L3);
list<int>L4(10, 1000);
printList(L4);
}
int main() {
// 程序从 main 函数开始执行，下面的语句会按顺序运行。
test01();
// 返回 0 表示程序正常结束。
return 0;
}執行結果：
10 20 30 40
10 20 30 40
10 20 30 40
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000總結：list構造方式同其他幾個STL常用容器，熟練掌握即可
1.3.list 賦值和交換
功能描述：
- 給list容器進行賦值，以及交換list容器
函式原型：
assign(beg, end);//將[beg, end)區間中的資料複製賦值給本身。assign(n, elem);//將n個elem複製賦值給本身。list& operator=(const list &lst);//過載等號運算子swap(lst);//將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 test01()
{
list<int>L1;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
printList(L1);
//赋值
list<int>L2;
L2 = L1;
printList(L2);
list<int>L3;
L3.assign(L2.begin(), L2.end());
printList(L3);
list<int>L4;
L4.assign(10, 100);
printList(L4);
}
//交换
void test02()
{
list<int>L1;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
list<int>L2;
L2.assign(10, 100);
cout << "交换前： " << endl;
printList(L1);
printList(L2);
cout << endl;
L1.swap(L2);
cout << "交换后： " << endl;
printList(L1);
printList(L2);
}
int main() {
//test01();
test02();
return 0;
}執行結果：
交换前：
10 20 30 40
100 100 100 100 100 100 100 100 100 100
交换后：
100 100 100 100 100 100 100 100 100 100
10 20 30 40總結：list賦值和交換操作能夠靈活運用即可
1.4.list 大小操作
功能描述：
- 對list容器的大小進行操作
函式原型：
-
size();//返回容器中元素的個數 -
empty();//判斷容器是否為空 -
resize(num);//重新指定容器的長度為num，若容器變長，則以預設值填充新位置。 //如果容器變短，則末尾超出容器長度的元素被刪除。
-
resize(num, elem);//重新指定容器的長度為num，若容器變長，則以elem值填充新位置。 //如果容器变短，则末尾超出容器长度的元素被删除。
示例：
#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 test01()
{
list<int>L1;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
if (L1.empty())
{
cout << "L1为空" << endl;
}
else
{
cout << "L1不为空" << endl;
cout << "L1的大小为： " << L1.size() << endl;
}
//重新指定大小
L1.resize(10);
printList(L1);
L1.resize(2);
printList(L1);
}
int main() {
test01();
return 0;
}執行結果：
L1不为空
L1的大小为： 4
10 20 30 40 0 0 0 0 0 0
10 20總結：
- 判斷是否為空 --- empty
- 返回元素個數 --- size
- 重新指定個數 --- resize
1.5.list 插入和刪除
功能描述：
- 對list容器進行資料的插入和刪除
函式原型：
- 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值匹配的元素。
示例：
#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 test01()
{
list<int> L;
//尾插
L.push_back(10);
L.push_back(20);
L.push_back(30);
//头插
L.push_front(100);
L.push_front(200);
L.push_front(300);
printList(L);
//尾删
L.pop_back();
printList(L);
//头删
L.pop_front();
printList(L);
//插入
list<int>::iterator it = L.begin();
L.insert(++it, 1000);
printList(L);
//删除
it = L.begin();
L.erase(++it);
printList(L);
//移除
L.push_back(10000);
L.push_back(10000);
L.push_back(10000);
printList(L);
L.remove(10000);
printList(L);
//清空
L.clear();
printList(L);
}
int main() {
test01();
return 0;
}執行結果：
300 200 100 10 20 30
300 200 100 10 20
200 100 10 20
200 1000 100 10 20
200 100 10 20
200 100 10 20 10000 10000 10000
200 100 10 20總結：
- 尾插 --- push_back
- 尾刪 --- pop_back
- 頭插 --- push_front
- 頭刪 --- pop_front
- 插入 --- insert
- 刪除 --- erase
- 移除 --- remove
- 清空 --- clear
1.6.list 資料存取
功能描述：
- 對list容器中資料進行存取
函式原型：
front();//返回第一個元素。back();//返回最後一個元素。
示例：
#include <iostream>
#include <list>
using namespace std;
//数据存取
void test01()
{
list<int>L1;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
//cout << L1.at(0) << endl;//错误 不支持at访问数据
//cout << L1[0] << endl; //错误 不支持[]方式访问数据
cout << "第一个元素为： " << L1.front() << endl;
cout << "最后一个元素为： " << L1.back() << endl;
//list容器的迭代器是双向迭代器，不支持随机访问
list<int>::iterator it = L1.begin();
//it = it + 1;//错误，不可以跳跃访问，即使是+1
}
int main() {
test01();
return 0;
}
執行結果：
第一个元素为： 10
最后一个元素为： 40總結：
- list容器中不可以通過[]或者at方式訪問資料
- 返回第一個元素 --- front
- 返回最後一個元素 --- back
1.7.list 反轉和排序
功能描述：
- 將容器中的元素反轉，以及將容器中的資料進行排序
函式原型：
reverse();//反轉連結串列sort();//連結串列排序
示例：
#include <iostream>
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;
}
bool myCompare(int val1 , int val2)
{
return val1 > val2;
}
//反转和排序
void test01()
{
list<int> L;
L.push_back(90);
L.push_back(30);
L.push_back(20);
L.push_back(70);
printList(L);
//反转容器的元素
L.reverse();
printList(L);
//排序
L.sort(); //默认的排序规则 从小到大
printList(L);
L.sort(myCompare); //指定规则，从大到小
printList(L);
}
int main() {
test01();
return 0;
}執行結果：
90 30 20 70
70 20 30 90
20 30 70 90
90 70 30 20總結：
- 反轉 --- reverse
- 排序 --- sort （成員函式）
1.8.排序案例
案例描述：將Person自定義資料型別進行排序，Person中屬性有姓名、年齡、身高
排序規則：按照年齡進行升序，如果年齡相同按照身高進行降序
示例：
#include <iostream>
#include <list>
#include <string>
using namespace std;
class Person {
public:
Person(string name, int age , int height) {
m_Name = name;
m_Age = age;
m_Height = height;
}
public:
string m_Name; //姓名
int m_Age; //年龄
int m_Height; //身高
};
bool ComparePerson(Person& p1, Person& p2) {
if (p1.m_Age == p2.m_Age) {
return p1.m_Height > p2.m_Height;
}
else
{
return p1.m_Age < p2.m_Age;
}
}
void test01() {
list<Person> L;
Person p1("刘备", 35 , 175);
Person p2("曹操", 45 , 180);
Person p3("孙权", 40 , 170);
Person p4("赵云", 25 , 190);
Person p5("张飞", 35 , 160);
Person p6("关羽", 35 , 200);
L.push_back(p1);
L.push_back(p2);
L.push_back(p3);
L.push_back(p4);
L.push_back(p5);
L.push_back(p6);
for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age
<< " 身高： " << it->m_Height << endl;
}
cout << "---------------------------------" << endl;
L.sort(ComparePerson); //排序
for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
cout << "姓名： " << it->m_Name << " 年龄： " << it->m_Age
<< " 身高： " << it->m_Height << endl;
}
}
int main() {
test01();
return 0;
}執行結果：
姓名： 刘备 年龄： 35 身高： 175
姓名： 曹操 年龄： 45 身高： 180
姓名： 孙权 年龄： 40 身高： 170
姓名： 赵云 年龄： 25 身高： 190
姓名： 张飞 年龄： 35 身高： 160
姓名： 关羽 年龄： 35 身高： 200
---------------------------------
姓名： 赵云 年龄： 25 身高： 190
姓名： 关羽 年龄： 35 身高： 200
姓名： 刘备 年龄： 35 身高： 175
姓名： 张飞 年龄： 35 身高： 160
姓名： 孙权 年龄： 40 身高： 170
姓名： 曹操 年龄： 45 身高： 180總結：
-
對於自定義資料型別，必須要指定排序規則，否則編譯器不知道如何進行排序
-
高階排序只是在排序規則上再進行一次邏輯規則制定，並不複雜