C++：标準容器庫List

資料來源：https://www.cnblogs.com/loleina/p/5179677.html、《C++Primer》
           

一、什麼是List？

• 雙向連結清單，隻支援雙向順序通路。
• 在list中任何位置進行插入/删操作速度都很快。
• 作為代價他不支援元素的随機通路，為了通路一個元素，我們隻能周遊整個容器。
• 與vector、deque、array相比，他的額外記憶體開銷也很大。

        list是一個線性雙向連結清單結構，他的資料由若幹個節點構成，每個節點都包括一個資訊塊（即實際存儲的資料）、一個前驅指針和一個後驅指針。他無需配置設定指定的記憶體大小且可以任意伸縮，這是因為他存儲在非連續的記憶體空間中，并且由指針将有序的元素連結起來。由于其結構的原因，list随機檢索的性能非常不好，因為他不像vector那樣直接找到元素的位址，而是要從頭一個一個的順序查找，這樣目标元素越靠後，他的檢索時間就越長。檢索時間與目标元素的位置成正比。雖然随機檢索的速度不夠快，但是他可以迅速地在任何節點進行插入和删除操作。因為list的每個節點儲存這他在連結清單中的位置，插入或删除一個元素僅對最多三個元素有所影響，不像vector會對操作點之後的所有元素的存儲位址都有影響，這一點是vector不可比拟的。

二、List的特點

1. 不使用連續的記憶體空間這一可以随意地進行動态操作。
2. 可以在内部任何位置快速地插入或删除，當然也可以在兩端進行push和pop。
3. 不能進行内部的随機通路，即不支援[ ]操作和vector.at();
4. 相對于vector占用更多的記憶體

List的定義，插入，周遊列印。

#include<iostream>
#include<list>
#include<string>
#include<algorithm>
using namespace std;

void PrintIt(string & StringToPoint)
{
	cout << StringToPoint << endl;
} 
int main()
{
	list<string> test;
	list<string>::iterator testiterator;

	test.push_back("no");
	test.push_back("march");
	test.push_front("ok");

	for (testiterator = test.begin(); testiterator != test.end(); ++testiterator)
	{
		cout << *testiterator << endl;
	}
	cout << "-------------" << endl;
	for_each(test.begin(), test.end(), PrintIt);
	cout << "-------------" << endl;
	system("pause");
	return 0;
}
           

1、利用疊代器iterator周遊整個List，調用指針指向開頭的iterator，然後與iterator.end()的傳回值進行比較。重複利用比較和循環列印字元串。

2、STL的通用算法for_each()，他能周遊一個iterator的範圍，然後調用PrintIt()來處理每個對象。不需要初始化、比較和給iterator增量，for_each()完成了這些工作。簡化了第一種方法。