C++中l(wèi)ist容器的實(shí)現(xiàn)

更新時(shí)間：2023年03月31日 10:18:50 作者：Darren_pty

本文主要介紹了C++中l(wèi)ist容器的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

一、list容器

1.1 簡介

① 功能：將數(shù)據(jù)進(jìn)行鏈?zhǔn)酱鎯Α?/p>

② 鏈表(list)是一種物理存儲單元上非連續(xù)的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接實(shí)現(xiàn)的。

③ 鏈表的組成：鏈表由一系列結(jié)點(diǎn)組成。

④ 結(jié)點(diǎn)的組成：一個(gè)是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲下一個(gè)結(jié)點(diǎn)地址的指針域。

⑤ 添加元素，將原指向下一個(gè)元素的指針指向新元素即可，新元素指向下一個(gè)元素

⑥ STL中的鏈表是一個(gè)雙向循環(huán)鏈表。

雙向：每一個(gè)指針既指向下一個(gè)結(jié)點(diǎn)的元素，也指向上一個(gè)結(jié)點(diǎn)的元素。
循環(huán)：最后一個(gè)結(jié)點(diǎn)的指針會指向第一個(gè)結(jié)點(diǎn)的元素，第一個(gè)結(jié)點(diǎn)的指針會指向最后一個(gè)結(jié)點(diǎn)的元素。

⑦ 由于鏈表的存儲方式并不是連續(xù)的內(nèi)存空間，因此鏈表list中的迭代器只支持前移和后移，屬于雙向迭代器。

它只能通過指針域一個(gè)一個(gè)前移/后移去找，而不能連續(xù)的內(nèi)存空間，指針加一個(gè)數(shù)字，就可以找到數(shù)據(jù)。

⑧ list的優(yōu)點(diǎn)：

采用動態(tài)存儲分配，不會造成內(nèi)存浪費(fèi)和溢出。
鏈表執(zhí)行插入和刪除操作十分方便，修改指針即可，不需要移動大量數(shù)據(jù)。

⑨ list的缺點(diǎn)：

鏈表靈活，但是空間(指針域)和時(shí)間(遍歷)額外耗費(fèi)較大。

10.list有一個(gè)重要的性質(zhì)，插入操作和刪除操作都不會造成原有l(wèi)ist迭代器的失效，這在vector中是不成立的，vector當(dāng)插入操作會創(chuàng)建一個(gè)更大的數(shù)據(jù)內(nèi)容，而vector容器的迭代器卻指向原有內(nèi)存，所以原有的vector容器失效了。

11.STL中l(wèi)ist和vector是兩個(gè)最長被用的容器，各有優(yōu)缺點(diǎn)。

1.2 構(gòu)造函數(shù)

① 功能描述：創(chuàng)建list容器。

② 函數(shù)原型：

list lst; //list采用模板類實(shí)現(xiàn)對象的默認(rèn)構(gòu)造形式
list(beg,end); //構(gòu)造函數(shù)將[beg,end)區(qū)間中的元素拷貝給本身。
list(n,elem); //構(gòu)造函數(shù)將n個(gè)elem拷貝給本身。
list(const list &lst); //拷貝構(gòu)造函數(shù)。

③ list構(gòu)造方式同其他幾個(gè)STL容器一樣。

#include<iostream>
using namespace std;
#include <list>
 
