[STL]list使用

注：本文測試環(huán)境是visual studio2019。

1. list介紹

1. list是可以在常量時間內(nèi)在任意位置進行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
2. list的底層是雙向鏈表結(jié)構(gòu)，雙向鏈表中每個元素存儲在互不相關(guān)的獨立節(jié)點中，在節(jié)點中通過指針指向其前一個元素和后一個元素。
3. list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡單高效。
4. 與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進行插入、移除元素的執(zhí)行效率更好。
5. 與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機訪問，比如：要訪問list 的第6個元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置。

2. 構(gòu)造函數(shù)

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

默認構(gòu)造函數(shù)。

list<int> l; //創(chuàng)建一個空list

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

創(chuàng)建一個有n個結(jié)點，結(jié)點數(shù)據(jù)為val的list。

list<int> l(10, 66); 

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

使用迭代器構(gòu)造列表。

vector<int> v(10, 6);
list<int> l(v.begin(), v.end()); //創(chuàng)建一個存儲int類型的鏈表，使用v初始化數(shù)據(jù)

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

拷貝構(gòu)造函數(shù)

list<int> l1(10,6);
list<int> l2(l1); //使用l2拷貝構(gòu)造l1

3. 迭代器相關(guān)函數(shù)

begin函數(shù)和end函數(shù)

begin函數(shù)：

返回指向list第一個結(jié)點的正向迭代器。

end函數(shù)：

返回指向list結(jié)尾的正向迭代器。

#include <iostream>
#include <list>
#include <vector>
using namespace std;
int main()
{vector<int> v;v.push_back(1); //在list中尾插數(shù)據(jù)1v.push_back(2); //在list中尾插數(shù)據(jù)2v.push_back(3);	//在list中尾插數(shù)據(jù)3v.push_back(4);	//在list中尾插數(shù)據(jù)4list<int> l(v.begin(), v.end());list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";it++;}cout << endl; //輸出為 1 2 3 4return 0;
}

rbegin函數(shù)和rend函數(shù)

rbegin函數(shù)：

返回指向list最后一個含有數(shù)據(jù)的結(jié)點的反向迭代器。

rend函數(shù)：

指向list反向結(jié)尾的反向迭代器。

#include <iostream>
#include <list>
#include <vector>
using namespace std;
int main()
{vector<int> v;v.push_back(1); //在list中尾插數(shù)據(jù)1v.push_back(2); //在list中尾插數(shù)據(jù)2v.push_back(3);	//在list中尾插數(shù)據(jù)3v.push_back(4);	//在list中尾插數(shù)據(jù)4list<int> l(v.begin(), v.end());list<int>::reverse_iterator it = l.rbegin();while (it != l.rend()){cout << *it << " ";it++;}cout << endl; //輸出為 4 3 2 1return 0;
}

4. 容量相關(guān)函數(shù)

empty函數(shù)

判斷l(xiāng)ist是否為空.

#include <iostream>
#include <list>
#include <vector>
using namespace std;
int main()
{list<int> l1;list<int> l2(5, 6);cout << l1.empty() << endl;//輸出為1cout << l2.empty() << endl;//輸出為0return 0;
}

size函數(shù)

獲取list存儲的結(jié)點個數(shù)。

#include <iostream>
#include <list>
#include <vector>
using namespace std;
int main()
{vector<int> v;v.push_back(1); //在list中尾插數(shù)據(jù)1v.push_back(2); //在list中尾插數(shù)據(jù)2v.push_back(3);	//在list中尾插數(shù)據(jù)3v.push_back(4);	//在list中尾插數(shù)據(jù)4list<int> l(v.begin(), v.end());cout << l.size() << endl;  //輸出為4return 0;
}

5. 數(shù)據(jù)修改函數(shù)

push_back函數(shù)和pop_back函數(shù)

push_back函數(shù)：

在list結(jié)尾插入結(jié)點。

#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);cout << l.size() << endl; //輸出為3return 0;
}

pop_back函數(shù)：

在list結(jié)尾刪除結(jié)點。

#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);cout << l.size() << endl; //輸出為3l.pop_back();l.pop_back();cout << l.size() << endl; //輸出為1l.pop_back();//l.pop_back(); -- 報錯 -- 沒有結(jié)點可刪return 0;
}

push_front函數(shù)和pop_front函數(shù)

push_front函數(shù)：

在list中頭插結(jié)點。

#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> l;l.push_front(1);l.push_front(2);l.push_front(3);l.push_front(4);list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl; // 輸出為 4 3 2 1return 0;
}

pop_front函數(shù)：

在list中頭刪結(jié)點。

#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> l;l.push_front(1);l.push_front(2);l.push_front(3);l.push_front(4);list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;l.pop_front();l.pop_front();it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl; // 輸出為 2 1return 0;
}

insert函數(shù)和erase函數(shù)

和vector容器類似，list容器也沒有提供find函數(shù)，而insert函數(shù)和erase函數(shù)是需要配合迭代器使用的，因此需要使用算法庫的find函數(shù)。

find函數(shù)查找成功會返回指向數(shù)據(jù)的迭代器，失敗會返回傳入的last迭代器，注意find函數(shù)的查找范圍是從first迭代器至last迭代器前，不包括last迭代器。

insert函數(shù)

功能1： 在某一位置插入結(jié)點。

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);list<int>::iterator pos = find(l.begin(), l.end(), 2);l.insert(pos, 66);list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl; //輸出為1 66 2 3 4return 0;
}

功能2： 在某一位置插入n個存儲相同數(shù)據(jù)的結(jié)點。

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);list<int>::iterator pos = find(l.begin(), l.end(), 2);l.insert(pos, 3, 66);list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl; //輸出為1 66 66 66 2 3 4return 0;
}

