歡迎來到博主的專欄：c++編程
博主ID：代碼小豪
文章目錄
- list
- 成員類型
- 構造、析構、與賦值
- iterator
- 元素訪問
- 修改元素
- list的操作
list
list的數據結構是一個鏈表，準確的說應該是一個雙向鏈表。這是一個雙向鏈表的節點結構：
list的使用方式和vector大差不差，區別主要還是體現在某些操作的效率方面，如下：
| list | vector | |
|---|---|---|
| 插入與刪除 | O(1) | O(N) |
| 遍歷 | O(N) | O(N) |
| 訪問 | O(N) | O(1) |
總體而言，如果線性表需要大量的刪除和插入，那么使用list會更加高效，如果只是單純的存儲數據，vector比list更好用，而且vector的空間還比list小。
OK，話不多說，開始看看list都有什么操作。
成員類型
由于STL中的容器都是模板類，因此數據的類型和常見的內置類型肯定不同，了解成員類型可以更好的讀懂list的各個函數原型。
list的模板如下：
template < class T, class Alloc = allocator<T> >
class list;
函數原型常見類型有：
| 類型 | 作用 |
|---|---|
| value_type | 模板當中的第一個類型，即T |
| reference | value_type類型的引用，即T& |
| pointer | value_type類型的指針，即T* |
| size_type | 代表無符號整型 |
| difference_type | 代表有符號整型 |
希望大家能記住以上類型，因為接下來的list的函數原型經常會出現上述類型的參數。
構造、析構、與賦值
由于博主也不太會使allocator，因此介紹使用list的時候，參數一律使用alloc的缺省值。
default (1)
explicit list (const allocator_type& alloc = allocator_type());
fill (2)
explicit list (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());
range (3)
template <class InputIterator>list (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());
copy (4)
list (const list& x);
- default構造：初始化時不傳入任何參數，就能實例化出一個空鏈表。
list<int> L1;//實例化一個容納int變量的空鏈表list<float> L2;//實例化一個容納int變量的空鏈表list<string>L3;//實例化一個容納string對象的空鏈表
- 填充（fill）構造：構造一個n個值為val的對象的鏈表。
list<int>L4(4, 2);//{2,2,2,2}list<float>L5(5, 3.14);//{ 3.14, 3.14, 3.14, 3.14, 3.14}list<string>L6(2, "hello world");//{"hello world","hello world"}
- c++11標準還支持使用initializer_list初始化。
list (initializer_list<value_type> il,const allocator_type& alloc = allocator_type());
這種初始化方式非常方便，非常好用。關于initializer_list的介紹可以去看看博主的c++雜談系列。
使用方法大致如下：
list<int>L7{ 1,2,3,4,5 };//{1,2,3,4,5}list<string>L8{ "haha","hehe","xixi"};//{"haha","hehe","xixi"}
是不是有點像給數組初始化時的用法，非常方便。
- 范圍（range）構造
這種該構造是通過使用傳入迭代器的方式，將迭代器內的元素傳入list容器當中。
list<int>L7{ 1,2,3,4,5 };//{1,2,3,4,5}
list<string>L8{ "haha","hehe","xixi"};//{"haha","hehe","xixi"}
list<int>L9(L7.begin(), L7.end());//{1,2,3,4,5}
list<string>L9(L8.begin(), L8.end());//{"haha","hehe","xixi"}
當然了，這里的迭代器可以是與list<T>相同類型的迭代器。比如這種用法也是合理的。
string str("hello world");list<char>L11(str.begin(), str.end());//{'h','e','l','l','o',' ','w','o','r','d'}
當然了，上面的說法是存在嚴重錯誤的，list<char>和string：：iterator的類型當然是不一樣的，只是讀起來順口而已。實際上我想表達的是：list<char>容器的元素類型是char，而string::iterator指向的元素也是char類型。因此可以這樣構造。
- 拷貝（copy）構造，構造一個與x一致的容器。
list<int>L12{ 1,2,3,4,5 };
list<int>L13(L12);//L13與L12一致
賦值運算符重載和拷貝構造的使用方法完全一致
list& operator= (const list& x);
list<int> list1{ 1,2,3,4 };list<int>list2;list2 = list1;//list2與list1一致
至于析構函數則沒什么需要大家操作的地方了，當list超出作用域時，會自動調用list的析構函數。而且list析構函數還不需要傳入參數
iterator
list的迭代器也是分為四種，分別是
（1）正向迭代器
（2）正向定值迭代器
（3）反向迭代器
（4）反向定值迭代器
STL的迭代器用法基本差不多，這里博主就不多演示怎么使用了，大家可以參考vector和string的迭代器用法。
list迭代器的不同之處在于，vector和string的迭代器都是隨機迭代器（random access iterator），而list是雙向迭代器（bidirectional iterator），隨機迭代器可以支持++，–，以及加減算術的操作，而雙向迭代器只能使用++或者–操作。
list<int>list1{ 1,2,3,4,5,6 };
list<int>::iterator it = list1.begin();
it + 1;//error，雙向迭代器不支持算術加減
it++;//ok,雙向迭代器支持自加自減
這意味著我們可以通過一下兩種方式遍歷list1.
list<int>list1{ 1,2,3,4,5,6 };
list<int>::iterator it = list1.begin();while (it != list1.end())
{cout << *it;it++;
}for (auto& e : list1)
{cout << e;
}
元素訪問
list不支持使用下標訪問符（[]）訪問容器內的元素了。實際上，list一共就提供了兩個函數，一個front，一個back。用來訪問第一個或者最后一個元素。
reference front();
const_reference front() const;
reference back();
const_reference back() const;
list1.front() = 7;//第一個元素1修改成7
list1.back() = 1;//最后一個元素修改成1
修改元素
大家看看list關于修改元素的函數結口，是不是感覺很熟悉
可以發現list和vector關于修改元素的函數接口簡直是如出一轍、
這是因為Victor，string，list都是線性表的結構，因此對元素的修改操作的效果都是一致的，區別只在于涉及的算法不同，這里我打算將算法放在list的模擬實現當中講解，或者也可以去看博主的C語言數據結構關于雙鏈表的博客。
list的操作
list和vector雖然在邏輯上是一致的，但是在內存結構上卻完全不同了，因此list可執行的操作和vector是不同的。
- remove——移除所有值為val的節點
void remove (const value_type& val);
- unique——去掉鏈表中所有的重復元素。（鏈表需有序）
list<int>list2{ 5,6,3,2,1,1,5 };list2.sort();//排序list2.unique();//list2={1,2，3,5，6}
- sort——排序
(1) void sort();
(2)
template <class Compare>void sort (Compare comp);
默認情況下會將鏈表排成升序，如果想要將鏈表排成降序，就需要用到仿函數（像函數一樣使用的類）。
list<int>list2{ 5,6,3,2,1,1,5 };list2.sort();//升序for (auto& e : list2){cout << e << ' ';}cout << endl;list2.sort(greater<int>());//降序，這個greater是一個仿函數模板，博主不做說明for (auto& e : list2){cout << e << ' ';}
- reverse——逆置鏈表
void reverse();
reverse可以讓鏈表中的所有元素的順序顛倒過來。
- merge——合并鏈表
(1) void merge (list& x);
(2)
template <class Compare>void merge (list& x, Compare comp);
(1)
list容器將與x合并，merge會將x的所有成員都轉移到list容器當中。（x會變成一個空鏈表，而list則會變大）。合并的兩個鏈表必須擁有相同的順序（升序，不能是逆序）。合并后的鏈表也會呈升序
list<int>list4{6,5,5,3,5};list<int>list5{ 7,9,3,4,2 };list4.sort();//list4排成升序list5.sort();//list5排成升序list4.merge(list5);//將list5和list4合并for (auto& e : list4){cout << e << ' ';//{2，3,3，4,5，5，5，6,7，9}}
(2)
如果我們想要讓合并后的鏈表是逆序的，那就將待合并的鏈表排成逆序，再傳入仿函數comp，可以讓合并后的鏈表呈逆序。
list<int>list4{6,5,5,3,5};list<int>list5{ 7,9,3,4,2 };list4.sort(greater<int>());//排成逆序list5.sort(greater<int>());//排成逆序list4.merge(list5,greater<int>());//合并成逆序for (auto& e : list4){cout << e << ' ';//{9,7,6,5,5,5,4,3,3,2}}
- splice——粘接（感覺像是剪切）
entire list (1)
void splice (iterator position, list& x);
single element (2)
void splice (iterator position, list& x, iterator i);
element range (3)
void splice (iterator position, list& x, iterator first, iterator last);
splice重載了三個版本，每個版本都有不一樣的效果
第一版：全部粘接，將x的全部元素粘接到list容器的迭代器指向的位置。x會變成一個空鏈表。
list<int>list1{ 1,2,3,4 };list<int>list2{ 10,20,30,40 };list1.splice(list1.begin(), list2);for (auto& e : list1){cout << e << ' '; //{10, 20, 30, 40, 1, 2, 3, 4};}
第二版，單元素粘接，將x中的迭代器i指向的元素粘接到容器position指向的位置。
list<int>list1{ 1,2,3,4 };list<int>list2{ 10,20,30,40 };list1.splice(list1.begin(), list2,list2.begin());for (auto& e : list1){cout << e << ' '; //{10,1, 2, 3, 4};}
第三版，迭代區間粘接。將x中[first，last）區間內的所有元素都粘接到list容器的position位置上。
list<int>list1{ 1,2,3,4 };list<int>list2{ 10,20,30,40 };list1.splice(++list1.begin(), list2,++list2.begin(),--list2.end());for (auto& e : list1){cout << e << ' '; //{1,20,30 2, 3, 4};}
