（四）泛型編程

STL是一種泛型編程烘跺，面向?qū)ο蟮木幊剃P(guān)注的是數(shù)據(jù)結(jié)構(gòu)，而泛型編程關(guān)注的是算法。它們的共同點是抽象和創(chuàng)建可重用代碼稀余。

1.迭代器

基于算法的要求，來設(shè)計基本迭代器的特征和基本容器的特征趋翻。容器類模板是將算法獨立于存儲的數(shù)據(jù)類型睛琳，而迭代器是將算法獨立于各種容器類模板，使得某種算法可以使用各容器類的迭代器用相同的方式來處理不同的容器類型踏烙。模板提供了存儲在容器中的數(shù)據(jù)類型的通用表示师骗，使得算法獨立于不同的數(shù)據(jù)類型，而迭代器則提供了遍歷不同容器類數(shù)據(jù)的通用表示讨惩，使得算法獨立于不同容器（比如數(shù)組和鏈表）的具體的數(shù)據(jù)結(jié)構(gòu)辟癌。

對于普通的數(shù)組來說，相應(yīng)類型的數(shù)組指針就可以作為迭代器荐捻，而對于更一般的類對象來說黍少，迭代器也是相應(yīng)的類對象（但是具有與指針相似的性質(zhì)）寡夹，可以對迭代器使用解除引用運算符（解除引用后就是相應(yīng)的存儲的數(shù)據(jù)）以及++運算符等（這些運算符在迭代器類中進行了重載），一般來說厂置，每個容器類都定義了自己的迭代器要出，而且迭代器的類型各不相同，為的是可以實現(xiàn)不同的功能农渊。

為了區(qū)分++運算符的前綴版本和后綴版本患蹂，c++中規(guī)定了將operator++作為前綴版本，將operator++（int）作為后綴版本（括號中的參數(shù)永遠不會用到砸紊，只是后綴版本的一種標(biāo)識传于，因此不必有變量名稱），前綴版本是先加后返回加了之后的值醉顽，而后綴版本是返回加之前的值沼溜，并進行++操作。

為了能夠統(tǒng)一不同的容器類游添，c++規(guī)定迭代器都有起始迭代器和超尾迭代器（超尾標(biāo)記）系草，比如鏈表容器類就要有個沒有數(shù)據(jù)的超尾結(jié)點。begin()和end()就是指向起始位置和超尾位置的迭代器唆涝，我們無需知道超尾是如何實現(xiàn)的找都，也無需知道迭代器是如何實現(xiàn)的，我們僅僅知道迭代器的通用方法即可廊酣。注意能耻，一個類的迭代器，我們僅需要這樣使用亡驰，比如vector<double>::iterator pp;就是一個指向vector<double>類對象的迭代器晓猛，其他模板類也是如此。

2.迭代器的類型

輸入迭代器：這個輸入是對程序而言的凡辱，即從容器中讀取數(shù)據(jù)戒职，解除引用可以讓迭代器得到容器的數(shù)據(jù)。輸入迭代器是單向迭代器透乾，可以遞增洪燥，但不可以倒退。輸入迭代器還是單通行的续徽，也就是說不依賴于前一次遍歷的值也不依賴于本次已經(jīng)遍歷的值蚓曼。

輸出迭代器：表示程序用這個迭代器將內(nèi)容輸出到容器（也是對程序而言的），對其解除引用可以讓程序修改容器值钦扭，而不是讀取纫版。簡而言之，對于單通行客情，只讀算法其弊，可以使用輸入迭代器癞己；而對于單通行，只寫算法梭伐，可以使用輸出迭代器痹雅。

正向迭代器：和輸入迭代器與輸出迭代器相同，正向迭代器只使用++運算符來遍歷容器糊识，正向迭代器可以讀取也可以寫入绩社，如果使用const修飾可以設(shè)置成只能讀取。正向迭代器就是輸入迭代器和輸出迭代器的結(jié)合體赂苗，并且正向迭代器是多次通行的愉耙。

雙向迭代器：可以雙向遍歷容器，比如前一個遞加拌滋，后一個遞減朴沿。

