第 18.8 節

list 容器

0瀏覽次數0訪問次數--跳出率--平均停留

list容器

list基本概念

**功能：**將數據進行鏈式存儲

鏈表（list）是一種物理存儲單元上非連續的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接實現的

鏈表的組成：鏈表由一系列結點組成

結點的組成：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域

STL中的鏈表是一個雙向循環鏈表

說明: 2015-11-15_225145

由於鏈表的存儲方式並不是連續的內存空間，因此鏈表list中的迭代器只支持前移和後移，屬於雙向迭代器

list的優點：

採用動態存儲分配，不會造成內存浪費和溢出
鏈表執行插入和刪除操作十分方便，修改指針即可，不需要移動大量元素

list的缺點：

鏈表靈活，但是空間(指針域) 和時間（遍歷）額外耗費較大

List有一個重要的性質，插入操作和刪除操作都不會造成原有list迭代器的失效，這在vector是不成立的。

總結：STL中List和vector是兩個最常被使用的容器，各有優缺點

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常用容器，熟練掌握即可

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賦值和交換操作能夠靈活運用即可

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

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

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

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 （成員函數）

排序案例

案例描述：將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

總結：

對於自定義數據類型，必須要指定排序規則，否則編譯器不知道如何進行排序
高級排序只是在排序規則上再進行一次邏輯規則制定，並不複雜