C++--＞stl: list的使用

前言list的認識

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

1?list的構造

常用的構造函數

default (1) （默認構造）	explicit list (const allocator_type& alloc = allocator_type());
? ? ? fill (2) ?n個val值填充	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);

參考代碼：?

? ?

void print_list(list<int>& list1)
{list<int>::iterator it = list1.begin();while (it != list1.end()){cout << *it;it++;}cout << endl;}
void construct_test()
{list<int>list_1;// 空構造list<int>list_2(20,0);// n  vallist<int>::iterator it = list_2.begin();  // 迭代器構造 list<int> th(list_2.begin(),list_2.end());// 不支持的寫法 list<int> th(list_2.begin(),list_2.begin()+4);// 因為list的迭代器不支持隨機訪問哦 其實本質上是因為只給迭代器封裝了++的操作 int arr[] = {1,2,3,4,5,6};list<int>four(arr,arr+4);// 這也是迭代器構造 數組肯定是可以通過下標 隨機訪問啦 // 拷貝構造//list<int> five = four;list<int> five(four);print_list(five);}

2. list的迭代器?

? ? list的圖解?

迭代器的理解:

? 這個迭代器的內部封裝可以大致這么理解：

? ? 肯定是對node的操作，封裝node的移動，有++,--以及!=? ?判斷倆個迭代器是否相等就這樣就很常見，封裝的目的很簡單，就是為了統一容器的操作哦！。
? ? 后期博客我會更新其中的模擬實現這是很有意思的：
? ?內部是沒有封裝+某個數的?
? ?所以之前例子中指出像這樣的 list<int>::iterator(it,it+3);? 是不被允許的哦！
總之因為list的底層容器是雙向鏈表，每個節點地址之間是不連續的，所以我們為了統一容器操作就封裝迭代器了。

迭代器使用：代碼實例：

void iterator_test() {int arr[] = { 1,2,3,4,5,6 };list<int>four(arr, arr + 5);// 用迭代器遍歷four這個鏈表list<int>::iterator it = four.begin();// 正向迭代器list<int>::reverse_iterator rit = four.rbegin();// 反向迭代器while (it != four.end()){cout << *it;it++;}cout << endl;while (rit != four.rend()){cout << *rit;rit++;}cout << endl;}

輸出：12345? ?

? ? ? ? ? ?54321

doubly list的圖解

? ?這里只標出了 node之間指針的關系，這里值得注意的就是如何實現雙向循環的，就是創建一個頭節點，頭節點作用就是用來很方便的實現增刪查改（減少判空這個策略數據結構中可以多了解理解）總之就是讓頭節點的pre指向尾節點，尾節點的next指向頭節點。總之頭節點是不存放有效數據的！所以下面我說說迭代器遍歷的問題！

?list迭代器遍歷的理解：?

? ? ? 顯然 list<T>iterator:: begin 指向的是頭節點的下一個位置，node結構體中總是存放的是頭節點，所以需要遍歷的時候需要總是從頭節點開始一一遍歷，而不是隨機訪問。?
? ? 判斷到尾部的方法有很多一個是根據size，以及cur節點的遍歷到了頭節點了。

3. list element access(元素獲取)

? ? ?list的獲取常用的就是一個是front? 和 back? 雙向鏈表根據頭節點實現起來很方便的。
? ? ?

3.1 reference front()? 和reference back的使用

? ? ? ? 這個list的front的成員函數，簡單來說就是返回一個頭節點的元素引用。?
這里的referrence其實是一個typedef，這個在庫里面實現是很常見的? 可以這樣理解：
typedef reference T;
? back同理如上。

? ?

// list::front
#include <iostream>
#include <list>int main ()
{std::list<int> mylist;mylist.push_back(77);mylist.push_back(22);// now front equals 77, and back 22mylist.front() -= mylist.back();std::cout << "mylist.front() is now " << mylist.front() << '\n';return 0;
}

輸出： 55

4. list modified 元素修改

? ? list常用的修改方面的有：? 頭插，頭刪，尾刪，尾插，還有指定位置刪除，和指定位置插入，還有指定尾插刪除，以及swap （經常被用于去寫構造函數的還有拷貝構造）

4.1 push_front 和pop_front

實現：

// list::push_front
#include <iostream>
#include <list>int main ()
{std::list<int> mylist (2,100);         // two ints with a value of 100mylist.push_front (200);mylist.push_front (300);std::cout << "mylist contains:";for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

實現：

// list::pop_front
#include <iostream>
#include <list>int main ()
{std::list<int> mylist;mylist.push_back (100);mylist.push_back (200);mylist.push_back (300);std::cout << "Popping out the elements in mylist:";while (!mylist.empty()){std::cout << ' ' << mylist.front();mylist.pop_front();}std::cout << "\nFinal size of mylist is " << mylist.size() << '\n';return 0;
}

4.2 push_back和pop_front?

? ? 尾插和尾刪返回值都是void注意哦

// list::push_back
#include <iostream>
#include <list>int main ()
{std::list<int> mylist;int myint;std::cout << "Please enter some integers (enter 0 to end):\n";do {std::cin >> myint;mylist.push_back (myint);} while (myint);std::cout << "mylist stores " << mylist.size() << " numbers.\n";return 0;
}

// list::pop_back
#include <iostream>
#include <list>int main ()
{std::list<int> mylist;int sum (0);mylist.push_back (100);mylist.push_back (200);mylist.push_back (300);while (!mylist.empty()){sum+=mylist.back();mylist.pop_back();}std::cout << "The elements of mylist summed " << sum << '\n';return 0;
}

4.3 insert

? 在指定位置（用迭代器哦）插入一個元素，
? ? ?插入n個val 在指定位置
? 在指定位置插入一個范圍迭代器區間的元素


void insert_test() {int arr[] = { 1,2,3,4,5 };//    1  2  3  4  5int arr1[] = { 11,12,13,14,15 };//    11  12  13  14  15vector<int>v1(arr,arr+5);list<int> mylist(arr1,arr1+5);     //     !list<int>::iterator it = mylist.begin();it++;mylist.insert(it,10);// 迭代器可能存在失效的問題 所以這里一定要給it重賦值   print_list(mylist);// n valit = mylist.begin();it++;mylist.insert(it, 10,1);print_list(mylist);//  范圍插入it = mylist.begin();it++;mylist.insert(it, v1.begin()+2, v1.end());print_list(mylist);}

輸出：11 10 12 13 14 15
11 1 1 1 1 1 1 1 1 1 1 10 12 13 14 15
11 3 4 5 1 1 1 1 1 1 1 1 1 1 10 12 13 14 15

4.4 erase 刪除

?傳遞的參數是list的迭代器，指定位置刪除和指定的迭代器范圍區間的元素刪除。
std:: iterator& advance(iterator，len) 這是庫里的移動迭代器的函數

// erasing from list
#include <iostream>
#include <list>int main ()
{std::list<int> mylist;std::list<int>::iterator it1,it2;// set some values:for (int i=1; i<10; ++i) mylist.push_back(i*10);// 10 20 30 40 50 60 70 80 90it1 = it2 = mylist.begin(); // ^^advance (it2,6);            // ^                 ^++it1;                      //    ^              ^it1 = mylist.erase (it1);   // 10 30 40 50 60 70 80 90//    ^           ^it2 = mylist.erase (it2);   // 10 30 40 50 60 80 90//    ^           ^++it1;                      //       ^        ^--it2;                      //       ^     ^mylist.erase (it1,it2);     // 10 30 60 80 90//        ^std::cout << "mylist contains:";for (it1=mylist.begin(); it1!=mylist.end(); ++it1)std::cout << ' ' << *it1;std::cout << '\n';return 0;
}

5. 迭代器失效問題

? ?我們之前說過迭代器的實現可以理解為一個封裝了node的移動和判斷的類。? 這里的數據存放是node，所以本質上還是用node*指向了一個節點，所以在list中只要該節點不刪除，這個節點依然存在。?
? 在list中插入不會導致迭代器失效，因為這個節點并沒有被銷毀（vector中的迭代器失效是因為他們的內存是連續的，當擴容的時候可能導致舊內存被銷數據被移動到新內存）但是list的底層是雙向循環鏈表，內存之間都是用指針（地址）連接起來的，不用在乎是否連續，你不主動銷毀內存是不會被銷毀的。
? ?所以只有當刪除的時候才會被銷毀。

談談erase和insert的返回值

? ?erase:

iterator erase (iterator position);
iterator erase (iterator first, iterator last);

insert:

single element (1)	iterator insert (iterator position, const value_type& val);
fill (2)	void insert (iterator position, size_type n, const value_type& val);
range (3)	template <class InputIterator>void insert (iterator position, InputIterator first, InputIterator last);

single element (1)

iterator insert (iterator position, const value_type& val);

fill (2)

void insert (iterator position, size_type n, const value_type& val);

range (3)

template <class InputIterator>void insert (iterator position, InputIterator first, InputIterator last);

insert：大體上分為兩，一種是插入一個元素，一個是插入多個元素。
返回值：簡單理解就是返回插入元素后的下一個位置的元素
erase則是返回刪除元素的下一個位置

處理迭代器失效：就是重新賦值給迭代器：

錯誤實例沒有重新賦值?

修正：?

? ?代碼：?

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時，必須先給//其賦值it =l.erase(it);++it;}
}