list的學習

list的介紹

list文檔的介紹
請添加圖片描述

list是可以在常數范圍內在任意位置進行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
list的底層是雙向鏈表結構，雙向鏈表中每個元素存儲在互不相關的獨立節點中，在節點中通過指針指向其前一個元素和后一個元素。
list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡單高效。
與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進行插入、移除元素的執行效率更好。
與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機訪問，比如：要訪問list的第6個元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時間開銷；list還需要一些額外的空間，以保存每個節點的相關聯信息(對于存儲類型較小元素的大list來說這可能是一個重要的因素

list的使用

list中的接口比較多，此處類似，只需要掌握如何正確的使用，然后再去深入研究背后的原理，已達到可擴展的能力。以下為list中一些常見的重要接口。

list的構造

請添加圖片描述

explicit list (const allocator_type& alloc = allocator_type());

解釋：構造一個空的容器，里面沒有任何元素
`explicit list (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());
解釋：構造一個包含 n 個元素的容器。每個元素都是 val 的副本
list (InputIterator first, InputIterator last)
解釋：構造一個容器，里面的元素是[first,last)，里面的每個元素都來自這個范圍里對應的元素，順序相同。
list (const list& x)
解釋：構造一個容器，其中包含 x 中每個元素的，順序相同。
示例：

void test_list1()
{list<int> l1;                         // 構造空的l1list<int> l2(4, 100);                 // l2中放4個值為100的元素list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end()）左閉右開的區間構造l3list<int> l4(l3);                    // 用l3拷貝構造l4// 以數組為迭代器區間構造l5int array[] = { 16,2,77,29 };list<int> l5(array, array + sizeof(array) / sizeof(int));// 列表格式初始化C++11list<int> l6{ 1,2,3,4,5 };// 用迭代器方式打印l5中的元素list<int>::iterator it = l5.begin();while (it != l5.end()){cout << *it << " ";  //16 2 77 29++it;}cout << endl;// C++11范圍for的方式遍歷for (auto& e : l5)cout << e << " ";  //16 2 77 29cout << endl;
}

list的遍歷

// 注意：遍歷鏈表只能用迭代器和范圍for
void PrintList(const list<int>& l)
{// 注意這里調用的是list的 begin() const，返回list的const_iterator對象for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it){cout << *it << " ";// *it = 10; 編譯不通過}cout << endl;
}

1.list iterator的使用

此處，大家可暫時將迭代器理解成一個指針，該指針指向list中的某個節點。
iterator begin();const_iterator begin() const;
iterator end();const_iterator end() const;
reverse_iterator rbegin();const_reverse_iterator rbegin() const
reverse_iterator rend();const_reverse_iterator rend() const;
這里的使用方法和string、vector一樣，就不再過多介紹了。

注意
1.begin與end為正向迭代器，對迭代器執行++操作，迭代器向后移動
2.rbegin(end)與rend(begin)為反向迭代器，對迭代器執行++操作，迭代器向前移動

2.list capacity

empty
bool empty() const;

解釋：檢測list是否為空，是返回true，否則返回false
示例：

void test_list2()
{list<int> l1;list<int> l2;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);cout << l1.empty() << endl;  //0cout << l2.empty() << endl;  //1
}

size
size_type size() const;

解釋：返回list中有效節點的個數
用法跟前面的一樣，不在過多闡述。

3.list 的元素的訪問

front
reference front();const_reference front() const;

解釋：返回list的第一個節點中值的引用
示例：

void test_list3()
{list<int> mylist;mylist.push_back(77);mylist.push_back(22);// now front equals 77, and back 22mylist.front() -= mylist.back();cout << "mylist.front() is now " << mylist.front() << '\n';  //mylist.front() is now 55}

back
reference back();const_reference back() const;

解釋：返回list的最后一個節點中值的引用
示例：

void test_list3()
{list<int> mylist;mylist.push_back(10);while (mylist.back() != 0){mylist.push_back(mylist.back() - 1);}cout << "mylist contains:";for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)cout << ' ' << *it;  //mylist contains: 10 9 8 7 6 5 4 3 2 1 0
}

4.list的插入、刪除、交換、清空

push_front
請添加圖片描述

解釋：在list首元素前插入值為val的元素
pop_front
解釋：刪除list中第一個元素
push_back
解釋：在list尾部插入值為val的元素
pop_back
解釋：刪除list中最后一個元素
示例：

void test_list4()
{int array[] = { 1, 2, 3 };list<int> L(array, array + sizeof(array) / sizeof(array[0]));// 在list的尾部插入4，頭部插入0L.push_back(4);L.push_front(0);list<int>::iterator it = L.begin();while (it != L.end()){cout << *it << " ";  //0 1 2 3 4++it;}cout << endl;// 刪除list尾部節點和頭部節點L.pop_back();L.pop_front();list<int>::iterator it1 = L.begin();while (it1 != L.end()){cout << *it1 << " ";  //1 2 3++it1;}
}

insert
請添加圖片描述

解釋：在position位置之前，插入值為val的元素。其它形式的用法和之前一樣。
erase
解釋：刪除position位置的值或者刪除某個區間的所有元素。
示例：

void test_list5()
{//這里的PrintList(L)就是上面list的遍歷int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 獲取鏈表中第二個節點auto pos = ++L.begin();cout << *pos << endl;  //2// 在pos前插入值為4的元素L.insert(pos, 4);PrintList(L);  //1 4 2 3// 在pos前插入5個值為5的元素L.insert(pos, 5, 5);PrintList(L);  //1 4 5 5 5 5 5 2 3// 在pos前插入[v.begin(), v.end)區間中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);  //1 4 5 5 5 5 5 7 8 9 2 3// 刪除pos位置上的元素L.erase(pos);PrintList(L);  //1 4 5 5 5 5 5 7 8 9 3// 刪除list中[begin, end)區間中的元素，即刪除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);  //
}

swap
請添加圖片描述

解釋交換兩個list中的元素。
clear
解釋：清空list中的有效元素。
示例：

void test_list6()
{// 用數組來構造listint array1[] = { 1, 2, 3 };list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));PrintList(l1);  //1 2 3// 交換l1和l2中的元素list<int> l2(3, 1);l1.swap(l2);PrintList(l1); //1 1 1PrintList(l2); //1 2 3// 將l2中的元素清空l2.clear();cout << l2.size() << endl;  //0
}

5.list的其它操作

sort
請添加圖片描述

解釋：對列表中的元素進行排序，更改它們在容器中的位置。(默認是按照升序排列)
示例：

void test_list7()
{list<int> l1 = { 3,2,1,4,5 };auto it = l1.begin();while (it != l1.end()){cout << *it << " ";  //3 2 1 4 5++it;}cout << endl;//升序排列：lessl1.sort();for (list<int>::iterator i = l1.begin(); i != l1.end(); i++){cout << *i << " ";  //1 2 3 4 5}
}

如果想按照降序排列，就按以下的方式寫。這里就先展示如何寫，到后面的學習在深入講解這個知識點，也就是“仿函數”。

void test_list7()
{list<int> l1 = { 3,2,1,4,5 };auto it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;//降序排列：greater//greater<int> gt;//l1.sort(gt);l1.sort(greater<int>());  //推薦這種寫法for (list<int>::iterator i = l1.begin(); i != l1.end(); i++){cout << *i << " ";  //5 4 3 2 1}
}

請添加圖片描述

解釋：對[first,last)范圍內的元素進行排序。也可以通過迭代器對指定范圍內的元素進行排序。默認是按升序排序，當然也可以通過仿函數來按照降序排列。
示例：

int main()
{vector<int> v = { 6,3,4,5,2,1,7,9,8 };sort(v.begin(), v.end());for (auto i : v){cout << i << " ";  //1 2 3 4 5 6 7 8 9}cout << endl;vector<int> v1 = { 3,2,4,5,6,8,1 };sort(v1.begin(), v1.begin() + 4);for (auto x : v1){cout << x << " ";  //2 3 4 5 6 8 1}return 0;
}

通過對list和算法庫里的sort對比。我們可以知道list里的排序沒法使用迭代器來進行排序，因為list的底層是帶頭雙向循環鏈表，當使用end()時，由于像vector和string里的迭代器不同，它們的end是最后一個元素的下一個位置，而在鏈表中，鏈表的物理空間并不連續，end的下一個數據就會指向頭結點。所以我們要對迭代器進行一定的封裝。讓迭代器符合統一的迭代器使用規則。
請添加圖片描述

那么如何進行封裝呢？等到list的模擬實現的時候在給各位細心講解。

unique
請添加圖片描述

解釋：從容器中每個連續的相等元素組中刪除除第一個元素之外的所有元素，也就是去除重復元素。注意，只有當元素與緊接其前面的元素相等時，才會從列表容器中刪除該元素。因此，此函數對于排好序的列表特別有用。（只對于版本1）
示例：

void test_list9()
{list<int> l1 = { 1,2,2,2,3,4,4,2,2,5 };l1.unique();auto i = l1.begin();while (i != l1.end()){cout << *i << " ";  //1 2 3 4 2 5++i;}cout << endl;list<int> l2 = { 1,1,3,4,2,5,5,5,6 };l2.sort();l2.unique();auto x = l2.begin();while (x != l2.end()){cout << *x << " ";  //1 2 3 4 5 6++x;}
}

reverse
請添加圖片描述

解釋：逆置列表中元素的順序
示例：

int main()
{list<int> mylist;for (int i = 1; i < 10; ++i) mylist.push_back(i);mylist.reverse();cout << "mylist contains:";for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)cout << ' ' << *it;  //mylist contains: 9 8 7 6 5 4 3 2 1return 0;
}

list的模擬實現

List的模擬實現

list迭代器失效問題

前面說過，此處大家可將迭代器暫時理解成類似于指針，迭代器失效即迭代器所指向的節點的無效，即該節點被刪除了。因為list的底層結構為帶頭結點的雙向循環鏈表，因此在list中進行插入時是不會導致list的迭代器失效的，只有在刪除時才會失效，并且失效的只是指向被刪除節點的迭代器，其他迭代器不會受到影響。

void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函數執行后，it所指向的節點已被刪除，因此it無效，在下一次使用it時，必須先給其賦值l.erase(it);++it;}
}// 改正
void TestListIterator()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);}
}

list與vector的對比

vector與list都是STL中非常重要的序列式容器，由于兩個容器的底層結構不同，導致其特性以及應用場景不同，其主要不同如下：

	vector	list
底層結構	動態順序表，一段連續空間	帶頭結點的雙向循環鏈表
隨機訪問	支持隨機訪問，訪問某個元素效率O(1)	不支持隨機訪問，訪問某個元素效率O(N)
插入和刪除	任意位置插入和刪除效率低，需要搬移元素，時間復雜度為O(N)，插入時有可能需要增容，增容：開辟新空間，拷貝元素，釋放舊空間，導致效率更低	任意位置插入和刪除效率高，不需要搬移元素，時間復雜度為O(1)
空間利用率	底層為連續空間，不容易造成內存碎片，空間利用率高，緩存利用率高	底層節點動態開辟，小節點容易造成內存碎片，空間利用率低，緩存利用率低
迭代器	原生態指針	對原生態指針(節點指針)進行封裝
迭代器失效	在插入元素時，要給所有的迭代器重新賦值，因為插入元素有可能會導致重新擴容，致使原來迭代器失效，刪除時，當前迭代器需要重新賦值否則會失效。	插入元素不會導致迭代器失效，刪除元素時，只會導致當前迭代器失效，其他迭代器不受影響
使用場景	需要高效存儲，支持隨機訪問，不關心插入刪除效率	大量插入和刪除操作，不關心隨機訪問