功能3： 傳入其他list容器或者其他類型容器的迭代器，將傳入的迭代器區(qū)間內(nèi)的數(shù)據(jù)插入。

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main()
{list<int> l1(3, 66);list<int> l2;l2.push_back(1);l2.push_back(2);l2.push_back(3);list<int>::iterator pos = find(l2.begin(), l2.end(), 2);l2.insert(pos, l1.begin(), l1.end());list<int>::iterator it = l2.begin();while (it != l2.end()){cout << *it << " ";++it;}cout << endl;  //輸出為1 66 66 66 2 3return 0;
}

erase函數(shù)

功能1： 刪除迭代器指向的結(jié)點。

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);list<int>::iterator pos = find(l.begin(), l.end(), 2);l.erase(pos);list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl; // 輸出為 1 3return 0;
}

功能2： 將迭代器范圍的結(jié)點都刪除。

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);list<int>::iterator start = find(l.begin(), l.end(), 2);list<int>::iterator finish = find(l.begin(), l.end(), 5);l.erase(start, finish);list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl; // 輸出為 1 5return 0;
}

swap函數(shù)

將兩個list數(shù)據(jù)交換，通過交換list指向的頭結(jié)點實現(xiàn)。

#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> l1(3, 66);list<int> l2;l2.push_back(1);l2.push_back(2);l2.push_back(3);l1.swap(l2);list<int>::iterator it1 = l1.begin();while (it1 != l1.end()){cout << *it1 << " ";  //輸出為 1 2 3++it1;}cout << endl;list<int>::iterator it2 = l2.begin();while (it2 != l2.end()){cout << *it2 << " "; //輸出為 66 66 66++it2;}cout << endl;return 0;
}

resize函數(shù)

1. 如果n < size, 會將結(jié)點刪除至list只有n個結(jié)點，由于list結(jié)點的釋放成本是不高的，因此不同于vector只是將末尾指向修改，list會實際上的在調(diào)用resize函數(shù)時的刪除結(jié)點。
2. 如果n > size，就將插入結(jié)點使得list有n個結(jié)點

#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.push_back(5);cout << l.size() << endl; //輸出為5l.resize(3); // n < sizecout << l.size() << endl; //輸出為3l.resize(6); // n > sizecout << l.size() << endl; //輸出為6return 0;
}

clear函數(shù)

釋放所有結(jié)點，使得list為空鏈表。

#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> l(66, 6);cout << l.size() << endl; // 輸出為66l.clear();cout << l.size() << endl; // 輸出為0return 0;
}

6. 數(shù)據(jù)操作函數(shù)

sort函數(shù)

對list中的數(shù)據(jù)進行排序。

#include <iostream>
#include <list>
using namespace std;int main()
{list<int> l1;l1.push_back(2);l1.push_back(1);l1.push_back(4);l1.push_back(7);l1.push_back(5);l1.push_back(9);l1.push_back(8);l1.sort();list<int>::iterator it = l1.begin();it = l1.begin();while (it != l1.end()){cout << *it << ' ';  //輸出為: 1 2 4 5 7 8 9it++;}return 0;
}

注： 由于list是鏈表實現(xiàn)的，迭代器是雙向迭代器，因此不能調(diào)用algorithm庫內(nèi)的sort函數(shù)，因此需要單獨設(shè)計sort函數(shù)，但是list的sort函數(shù)由于結(jié)構(gòu)原因?qū)е滦阅懿桓摺?/p>

reverse函數(shù)

將list內(nèi)的結(jié)點逆置。

#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << ' ';  //輸出為: 1 2 3 4it++;}l.reverse(); //將list逆置it = l.begin();while (it != l.end()){cout << *it << ' '; //輸出為: 4 3 2 1it++;}cout << endl;return 0;
}

merge函數(shù)

如果兩個list有序并且排序方式相同，可以將一個list的結(jié)點連接到另一個list上并保持有序，排序方式和連接前相同。

#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);list<int> l2;l2.push_back(6);l2.push_back(7);l2.push_back(8);l2.push_back(9);l2.merge(l1); //將l1的結(jié)點連接到l2，連接后l1為空list<int>::iterator it = l2.begin();while (it != l2.end()){cout << *it << ' ';it++;}cout << endl;return 0;
}

unique函數(shù)

只能給數(shù)據(jù)有序的list進行數(shù)據(jù)去重操作，如果數(shù)據(jù)無序去重操作會出現(xiàn)問題。

#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(2);l.push_back(2);l.push_back(3);l.push_back(3);l.push_back(3);l.push_back(4);l.unique();	//對list內(nèi)的數(shù)據(jù)去重list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << ' ';	// 輸出為: 1 2 3 4it++;}cout << endl;return 0;
}

remove函數(shù)

查找對應(yīng)的數(shù)據(jù)并進行刪除操作，數(shù)據(jù)存在就刪除，不存在不會進行任何操作。

#include <iostream>
#include <list>
using namespace std;
int main()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);l.remove(3); //刪除數(shù)據(jù)為3的結(jié)點list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << ' '; //輸出為: 1 2 4it++;}cout << endl;return 0;
}

splice函數(shù)

將以一個list的指定部分的結(jié)點轉(zhuǎn)移給其他list。

#include <iostream>
#include <list>
using namespace std;int main()
{list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);list<int> l2;l2.push_back(5);l2.push_back(6);l2.push_back(9);l2.push_back(8);list<int>::iterator it = l1.begin();l1.splice(it, l2); //將l2的所有結(jié)點轉(zhuǎn)移到l1的begin位置it = l1.begin();while (it != l1.end()){cout << *it << ' '; //輸出為:5 6 9 8 1 2 3 4it++;}return 0;
}