目錄
介紹
常用函數
函數使用舉例
建立list并指派
周遊和查找
删除元素
清空清單
向list中插入元素
使用assign給容器增加新元素
兩個list交換
使用resize改變list的大小。
使用splice函數操作list
删除重複的元素
合并list
排序
list和vector的差別
list是線性雙向連結清單結構，它的資料由若幹個節點構成，每一個節點都包括一個資訊塊（即實際存儲的資料）、一個前驅指針和一個後驅指針。它無需配置設定指定的記憶體大小且可以任意伸縮，這是因為它存儲在非連續的記憶體空間中，并且由指針将有序的元素連結起來。由于其結構的原因，list 随機檢索的性能非常的不好，因為它不像vector 那樣直接找到元素的位址，而是要從頭一個一個的順序查找，這樣目标元素越靠後，它的檢索時間就越長。檢索時間與目标元素的位置成正比。雖然随機檢索的速度不夠快，但是它可以迅速地在任何節點進行插入和删除操作。因為list 的每個節點儲存着它在連結清單中的位置，插入或删除一個元素僅對最多三個元素有所影響，不像vector 會對操作點之後的所有元素的存儲位址都有所影響，這一點是vector 不可比拟的。
t 的特點：
(1) 不使用連續的記憶體空間，這樣可以随意地進行動态操作；
(2) 可以在内部任何位置快速地插入或删除，當然也可以在兩端進行push 和pop 。
(3) 不能進行内部的随機通路，即不支援[ ] 操作符和vector.at() ；
(4) 相對于verctor 占用更多的記憶體。
List的構造函數和析構函數
list<Elem> c
産生一個空list，其中沒有任何元素
list<Elem> c1(c2)
産生另一個同型list的副本(所有的元素都被拷貝)
list<Elem> c(n)
利用元素的default構造函數産生一個大小為n的list
list<Elem> c(n,elem)
産生一個大小為n的list，每個元素值都是elem
list<Elem> c(beg, end)
産生一個list，以區間[beg, end)做為元素初值
c.~list<Elem>()
銷毀所有元素，并釋放記憶體
list的非變動性操作
size()
傳回容器的大小
empty()
判斷容器是否為空,等價于size()==0,但可能更快
max_size()
傳回容器最大的可以存儲的元素
reserve()
如果容量不足，擴大之
c1 == c2
判斷c1 是否等于c2
c1 != c2
判斷c1是否不等于c2
c1 < c2
判斷c1 是否小于c2
c1 > c2
判斷c1 是否大于c2
c1 <= c2
判斷c1是否小于等于c2
c1 >= c2
判斷c1是否大于等于c2
list的指派操作
c1 = c2
将c2的全部元素指派給c1
assign(n, elem)
複制n個elem，複制給c
assign(beg, end)
将區間[beg;end）内的元素指派給c
c1.swap(c2)
将c1和c2元素互換
swap(c1,c2)
同上，此為全局函數
元素通路
front
傳回第一個元素，不檢查元素存在與否
back
傳回最後一個元素，不檢查元素存在與否
疊代器相關函數
begin()
傳回一個雙向疊代器，指向第一個元素
end()
傳回一個雙向疊代器，指向最後一個元素的下一個位置
rbegin()
傳回一個逆向疊代器，指向逆向疊代的第一個元素
傳回一個逆向疊代器，指向逆向疊代的最後一個元素的下一個位置
list安插、移除操作函數
insert(pos, elem)
在疊代器pos所指位置上安插一個elem副本，并傳回新元素的位置
insert(pos,n,elem)
在pos位置上插入n個elem副本，無傳回值
insert(pos,beg,end)
在pos位置上插入區間[beg,end)内的所有元素的副本，沒有傳回值
push_back(elem)
在尾部添加一個elem副本
pop_back()
移除最後一個元素，無傳回值
push_front()
在頭部添加一個elem副本
pop_front()
移除第一個元素，但不傳回
remove(val)
移除所有其值為val的元素
remove_if()
删除一個連結清單中所有滿足條件的元素
erase(pos)
移除pos位置上的元素，傳回下一個元素的位置
erase(beg, end)
移除[beg, end)區間内的所有元素，傳回下一個元素的位置
resize(num)
将元素數量改為num(如果size()變大了，多出來的新元素都需以default構造函數完成)
resize(num,elem)
将元素數量改為num(如果size()變大了，多出來的新元素都elem的副本)
clear()
移除所有元素，将容器清空
備注：安插和移除元素，都會使“作用點”之後的各個元素的iterator等失效，若發生記憶體重新配置設定，該容器身上的所有iterator等都會失效
List的特殊變動性操作
unique()
如果存在若幹相鄰而數值相等的元素，就移除重複元素，
之留下一個
unique(op)
如果存在若幹相鄰元素，都使op()的結果為ture，
則移除重複元素，隻留下一個。
c1.splice(pos, c2)
将c2内的所有元素轉移到c1之内，疊代器pos之前
c1.splice(pos, c2, c2pos)
将c2内的c2pos所指元素轉移到c1之内的pos所指位置上
(c1,c2可相同)
c1.splice(pos, c2,c2beg，c2end)
将c2内的[c2beg，c2end）區間内所有元素轉移到
c1内的pos之前(c1,c2可相同)
sort()
以operator<為準則，對所有元素排序
sort(op)
以op()為準則，對所有元素排序
c1.merge(c2)
假設c1和c2容器都包含已序(相同的排序方式)元素，将c2的全部元素轉移到c1，并保證合并後的list還是已序。
c1.merge(c2，op)
假設c1和c2容器都包含op()原則下的已序(相同的排序方式)元素，将c2的全部元素轉移到c1，并保證合并後的list在op（）原則仍是已序。
reverse()
将所有元素反序
#include <iostream>
#include <list>
using namespace std;
int main() {
//第一種，通過構造函數
int myints[] = { 44,77,22,11,12 };
list<int> mylist1(myints, myints + 5);
list<int> mylist2(2, 100); // 2個值為100的元素
//第二種，用push_back，或push_front
for (int i = 1; i <= 5; ++i) mylist1.push_back(i);
mylist2.push_front(20);
mylist2.push_front(30);
//第三種,用assign
list<int> first;
list<int> second;
first.assign(7, 10); // 給first添加7個值為10的元素
second.assign(first.begin(), first.end()); // 複制first給second
int myints1[] = { 32, 8, 4 };
first.assign(myints1, myints1 + 3); // 将數組myints的内容添加給first
return 0;
}
int myints[] = { 44,77,22,11,12};
list<int> myList(myints, myints + 5);
cout << "mylist contains:";
//周遊
for (list<int>::iterator it = myList.begin(); it != myList.end(); ++it)
{
cout << " " << *it;
}
cout << "\n";
//查找
if (*it == 22)
{
cout << "存在22";
}
//追加
for (int i = 1; i <= 5; ++i)
myList.push_back(i);
//逆序周遊
for (list<int>::reverse_iterator rit = myList.rbegin(); rit != myList.rend(); ++rit)
cout << ' ' << *rit;
// 建立執行個體以及指派
bool single_digit(const int& value) { return (value < 20); }
struct is_odd {
//重載操作符 ()
bool operator() (const int& value) { return (value % 2) == 1; }
};
//remove和remove_if删除元素
myList.remove(22);
myList.remove_if(single_digit);
myList.remove_if(is_odd());
for (list<int>::iterator it = myList.begin(); it != myList.end(); it++)
myList.push_back(22);
for (list<int>::iterator it = myList.begin(); it != myList.end(); it++) {
//周遊删除，這是一種錯誤的寫法。
/*for (auto it = myList.begin(); it != myList.end(); it++)
if (*it == 11) {
myList.erase(it);
}*/
//第一種寫法
for (auto it = myList.begin(); it != myList.end();)
if (*it == 22) {
myList.erase(it++);
else
cout << " " << *it;
it++;
//第二種寫法
it=myList.erase(it);
list<int> mylist;
list<int>::iterator it;
mylist.push_back(10);
mylist.push_back(20);
mylist.push_back(30);
for (it = mylist.begin(); it != mylist.end(); ++it)
cout << ' ' << *it;
cout << '\n';
mylist.clear();
mylist.push_back(2121);
mylist.push_back(3232);
#include <vector>
// 初始化
for (int i = 1; i <= 5; ++i) mylist.push_back(i); // 1 2 3 4 5
it = mylist.begin();
++it; // 疊代器it現在指向數字2 ^
//在i0t指向的位置出插入元素10
mylist.insert(it, 10); // 1 10 2 3 4 5
// "it" 仍然指向數字2 ^
//在it指向的位置出插入兩個元素20
mylist.insert(it, 2, 20); // 1 10 20 20 2 3 4 5
--it; // 現在it指向數字20 ^
vector<int> myvector(2, 30); //建立vector容器，并初始化為含有2個值為30的元素
//将vector容器的值插入list中
mylist.insert(it, myvector.begin(), myvector.end());
// 1 10 20 30 30 20 2 3 4 5
//it仍然指向數字20 // ^
first.assign(7, 10);// 給first添加7個值為10的元素
int myints[] = { 22, 33, 44 };
first.assign(myints, myints + 3); // 将數組myints的内容添加給first
cout << "Size of first: " << int(first.size()) << '\n';
cout << "Size of second: " << int(second.size()) << '\n';
// swap lists
list<int> first(3, 100); // 三個值為100的元素
list<int> second(5, 200); // 五個值為200的元素
first.swap(second);
cout << "first contains:";
for (list<int>::iterator it = first.begin(); it != first.end(); it++)
cout << "second contains:";
for (list<int>::iterator it = second.begin(); it != second.end(); it++)
// resizing list
for (int i = 1; i < 10; ++i) mylist.push_back(i);//list為0 1 2 3 4 5 6 7 8 9
mylist.resize(5);//list的長度變為5，元素為：0 1 2 3 4
mylist.resize(8, 100);//list的長度變為8，超過5的部分變為100，元素為：0 1 2 3 4 100 100 100
mylist.resize(12);//list的長度變為12，超過5的部分賦預設值0，元素為：0 1 2 3 4 100 100 100 0 0 0 0
for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
// splicing lists
list<int> mylist1, mylist2;
for (int i = 1; i <= 10; ++i)
mylist1.push_back(i); // mylist1: 1 2 3 4 5 6 7 8 9
for (int i = 1; i <= 3; ++i)
mylist2.push_back(i * 10); // mylist2: 10 20 30
it = mylist1.begin();
++it; // 指向數字2
mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
// mylist2 (empty)
// "it" 仍然指向數字2
mylist2.splice(mylist2.begin(), mylist1, it);
// mylist1: 1 10 20 30 3 4
// mylist2: 2
// "it" 此時已經無效了
advance(it, 3); // "it" 指向數字30
mylist1.splice(mylist1.begin(), mylist1, it, mylist1.end());
// mylist1: 30 3 4 1 10 20
cout << "mylist1 contains:";
for (it = mylist1.begin(); it != mylist1.end(); ++it)
cout << "mylist2 contains:";
for (it = mylist2.begin(); it != mylist2.end(); ++it)
// list::unique
#include <cmath>
// a binary predicate implemented as a function:
bool same_integral_part(double first, double second) { return (int(first) == int(second)); }
// a binary predicate implemented as a class:
struct is_near {
bool operator() (double first, double second) { return (fabs(first - second) < 5.0); }
double mydoubles[] = { 12.15, 2.72, 73.0, 12.77, 3.14,
12.77, 73.35, 72.25, 15.3, 72.25 };
list<double> mylist(mydoubles, mydoubles + 10);
for (list<double>::iterator it = mylist.begin(); it != mylist.end(); ++it)
mylist.unique();
mylist.sort(); // 2.72, 3.14, 12.15, 12.77, 12.77,
// 15.3, 72.25, 72.25, 73.0, 73.35
mylist.unique(); // 2.72, 3.14, 12.15, 12.77
// 15.3, 72.25, 73.0, 73.35
mylist.unique(same_integral_part); // 2.72, 3.14, 12.15 // 15.3, 72.25, 73.0
mylist.unique(is_near()); // 2.72, 12.15, 72.25
bool mycomparison(double first, double second) { return ((first) < (second)); }
list<double> first, second;
first.push_back(3.1);
first.push_back(2.2);
first.push_back(2.9);
second.push_back(3.7);
second.push_back(7.1);
second.push_back(1.4);
first.sort();
second.sort();
first.merge(second);
for (list<double>::iterator it = first.begin(); it != first.end(); ++it)
// (second 現在為空)
second.push_back(1.1);
second.push_back(2.1);
second.push_back(2.5);
first.merge(second, mycomparison);
for (list<double>::iterator it = first.begin(); it != first.end(); it++)
// list::sort
#include <string>
#include <cctype>
// comparison, not case sensitive.
bool compare_nocase(const string& first, const string& second) {
unsigned int i = 0;
while ((i < first.length()) && (i < second.length())) {
//将大寫字母轉為小寫字母
if (tolower(first[i]) < tolower(second[i])) return true;
else if (tolower(first[i]) > tolower(second[i])) return false;
++i;
return (first.length() < second.length());
list<string> mylist;
list<string>::iterator it;
mylist.push_back("one");
mylist.push_back("two");
mylist.push_back("Three");
mylist.push_back("Four");
mylist.push_back("Five");
mylist.push_back("Six");
mylist.sort();
mylist.sort(compare_nocase);
vector資料結構
vector和數組類似，擁有一段連續的記憶體空間，并且起始位址不變。
是以能高效的進行随機存取，時間複雜度為o(1);
但因為記憶體空間是連續的，是以在進行插入和删除操作時，會造成記憶體塊的拷貝，時間複雜度為o(n)。
另外，當數組中記憶體空間不夠時，會重新申請一塊記憶體空間并進行記憶體拷貝。
vector擁有一段連續的記憶體空間，能很好的支援随機存取，
是以vector<int>::iterator支援“+”，“+=”，“<”等操作符。
list資料結構
list是由雙向連結清單實作的，是以記憶體空間是不連續的。
隻能通過指針通路資料，是以list的随機存取非常沒有效率，時間複雜度為o(n);
但由于連結清單的特點，能高效地進行插入和删除。
list的記憶體空間可以是不連續，它不支援随機通路，
是以list<int>::iterator則不支援“+”、“+=”、“<”等
vector<int>::iterator和list<int>::iterator都重載了“++”運算符。
總之，如果需要高效的随機存取，而不在乎插入和删除的效率，使用vector;
如果需要大量的插入和删除，而不關心随機存取，則應使用list。
參考：
1、
https://www.cnblogs.com/wj0816/p/6568630.html
![C語言第四章自述2第四章 選擇結構程式設計[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)