高效的使用STL，使用STL

高效的使用STL

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

當對象很大時，建立指針的容器而不是對象的容器

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

vecttor <BigObj> vt1;
vt1.push_bach(myBigObj);

vecttor <BigObj* > vt2;
vt2.push_bach(new BigObj());

注意事項：
1）容器銷毀前需要自行銷毀指針所指向的對象；否則就造成了內存洩漏；
2）使用排序等算法時，需要構造基於對象的比較函數，如果使用默認的比較函數，其結果是基於指針大小的比較，而不是對象的比較；

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

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

盡量用區間成員函數代替單元素操作

使用區間成員函數有以下好處：
1）更少的函數調用
2）更少的元素移動
3）更少的內存分配

例：將v2後半部的元素賦值給v1：
單元式操作：

for (vector<Widget>::const_iterator ci = v2.begin() + v2.size() / 2;
ci != v2.end();
++ci)
v1.push_back(*ci)

使用區間成員函數assign()：

v1.assign(v2.begin() + v2.size() / 2, v2.end()); 

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

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

如果預先知道空間的大小，預先分配了空間避免了重新分配空間和復制的代價；
注：reserve()只是修改了容量，並非大小，向vector中增加元素還是需要通過push_back加入；

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

對階段性操作的定義：
先做一系列插入、完成之後，後續操作都是查詢；

在階段性的操作下，使用vector有以下優勢：
1）因為vector有序，關聯容器帶來的有序優勢散失；
2）都是使用二分法查找的前提下，查詢算法對連續的內存空間的訪問要快於離散的空間；

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

插入時，insert效率高；因為operator會先探查是否存在這個元素，如果不存在就構造一個臨時的，然後才涉及到賦值，多了一個臨時對象的構造；
更新時，［］效率更高，insert會創造一個對象，然後覆蓋一個原有對象；而［］是在原有的對象上直接賦值操作；

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

盡量用算法替代手寫的循環

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

盡量用成員函數代替同名的算法

1）基於效率考慮，成員函數知道自己這個容器和其他容器有哪些特有屬性，能夠利用到這些特性；而通用算法不可以；
2）對於關聯容器，成員函數find基於等價搜索；而通用算法find基於相等來搜索；可能導致結果不一樣；

使用函數對象代替裸函數作為算法的輸入參數

因為內聯，在函數對象的方式中，內聯有效，而作為函數指針時，一般編譯器都不會內聯函數指針指向的函數；即使指定了inline；
比如：

inline bool doubleGreater(double d1, double d2)
{
    return dl > d2;
}
vector<double> v;
...
sort(v.begin(), v.end(), doubleGreater);

這個調用不是真的把doubleGreater傳給sort，它傳了一個doubleGreater的指針。
更好的方式是使用函數對象：

sort(v.begin(), v.end(), greater<double>())

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

選擇合適的排序算法

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

partition > stable_partition / nth_element / patical_sort / sort / stable_sort

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

選擇合適的容器

為什麼vector不提供push_front()成員方法？因為效率太差，如果有太多從前面插入的需求，就不應該使用vector，而用list；
關心查找速度，首先應該考慮散列容器（非標准STL容器,如：unordered_map,unordered_set)；其次是排序的vector，然後是標准的關聯容器；

參考

《effictive STL》
《Efficient C++》

Posted by: 大CC | 23JUN,2015
博客：blog.me115.com [訂閱]
微博：新浪微博