第8章 C++標(biāo)準(zhǔn)模板庫簡介

第8章C++標(biāo)準(zhǔn)模板庫簡介

本章主要內(nèi)容：8.1泛型編程和標(biāo)準(zhǔn)模板庫

8.2常用容器簡介

8.3迭代器簡介

8.4函數(shù)對象簡介

8.5STL常用算法簡介

計(jì)算機(jī)學(xué)院李衛(wèi)明8.1泛型編程和標(biāo)準(zhǔn)模板庫8.1.1泛型編程的基本概念泛型編程就是使程序設(shè)計(jì)代碼盡量適用于各種數(shù)據(jù)類型，包括內(nèi)置數(shù)據(jù)類型和標(biāo)準(zhǔn)庫、用戶設(shè)計(jì)實(shí)現(xiàn)的類類型。利用面向?qū)ο蟪绦蛟O(shè)計(jì)和泛型程序設(shè)計(jì)思想，在總結(jié)、歸納了程序設(shè)計(jì)領(lǐng)域常用的數(shù)據(jù)結(jié)構(gòu)和常用的算法基礎(chǔ)上，形成了經(jīng)典、通用、功能強(qiáng)大的C++標(biāo)準(zhǔn)模板庫。

計(jì)算機(jī)學(xué)院李衛(wèi)明

PrintContents是一個函數(shù)模板，輸出顯示容器類對象的所有元素，每個元素后輸出delim作分隔，容器con的begin、end成員函數(shù)返回稱為迭代器的對象，用于遍歷容器內(nèi)所有元素。//輸出容器內(nèi)容template<typenameContainerT>voidPrintContents(stringtitle,constContainerT&con,constchar*delim=nullptr){cout<<title<<":";for(autoit=con.begin();it!=con.end();++it){cout<<*it;if(delim)cout<<delim;}cout<<endl;}計(jì)算機(jī)學(xué)院李衛(wèi)明main函數(shù)中，使用了C++標(biāo)準(zhǔn)模板庫提供的多種類模板，構(gòu)造了整形集合、無序集合、鏈表、雙端隊(duì)列容器對象，它們都可存放若干整數(shù)。intmain(){set<int>S1{1,3,9,7,5};unordered_set<int>S2{1,3,9,7,5};list<int>L1{1,3,9,7,5};deque<int>DQ1{1,3,9,7,5};PrintContents("setS1",S1,"\t");PrintContents("unordered_setS2",S2,"\t");PrintContents("listS1",L1,"\t");PrintContents("dequeS1",DQ1,"\t");}具體代碼參見樣例Ex8.1計(jì)算機(jī)學(xué)院李衛(wèi)明

泛型程序設(shè)計(jì)中，用概念（concept）來描述作為參數(shù)的數(shù)據(jù)類型所需具備的功能。“概念”代表所有具備這些功能的數(shù)據(jù)類型，一般用代表這個概念意義的名稱作為泛型程序中類型參數(shù)的名稱，有利于泛型程序的可讀性。容器類型就是C++標(biāo)準(zhǔn)模板庫中一個概念，它不但可以通過成員函數(shù)操作容器，也提供了用于遍歷容器內(nèi)存放的所有元素對象的begin、end成員函數(shù)，Ex8.1中用ContainerT命名；迭代器也是C++標(biāo)準(zhǔn)模板庫中一個概念，它是一個泛型指針對象，代表容器中的某個位置，通過迭代器可以訪問這個位置的元素對象，通過控制迭代器的移動，可以訪問容器內(nèi)的所有元素。具備一個概念所需要的功能的數(shù)據(jù)類型稱為這個概念的一個模型（model），Ex8.1中set<int>、unordered_set<int>、list<int>、deque<int>都是容器概念的模型，迭代器概念的模型可由編譯器推導(dǎo)出來，用auto表示，實(shí)際分別是set<int>::iterator、unordered_set<int>::iterator、list<int>::iterator、deque<int>::iterator，由于代表類型的名稱較長，用auto代替更方便，也不影響程序的可讀性。泛型程序設(shè)計(jì)中，把概念進(jìn)一步提煉成子概念。對于兩個不同的概念A(yù)、B，如果概念A(yù)需要除了具有概念B所需要的所有功能外，還需要具有其它一些功能，那么稱概念A(yù)是概念B的子概念，子概念A(yù)的模型一定是概念B的模型。計(jì)算機(jī)學(xué)院李衛(wèi)明8.1.2標(biāo)準(zhǔn)模板庫組成

STL最初是由HP公司的AlexanderStepanov和MengLee開發(fā)的、用于支持C++泛型編程的模板庫，現(xiàn)已成為C++標(biāo)準(zhǔn)的一部分。雖然有不同的STL實(shí)現(xiàn)，但它們?yōu)橛脩籼峁┑慕涌谧袷赝瑯拥臉?biāo)準(zhǔn)。STL四大組件間關(guān)系如圖所示：圖8.1C++STL組件之間的關(guān)系計(jì)算機(jī)學(xué)院李衛(wèi)明

