這周的課講了將泛型算法。現(xiàn)在將泛型算法收集下求摇，備用。

(1)泛型算法用迭代器來解決第一個(gè)要求：遍歷容器。所有迭代器都支持自增操作符共屈，從一個(gè)元素定位下一個(gè)元素借宵，并提供解引用操作符訪問元素的值?

(2)算法也許會(huì)改變存儲(chǔ)在容器中的元素的值，也許會(huì)在容器內(nèi)移動(dòng)元素，但是猎贴，算法從不直接添加或刪除元素。??

【 只讀算法】?

?(3)只讀算法是 accumulate趁耗，該算法在 numeric 頭文件中定義装蓬。? accumulate 帶有三個(gè)形參。頭兩個(gè)形參指定要累加的元素范圍暗赶。第三個(gè)形參則是累加的初值。 假設(shè) vec 是一個(gè) int 型的 vector 對(duì)象岳锁，下面的代碼：? ? ??

// sum the elements in vec starting the summation with the value 42? ? ??

int sum = accumulate(vec.begin(), vec.end(), 42);

?將 sum 設(shè)置為 vec 的元素之和再加上 42。 首先招盲，調(diào)用該函數(shù)時(shí)必須傳遞一個(gè)起始值，否則，accumulate 將不知道使用什么起始值蜕衡。 其次，容器內(nèi)的Section 11.2.? A First Look at the Algorithms元素類型必須與第三個(gè)實(shí)參的類型匹配，或者可轉(zhuǎn)換為第三個(gè)實(shí)參的類型万皿。?

(4) find_first_of 函數(shù)。? ? 這個(gè)算法帶有兩對(duì)迭代器參數(shù)來標(biāo)記兩段元素范圍，在第一段范圍內(nèi)查找與第二段范圍中任意元素匹配的元素位岔，然后返回一個(gè)迭代器，指向第一個(gè)匹配的元素。如果找不到元素抓于，則返回第一個(gè)范圍的 end 迭代器。? ? ??

size_t cnt = 0;? ? ?

?list::iterator it = roster1.begin();? ? ?

?// look in roster1 for any name also in roster2? ? ??

while ((it = find_first_of(it, roster1.end(),roster2.begin(), roster2.end()))!= roster1.end())? ? ? ? ? ? {? ? ? ??

? ? ? ? ++cnt;? ? ? ??

?// we got? a match, increment it to look in the rest of roster1

? ? ? ? ++it;

? ? ? }

? ? ? cout << "Found " << cnt<< " names on both rosters" << endl;

? ? 注意：find_first_of，帶有兩對(duì)迭代器參數(shù)吼和。每對(duì)迭代器中，兩個(gè)實(shí)參的類型必須精確匹配末捣，但不要求兩對(duì)之間的類型匹配妥畏。特別是燃辖，元素可存儲(chǔ)在不同類型序列中薪韩，只要這兩序列的元素可以比較即可。?

?【 寫容器元素的算法】**********************************************************?

?(5) fill 函數(shù)桨菜，寫入到輸入序列的算法? ? fill 帶有一對(duì)迭代器形參，用于指定要寫入的范圍谊路，而所寫的值是它的第三個(gè)形參的副本。執(zhí)行時(shí)，將該范圍內(nèi)的每個(gè)元素都設(shè)為給定的值脱羡。如果輸入范圍有效，則可安全寫 入氓鄙。這個(gè)算法只會(huì)對(duì)輸入范圍內(nèi)已存在的元素進(jìn)行寫入操作舷暮。

? ? ?fill(vec.begin(), vec.end(), 0);?// reset each element? to 0 ? ? ?

// set? subsequence of the range to 10

? ? ? fill(vec.begin(), vec.begin() + vec.size()/2, 10);?

(6) fill_n函數(shù)，不檢查寫入操作的算法? ? fill_n 函數(shù)帶有的參數(shù)包括：一個(gè)迭代器耗啦、一個(gè)計(jì)數(shù)器以及一個(gè)值。該函數(shù)從迭代器指向的元素開始获黔，將指定數(shù)量的元素設(shè)置為給定的值。fill_n 函數(shù)假定對(duì)指定數(shù)量的元 素做寫操作是安全的预茄。? ? 注意：初學(xué)者常犯的錯(cuò)誤的是：在沒有元素的空容器上調(diào)用 fill_n 函數(shù)（或者類似的寫元素算法）：? ? ??

*****************************************************

? ? ? vectorvec; // empty vector

? ? ? // disaster: attempts to write to 10 (nonexistent) elements in vec

? ? ? fill_n(vec.begin(), 10, 0);

? ? ? //vec 是空的刨沦，其結(jié)果未定義召庞，很可能導(dǎo)致嚴(yán)重的運(yùn)行時(shí)錯(cuò)誤徘禁。? ? ? *****************************************************