隨機訪問迭代器：也就是可以跳到容器中的任何一個元素，上面的迭代器可以遞加遞減等败砂，但不可以加上一個整型赌渣，也就是隨機訪問。這里的隨機并不是指隨機指向一個元素昌犹，而是我希望指向哪個元素都可以立即指向它坚芜，也就是直接跳到容器的任何一個元素，這就叫作隨機訪問祭隔。隨機訪問迭代器支持上面的雙向迭代器的所有功能货岭，同時還支持重載的加法運算路操，并且迭代器可以進行比較運算疾渴。

3.迭代器的層次結(jié)構(gòu)

高層次的迭代器擁有低層次迭代器的全部功能，輸入和輸出迭代器是最低層次的迭代器屯仗；再是正向迭代器搞坝；再是雙向迭代器；再是隨機訪問迭代器魁袜。一般我們可以直接使用隨機訪問迭代器桩撮，只有在特定的具有安全性要求的場合下我們才使用特定類型的迭代器。隨機訪問迭代器層次下的迭代器沒有[]運算和加法減法等運算峰弹。

4.概念店量，改進和模型

各種迭代器的類型只是一種概念性的描述，并不是目前已經(jīng)實現(xiàn)和存在的鞠呈，比如list<double> a;就是一個雙向迭代器融师，而vector<double> b;就是一個隨機訪問迭代器。

上面講到的迭代器是更多的是一種要求蚁吝，而不是類型旱爆，這種要求就是概念舀射。概念的類似繼承的關(guān)系叫作改進，比如雙向迭代器就是正向迭代器的改進怀伦；概念的具體化叫作模型脆烟。比如指向一個int類型的常規(guī)指針就是一個隨機訪問迭代器的模型。

可以將STL算法用于常規(guī)數(shù)組房待，因為數(shù)組指針可以看成是一種隨機訪問迭代器邢羔。STL提供了一組預(yù)定義的迭代器，比如copy（a,b,c）;函數(shù)就可以將迭代器a桑孩，b的內(nèi)容復(fù)制到c迭代器位置张抄，也就是將一個容器的內(nèi)容復(fù)制到另一個容器的相應(yīng)位置；使用這種copy的方法洼怔，我們可以將容器的內(nèi)容輸出到輸出流中署惯，首先我們要定義一個輸出流的迭代器（或者可以被稱為適配器）钥飞，比如可以包含文件:

#include <iterator>

ostream_iterator<int,char> out_iter(cout,””);//定義輸出流迭代器搬素，輸出類型為int，輸出的字符類型為char碘赖，輸出以空格分隔安岂，使用cout輸出到屏幕

copy(dice.begin(),dice.end(),out_iter);

這種方法可以使容器類的輸入輸出更為方便轻猖。

5.其他有用的迭代器

c++的STL中，迭代器也是一種類模板域那，比如istream_iterator<int,char> a(cout,”;”);這種輸出流迭代器咙边。STL提供了一系列的迭代器來方便對數(shù)據(jù)的處理和輸入輸出等操作。除了istream_iterator和ostream_iterator迭代器之外次员，還有reverse_iterator,back_insert_iterator败许，front_insert_iterator和insert_iterator。

reverse_iterator：對reverse_iteratora執(zhí)行遞增操作導(dǎo)致它遞減淑蔚，這主要是為了簡化已有的函數(shù)（通過這種反轉(zhuǎn)的迭代器可以使遞增輸出的函數(shù)來遞減輸出）市殷。比如vector模板類中有一個rebegin()和rend()的函數(shù)，這兩個函數(shù)分別返回超尾迭代器和指向第一個元素的迭代器刹衫，但是都是reverse_iterator類型的迭代器醋寝。因為對反向迭代器的遞增操作就是遞減，因此可以使用如下的方法來反向顯示容器的內(nèi)容：copy(dice.rebegin(),rend(),out_iter);這樣甚至不必聲明反向迭代器带迟。這里要注意的是對于反向迭代器來說音羞，對它使用解除引用，相當(dāng)于對它遞減1之后再使用解除引用（本質(zhì)是指向它的前一個元素）仓犬，這就是反向迭代器的特殊補償嗅绰。