STL實(shí)現(xiàn)了常用的數(shù)據(jù)結(jié)構(gòu)和算法，容器和算法是STL的核心組件。STL以類模板形式提供了各種常用的容器，vector、list、deque、forward_list都是STL的容器，STL還包括其它功能強(qiáng)大的容器，在本章第2節(jié)介紹。STL類模板形式提供的容器可以用來建立模板類的容器對象，用于存放類型相同的若干元素，通過容器的成員函數(shù)可以對容器進(jìn)行各種操作；此外，STL提供的泛型算法也可以操作容器。同一個STL算法通過迭代器可以操作不同類型容器內(nèi)元素，算法還可通過迭代器區(qū)間指定處理容器內(nèi)某個范圍的所有元素。迭代器是支持STL算法操作容器必不可少的組件，是泛型程序設(shè)計(jì)中的泛型指針類型。各類容器都有各自的迭代器，代表容器內(nèi)位置，可通過迭代器訪問指向的容器內(nèi)元素，迭代器還可前、后移動，指向不同的位置。指向數(shù)組元素的傳統(tǒng)指針可以看作特殊的迭代器。許多STL算法需要靈活處理策略，如查找符合某個規(guī)則的元素，這種靈活性主要由函數(shù)對象提供，函數(shù)對象作為算法的參數(shù)靈活操作迭代器指向的元素或某個范圍內(nèi)的所有元素。stack、queue是通過改變deque、list、vector等容器對象的接口實(shí)現(xiàn)的，也稱為容器適配器。通過改變stack、queue類模板的第二缺省參數(shù)類型可改變作為成員子對象的容器類型，一般缺省容器類型是雙端隊(duì)列。計(jì)算機(jī)學(xué)院李衛(wèi)明8.2常用容器簡介

C++標(biāo)準(zhǔn)模板庫提供了多種容器類模板，每個容器都可用于存放若干相同類型的元素，每個容器無參構(gòu)造時狀態(tài)為空，也可支持構(gòu)造時指定初始元素，在運(yùn)行時可動態(tài)增加、插入、刪除元素，容器撤銷時會執(zhí)行每個元素的析構(gòu)函數(shù)、并釋放容器本身占有的空間，所有容器支持拷貝構(gòu)造、移動構(gòu)造、復(fù)制賦值、移動賦值，所有容器都包含下面幾個成員函數(shù)：boolempty()const;//判別容器是否為空size_tsize()const;//容器內(nèi)存放的元素個數(shù)voidclear();//容器清空所有容器都提供了各自的迭代器類型，begin()成員函數(shù)返回容器內(nèi)開始位置迭代器，end()返回容器內(nèi)結(jié)束位置迭代器，正如樣例Ex8.1所示，通過這一對迭代器，可遍歷容器內(nèi)所有元素。基于實(shí)現(xiàn)這些容器的數(shù)據(jù)結(jié)構(gòu)不同，這些容器可分為三類：順序容器、關(guān)聯(lián)容器、無序容器，這三類容器滿足前述容器的所有功能，又具有各自的特點(diǎn)和功能，這些容器可看作容器概念的子概念。需要在數(shù)據(jù)結(jié)構(gòu)知識基礎(chǔ)上理解這些容器。

下面表格列出了標(biāo)準(zhǔn)模板庫各類容器和使用它們需要包含的頭文件。計(jì)算機(jī)學(xué)院李衛(wèi)明容器類模板描述頭文件向量(vector)所有元素連續(xù)存儲<vector>鏈表(list)雙向鏈表，每個結(jié)點(diǎn)包含一個元素<list>單鏈表(forward_list)單鏈表，每個結(jié)點(diǎn)包含一個元素<forward_list>雙端隊(duì)列(deque)所有元素分多段存放，段間不連續(xù)，段內(nèi)連續(xù)<deque>集合(set)基于紅黑樹，每個節(jié)點(diǎn)包含一個元素，元素間有序，無相同元素<set>多重集合(multiset)基于紅黑樹，每個節(jié)點(diǎn)包含一個元素，元素間有序，容許相等元素<set>映射(map)每個元素{鍵，值}對組成的集合，無元素鍵相同<map>多重映射(multimap)每個元素{鍵，值}對組成的多重集合，容許元素鍵相同<map>無序集合(unordered_set)基于哈希表實(shí)現(xiàn)，元素間無序，無相同元素<unordered_set>無序多重集合(unordered_multiset)基于哈希表實(shí)現(xiàn)，元素間無序，容許相同元素<unordered_set>無序映射(unordered_map)每個元素{鍵，值}對組成的無序集合，無元素鍵相同<unordered_map>無序多重映射(unordered_multimap)每個元素{鍵，值}對組成的多重?zé)o序集合，容許元素鍵相同<unordered_map>計(jì)算機(jī)學(xué)院李衛(wèi)明

8.2.1 順序容器向量(vector)、鏈表(list)、前向鏈表(forward_list)、雙端隊(duì)列(deque)都是順序容器，分別基于動態(tài)分配的連續(xù)空間、雙鏈表、單鏈表、多段動態(tài)分配空間存儲容器內(nèi)所有元素，元素間存在順序關(guān)系，這也是順序容器名稱的由來，STLstd名字空間內(nèi)含如下聲明：template<typenameT,typenameAllocator=allocator<T>>classvector;template<typenameT,typenameAllocator=allocator<T>>classlist;template<typenameT,typenameAllocator=allocator<T>>classforward_list;template<typenameT,typenameAllocator=allocator<T>>classdeque;順序容器類模板第一參數(shù)類型是元素類型，可以是內(nèi)置數(shù)據(jù)類型、類類型，包括智能指針，第二參數(shù)類型是分配器類型，分配器負(fù)責(zé)分配、生成、銷毀、回收元素對象，絕大多數(shù)程序都使用缺省分配器即可。計(jì)算機(jī)學(xué)院李衛(wèi)明順序容器前面章節(jié)已多次涉及，它們各有特點(diǎn)。向量和雙端隊(duì)列都支持快速下標(biāo)訪問；向量在尾部添加、刪除元素較快，其它位置刪除和插入元素較慢，雙端隊(duì)列在兩端添加和刪除元素較快，在其它位置刪除和插入元素較慢；鏈表、前向鏈表在指定位置插入、刪除元素較快，但需要額外的指針空間，不支持下標(biāo)訪問；鏈表容器，也稱雙鏈表容器，適合雙向處理；前向鏈表容器，也稱單鏈表容器，適合單向處理。所有這些順序容器的查找平均時間復(fù)雜性一般是O(n)級，效率不太高。程序設(shè)計(jì)中結(jié)合數(shù)據(jù)結(jié)構(gòu)知識，根據(jù)需要選擇合適的容器。計(jì)算機(jī)學(xué)院李衛(wèi)明8.2.2 *關(guān)聯(lián)容器

