前記：本周進(jìn)入STL的最后一周钧惧，主要講解的是各種泛型算法：非變易型算法丧裁，變易型算法礁阁，排序，數(shù)值算法族奢，最后還介紹了內(nèi)存分配器姥闭。下面為我的一些個(gè)人所得：
算法（Algorithms）
在STL中算法可以比喻為刻刀，通過對(duì)各種精妙算法的運(yùn)用越走，才能將程序雕刻成一座完美的藝術(shù)品棚品。
重要的一點(diǎn)是算法是數(shù)學(xué)思想靠欢，并不是STL或者C++所獨(dú)有。STL的標(biāo)準(zhǔn)算法是將一些精妙的算法思想進(jìn)行了實(shí)作（實(shí)現(xiàn)）铜跑，以方便我們快捷的運(yùn)用门怪。因此在使用他們的時(shí)候，不光應(yīng)該知道怎么使用锅纺，更應(yīng)該知道其算法思想及其實(shí)現(xiàn)方式掷空。只有后兩者才是算法真正有價(jià)值的核心。
首先應(yīng)該了解一點(diǎn)囤锉，算法一般不是成員函數(shù)坦弟，而是搭配迭代器使用的全局函數(shù)。這樣也是為了使算法更好的配合更多的容器進(jìn)行使用官地。
算法大體上分為四類：
1酿傍、非變易型算法：指不直接修改其所操作的容器內(nèi)容的算法。
2驱入、變易型算法：指可以修改它們所操作的容器內(nèi)容的算法赤炒。
3、排序算法：包括對(duì)序列進(jìn)行排序和合并的算法亏较、搜索算法以及有序序列上的集合操作莺褒。
4、數(shù)值算法：對(duì)容器內(nèi)容進(jìn)行數(shù)值計(jì)算宴杀。
帶后綴名的算法
在以上總體基礎(chǔ)上癣朗，還需要注意的兩個(gè)很特別的詞尾(后綴）：
1，后綴_if
例如count(),find()的非變易型算法或者remove()這樣的非變易型算法旺罢，要求參數(shù)傳遞一個(gè)值旷余，與區(qū)間內(nèi)容進(jìn)行比較，得出想要的結(jié)果扁达。但是如果我們想要傳遞一個(gè)函數(shù)或者仿函數(shù)正卧，例如判定OP(elem)的true或false來得出結(jié)果呢，這就要用到后綴_if了跪解，比如count_if():
difference_type
count_if(InputIterator beg,InputIterator end,UnaryPredicate op)
表示計(jì)算在[beg,end)區(qū)間中op(elem)判定為true的元素個(gè)數(shù)炉旷。
2，后綴_copy
replace(),remove()等算法是在容器本體上進(jìn)行的修改操作叉讥，如果不想修改原容器窘行，而是將修改后的內(nèi)容復(fù)制到新的區(qū)間里呢？用_copy后綴就對(duì)啦图仓。
例如：remove_copy()
OutputInterator
remove_copy (InputIterator sourceBeg, InputIterator sourceEnd,
OutputIterator destBeg,
const T& value)
表示復(fù)制[beg,end)區(qū)間內(nèi)的值到destBeg開始的目標(biāo)區(qū)間罐盔，并將與值value相等的值移除。原區(qū)間內(nèi)容不變哦救崔。
當(dāng)然_if和_copy也可以一起使用哦惶看，例如remove_copy_if:
OutputInterator
remove_copy_if (InputIterator sourceBeg, InputIterator sourceEnd,
OutputIterator destBeg,
UnaryPredicat op)
表示復(fù)制[beg,end)區(qū)間內(nèi)的值到destBeg開始的目標(biāo)區(qū)間捏顺，并將op(elem)判定為ture的值移除，原區(qū)間內(nèi)容不變纬黎。
復(fù)雜度
復(fù)雜度是算法的帶來的數(shù)學(xué)性質(zhì)幅骄。復(fù)雜度與程序效率息息相關(guān)。
分為兩種(參考資料[1])：
1本今，時(shí)間復(fù)雜度
包含時(shí)間頻度T(n)和時(shí)間復(fù)雜度Ｏ(f(n))兩個(gè)概念拆座。簡(jiǎn)單的說就是運(yùn)行時(shí)間上的效率。
2诈泼，空間復(fù)雜度
一個(gè)程序的空間復(fù)雜度是指運(yùn)行完一個(gè)程序所需內(nèi)存的大小懂拾。利用程序的空間復(fù)雜度，可以對(duì)程序的運(yùn)行所需要的內(nèi)存多少有個(gè)預(yù)先估計(jì)铐达。
包含兩個(gè)部分：
（1）固定部分岖赋。主要包括指令空間（即代碼空間）、數(shù)據(jù)空間（常量瓮孙、簡(jiǎn)單變量）等所占的空間唐断。這部分屬于靜態(tài)空間。
（2）可變空間杭抠。這部分空間的主要包括動(dòng)態(tài)分配的空間脸甘，以及遞歸棧所需的空間等。這部分的空間大小與算法有關(guān)偏灿。
一個(gè)算法所需的存儲(chǔ)空間用f(n)表示丹诀。S(n)=O(f(n)) 其中n為問題的規(guī)模，S(n)表示空間復(fù)雜度翁垂。
在STL中主要以Big-O表示法分類算法的運(yùn)行時(shí)間铆遭。指的是將一個(gè)算法的運(yùn)行時(shí)間以輸入量n的函數(shù)表示：
O(1) 常數(shù) 運(yùn)行時(shí)間與元素個(gè)數(shù)無關(guān)。
O(log(n)) 對(duì)數(shù) 運(yùn)行時(shí)間隨元素個(gè)數(shù)呈對(duì)數(shù)增長沿猜。
O(n) 線性 運(yùn)行時(shí)間隨元素個(gè)數(shù)n的增長呈線性增長枚荣。
O(n*long(n)) n-log-n 運(yùn)行時(shí)間隨元素個(gè)數(shù)呈"線性和對(duì)數(shù)的乘積"增長。
O(n2) 二次方 運(yùn)行時(shí)間隨元素個(gè)數(shù)呈平方增長啼肩。
在大型程序中復(fù)雜度的重要性體現(xiàn)的尤其明顯橄妆。