?(7) copy 函數(shù)娘荡，寫入到目標(biāo)迭代器的算法? ? copy 帶有三個(gè)迭代器參數(shù)：頭兩個(gè)指定輸入范圍回怜，第三個(gè)則指向目標(biāo)序列的一個(gè)元素翔试。傳遞給 copy 的目標(biāo)序列必須至少要與輸入范圍一樣大赢底。? ? 假設(shè) ilst 是一個(gè)存放 int 型數(shù)據(jù)的 list 對(duì)象粹庞，可如下將它 copy 給一個(gè) vector 對(duì)象：

? ? vectorivec; // empty vector

? ? // copy elements from ilst into ivec

? ? copy (ilst.begin(), ilst.end(), back_inserter(ivec));

?(8)算法的 _copy 版本? 有些算法提供所謂的“復(fù)制（copying）”版本流码。這些算法對(duì)輸入序列的元素做出處理，但不修改原來的元素驾荣，而是創(chuàng)建一個(gè)新序列存儲(chǔ)元素的處理結(jié)果。但不修改原來的元素， 而是創(chuàng)建一個(gè)新序列存儲(chǔ)元素的處理結(jié)果眯亦。

?(9)replace 算法板祝，對(duì)輸入序列做讀寫操作孤里，將序列中特定的值替換為新的值? 該算法帶有四個(gè)形參：一對(duì)指定輸入范圍的迭代器和兩個(gè)值炸枣。每一個(gè)等于 第一值的元素替換成第二個(gè)值霍衫。

? ? ? // replace any element? with value of 0 by 42

? ? ? replace(ilst.begin(), ilst.end(), 0, 42);?

(10)replace_copy? ? 這個(gè)算法接受第三個(gè)迭代器實(shí)參，指定保存調(diào)整后序列的目標(biāo)位置麸俘。

? ? ? // create empty vector to hold the replacement? ? ? vector<i>ivec;

? ? ? // use back_inserter to grow destination as needed

? ? ? replace_copy (ilst.begin(), ilst.end(),back_inserter(ivec), 0, 42);

? ? 調(diào)用該函數(shù)后徐紧，ilst 沒有改變，ivec 存儲(chǔ) ilst 一份副本稻励，而 ilst 內(nèi)所有的 0 在 ivec 中都變成了 42。??

【 對(duì)容器元素重新排序的算法】**************************************************

?(11)sort 算法? ? sort 算法帶有兩個(gè)迭代器實(shí)參，指出要排序的元素范圍。這個(gè)算法使用小于（<）操作符比較元素鸠窗。

?(12)unique 算法，該算法刪除相鄰的重復(fù)元素净刮，然后重新排列輸入范圍內(nèi)的元素星持，并且返回一個(gè)迭代器揪垄，表示無重復(fù)的值范圍的結(jié)束八回。? ? 它帶有兩個(gè)指定元素范圍的迭代器參數(shù)缠诅。? ? 注：調(diào)用 unique“刪除”了相鄰的重復(fù)值。給“刪除”加上引號(hào)是因?yàn)?unique 實(shí)際上并沒有刪除任何元素，而是將無重復(fù)的元素復(fù)制到序列的前端饥臂，從而覆蓋相鄰的重復(fù)元素屯援。unique 返回的迭代器指向超出無重復(fù)的元素范圍末端的下一位置。(想真正刪除元素要與erase函數(shù)連用)

?(13)stable_sort 算法庐橙，有著相同長(zhǎng)度的元素還能以字典次序的不同而區(qū)分? ? stable_sort 算法有第三個(gè)形參：比較元素所使用的謂詞函數(shù)的名字。這個(gè)謂詞函數(shù)必須接受兩個(gè)實(shí)參浸须，實(shí)參的類型必須與元素類型相同顺囊，并返回一個(gè)可用作條件檢測(cè)的值。

? ? ? // sort words by size,? but? maintain alphabetic order for words of the same size? ? ? stable_sort(words.begin(), words.end(), isShorter);?

?? ? // comparison function to be used to sort? by word length

? ? ? bool isShorter(const string &s1, const string &s2)

? ? ? {

? ? ? ? ? return s1.size() < s2.size();

? ? ? }

?(14)count_if 算法，統(tǒng)計(jì)個(gè)數(shù)? ? 執(zhí)行 count_if 時(shí)，首先讀取它的頭兩個(gè)實(shí)參所標(biāo)記的范圍內(nèi)的元素或辖。每讀出一個(gè)元素但惶，就將它傳遞給第三個(gè)實(shí)參表示的謂詞函數(shù)。此謂詞函數(shù)财喳。此謂詞函數(shù)需要單個(gè)元素類型 的實(shí)參，并返回一個(gè)可用作條件檢測(cè)的值。count_if 算法返回使謂詞函數(shù)返回條件成立的元素個(gè)數(shù)误证。? ? ? vector::size_type wc =count_if(words.begin(), words.end(), GT6);

? ? ? // determine whether a length of a given word is 6 or more

? ? ? bool GT6(const string &s)

? ? ? {?

?? ? ? ? return s.size() >= 6;

? ? ? }

? 【 再談迭代器】****************************************************************?