集合(set)、多重集合(multiset)、映射(map)、多重映射(multimap)都是關(guān)聯(lián)容器，都基于二叉平衡樹或紅黑樹，需要結(jié)合數(shù)據(jù)結(jié)構(gòu)相關(guān)知識理解，STLstd名字空間內(nèi)含如下聲明：template<typenameT,typenameCompare=less<T>,typenameAllocator=allocator<T>>classset;template<typenameT,typenameCompare=less<T>,typenameAllocator=allocator<T>>classmultiset;template<typenamekey,typenamevalue,typenameCompare=less<key>,typenameAllocator=allocator<pair<constkey,value>>>classmap;template<typenamekey,typenamevalue,typenameCompare=less<key>,typenameAllocator=allocator<pair<constkey,vlaue>>>classmultimap;計(jì)算機(jī)學(xué)院李衛(wèi)明圖8.2set、multiset和map、muitimap內(nèi)部結(jié)構(gòu)計(jì)算機(jī)學(xué)院李衛(wèi)明集合、多重集合類模板第一參數(shù)類型是元素類型，可以是內(nèi)置數(shù)據(jù)類型、類類型，包括智能指針；第二參數(shù)類型用于兩個元素的比較，缺省比較類型是less<T>，內(nèi)部使用運(yùn)算符<比較兩個元素，元素類型如果是類類型，需重載運(yùn)算符<，根據(jù)需要，也可以更換比較規(guī)則；第三參數(shù)類型是分配器類型，絕大多數(shù)程序都使用缺省分配器即可。集合、多重集合容器的差異在于集合容器不允許相同元素，多重集合容器允許相同元素存在。集合、多重集合容器實(shí)現(xiàn)都基于二叉平衡樹或紅黑樹，集合和多重集合容器的查找、插入、刪除元素操作，它們的算法平攤時間復(fù)雜性基本都是O(logn)，這些相關(guān)成員函數(shù)運(yùn)算的參數(shù)和返回值經(jīng)常是迭代器，代表相關(guān)元素位置，也就是代表二叉平衡樹或紅黑樹相關(guān)結(jié)點(diǎn)，關(guān)于迭代器類型，在后面小節(jié)介紹。映射、多重映射類模板類似于集合、多重集合類模板，實(shí)現(xiàn)同樣基于二叉平衡樹或紅黑樹，不同的是，實(shí)現(xiàn)集合、多重集合容器的二叉平衡樹或紅黑樹結(jié)點(diǎn)中數(shù)據(jù)只包含元素對象一個部分，而實(shí)現(xiàn)映射、多重映射容器的二叉平衡樹或紅黑樹結(jié)點(diǎn)中數(shù)據(jù)包含組成元素的鍵（key）和值(value)兩個部分，所以，映射、多重映射類模板在集合、多重集合類模板基礎(chǔ)上多了一個類型參數(shù):元素鍵（key）類型。計(jì)算機(jī)學(xué)院李衛(wèi)明O()

O()

Ex8.2是容器使用樣例，分別建立了4個不同類型的容器：整數(shù)集合、多重整數(shù)集合、字匯表、電話簿，具有初始元素；映射容器元素類型是對pair，插入時需要使用make_pair構(gòu)建對pair，元素輸出時需要分別輸出對pair的first、second部分，也就是鍵(key)、值(value)部分；集合(set)、映射(map)容器內(nèi)元素鍵不可重復(fù)，多重集合(multiset)、多重映射(multimap)容器元素鍵可重復(fù)；最后，輸出所有有序關(guān)聯(lián)容器內(nèi)元素按鍵有序。

