【正文】 } 121 1 6 3 4 8 30 5 22 17 7 12 19 22 44 89 1 3 4 6 8 30 5 22 17 1 3 4 6 7 8 12 19 22 30 5 22 17 44 89 程序的運行結(jié)果為： 122 ? 此類算法實現(xiàn)序列的排序 、 合并 、 查找等功能 ， 表 表 算法 說明 accumulate 計算序列中所有元素的累加和 partical_sum 用序列中元素從前到后的迭代和產(chǎn)生一個新的序列 adjacent_diffence 計算序列中相鄰元素的差 ， 保存到另一個序列中 inner_product 計算內(nèi)積 ， 即兩個序列對應(yīng)位置的元素相乘然。 //輸出 coutendl。 //合并 v1,v2元素到 v3中，且進(jìn)行排序 merge((),(),(),(),in())。 copy((),(),output)。 //輸出 coutendl。 120 sort((),())。 //初始化 v3， 設(shè)定大小 copy((),(),output)。 //用第 1組數(shù)初始化向量 v1 vectorint v2(ary2,ary2+num2)。 //元素數(shù)目 ostream_iteratorint output(cout, )。 //第 2組數(shù)據(jù) int num1=sizeof(ary1)/sizeof(int)。 int main() { int ary1[]={1,6,3,4,8,30,5,22,17}。 表 算法 說明 sort 對給定區(qū)間的序列排序 stable_sort 對給定區(qū)間的序列排序并保持等值元素的相對位置 partial_sort 對給定區(qū)間的序列進(jìn)行局部排序 nth_element 對給定區(qū)間的序列排序 ， 使第 n個元素前的元素小于它 ， 之后的元素大于等于它 merge 合并兩個區(qū)間 binary_search 按二分法查找元素 119 【例 】常用排序算法函數(shù)應(yīng)用。 return 0。 copy((),(),output)。 copy((),(),output)。 swap(v1,v2)。 copy((),(),output)。 it=remove((),(),6)。//輸出 coutendl。 reverse((),())。//輸出 v2所有元素值 coutendl。//輸出 v1所有元素值 coutendloriginal v2: 。 //填充算法，使 v2中所有元素等于 10 115 coutoriginal v1: 。 //整型向量迭代器 ostream_iteratorint output(cout, )。 //整型向量 vectorint v2(N)。 int ary1[N]={1,6,3,4,6,5,9}。 /* */ include algorithm include iostream include vector include functional using namespace std。 } 112 44 presents 1 times found it 44 the max is 87 程序的運行結(jié)果為： 113 2. 可變序列算法 ? 可變序列算法可以修改容器內(nèi)的元素 ， 此類算法包括的典型算法如表 。 coutthe max is *it。 else coutfound it keyendl。 //調(diào)用 find算法函數(shù)，返回向量 v1中首個與 key相同元素出現(xiàn)的位置 it=find((),(),key)。 //調(diào)用 count算法函數(shù)，計算向量 v1中與 key相等元素的個數(shù) size_t t=count((),(),key)。 vectorint::iterator it。 int num=sizeof(ary1)/sizeof(int)。 /* */ include algorithm include iostream include vector include functional using namespace std。 } 108 Original data: 1 7 3 4 6 5 9 Sort ascending: 1 3 4 5 6 7 9 Sort descending: 9 7 6 5 4 3 1 程序的運行結(jié)果為： 109 常用算法舉例 1. 不變序列算法 典型的不變序列算法如表 。 coutendl。 sort((),(),greaterint())。 //用默認(rèn)規(guī)則排序（升序） copy((),(),output)。 coutendlSort ascending: 。//輸出流迭代器 coutOriginal data: 。 vectorint v1(ary, ary+7)。 /* */ include algorithm include iostream include vector include functional using namespace std。 ? 而對于某些特殊的要求，則需要給算法函數(shù)一個特殊的規(guī)則，而這種特殊的規(guī)則就需要用函數(shù)對象來實現(xiàn)（函數(shù)對象在后面的章節(jié)里會介紹），通過實例看一下 sort函數(shù)的兩種使用形式。//把 v1內(nèi)容復(fù)制給輸出流迭代器 return 0。 //整型數(shù)向量 ,利用數(shù)組初始化 ostream_iteratorint output(cout, )。 int main() { int a[5]={1,3,5,7,9}。 可以采用如下方法來適用以上的 copy函數(shù)： 104 【例 】 copy函數(shù)的使用。 103 在以上的函數(shù)原型中隱含著如下的信息： （ 1） 其中定義 InputIterator抽象類型代表輸入型迭代器 ， OutputIterator代表輸出型迭代器 ， 滿足了最低層次的迭代器的要求 。 102 算法的使用形式 ? 由迭代器的知識可以知道 ， 所有的迭代器都會提供最基本的共性操作 ， 那就是迭代器可以指向序列中的元素 ， 迭代器對象本身可以遞推指向下一個元素 。 100 圖 元素序列 101 STL的算法可以分成四大類： （ 1） 不可變序列的算法 ， 這類算法在對容器進(jìn)行操作時不會改變?nèi)萜鞯膬?nèi)容 ， 這類算法比較典型的有查找 find()、計數(shù) count()、 比較 equal()等 。 ? 算法因此可以靈活地處理不同長度的數(shù)據(jù)集合 。 ? 因此它們是通用的 ， 可適用于不同類型的數(shù)據(jù) 。 return 0。 cit++) cout *cit 。 //循環(huán)使 v1中每個元素加 10 for (cit=()。it!=()。 //it=()。 //普通迭代器 vectorint::const_iterator cit。 //整型數(shù)向量 vectordouble v2。 int main() { int a[5]={1,3,5,7,9}。 97 【例 】容器的迭代器常用操作。 ? 其中容器類可以是 list、 vector、 deque、 set、map等，數(shù)據(jù)類型實參可以是任何數(shù)據(jù)類型，但是定義迭代器絕不是孤立的，其數(shù)據(jù)類型實參必須與迭代器要指向的容器元素類型相同。 } 93 8 4 程序的運行結(jié)果為： 94 容器類迭代器的基本操作 ? STL中的容器有很多種 ， 不同容器定義的迭代器也不一樣 ， 但都提供一組相同的函數(shù)接口 ， 以便訪問迭代器所指位置中的數(shù)據(jù) ， 并驅(qū)動迭代器在有效區(qū)間上移動 。 //向前移動 2個元素 cout*iterendl。 //輸出 iter=()。 //迭代器指向 l1首元素 advance(iter,5)。 //定義鏈表，數(shù)據(jù)用數(shù)組 ary初始化 listint::iterator iter。 int main() { int ary[10]={1,7,9,3,2,8,6,5,4,0}。 92 【例 】用迭代器操作函數(shù)對 list進(jìn)行隨機(jī)訪問。fi1, FwdIt2 amp。to)。 91 （ 2） distance（ ） 函數(shù)可以計算兩個迭代器之間的距離 ， 其函數(shù)模板原型為： template typename _InIt int distance(_InIt amp。 89 ? STL還為迭代器提供了 3個輔助函數(shù)（模板）： ? advance( ) ? distance( ) ? iter_swap( ) 90 （ 1） advance（ ） 函數(shù)可以改變迭代器的位置 ， 具體改變的幅度和方向由參數(shù)決定 ， 本質(zhì)上是在函數(shù)內(nèi)部對迭代器進(jìn)行了若干次迭代 ， 然后指向新的元素 ， 其函數(shù)模板原型為： template typename _InIt,typename _Diff void advance(_InIt amp。 88 （ 4） 雙向迭代器的功能與前向迭代器相似 ， 區(qū)別在于雙向迭代器在兩個方向上都可以對數(shù)據(jù)遍歷 ，如鏈表容器 list的迭代器就符合此種類型的基本特征 。 （ 2） 輸出迭代器 ， 與輸入迭代器類似 ， 層次較低 ，允許向序列中寫入數(shù)據(jù) ， 但是不一定能從其中讀取數(shù)據(jù) 。 ? 它可以指向容器中的一個位置 ， 用戶不必關(guān)心這個位置的真正物理地址 ， 無須關(guān)心其存儲形式 ， 只要通過迭代器就能訪問這個位置的元素 。 85 ? 迭代器是個抽象的概念 。 ? 可以使用運算符函數(shù) “ ++” 或 “ ” ，讓迭代器前后移動，然后用 “ *迭代器 ” 的形式來訪問迭代器所指向的數(shù)據(jù)。 ? 迭代器就是用面向?qū)ο蠹夹g(shù)封裝的 高級指針 。 //輸出鍵值 ” blue”對應(yīng)的元素值 return 0。)。 //藍(lán)色 couthexsetw(6)setfill(39。 coutm1[green]endl。039。 //輸出鍵值 ” red”對應(yīng)的元素值 coutgreen color = 。)。 //輸出紅色提示 couthexsetw(6)setfill(39。i++) //循環(huán)實現(xiàn)把三個 “ 鍵值 /元素 ”插入 m1 m1[snames[i]]= colors[i]。 //定義一個 map對象 82 for(int i=0。 //定義三個字符串作鍵值 int colors[3]={0xff0000,0x00ff00,0x0000ff}。 /* */ include iostream include iomanip include string include map using namespace std。 ? 其中 set/multiset 使用的鍵值和元素值都是同一元素 ， 這是與 map/ multimap的區(qū)別 。 (4) multimap， 和 map相同 ， 它允許重復(fù)元素 ， 即 multimap可以包含多個鍵值 key相同的元素 。 每一個鍵只能出現(xiàn)一次 ， 不允許重復(fù) 。 (2) multiset , 和 set 相同 ， 它允許重復(fù)元素 ， 即 multiset可包括多個值相同的元素 。 ? 關(guān)聯(lián)式容器的差別主要在于元素的類型以及處理重復(fù)元素時的方式 。 ? 在二叉樹中 ， 每個元素為一個節(jié)點 ， 都有一個父節(jié)點和兩個子節(jié)點：左子樹中的所有元素值都比自身小 ， 右子樹中的所有元素值都比自身大 。 ? 排序準(zhǔn)則以函數(shù)形式給出 ， 用來比較元素的值 ，或是元素的鍵值 (KEY)， 一般采用運算符 “ ”進(jìn)行比較操作 ， 不過也可以自定義比較函數(shù) ，執(zhí)行和系統(tǒng)默認(rèn)不同的排序規(guī)則 。 78 ? STL中所謂 關(guān)聯(lián)式容器 ， 就是把一個 鍵值 key與一個 元素值 value 相聯(lián)系 ， 并以該鍵值 key 作為準(zhǔn)則來執(zhí)行查找 、 插人和刪除等操作 。 //刪除末端元素 print(ds)。 //插入數(shù)據(jù)