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í)間。
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è)元素的迭代器失效波岛，其他迭代器不受任何影響。
3.list常用API
- list構(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ù)灰蛙。
- list數(shù)據(jù)元素插入和刪除操作
push_back(elem);//在容器尾部加入一個(gè)元素
pop_back();//刪除容器中最后一個(gè)元素
push_front(elem);//在容器開頭插入一個(gè)元素
pop_front();//從容器開頭移除第一個(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值匹配的元素组力。
- list大小操作
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)度的元素被刪除滨砍。
- list賦值操作
assign(beg, end);//將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。
assign(n, elem);//將n個(gè)elem拷貝賦值給本身妖异。
list& operator=(const list &lst);//重載等號(hào)操作符
swap(lst);//將lst與本身的元素互換惋戏。
- list數(shù)據(jù)的存取
front();//返回第一個(gè)元素。
back();//返回最后一個(gè)元素他膳。
- list反轉(zhuǎn)排序
reverse();//反轉(zhuǎn)鏈表响逢，比如lst包含1,3,5元素，運(yùn)行此方法后矩乐，lst就包含5,3,1元素龄句。
sort(); //list排序
4.list容器的數(shù)據(jù)結(jié)構(gòu)
- list容器不僅是一個(gè)雙向鏈表，而且還是一個(gè)循環(huán)的雙向鏈表散罕。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<list>
using namespace std;
int main(){
list<int> myList;
for (int i = 0; i < 10; i ++){
myList.push_back(i);
}
list<int>::_Nodeptr node = myList._Myhead->_Next;
for (int i = 0; i < myList._Mysize * 2;i++){
cout << "Node:" << node->_Myval << endl;
node = node->_Next;
if (node == myList._Myhead){
node = node->_Next;
}
}
system("pause");
return EXIT_SUCCESS;
}