具體代碼參見樣例Ex8.2。關(guān)于有序關(guān)聯(lián)容器更多知識，可結(jié)合數(shù)據(jù)結(jié)構(gòu)知識查閱有關(guān)資料。計(jì)算機(jī)學(xué)院李衛(wèi)明8.2.3 *無序關(guān)聯(lián)容器無序集合(unordered_set)、無序多重集合(unordered_multiset)、無序映射(unordered_map)、無序多重映射(unordered_multimap)的功能與對應(yīng)的集合(set)、多重集合(multiset)、映射(map)、多重映射(multimap)大體相似，內(nèi)部基于哈希表實(shí)現(xiàn)，用空間換取時間，哈希函數(shù)設(shè)計(jì)合理情況下，這些容器查找、插入、刪除元素操作，算法平攤時間復(fù)雜性基本都是O(1)，與集合大小無關(guān)，同樣需要結(jié)合數(shù)據(jù)結(jié)構(gòu)相關(guān)知識理解。右圖是unordered_map、unordered_muitimap內(nèi)部結(jié)構(gòu)計(jì)算機(jī)學(xué)院李衛(wèi)明STLstd名字空間內(nèi)含如下聲明：template<typenameT,typenameHash=hash<T>,typenamePred=equal_to<T>，typenameAllocator=allocator<T>>classunordered_set;template<typenameT,typenameHash=hash<T>,typenamePred=equal_to<T>，typenameAllocator=allocator<T>>classunordered_multiset;template<typenamekey,typenamevalue,typenameHash=hash<key>,typenamePred=equal_to<key>，typenameAllocator=allocator<pair<constkey,value>>>classunordered_map;template<typenamekey,typenamevalue,typenameHash=hash<key>,typenamePred=equal_to<key>，typenameAllocator=allocator<pair<constkey,value>>>classunordered_multimap;計(jì)算機(jī)學(xué)院李衛(wèi)明將樣例Ex8.2中容器類型從關(guān)聯(lián)容器改為對應(yīng)的無序關(guān)聯(lián)容器形成了樣例Ex8.3，可以看出，無序關(guān)聯(lián)容器和有序關(guān)聯(lián)容器的使用方法基本一致，只是最后容器內(nèi)元素輸出是無序的。具體代碼參見樣例Ex8.3。關(guān)于無序關(guān)聯(lián)容器更多知識，可在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上參閱《C++標(biāo)準(zhǔn)庫（第二版）》計(jì)算機(jī)學(xué)院李衛(wèi)明8.3 迭代器簡介迭代器（iterator）是泛型程序設(shè)計(jì)中的“指針”，用于表示容器中特定的元素位置，通過迭代器可以訪問所在位置的元素，迭代器可以在容器內(nèi)移動，用于遍歷容器和操作容器。STL容器提供了統(tǒng)一的迭代器接口，基于迭代器接口，同一個STL泛型算法可以用于操作不同的容器。前面樣例Ex8.1中，PrintContents泛型函數(shù)模板通過容器con的begin、end成員函數(shù)返回的代表容器內(nèi)元素開始位置和結(jié)束位置的迭代器，通過迭代器對象輸出迭代器所在位置元素*it，并通過++it移動迭代器至下一元素位置，利用迭代器!=操作作為循環(huán)條件，循環(huán)操作，直至結(jié)束位置。樣例Ex8.2中，PrintMapContents泛型函數(shù)模板在獲取迭代器后，利用迭代器->操作，訪問迭代器所指map中元素的鍵(it->first)和值(it->second)。迭代器it操作表示如下：*it//對it進(jìn)行解引用，返回迭代器it指向的元素的引用it->men//成員選擇，獲取指定元素中名為men的成員。等效于(*it).men++it//先++，副作用使其指向容器的下一個元素，返回迭代器新值it++/后++，副作用使其指向容器的下一個元素，返回迭代器老值it1==it2//比較兩個迭代器是否相等it1!=it2//比較兩個迭代器是否不等事實(shí)上，指向數(shù)組的指針就是特殊的迭代器。計(jì)算機(jī)學(xué)院李衛(wèi)明根據(jù)迭代器作用不同，支持的操作不同，迭代器概念還可分為輸入迭代器、輸出迭代器、前向迭代器、雙向迭代器、隨機(jī)迭代器5個迭代器子概念，如圖8.4所示。圖8.4迭代器概念之間的關(guān)系輸入迭代器可用于輸入；輸出迭代器可用于輸出；前向迭代器既是輸入迭代器，也是輸出迭代器，它可以通過自增運(yùn)算向前移動；雙向迭代器也是前向迭代器，不但可以前向移動，也可以反向移動；隨機(jī)存取迭代器也是雙向迭代器，支持+n和-n運(yùn)算，在容器范圍內(nèi)隨機(jī)移動，隨機(jī)訪問容器內(nèi)元素。計(jì)算機(jī)學(xué)院李衛(wèi)明關(guān)聯(lián)容器和無序關(guān)聯(lián)容器不可直接修改元素的鍵（key），必要時，需要刪除元素、插入元素來代替。輸出迭代器用于算法的輸出，“*it=表達(dá)式”這樣的使用中，給迭代器it所指位置元素賦值，此處it就是輸出迭代器。注意，用作輸出迭代器時，*it所指位置必須存在，而且可賦值。例如：vector<int>V1(5),V2;set<int>S1{1,3,5};autoit1=V1.begin();autoit2=V2.begin();autoit3=S2.begin();autoit4=V1.end();上述語句運(yùn)行時建立了5個元素的向量V1、空向量V2、3個元素的集合S1、5個迭代器對象，注意下述輸出迭代器使用的有效性：*it1=10;//正確，將第一個元素修改為10*it2=10;//語義錯誤，it2也代表容器的實(shí)際結(jié)束位置，不可訪問//*it3=10;//語法錯，關(guān)聯(lián)容器和無序關(guān)聯(lián)容器不可修改鍵（key）*it4=10;//語義錯誤，it4代表容器的結(jié)束位置，不可訪問計(jì)算機(jī)學(xué)院李衛(wèi)明