back_insert_iterator，會將內(nèi)容插入到容器的尾部；front_insert_iterator办陷，會將內(nèi)容插入到容器的頭部貌夕；insert_iterator，可以將內(nèi)容插入到容器的構(gòu)造參數(shù)位置的前面民镜，它有兩個構(gòu)造參數(shù)啡专，一個是容器的名稱，另一個是指向容器的要在前面插入內(nèi)容的元素的迭代器制圈。這三個迭代器都是輸出容器迭代器的概念模型（輸出迭代器就是只寫）们童。使用方法：要為名為dice的vector<double>容器創(chuàng)建一個back_insert_iterator迭代器，可以使用如下的方式鲸鹦，back_insert_iterator<vector<double>? > back_iter(dice);慧库，可以看出，迭代器也是一種模板馋嗜，需要使用具體化的容器模板來對它進行具體化齐板，而構(gòu)造函數(shù)的參數(shù)就是具體的容器對象。這個迭代器模板是在<interator>中定義的葛菇，而一般的迭代器是在相應(yīng)的容器的模板文件中定義的甘磨。必須使用容器類型來進行聲明的原因是迭代器必須使用合適的容器類的方法。

6.容器種類

（1）容器概念：容器是存儲對象的對象眯停。被存儲的對象必須是同一種類型的济舆，可以是內(nèi)置數(shù)據(jù)類型，也可以是OOP意義上的對象莺债。不是任意類型的對象都可以添加到容器中的滋觉，只有那些具有復(fù)制構(gòu)造函數(shù)和可賦值的類對象才可以添加到容器中（也就是復(fù)制構(gòu)造函數(shù)和賦值運算符都是公有的）。

（2）容器要求：復(fù)雜度要求（線性復(fù)雜度齐邦，固定復(fù)雜度）（編譯時間就是在編譯的時候已經(jīng)計算了所有的計算量）椎侠；返回類型要求。

復(fù)制構(gòu)造和復(fù)制賦值以及移動構(gòu)造和移動賦值之間的差別主要是：復(fù)制操作保留源對象侄旬，而移動操作可能修改原對象肺蔚，還可以轉(zhuǎn)讓所有權(quán)而不做任何復(fù)制。通常移動操作的效率要高于復(fù)制操作儡羔。

（3）序列：可以通過添加要求來改進基本的容器概念，序列是一種重要的改進璧诵。序列中的元素具有特定的順序（這里的順序并不是說要由小到大汰蜘，而是具有固定的不變的順序）。

（4）有七種序列容器類型之宿，下面加以介紹族操。

Vector：除序列外，vector還是一個可反轉(zhuǎn)容器，vector模板類是最簡單的序列類型色难，除非其他序列的優(yōu)點能更好滿足程序的要求泼舱，否則我們優(yōu)先選取vector模板類來構(gòu)造對象。

Deque類：在頭文件<deque>中定義枷莉，在頭文件中定義娇昙，表示雙端隊列，類似于vector容器笤妙，但與vector類相比不同點是冒掌，從起始位置執(zhí)行插入和刪除操作的時間復(fù)雜度也是固定時間，而不是像vector類那樣從結(jié)尾處是固定時間蹲盘，從開頭和中間是線性時間股毫。

List類：表示雙向鏈表。與vector的區(qū)別是召衔，所有的節(jié)點的插入與刪除的時間都是固定時間铃诬。而vector類只有在結(jié)尾處是固定時間的插入，但是在開頭和中間是線性時間的插入苍凛。因此氧急，vector強調(diào)的是通過隨機訪問進行快速訪問，而list類（雙向鏈表）強調(diào)的是元素的快速插入和刪除（list雙向鏈表在任何位置的插入和刪除都是固定時間）毫深。list的典型的成員函數(shù)：sort()排序吩坝，splice(iterator pos,list<T,Alloc> x)將鏈表x插入到迭代器pos之前，并且是移動插入（不改變指向x的迭代器）哑蔫，unique()函數(shù)钉寝，就是將連續(xù)的相同的元素合并成一個。需要注意的是非成員的函數(shù)sort闸迷，因為sort函數(shù)需要隨機訪問迭代器嵌纲，而鏈表可以執(zhí)行快速插入的代價就是放棄隨機訪問，因此不能將鏈表應(yīng)用于非成員的sort函數(shù)腥沽。

Foward_list類：每個節(jié)點只連接到下一個節(jié)點逮走，而沒有鏈接到上一個節(jié)點，因此是不可反轉(zhuǎn)的容器今阳。

Queue容器類：隊列师溅，功能更少，甚至不能遍歷容器盾舌。它是一個適配器接口墓臭，功能是讓底層類，默認(rèn)為讓deque展示典型的隊列接口妖谴。也即是隊列只能進行從結(jié)尾加窿锉，從開頭刪，是否非空等操作。