void printList(const list<int>&L)
{
    for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
 
void test01()
{
    //創(chuàng)建list容器
    list<int>L1;  //默認(rèn)構(gòu)造
 
    //添加數(shù)據(jù)
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
 
    //遍歷容器
    printList(L1);
 
    //區(qū)間方式構(gòu)造
    list<int>L2(L1.begin(), L1.end());
    printList(L2);
 
    //拷貝構(gòu)造
    list<int>L3(L2);
    printList(L3);
 
    //n個(gè)elem
    list<int>L4(10, 1000);
    printList(L4);
    
}
 
int main() {
 
    test01();
 
    system("pause");
 
    return 0;
 
}

運(yùn)行結(jié)果：

10 20 30 40
10 20 30 40
10 20 30 40
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
請按任意鍵繼續(xù). . .

1.3 賦值和交換

① 功能描述：給list容器進(jìn)行賦值，以及交換list容器。

② 函數(shù)原型：

assign(beg,end); //將[beg,end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。
assign(n,elem); //將n個(gè)elem拷貝賦值給本身。
list& operator=(const list &list); //重載等號操作符。
swap(list); //將lst與本身的元素互換。

#include<iostream>
using namespace std;
#include <list>
 
//list容器賦值和交換
 
void printList(const list<int>&L)
{
    for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
 
void test01()
{
    //創(chuàng)建list容器
    list<int>L1;  //默認(rèn)構(gòu)造
 
    //添加數(shù)據(jù)
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
 
    //遍歷容器
    printList(L1);
 
    list<int>L2;
    L2 = L1;  //operator= 賦值
    printList(L2);
 
    list<int>L3;
    L3.assign(L2.begin(), L2.end());
    printList(L3);
 
    list<int>L4;
    L4.assign(10, 100);
    printList(L4);
 
}
 
//交換
void test02()
{
    //創(chuàng)建list容器
    list<int>L1;  //默認(rèn)構(gòu)造
    
    //添加數(shù)據(jù)
    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);
 
    L1.swap(L2);
    cout << "交換后：" << endl;
    printList(L1);
    printList(L2);
}
 
int main() {
 
    test01();
    test02();
 
    system("pause");
 
    return 0;
 
}

運(yùn)行結(jié)果：

10 20 30 40
10 20 30 40
10 20 30 40
100 100 100 100 100 100 100 100 100 100
交換前：
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
請按任意鍵繼續(xù). . .

1.4 大小操作

① 功能描述：對list容器的大小進(jìn)行操作。

② 函數(shù)原型：

//返回容器中元素的個(gè)數(shù)。

size();

//判斷容器是否為空。

empty();

//重新指定容器的長度為num，若容器變長，則以默認(rèn)值填充新位置。

//如果容器變短，則末尾超出容器長度的元素被刪除。

resize(num);

//重新指定容器的長度為num，若容器變成，則以elem值填充新位置。

//如果容器變短，則末尾超出容器長度的元素被刪除。

resize(num,elem);

#include<iostream>
using namespace std;
#include <list>
 
//list容器賦值和交換
 
void printList(const list<int>&L)
{
    for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
 
void test01()
{
    //創(chuàng)建list容器
    list<int>L1;  //默認(rèn)構(gòu)造
 
    //添加數(shù)據(jù)
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
 
    //遍歷容器
    printList(L1);
 
    //判斷容器是否為空
    if(L1.empty())
    {
        cout << "L1為空" << endl;
    }
    else
    {
        cout << "L1不為空：" << endl;
        cout << "L1的元素個(gè)數(shù)為：" << L1.size() << endl;
    }
 
    //重新指定大小
    L1.resize(10,10000);
    printList(L1);
 
    L1.resize(2);
    printList(L1);
}
 
int main() {
 
    test01();
    
    system("pause");
 
    return 0;
 
}

運(yùn)行結(jié)果：

10 20 30 40
L1不為空：
L1的元素個(gè)數(shù)為：4
10 20 30 40 10000 10000 10000 10000 10000 10000
10 20
請按任意鍵繼續(xù). . .

1.5 插入和刪除

① 功能描述：對list容器進(jìn)行數(shù)據(jù)的插入和刪除。

② 函數(shù)原型：

push_back(elem); //在容器尾部加入一個(gè)元素。
pop_back(); //刪除容器中最后一個(gè)元素。
push_front(elem); //在容器開頭插入一個(gè)元素。
pop_front(); //從哪個(gè)容器開頭移除第一個(gè)元素
insert(pos,elem); //在pos位置插e(cuò)lem元素的拷貝，返回新數(shù)據(jù)的位置。
insert(pos,n,elem); //在pos位置插入n個(gè)elem數(shù)據(jù)，無返回值。
insert(pos,beg,end); //在pos位置插入[beg,end)區(qū)間的數(shù)據(jù)，無返回值。
clear(); //移除容器的所有數(shù)據(jù)。
erase(beg,end); //刪除[beg,end)區(qū)間的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。
erase(pos); //刪除pos位置的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。
remove(elem); //刪除容器中所有與elem值匹配的元素。

#include<iostream>
using namespace std;
#include <list>
 
//list容器賦值和交換
 
void printList(const list<int>&L)
{
    for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
 
void test01()
{
    //創(chuàng)建list容器
    list<int>L1;  //默認(rèn)構(gòu)造
 
    //添加數(shù)據(jù)
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
 
    L1.push_front(100);
    L1.push_front(200);
    L1.push_front(300);
 
    //遍歷容器
    printList(L1);
 
    //尾刪
    L1.pop_back();
    printList(L1);
 
    //頭刪
    L1.pop_front();
    printList(L1);
 
    //insert插入
    list<int>::iterator it = L1.begin();
    L1.insert(++it, 1000);
    printList(L1);
 
    //刪除
    it = L1.begin();
    L1.erase(it);
    printList(L1);
 
    //移除
    L1.push_back(10000);
    L1.push_back(10000);
    L1.push_back(10000);
    L1.push_back(10000);
    printList(L1);
 
    L1.remove(10000);
    printList(L1);
 
    //清空
    L1.clear();
    printList(L1);
 
}
 
int main() {
 
    test01();
 
    system("pause");
 
    return 0;
 
}

運(yùn)行結(jié)果：

300 200 100 10 20 30
300 200 100 10 20
200 100 10 20
200 1000 100 10 20
1000 100 10 20
1000 100 10 20 10000 10000 10000 10000
1000 100 10 20
請按任意鍵繼續(xù). . .

1.6 數(shù)據(jù)存取

① 功能描述：對list容器中數(shù)據(jù)進(jìn)行存取。

② 函數(shù)原型：

front(); //返回第一個(gè)元素。
back(); //返回最后一個(gè)元素。

③ list容器不是連續(xù)的內(nèi)存空間，所以不能通過[]、at等方式隨機(jī)訪問。

#include<iostream>
using namespace std;
#include <list>
 
//list容器  數(shù)據(jù)存取
 
void printList(const list<int>&L)
{
    for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
 
void test01()
{
    //創(chuàng)建list容器
    list<int>L1;  //默認(rèn)構(gòu)造
 
    //添加數(shù)據(jù)
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
 
    //L1[0] 不可以用[]訪問list容器中的元素
 
    //L1.at(0) 不可以用at方式訪問list容器中的元素
 
    //原因是list本質(zhì)鏈表，不是用連續(xù)線性空間存儲數(shù)據(jù)，迭代器也是不支持隨機(jī)訪問的。
 
    cout << "第一個(gè)元素為：" << L1.front() << endl;
 
    cout << "第一個(gè)元素為：" << L1.back() << endl;
 
    //驗(yàn)證迭代器是不支持隨機(jī)訪問的
 
    list<int>::iterator it = L1.begin();
 
    it++;  //因?yàn)閘ist是雙向的，所以支持遞增、遞減++、--的操作，但是不支持it = it+1;it = it+2;....，即不支持這樣的隨機(jī)訪問      
 
}
 
int main() {
 
    test01();
 
    system("pause");
 
    return 0;
 
}

運(yùn)行結(jié)果：

第一個(gè)元素為：10
第一個(gè)元素為：40
請按任意鍵繼續(xù). . .

1.7 反轉(zhuǎn)和排序

① 功能描述：將容器中的元素反轉(zhuǎn)，以及將容器中的數(shù)據(jù)進(jìn)行排序。

② 函數(shù)原型：

reverse(); //反轉(zhuǎn)鏈表
sort(); //鏈表排序

#include<iostream>
using namespace std;
#include <list>
#include<algorithm>
 
//list容器  反轉(zhuǎn)和排序
 
void printList(const list<int>&L)
{
    for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
 
bool myCopare(int v1, int v2)
{
    //降序 就讓第一個(gè)數(shù) 大于第二個(gè)數(shù)為真
    return v1 > v2;
 
}
 
void test01()
{
    //反轉(zhuǎn)
    list<int>L1;  
 
    //添加數(shù)據(jù)
    L1.push_back(20);
    L1.push_back(10);
    L1.push_back(50);
    L1.push_back(40);
    L1.push_back(30);
 
    cout << "反轉(zhuǎn)前：" << endl;
    printList(L1);
 
    //反轉(zhuǎn)
    L1.reverse();
    cout << "反轉(zhuǎn)后：" << endl;
    printList(L1);
 
    //排序
    cout << "排序前：" << endl;
    printList(L1);
 
    //所有不支持隨機(jī)訪問迭代器的容器，不可以用標(biāo)準(zhǔn)算法
    //不支持隨機(jī)訪問迭代器的容器，內(nèi)部會提供對應(yīng)的一些算法
    //sort(L1.begin(),L1.end());  //報(bào)錯(cuò)，這是標(biāo)準(zhǔn)算法，全局函數(shù)的sort()
    L1.sort();  //默認(rèn)排序規(guī)則 從小到大 升序
    cout << "排序后：" << endl;
    printList(L1);
 
    L1.sort(myCopare);  //降序排列 這是成員函數(shù)的sort()
    cout << "重載排序算法，降序排序后：" << endl;
    printList(L1);
    
}
 
 
int main() 
{
    test01();
 
    system("pause");
 
    return 0;
}

運(yùn)行結(jié)果：