STL提供泛型copy算法，此算法需要輸入迭代器、輸出迭代器，使用時需包含頭文件<algorithm>，等效實(shí)現(xiàn)如下:template<classInputIterator,classOutputIterator>OutputIteratorcopy(InputIteratorfirst,InputIteratorlast,OutputIteratorresult){while(first!=last){*result=*first;++result;++first;}returnresult;}算法中，[first,last)組成了迭代器區(qū)間。STL算法常以迭代器的區(qū)間作為輸入，指明輸入數(shù)據(jù)范圍。合格的迭代器區(qū)間[p1,p2)用兩個迭代器表示，p1經(jīng)過n次(n>=0)自增(++)操作后必須滿足p1==p2，區(qū)間范圍包含p1，但不包含p2。計(jì)算機(jī)學(xué)院李衛(wèi)明除了普通迭代器，STL還定義了幾種特殊的迭代器，如流迭代器、插入迭代器，定義在<iterator>頭文件中。流迭代器可分為輸入流迭代器（istream_iterator）、輸出流迭代器（ostream_iterator），前者是輸入迭代器，后者是輸出迭代器，下述樣例程序Ex8.4建立了2個匿名的輸入流迭代器，作為copy算法的輸入范圍；建立了匿名輸出流迭代器，用于輸出，每次元素輸出后輸出空格；程序調(diào)用copy算法將輸入流中指定范圍的若干整數(shù)拷貝輸出至輸出流對象。//Ex8.4#include<iostream>#include<iterator>#include<algorithm>usingnamespacestd;intmain(void){copy(istream_iterator<int>(cin),istream_iterator<int>(),ostream_iterator<int>(cout,""));}流迭代器需要指明輸入、輸出流對象和輸入輸出元素類型，上述程序輸入、輸出的都是int類型；建立輸入流迭代器時，如果沒有指定輸入流對象，代表輸入結(jié)束狀態(tài)。計(jì)算機(jī)學(xué)院李衛(wèi)明如果需要使用算法在容器中插入元素，往往需要用到插入迭代器，STL提供inserter、back_inserter、front_inserter三個函數(shù)，返回容器的插入迭代器，插入迭代器是一種輸出迭代器。前者需要容器和容器內(nèi)迭代器作為參數(shù)，用作輸出迭代器輸出時內(nèi)部轉(zhuǎn)換為調(diào)用容器的insert成員函數(shù)，第二、三兩個函數(shù)使用時只需要容器作為參數(shù)，用作輸出迭代器輸出時內(nèi)部分別轉(zhuǎn)換為調(diào)用容器的push_front、push_back成員函數(shù)，當(dāng)然，其中的容器必須具備push_front、push_back成員函數(shù)。樣例Ex8.5調(diào)用copy算法從輸入流輸入若干整數(shù)，插入到鏈表容器L尾部，再調(diào)用copy算法將容器L內(nèi)元素輸出至輸出流對象。大家可以測試樣例，并思考如果將樣例里back_inserter改為front_inserter，結(jié)果將有什么變化。具體代碼參見樣例Ex8.5。

計(jì)算機(jī)學(xué)院李衛(wèi)明8.4 函數(shù)對象簡介

STL中，很多泛型算法需要傳遞排序、查找等處理規(guī)則，使算法更靈活、更通用。例如，STL提供了泛型copy_if算法，使用時需包含頭文件<algorithm>，等效實(shí)現(xiàn)如下：template<classInputIterator,classOutputIterator,classUnaryPredicate>OutputIteratorcopy_if(InputIteratorfirst,InputIteratorlast,OutputIteratorresult,UnaryPredicatepred){while(first!=last){if(pred(*first)){*result=*first;++result;}++first;}returnresult;}計(jì)算機(jī)學(xué)院李衛(wèi)明算法中對象pred可以像函數(shù)一樣使用，用輸入迭代器first所指元素作為實(shí)參，如果判斷結(jié)果成立，拷貝元素至輸出迭代器。正如copy_if算法名字指出的一樣，它與泛型copy算法將迭代器區(qū)間所有元素拷貝至目標(biāo)位置不同的是，泛型copy_if算法，只將迭代器區(qū)間指定元素中符合條件的元素拷貝至目標(biāo)位置。STL泛型算法中類似情況很多，如count和count_if算法、find和find_if算法，另外，像本章第二節(jié)介紹的有序關(guān)聯(lián)容器和無序關(guān)聯(lián)容器也需要傳遞比較規(guī)則、哈希函數(shù)、相等判斷函數(shù)。這些泛型函數(shù)和泛型容器最后需要傳遞的對象可以像函數(shù)一樣使用，這樣的對象稱為函數(shù)對象（functionobject），或仿函數(shù)（functor），上述算法中pred就是這樣的函數(shù)對象或仿函數(shù)，它的類型UnaryPredicate只有一個元素作為參數(shù)，返回結(jié)果類型為bool類型，稱為一元謂詞；相應(yīng)的，如果函數(shù)對象具有二個元素作為參數(shù)，返回結(jié)果類型為bool類型，這樣的函數(shù)對象的類型稱為二元謂詞。計(jì)算機(jī)學(xué)院李衛(wèi)明

8.4.1 函數(shù)和函數(shù)對象重載了()運(yùn)算符的類對象可以作為函數(shù)對象，普通的函數(shù)也可視作一種函數(shù)對象。