Priority_queue類：也是在queue頭文件中聲明的嗡载。默認(rèn)的底層類是vector窑多，功能與queue差不多，不同點或者說最大特點是最大的元素被移到隊首（比如隊列中的vip用戶要優(yōu)先服務(wù)）洼滚。使用方法：priority_queue<int> a;或者priority_queue<int> b(greater<int>);其中第二個構(gòu)造函數(shù)是通過一個函數(shù)對象來進行初始化埂息，里面的greater<int>()是一個預(yù)定義的函數(shù)對象，greater是一個函數(shù)對象類模板判沟。

Stack：也是一個適配器類耿芹，它給底層類（我的理解是繼承關(guān)系），默認(rèn)為vector類提供了典型的棧接口挪哄。方法有壓入吧秕，彈出，查看棧頂值（不能進行遍歷迹炼，也就是不能查找砸彬，只能查看棧頂這元素），檢查元素數(shù)目和檢查是否為空等斯入。函數(shù)分別是push,pop,top,size,empty等砂碉。

Array類：在頭文件<array>中定義的，它并非STL容器刻两，因為它的長度是固定的增蹭，也因此不能使用push_back和insert等調(diào)整容器大小的操作。但是它定義了operator []和at()函數(shù)磅摹，并且可以將很多標(biāo)準(zhǔn)STL算法用于對象滋迈，比如for_each()和copy()。

6.關(guān)聯(lián)容器和無序關(guān)聯(lián)容器

關(guān)聯(lián)容器是對容器概念的另一個改進户誓，關(guān)聯(lián)容器將值與鍵關(guān)聯(lián)在一起饼灿，可以用鍵來查看值。通常帝美，對于一個容器X來說碍彭，X::value_type通常表示容器中儲存的值的類型，對于關(guān)聯(lián)容器來說悼潭，表達式X::key_type表示容器中的鍵的類型庇忌。關(guān)聯(lián)容器的優(yōu)點在于快速的檢索信息，一般來說女责，關(guān)聯(lián)容器有快速確定數(shù)據(jù)位置的算法漆枚，以便可以快速的插入和檢索信息。關(guān)聯(lián)容器通常是使用某種樹來實現(xiàn)的（也就是數(shù)據(jù)結(jié)構(gòu)中的樹或二叉數(shù)的邏輯形式）抵知。

STL提供有四種典型的關(guān)聯(lián)容器：set，multiset,map,multimap這四種。set和multiset是在頭文件<set>中定義的刷喜，而map和multimap是在頭文件<map>中定義的残制。set是鍵和值的類型相同的一種關(guān)聯(lián)容器，而multiset鍵和值的類型也是相同的掖疮，但是值可以有多個初茶。同樣，map是鍵和值類型不同的關(guān)聯(lián)容器浊闪，值只有一個恼布，multimap值可以有多個，鍵只能有一個搁宾。

set不能存儲多個相同的值折汞，因為它的鍵和值其實是一樣的，而鍵只能有一個盖腿，是唯一的爽待。set的模板構(gòu)造函數(shù)和vector，list相似翩腐，都是用存儲的類型來進行模板具體化鸟款，還有另外一個模板參數(shù)，就是指定用來進行比較的函數(shù)茂卦，默認(rèn)就是less<>模板函數(shù)何什，如set<string,less<> > A;。set的構(gòu)造函數(shù)也可以是兩個迭代器等龙，第一個指向第一個元素处渣，第二個指向超尾元素，set的構(gòu)造的對象會將相同的元素合并成一個而咆，然后會將元素按照特定的規(guī)則排序（默認(rèn)是less<>模板函數(shù)）霍比。

無序關(guān)聯(lián)容器是對容器概念的另一種改進，無序關(guān)聯(lián)容器也將值和鍵連接在一起暴备，并使用鍵來查找值悠瞬。二者的區(qū)別是，關(guān)聯(lián)容器是基于樹結(jié)構(gòu)的涯捻，而無序關(guān)聯(lián)容器是基于數(shù)據(jù)結(jié)構(gòu)哈希表的浅妆。旨在提高添加和刪除元素的速度以及提高查找算法的效率。四種無序關(guān)聯(lián)容器是：unordered_set,unordered_multiset,unordered_map,unordered_multimap障癌。