?(15)插入迭代器(insert iterators)：這類迭代器與容器綁定在一起叠殷，實(shí)現(xiàn)在容器中插入元素的功能稽亏。? 插入器是一種迭代器適配器，帶有一個(gè)容器參數(shù)咸作，并生成一個(gè)迭代器壳嚎，用于在指定容器中插入元素。通過插入迭代器賦值時(shí)刊驴，迭代器將會(huì)插入一個(gè)新的元素。C++ 語言提供了三種插入器业踢，其差別在于插入元素的位置不同：

?(a)back_inserter雇锡，創(chuàng)建使用 push_back 實(shí)現(xiàn)插入的迭代器。

?(b)front_inserter，使用 push_front 實(shí)現(xiàn)插入谅年。

? (c)inserter弄企，使用 insert 實(shí)現(xiàn)插入操作。除了所關(guān)聯(lián)的容器外洽瞬，inserter 還帶有第二實(shí)參：

? ? ? 指向插入起始位置的迭代器样漆。

?注：front_inserter 需要使用 push_front呻右，只有當(dāng)容器提供 push_front 操作時(shí)，才能使用 front_inserter。在 vector 或其他沒有 push_front 運(yùn)算的容器上使用front_inserter憾赁，將產(chǎn)生錯(cuò)下載文檔到電腦，查找使用更方便1下載券? 131人已下載下載還剩2頁未讀颓芭，繼續(xù)閱讀誤。

? ? ? listilst, ilst2, ilst3;

? ? // empty lists

? ? ? // after this loop ilst contains: 3 2 1 0

? ? ? for (list::size_type i = 0; i != 4; ++i)

? ? ? ? ? ilst.push_front(i);

? ? ? // after copy ilst2 contains: 0 1 2 3

? ? ? copy (ilst.begin(), ilst.end(), front_inserter(ilst2));?

?? ? // after copy, ilst3 contains: 3 2 1 0

? ? ? copy (ilst.begin(), ilst.end(),

? ? ? inserter (ilst3, ilst3.begin()));

?在復(fù)制并創(chuàng)建 ilst2 的過程中，元素總是在這個(gè) list 對(duì)象的所有元素之前插入。而在復(fù)制創(chuàng)建 ilst3 的過程中贫堰，元素則在 ilst3 中的固定位置插入缨该。剛開始時(shí)，這個(gè)插入 位置是此 list 對(duì)象的頭部皱碘，但插入一個(gè)元素后菱阵，就不再是首元素了。

? (16) iostream 迭代器

? ? 【注】流迭代器都是類模板：任何已定義輸入操作符（>> 操作符）的類型都可以定義 istream_iterator。類似地歌懒，任何已定義輸出操作符（<< 操作符）的類型也可定義ostream_iterator验烧。

? ? ? istream_iteratorcin_it(cin);? ? // reads ints1 from cin

? ? ? istream_iteratorend_of_stream;? // end iterator value

? ? ? // writes Sales_items from the ofstream named outfile

? ? ? // each element? is followed by a space? ? ? ofstream outfile;?

在創(chuàng)建 istream_iterator 時(shí)慨蓝，可直接將它綁定到一個(gè)流上。另一種方法是在創(chuàng)建時(shí)不提供實(shí)參洽蛀，則該迭代器指向超出末端位置。ostream_iterator 不提供超出末端迭代器。 在創(chuàng)建 ostream_iterator 對(duì)象時(shí)，可提供第二個(gè)（可選的）實(shí)參熙掺，指定將元素寫入輸出流時(shí)使用的分隔符缆镣。分隔符必須是 C 風(fēng)格字符串。因?yàn)樗?C 風(fēng)格字符串，所以必須以空字符結(jié)束煞聪；否則，其行為將是未定義的。

? ? 【注】流迭代器的限制：

?(a)不可能從 ostream_iterator 對(duì)象讀入燕雁，也不可能寫到 istream_iterator 對(duì)象中。

?(b)一旦給 ostream_iterator 對(duì)象賦了一個(gè)值，寫入就提交了。賦值后沛申，沒有辦法再改變這個(gè)值著觉。此外，ostream_iterator 對(duì)象中每個(gè)不同的值都只能正好輸出一次。

?(c)ostream_iterator 沒有 -> 操作符。

? ? ? istream_iteratorcin_it(cin);? ? // reads ints from cin

? ? ? istream_iteratorend_of_stream;? // end iterator value

? ? ? // initialize vec from the standard input:

? ? ? vectorvec(cin_it, end_of_stream);

? ? ? sort(vec.begin(), vec.end());

? ? ? // writes ints to cout using " " as the delimiter

? ? ? ostream_iterator<int>output(cout, " ");

//?write?only?the?unique?elements?in?vec?to?the?standard?output

?? ? unique_copy(vec.begin(),?vec.end(),?output);

輸入是：?23?109?45?89?6?34?12?90?34?23?56?23?8?89?23?輸出是：?6?8?12?23?34?45?56?89?90?109