程序設(shè)計(jì)中，經(jīng)常把數(shù)據(jù)保存在容器中，也經(jīng)常需要找出符合要求的所有數(shù)據(jù)，另存在其它容器中，借助STL，這樣的需求很容易處理。樣例Ex8.6建立了3個初始狀態(tài)為空的整形容器：鏈表L、向量V、集合S，利用copy算法和輸入迭代器、插入迭代器將輸入的整數(shù)保存在容器L中，再利用copy_if算法將容器L中保存的所有偶數(shù)拷貝至向量容器V中，此處用普通函數(shù)作為函數(shù)對象，接著，利用copy_if算法將容器L中保存的所有偶數(shù)拷貝至集合容器S中，此處用匿名對象作為函數(shù)對象。類對象可作為函數(shù)對象。樣例中可以看出，內(nèi)聯(lián)函數(shù)也可作為函數(shù)對象，這樣可以提高程序運(yùn)行速度。類對象作為函數(shù)對象時，類必須重載()運(yùn)算符，參數(shù)就是STL算法要處理的容器中元素；利用類對象作為函數(shù)對象，具有可記憶狀態(tài)的優(yōu)點(diǎn)，不足之處是需專門定義類或類模板。本章第二節(jié)容器類模板中用到的less、hash、equal_to就是STL中預(yù)定義的函數(shù)對象類模板?？梢?，運(yùn)用好STL，程序具有結(jié)構(gòu)清晰，可讀性好，開發(fā)和運(yùn)行效率高的優(yōu)點(diǎn)。具體代碼參見樣例Ex8.6。計(jì)算機(jī)學(xué)院李衛(wèi)明8.4.2 lambda表達(dá)式簡介C++11提供了lambda函數(shù)進(jìn)一步簡化了函數(shù)對象的使用，如上述樣例中，使用函數(shù)對象的語句31、35，可改為使用lambda函數(shù)的如下對應(yīng)語句：copy_if(L.begin(),L.end(),back_inserter(V),[](intx){returnx%2==0;});copy_if(L.begin(),L.end(),inserter(S,S.begin()),[](intx){returnx%2==0;});使用lambda函數(shù)后，無需原來樣例中的BeEven函數(shù)和EvenPredicate類，大大簡化了函數(shù)對象的使用，同時，函數(shù)對象的處理邏輯直接呈現(xiàn)在調(diào)用算法中，也有利于程序閱讀。lambda函數(shù)也稱為lambda表達(dá)式。編譯器在編譯lambda表達(dá)式時會自動產(chǎn)生lambda匿名類，并用此lambda匿名類的一個匿名對象替換lambda表達(dá)式。計(jì)算機(jī)學(xué)院李衛(wèi)明樣例Ex8.6通過上述修改后，編譯器編譯時自動產(chǎn)生如下類似的lambda匿名類：classlambda{public:booloperator()(intx)const{returnx%2==0;}};可以看出，編譯器自動產(chǎn)生的lambda匿名類與樣例Ex8.6中EvenPredicate類基本一致，上述修改簡化了程序，可以達(dá)到原先樣例Ex8.6同樣的效果。計(jì)算機(jī)學(xué)院李衛(wèi)明lambda函數(shù)是可以定義在表達(dá)式內(nèi)部的函數(shù)，以[]開始，以函數(shù)體定義結(jié)束，下述語句序列定義了lambda對象l，再通過對象l調(diào)用函數(shù)：

autol=[](){cout<<"Hello,lambda"<<endl;};l();//調(diào)用lambda函數(shù)也可以在定義lambda函數(shù)時直接調(diào)用它，下述語句輸出相同：

[](){cout<<"Hello,lambda"<<endl;}();上述lambda函數(shù)是最簡單的lambda函數(shù)形式，此函數(shù)不需要參數(shù)，返回值類型也由編譯器推導(dǎo)出來，也沒有訪問外部數(shù)據(jù)。計(jì)算機(jī)學(xué)院李衛(wèi)明lambda函數(shù)的一般形式如下：[...]{...}或[...]（...）mutableopt->retTypeopt

{...}其中，lambda函數(shù)開始的[...]表示捕捉外部數(shù)據(jù)的方式，在稍后介紹，如果沒有需要訪問外部數(shù)據(jù)，用[]表示；最后部分是函數(shù)體，必不可少；（...）表示函數(shù)參數(shù)表，前面例子中就用來聲明整形參數(shù)x，如果沒有參數(shù)表，可以用（）表示，在出現(xiàn)后面mutableopt->retTypeopt可選部分時，也必須出現(xiàn)，沒有后面可選部分時也可以省略；mutableopt

部分是可選的，稍后作介紹；retTypeopt部分也是可選的，可用于指明函數(shù)的返回值類型，而不是由編譯器根據(jù)return語句推導(dǎo)出來。計(jì)算機(jī)學(xué)院李衛(wèi)明lambda函數(shù)開始的[...]表示捕捉外部數(shù)據(jù)的方式，有傳值和傳引用2種方式，也可混合使用這2種方式：[=]表示外部對象以傳值方式傳給lambda函數(shù)，lambda函數(shù)內(nèi)可以讀取外部對象值，但不可修改它們，除非[...]后面有可選的mutable聲明；[&]表示外部對象以傳引用方式傳給lambda函數(shù)，lambda函數(shù)內(nèi)可以讀取也可以修改外部對象值。上述2種方式也可以混用，[...]內(nèi)可逐個指明對象傳遞方式，也可以指明總體傳遞方式和例外，如[x,&y]、[=,&y]、[&,x]傳遞外部對象x、y時具有一樣效果：傳值方式傳遞x，傳引用方式傳遞y。例如，樣例Ex8.7定義了2個lambda函數(shù)對象f1、f2，對象內(nèi)部具有數(shù)據(jù)成員x、y，建立函數(shù)對象時分別采用傳值和傳引用方式，函數(shù)對象f1、f2內(nèi)部數(shù)據(jù)成員x建立時都是1，建立后外部變量x的改變不影響內(nèi)部數(shù)據(jù)成員f1、f2內(nèi)部數(shù)據(jù)成員x，無mutable修飾的lambda函數(shù)不可修改傳值成員，mutable修飾的lambda函數(shù)可修改傳值成員，f2內(nèi)部數(shù)據(jù)成員x的改變也不影響外部變量x，y是外部變量y的引用，內(nèi)部數(shù)據(jù)成員y和外部變量y是同一個變量，調(diào)用函數(shù)對象f1、f2時參數(shù)變量z的值都是12。具體代碼參見樣例Ex8.7，請大家分析程序輸出結(jié)果。計(jì)算機(jī)學(xué)院李衛(wèi)明8.5 STL常用算法簡介

