高效使用STL

僅僅是個選擇的問題，都是STL,，可能寫出來的效率相差幾倍；
熟悉以下條款,，高效的使用STL；

當(dāng)對象很大時,，建立指針的容器而不是對象的容器

1）STL基于拷貝的方式的來工作,，任何需要放入STL中的元素,，都會被復(fù)制,；
這也好理解，STL工作的容器是在堆內(nèi)開辟的一塊新空間，而我們自己的變量一般存放在函數(shù)?；蛄硪粔K堆空間中,；為了能夠完全控制STL自己的元素，為了能在自己的地盤隨心干活,；這就涉及到復(fù)制,；
而如果復(fù)制的對象很大，由復(fù)制帶來的性能代價也不小 ,；
對于大對象的操作,，使用指針來代替對象能消除這方面的代價；
2）只涉及到指針拷貝操作,， 沒有額外類的構(gòu)造函數(shù)和賦值構(gòu)造函數(shù)的調(diào)用,；

注意事項：
1）容器銷毀前需要自行銷毀指針所指向的對象；否則就造成了內(nèi)存泄漏,；
2）使用排序等算法時,，需要構(gòu)造基于對象的比較函數(shù)，如果使用默認的比較函數(shù),，其結(jié)果是基于指針大小的比較,，而不是對象的比較；

用empty() 代替size()來檢查是否為空

因為對于list,，size()會遍歷每一個元素來確定大小,，時間復(fù)雜度 o（n），線性時間,；而empty總是保證常數(shù)時間,；

盡量用區(qū)間成員函數(shù)代替單元素操作

使用區(qū)間成員函數(shù)有以下好處：

1）更少的函數(shù)調(diào)用
2）更少的元素移動
3）更少的內(nèi)存分配

例：將v2后半部的元素賦值給v1：

單元式操作：

使用區(qū)間成員函數(shù)assign()：

使用reserver避免不必要的內(nèi)存分配(for vector)

新增元素空間不夠時，vector會進行如下操作：
1）分配當(dāng)前空間的兩倍空間,；
2）將當(dāng)前元素拷貝到新的空間中,；
3）釋放之前的空間；
4）將新值放入新空間指定位置,；

如果預(yù)先知道空間的大小,，預(yù)先分配了空間避免了重新分配空間和復(fù)制的代價；

注：reserve()只是修改了容量,，并非大小,，向vector中增加元素還是需要通過push_back加入；

使用有序的vector代替關(guān)聯(lián)容器(階段性的操作適用)

對階段性操作的定義：

先做一系列插入,、完成之后,，后續(xù)操作都是查詢；

在階段性的操作下,，使用vector有以下優(yōu)勢：

1）因為vector有序,，關(guān)聯(lián)容器帶來的有序優(yōu)勢散失,；
2）都是使用二分法查找的前提下，查詢算法對連續(xù)的內(nèi)存空間的訪問要快于離散的空間,；

在map的insert()和operator［］中仔細選擇

插入時,，insert效率高；因為operator會先探查是否存在這個元素,，如果不存在就構(gòu)造一個臨時的,，然后才涉及到賦值，多了一個臨時對象的構(gòu)造,；

更新時,，［］效率更高，insert會創(chuàng)造一個對象,，然后覆蓋一個原有對象,；而［］是在原有的對象上直接賦值操作；

散列函數(shù)的默認比較函數(shù)是equal＿to,，因為不需要保持有序,；

盡量用算法替代手寫的循環(huán)

1）效率相比手寫更高；

STL的代碼都是C++專家寫出來的,，專家寫出來的代碼在效率上很難超越,；
除非我們放棄了某些特性來滿足特定的需求，可能能快過stl,；比如,，基于特定場合下的編程，放棄通用性,，可移植性,；
2）不容易出錯；
3）使用高層次思維編程
相比匯編而言,，C是高級語言,；一條C語言語句，用匯編寫需要好幾條,；
同樣的,，在STL的世界中，我們也有高層次的術(shù)語：
高層次的術(shù)語：insert／find／for＿each（STL算法）
低層次的詞匯：for ／while（C++語法）
用高層次術(shù)語來思考編程,，會更簡單,；

盡量用成員函數(shù)代替同名的算法

1）基于效率考慮，成員函數(shù)知道自己這個容器和其他容器有哪些特有屬性,，能夠利用到這些特性,；而通用算法不可以；

2）對于關(guān)聯(lián)容器,，成員函數(shù)find基于等價搜索,；而通用算法find基于相等來搜索,；可能導(dǎo)致結(jié)果不一樣；

使用函數(shù)對象代替裸函數(shù)作為算法的輸入?yún)?shù)

因為內(nèi)聯(lián),，在函數(shù)對象的方式中，內(nèi)聯(lián)有效,，而作為函數(shù)指針時,，一般編譯器都不會內(nèi)聯(lián)函數(shù)指針指向的函數(shù)；即使指定了inline,；

比如：

這個調(diào)用不是真的把doubleGreater傳給sort,，它傳了一個doubleGreater的指針。
更好的方式是使用函數(shù)對象：

注：《effcient c＋＋》中的實驗結(jié)論,，使用函數(shù)對象一般是裸函數(shù)的1.5倍,，最多能快2倍多

選擇合適的排序算法

需要排序前思考我們的必要需求，可能我們只是需要前多少個元素,，這時并不需要使用sort這種線性時間的工具,，性能消耗更少的parttition可能是更好的選擇；
以下算法的效率從左到右依次遞減：

功能說明：
partition ：將集合分隔為滿足和不滿足某個標準兩個區(qū)間,；
stable_partition ：partition的穩(wěn)定版本,；
nth_element ：獲取任意順序的前N個元素；
patical_sort ：獲取前N個元素,，這個N個元素已排序,；
sort：排序整個區(qū)間；
stable_sort：sort的穩(wěn)定版本,；

選擇合適的容器

為什么vector不提供push_front()成員方法,？因為效率太差，如果有太多從前面插入的需求,，就不應(yīng)該使用vector,，而用list；

關(guān)心查找速度,，首先應(yīng)該考慮散列容器（非標準STL容器,如：unordered_map,unordered_set),；其次是排序的vector，然后是標準的關(guān)聯(lián)容器,；

參考

《effictive STL》

《Efficient C++》