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