STL除了提供功能強(qiáng)大、使用方便的各類常用泛型容器類模板外，還提供了上百個經(jīng)典的泛型算法。這些STL算法不以具體容器為參數(shù)，而是通過迭代器間接操作容器，同一個算法可適用于提供同樣概念迭代器的多種類型容器，上節(jié)介紹的copy、copy_if算法就是其中常用的2個算法。STL算法根據(jù)使用效果，主要分為只讀容器元素算法、修改容器元素算法、重排容器元素算法、數(shù)值算法，STL算法具有良好的命名規(guī)則，提高了使用STL算法程序的可讀性。使用STL算法時，需要結(jié)合數(shù)據(jù)結(jié)構(gòu)知識，選用合適的算法。當(dāng)使用特定容器的成員函數(shù)比使用STL算法具有更高效率時，應(yīng)該選用特定容器的成員函數(shù)。

迭代器就是泛型指針，正如鏈表改變時，指向原鏈表結(jié)點(diǎn)的指針可能失效一樣，有些情況下，使用改變?nèi)萜鞯腟TL算法或成員函數(shù)時，可能造成指向容器的原迭代器失效，繼續(xù)使用失效迭代器，很可能造成程序運(yùn)行崩潰。STL算法范圍很廣，為使大家對STL算法有初步認(rèn)識，下面以幾個常用STL算法為例，講述STL算法使用。學(xué)習(xí)較全面的STL算法知識，還需查閱有關(guān)資料或書籍。

使用STL算法，需包含頭文件<algorithm>。計(jì)算機(jī)學(xué)院李衛(wèi)明8.5.1 for_eachSTLfor_each算法針對輸入迭代器區(qū)間內(nèi)每個元素，調(diào)用函數(shù)對象進(jìn)行處理，等效實(shí)現(xiàn)如下:template<classInputIterator,classFunction>Functionfor_each(InputIteratorfirst,InputIteratorlast,Functionfn){while(first!=last){fn(*first);++first;}returnfn;}樣例Ex8.8利用copy_if算法和插入迭代器，將數(shù)組容器內(nèi)奇數(shù)拷貝添加至向量容器V尾部；再利用copy算法和輸出流迭代器，將向量容器內(nèi)所有元素拷貝至輸出流顯示；再利用for_each算法將向量容器內(nèi)所有元素變?yōu)樵档钠椒?；最后，再輸出改變后向量容器?nèi)容。程序中，begin(cont)、end(cont)是C++11新增輔助函數(shù)，返回容器cont的開始位置迭代器、結(jié)束位置迭代器，可同樣適用于一般容器類對象和數(shù)組。具體代碼參見樣例Ex8.8。計(jì)算機(jī)學(xué)院李衛(wèi)明8.5.2 count和count_ifSTLcount算法計(jì)算輸入迭代器區(qū)間內(nèi)與指定值相等的元素個數(shù)，此算法返回值類型來自萃取迭代器成員類型的iterator_traits類模板，基本等價(jià)于整形。等效實(shí)現(xiàn)如下:template<classInputIterator,classT>typenameiterator_traits<InputIterator>::difference_typecount(InputIteratorfirst,InputIteratorlast,constT&val){typenameiterator_traits<InputIterator>::difference_typeret=0;while(first!=last){if(*first==val)++ret;++first;}returnret;}計(jì)算機(jī)學(xué)院李衛(wèi)明STL還提供了與count算法作用類似的泛型count_if算法，計(jì)算輸入迭代器區(qū)間內(nèi)符合要求的元素個數(shù)，以一元謂詞函數(shù)對象作為判斷元素是否符合要求的依據(jù)。等效實(shí)現(xiàn)如下:template<classInputIterator,classUnaryPredicate>typenameiterator_traits<InputIterator>::difference_typecount_if(InputIteratorfirst,InputIteratorlast,UnaryPredicatepred){typenameiterator_traits<InputIterator>::difference_typeret=0;while(first!=last){if(pred(*first))++ret;++first;}returnret;}計(jì)算機(jī)學(xué)院李衛(wèi)明樣例Ex8.9建立了字符串向量容器；利用copy算法和輸出流迭代器，將向量容器內(nèi)所有字符串拷貝至輸出流顯示；再利用count算法計(jì)算向量容器內(nèi)等于"Sea"的字符串個數(shù)，并輸出結(jié)果；再利用count_if算法和lambda函數(shù)計(jì)算向量容器內(nèi)以字母S開始的字符串個數(shù)，并輸出結(jié)果。

