1、list容器基本概念

　　鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)(鏈表中每一個(gè)元素稱為結(jié)點(diǎn))組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。 相較于vector的連續(xù)線性空間，list就顯得負(fù)責(zé)許多，它的好處是每次插入或者刪除一個(gè)元素，就是配置或者釋放一個(gè)元素的空間。因此，list對(duì)于空間的運(yùn)用有絕對(duì)的精準(zhǔn)，一點(diǎn)也不浪費(fèi)。而且，對(duì)于任何位置的元素插入或元素的移除，list永遠(yuǎn)是常數(shù)時(shí)間。 List和vector是兩個(gè)最常被使用的容器。 List容器是一個(gè)雙向鏈表。

　　采用動(dòng)態(tài)存儲(chǔ)分配，不會(huì)造成內(nèi)存浪費(fèi)和溢出 鏈表執(zhí)行插入和刪除操作十分方便，修改指針即可，不需要移動(dòng)大量元素 鏈表靈活，但是空間和時(shí)間額外耗費(fèi)較大。

　　2、list容器的迭代器(雙向迭代器)

　　List容器不能像vector一樣以普通指針作為迭代器，因?yàn)槠涔?jié)點(diǎn)不能保證在同一塊連續(xù)的內(nèi)存空間上。List迭代器必須有能力指向list的節(jié)點(diǎn)，并有能力進(jìn)行正確的遞增、遞減、取值、成員存取操作。所謂”list正確的遞增，遞減、取值、成員取用”是指，遞增時(shí)指向下一個(gè)節(jié)點(diǎn)，遞減時(shí)指向上一個(gè)節(jié)點(diǎn)，取值時(shí)取的是節(jié)點(diǎn)的數(shù)據(jù)值，成員取用時(shí)取的是節(jié)點(diǎn)的成員。 由于list是一個(gè)雙向鏈表，迭代器必須能夠具備前移、后移的能力，所以list容器提供的是Bidirectional Iterators. List有一個(gè)重要的性質(zhì)，插入操作和刪除操作都不會(huì)造成原有l(wèi)ist迭代器的失效。這在vector是不成立的，因?yàn)関ector的插入操作可能造成記憶體重新配置，導(dǎo)致原有的迭代器全部失效，甚至List元素的刪除，也只有被刪除的那個(gè)元素的迭代器失效，其他迭代器不受任何影響。 list容器不僅是一個(gè)雙向鏈表，而且還是一個(gè)循環(huán)的雙向鏈表。

　　怎么判斷一個(gè)迭代器是隨機(jī)訪問(wèn)迭代器還是雙向迭代器？

　　簡(jiǎn)單判斷：迭代器+1，如果成功，就是隨機(jī)訪問(wèn)迭代器，否就是雙向迭代器。

　　案例：

int main() { 

vector<int> v; 

v.begin()+1;//隨機(jī)訪問(wèn)迭代器

list<int> l; 

//l.begin() +1;//err 雙向迭代器 不允許+1 }

　　3、list容器常用的API

　　3.1list構(gòu)造函數(shù)

list<T> lstT;//list采用采用模板類實(shí)現(xiàn),對(duì)象的默認(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ù)。

　　3.2list數(shù)據(jù)元素的插入和刪除操作

push_back(elem);//在容器尾部加入一個(gè)元素pop_back();//刪除容器中最后一個(gè)元素push_front(elem);//在容器開(kāi)頭插入一個(gè)元素pop_front();//從容器開(kāi)頭移除第一個(gè)元素insert(pos,elem);//在pos位置插e(cuò)lem元素的拷貝，返回新數(shù)據(jù)的位置。insert(pos,n,elem);//在pos位置插入n個(gè)elem數(shù)據(jù)，無(wú)返回值。insert(pos,beg,end);//在pos位置插入[beg,end)區(qū)間的數(shù)據(jù)，無(wú)返回值。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值匹配的元素。

　　3.3list大小操作

size();//返回容器中元素的個(gè)數(shù) empty();//判斷容器是否為空 resize(num);//重新指定容器的長(zhǎng)度為num， 若容器變長(zhǎng)，則以默認(rèn)值填充新位置。 如果容器變短，則末尾超出容器長(zhǎng)度的元素被刪除。 resize(num, elem);//重新指定容器的長(zhǎng)度為num， 若容器變長(zhǎng)，則以elem值填充新位置。 如果容器變短，則末尾超出容器長(zhǎng)度的元素被刪除。

　　3.4list賦值操作

assign(beg, end);//將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。 assign(n, elem);//將n個(gè)elem拷貝賦值給本身。

list& operator=(const list &lst);//重載等號(hào)操作符 swap(lst);//將lst與本身的元素互換

　　3.5list的數(shù)據(jù)存取

front();//返回第一個(gè)元素。 back();//返回最后一個(gè)元素。 3.6.4.6 list反轉(zhuǎn)排序 reverse();//反轉(zhuǎn)鏈表，比如lst包含1,3,5元素，運(yùn)行此方法后，lst就包含5,3,1元素。 sort(); //list排序

　　3.6list反轉(zhuǎn)排序

reverse();//反轉(zhuǎn)鏈表，比如lst包含1,3,5元素，運(yùn)行此方法后，lst就包含5,3,1元素。 sort(); //list排序

　　使用案例：

#include<iostream>#include<list>using namespace std;

void printListInt(list<int> &l){

    list<int>::iterator it=l.begin();

    for(;it!=l.end();it++)

    {

        cout<<*it<<" ";

    }

    cout<<endl;}

void test(){

    list<int> l1(5,100);

    printListInt(l1);

    list<int> l2;

    l2.push_back(10);

    l2.push_back(20);

    l2.push_back(30);

    l2.push_front(40);

    l2.push_front(50);

    l2.push_front(60);

    printListInt(l2);

    l2.insert(++l2.begin(), 3,10);

    printListInt(l2);

    l2.erase(l2.begin());

    printListInt(l2);

    //remove根據(jù)節(jié)點(diǎn)內(nèi)容刪除

    l2.remove(10);

    printListInt(l2);//50 40 20 30

    cout<<"front = "<<l2.front()<<endl;

    cout<<"back = "<<l2.back()<<endl;

    //鏈表反轉(zhuǎn)

    l2.reverse();

    printListInt(l2);//30 20 40 50

    //鏈表排序

    //STL的sort排序算法 只能用隨機(jī)訪問(wèn)迭代器

    //list容器的迭代器為雙向迭代器 所以無(wú)法使用系統(tǒng)算法

    //sort(l2.begin(), l2.end());//err

    l2.sort();

    printListInt(l2);//20 30 40 50

}int main(void){

    test();

    system("Pause");

    return 0;

}

　　更多關(guān)于“智能物聯(lián)網(wǎng)培訓(xùn)”的問(wèn)題，歡迎咨詢千鋒教育在線名師。千鋒教育多年辦學(xué)，課程大綱緊跟企業(yè)需求，更科學(xué)更嚴(yán)謹(jǐn)，每年培養(yǎng)泛IT人才近2萬(wàn)人。不論你是零基礎(chǔ)還是想提升，都可以找到適合的班型，千鋒教育隨時(shí)歡迎你來(lái)試聽(tīng)。