具體代碼參見樣例Ex8.9。計(jì)算機(jī)學(xué)院李衛(wèi)明8.5.3 find和find_ifSTLfind算法順序查找輸入迭代器區(qū)間內(nèi)與指定值相等的首個元素，如果未找到，算法返回結(jié)束位置迭代器；如果找到，算法返回首個符合要求的元素所在位置的迭代器，循環(huán)調(diào)用本算法可找出所有符合要求的元素。等效實(shí)現(xiàn)如下:template<classInputIterator,classT>InputIteratorfind(InputIteratorfirst,InputIteratorlast,constT&val){while(first!=last){if(*first==val)returnfirst;++first;}returnlast;}計(jì)算機(jī)學(xué)院李衛(wèi)明STL還提供了與find算法作用類似的泛型find_if算法，查找輸入迭代器區(qū)間內(nèi)符合要求的首個元素，如果未找到，算法返回結(jié)束位置迭代器；如果找到，算法返回首個符合要求元素的迭代器，循環(huán)調(diào)用本算法可找出所有符合要求的元素。查找輸入迭代器區(qū)間內(nèi)符合要求的首個元素，以一元謂詞函數(shù)對象作為判斷元素是否符合查找要求的依據(jù)。等效實(shí)現(xiàn)如下:template<classInputIterator,classUnaryPredicate>InputIteratorfind_if(InputIteratorfirst,InputIteratorlast,UnaryPredicatepred){while(first!=last){if(pred(*first))returnfirst;++first;}returnlast;}計(jì)算機(jī)學(xué)院李衛(wèi)明樣例Ex8.10建立了字符串鏈表容器；利用copy算法和輸出流迭代器，將鏈表容器內(nèi)所有字符串拷貝至輸出流顯示；再循環(huán)利用find算法找出鏈表容器內(nèi)所有值為“Sea”的字符串并輸出；再循環(huán)利用find_if算法和lambda函數(shù)找出鏈表容器內(nèi)所有以字母S開始的字符串并輸出。順便說下，如果容器內(nèi)元素有序，STL提供了更高效率的二分查找算法，有興趣讀者可自己查閱有關(guān)資料。

具體代碼參見樣例Ex8.10。計(jì)算機(jī)學(xué)院李衛(wèi)明8.5.4 sortSTLsort算法對隨機(jī)迭代器指定區(qū)間內(nèi)元素進(jìn)行排序，sort函數(shù)有2個版本，第一個版本依據(jù)元素小于運(yùn)算less<T>排序，第二個版本依據(jù)元素指定比較運(yùn)算comp排序，comp比較算法傳入的2個元素，返回bool形比較結(jié)果。主要容器中，只有數(shù)組、vector、deque容器的迭代器是隨機(jī)迭代器，對于list容器可使用成員函數(shù)sort對容器內(nèi)元素排序，STLsort算法保證平均時間復(fù)雜性為O(n*log(n))。template<classRandomAccessIterator>voidsort(RandomAccessIteratorfirst,RandomAccessIteratorlast);template<classRandomAccessIterator,classCompare>voidsort(RandomAccessIteratorfirst,RandomAccessIteratorlast,Comparecomp);計(jì)算機(jī)學(xué)院李衛(wèi)明樣例Ex8.11建立了自定義對象雙端隊(duì)列容器；保存若干元素后輸出雙端隊(duì)列容器內(nèi)所有對象；將容器內(nèi)對象按缺省遞增順序排列后，再輸出雙端隊(duì)列容器內(nèi)所有對象；再將容器內(nèi)對象按指定遞增順序排列后，再輸出雙端隊(duì)列容器內(nèi)所有對象。

具體代碼參見樣例Ex8.11。計(jì)算機(jī)學(xué)院李衛(wèi)明8.5.5 *transformSTLtransform算法有兩個版本，（版本1）對輸入迭代器區(qū)間內(nèi)每個元素，調(diào)用一元函數(shù)對象進(jìn)行加工處理后，或（版本2）對2個輸入迭代器區(qū)間內(nèi)每對元素，調(diào)用二元函數(shù)對象進(jìn)行加工處理后，將結(jié)果對象輸出至輸出迭代器。等效實(shí)現(xiàn)如下://版本1template<classInputIterator,classOutputIterator,classUnaryOperator>OutputIteratortransform(InputIteratorfirst1,InputIteratorlast1,OutputIteratorresult,UnaryOperatorop){while(first1!=last1){*result++=op(*first1++);}returnresult;}計(jì)算機(jī)學(xué)院李衛(wèi)明//版本2template<classInputIterator1,classInputIterator2,classOutputIterator,classBinaryOperator>OutputIteratortransform(InputIterator1first1,InputIterator1last1,InputIterator2first2,OutputIteratorresult,BinaryOperatorop){while(first1!=last1){*result++=binary_op(*first1++,*first2++);}returnresult;}計(jì)算機(jī)學(xué)院李衛(wèi)明樣例Ex8.12利用copy_if算法和插入迭代器，將數(shù)組容器內(nèi)奇數(shù)拷貝添加至向量容器V尾部；再利用copy算法和輸出流迭代器，將向量容器內(nèi)所有元素拷貝至輸出流顯示；然后，利用transform算法版本1將向量容器內(nèi)每個元素平方后插入至鏈表容器尾部；再利用transform算法版本2將向量容器內(nèi)每個元素和鏈表容器內(nèi)對應(yīng)位置元素相加后輸出替換鏈表容器內(nèi)原元素；最后，輸出改變后鏈表容器內(nèi)容。

具體代碼參見樣例Ex8.12。計(jì)算機(jī)學(xué)院李衛(wèi)明8.5.6 *set_union、set_intersection和set_differenceSTLset_union算法、set_intersection算法、set_difference算法對兩個輸入迭代器區(qū)間指定的遞增排序元素組成的集合進(jìn)行集合并、交、差運(yùn)算，運(yùn)算結(jié)果集元素通過輸出迭代器輸出至相關(guān)容器，STLset_union算法、set_intersection算法、set_difference算法時間