[計算機(jī)]STL詳解

1、.c+ STL 之list 用法精講 時間 ： 2011-01-05 作者：網(wǎng)絡(luò) 編輯：hawk 點(diǎn)擊： 118 評論 - 這篇文章是關(guān)于C+語言的一個新的擴(kuò)展標(biāo)準(zhǔn)模板庫的（Standard Template Library），也叫STL。 當(dāng)我第一次打算寫一篇關(guān)于STL的文章的時候，我不得不承認(rèn)我當(dāng)時低估了這個話題的深度和廣度。有很多內(nèi)容要含蓋，也有很多詳細(xì)描述STL的書。因此我重新考慮了一下我原來的想法。我為什么要寫這篇文章，又為什么要投稿呢？這會有什麼用呢？有再來一篇關(guān)于STL的文章的必要嗎？ 當(dāng)我翻開Musser and Saini的頁時，我看到了編程時代在我面前消融。我能看到深夜消失

2、了，目標(biāo)軟件工程出現(xiàn)了。我看到了可維護(hù)的代碼。一年過去了，我使用STL寫的軟件仍然很容易維護(hù)。讓人吃驚的是其他人可以沒有我而維護(hù)的很好！ 然而，我也記得在一開始的時候很難弄懂那些技術(shù)術(shù)語。一次，我買了Musser&Saini，每件事都依次出現(xiàn)，但是在那以前我最渴望得到的東西是一些好的例子。 當(dāng)我開始的時候，作為C+一部分的Stroustrup還沒出來，它覆蓋了STL。 因此我想寫一篇關(guān)于一個STL程序員的真實生活的文章可能會有用。如果我手上有一些好的例子的話，特別是象這樣的新題目，我會學(xué)的更快。 另外一件事是STL應(yīng)該很好用。因此，理論上說，我們應(yīng)該可以馬上開始使用STL。 什麼是STL呢？S

3、TL就是Standard Template Library，標(biāo)準(zhǔn)模板庫。這可能是一個歷史上最令人興奮的工具的最無聊的術(shù)語。從根本上說，STL是一些“容器”的集合，這些“容器”有l(wèi)ist,vector,set,map等，STL也是算法和其他一些組件的集合。這里的“容器”和算法的集合指的是世界上很多聰明人很多年的杰作。 STL的目的是標(biāo)準(zhǔn)化組件，這樣你就不用重新開發(fā)它們了。你可以僅僅使用這些現(xiàn)成的組件。STL現(xiàn)在是C+的一部分，因此不用額外安裝什麼。它被內(nèi)建在你的編譯器之內(nèi)。因為STL的list是一個簡單的容器，所以我打算從它開始介紹STL如何使用。如果你懂得了這個概念，其他的就都沒有問題了。另外

4、，list容器是相當(dāng)簡單的，我們會看到這一點(diǎn)。 這篇文章中我們將會看到如何定義和初始化一個list，計算它的元素的數(shù)量，從一個list里查找元素，刪除元素，和一些其他的操作。要作到這些，我們將會討論兩個不同的算法，STL通用算法都是可以操作不止一個容器的，而list的成員函數(shù)是list容器專有的操作。 這是三類主要的STL組件的簡明綱要。STL容器可以保存對象，內(nèi)建對象和類對象。它們會安全的保存對象，并定義我們能夠操作的這個對象的接口。放在蛋架上的雞蛋不會滾到桌上。它們很安全。因此，在STL容器中的對象也很安全。我知道這個比喻聽起來很老土，但是它很正確。 STL算法是標(biāo)準(zhǔn)算法，我們可以把它們應(yīng)

5、用在那些容器中的對象上。這些算法都有很著名的執(zhí)行特性。它們可以給對象排序，刪除它們，給它們記數(shù)，比較，找出特殊的對象，把它們合并到另一個容器中，以及執(zhí)行其他有用的操作。 STL iterator就象是容器中指向?qū)ο蟮闹羔?。STL的算法使用iterator在容器上進(jìn)行操作。Iterator設(shè)置算法的邊界，容器的長度，和其他一些事情。舉個例子，有些iterator僅讓算法讀元素，有一些讓算法寫元素，有一些則兩者都行。 Iterator也決定在容器中處理的方向。 你可以通過調(diào)用容器的成員函數(shù)begin()來得到一個指向一個容器起始位置的iterator。你可以調(diào)用一個容器的 end() 函數(shù)來得到過

6、去的最后一個值（就是處理停在那的那個值）。 這就是STL所有的東西，容器、算法、和允許算法工作在容器中的元素上的iterator。算法以合適、標(biāo)準(zhǔn)的方法操作對象，并可通過iterator得到容器精確的長度。一旦做了這些，它們就在也不會“跑出邊界”。還有一些其他的對這些核心組件類型有功能性增強(qiáng)的組件，例如函數(shù)對象。我們將會看到有關(guān)這些的例子，現(xiàn)在 ，我們先來看一看STL的list。 -定義一個list我們可以象這樣來定義一個STL的list： #include #include int main (void) list Milkshakes; return 0; We now have a li

7、st with four strings in it. The list member function push_back() places an object onto the back of the list. The list member function push_front() puts one on the front. I often push_back() some error messages onto a list, and then push_front() a title on the list so it prints before the error messa

8、ges. 我們現(xiàn)在有個4個字符串在list中。list的成員函數(shù)push_back()把一個對象放到一個list的后面，而 push_front()把對象放到前面。我通常把一些錯誤信息push_back()到一個list中去，然后push_front()一個標(biāo)題到list中，這樣它就會在這個錯誤消息以前打印它了。 -The list member function empty()list的成員函數(shù)empty() 知道一個list是否為空很重要。如果list為空，empty()這個成員函數(shù)返回真。我通常會這樣使用它。通篇程序我都用push_back()來把錯誤消息放到list中去。然后，通過調(diào)用

9、empty() 我就可以說出這個程序是否報告了錯誤。如果我定義了一個list來放信息，一個放警告，一個放嚴(yán)重錯誤，我就可以通過使用empty()輕易的說出到底有那種類型的錯誤發(fā)生了。 我可以整理這些list，然后在打印它們之前，用標(biāo)題來整理它們，或者把它們排序成類。 這是我的意思： /* | Using a list to track and report program messages and status */#include #include #include int main (void) #define OK 0 #define INFO 1 #define WARNING 2 i

10、nt return_code; list InfoMessages; list WarningMessages; / during a program these messages are loaded at various points InfoMessages.push_back(Info: Program started); / do work. WarningMessages.push_back(Warning: No Customer records have been found); / do work. return_code = OK; if (!InfoMessages.em

11、pty() / there were info messages InfoMessages.push_front(Informational Messages:); / . print the info messages list, well see how later return_code = INFO; if (!WarningMessages.empty() / there were warning messages WarningMessages.push_front(Warning Messages:); / . print the warning messages list, w

12、ell see how later return_code = WARNING; / If there were no messages say so. if (InfoMessages.empty() & WarningMessages.empty() cout There were no messages endl; return return_code; 用for循環(huán)來處理list中的元素 我們想要遍歷一個list，比如打印一個中的所有對象來看看list上不同操作的結(jié)果。要一個元素一個元素的遍歷一個list，我們可以這樣做： /* | How to print the contents

13、of a simple STL list. Whew! */ #include #include #include int main (void) list Milkshakes; list:iterator MilkshakeIterator; Milkshakes.push_back(Chocolate); Milkshakes.push_back(Strawberry); Milkshakes.push_front(Lime); Milkshakes.push_front(Vanilla); / print the milkshakes Milkshakes.push_front(The

14、 Milkshake Menu); Milkshakes.push_back(* Thats the end *); fo(MilkshakeIterator=Milkshakes.begin(); MilkshakeIterator!=Milkshakes.end();+MilkshakeIterator) / dereference the iterator to get the element cout *MilkshakeIterator endl; 這個程序定義了一個iterator，MilkshakeIterator。我們把它指向了這個list的第一個元素。這可以調(diào)用Milksha

15、kes.begin()來作到，它會返回一個指向list開頭的iterator。然后我們把它和Milkshakes.end()的返回值來做比較，當(dāng)我們到了那兒的時候就停下來。 容器的end()函數(shù)會返回一個指向容器的最后一個位置的iterator。當(dāng)我們到了那里，就停止操作。我們不能不理容器的end()函數(shù)的返回值。我們僅知道它意味著已經(jīng)處理到了這個容器的末尾，應(yīng)該停止處理了。所有的STL容器都要這樣做。 在上面的例子中，每一次執(zhí)行for循環(huán)，我們就重復(fù)引用iterator來得到我們打印的字符串。 在STL編程中，我們在每個算法中都使用一個或多個iterator。我們使用它們來存取容器中的對象。

16、要存取一個給定的對象，我們把一個iterator指向它，然后間接引用這個iterator。 這個list容器，就象你所想的，它不支持在iterator加一個數(shù)來指向隔一個的對象。就是說，我們不能用Milkshakes.begin()+2來指向list中的第三個對象，因為STL的list是以雙鏈的list來實現(xiàn)的，它不支持隨機(jī)存取。vector和deque(向量和雙端隊列)和一些其他的STL的容器可以支持隨機(jī)存取。 上面的程序打印出了list中的內(nèi)容。任何人讀了它都能馬上明白它是怎麼工作的。它使用標(biāo)準(zhǔn)的iterator和標(biāo)準(zhǔn)的list容器。沒有多少程序員依賴它里面裝的東西， 僅僅是標(biāo)準(zhǔn)的C+。這

17、是一個向前的重要步驟。這個例子使用STL使我們的軟件更加標(biāo)準(zhǔn)。 -用STL的通用算法for_each來處理list中的元素 使用STL list和 iterator，我們要初始化、比較和給iterator增量來遍歷這個容器。STL通用的for_each 算法能夠減輕我們的工作。 /* | How to print a simple STL list MkII */ #include #include #include #include PrintIt (string& StringToPrint) cout StringToPrint endl; int main (void) listFru

18、itAndVegetables; FruitAndVegetables.push_back(carrot); FruitAndVegetables.push_back(pumpkin); FruitAndVegetables.push_back(potato); FruitAndVegetables.push_front(apple); FruitAndVegetables.push_front(pineapple); for_each (FruitAndVegetables.begin(), FruitAndVegetables.end(), PrintIt); 在這個程序中我們使用STL的

19、通用算法for_each()來遍歷一個iterator的范圍，然后調(diào)用PrintIt()來處理每個對象。我們不需要初始化、比較和給iterator增量。for_each()為我們漂亮的完成了這些工作。我們執(zhí)行于對象上的操作被很好的打包在這個函數(shù)以外了，我們不用再做那樣的循環(huán)了，我們的代碼更加清晰了。 for_each算法引用了iterator范圍的概念，這是一個由起始iterator和一個末尾iterator指出的范圍。起始iterator指出操作由哪里開始，末尾iterator指明到哪結(jié)束，但是它不包括在這個范圍內(nèi)。 -用STL的通用算法count()來統(tǒng)計list中的元素個數(shù)。 STL的通

20、用算法count()和count_it()用來給容器中的對象記數(shù)。就象for_each()一樣，count()和count_if() 算法也是在iterator范圍內(nèi)來做的。 讓我們在一個學(xué)生測驗成績的list中來數(shù)一數(shù)滿分的個數(shù)。這是一個整型的List。 /* | How to count objects in an STL list */ #include #include int main (void) list Scores; Scores.push_back(100); Scores.push_back(80); Scores.push_back(45); Scores.push_b

21、ack(75); Scores.push_back(99); Scores.push_back(100); int NumberOf100Scores(0); count (Scores.begin(), Scores.end(), 100, NumberOf100Scores); cout There were NumberOf100Scores scores of 100 endl; The count() algorithm counts the number of objects equal to a certain value. In the above example it che

22、cks each integer object in a list against 100. It increments the variable NumberOf100Scores each time a container object equals 100. The output of the program is count()算法統(tǒng)計等于某個值的對象的個數(shù)。上面的例子它檢查list中的每個整型對象是不是100。每次容器中的對象等于100，它就給NumberOf100Scores加1。這是程序的輸出： There were 2 scores of 100-用STL的通用算法count_

23、if()來統(tǒng)計list中的元素個數(shù) count_if()是count()的一個更有趣的版本。他采用了STL的一個新組件，函數(shù)對象。count_if() 帶一個函數(shù)對象的參數(shù)。函數(shù)對象是一個至少帶有一個operator()方法的類。有些STL算法作為參數(shù)接收函數(shù)對象并調(diào)用這個函數(shù)對象的operator()方法。 函數(shù)對象被約定為STL算法調(diào)用operator時返回true或false。它們根據(jù)這個來判定這個函數(shù)。舉個例子會說的更清楚些。count_if()通過傳遞一個函數(shù)對象來作出比count()更加復(fù)雜的評估以確定一個對象是否應(yīng)該被記數(shù)。在這個例子里我們將數(shù)一數(shù)牙刷的銷售數(shù)量。我們將提交包含四

24、個字符的銷售碼和產(chǎn)品說明的銷售記錄。 /* | Using a function object to help count things */ #include #include #include const string ToothbrushCode(0003); class IsAToothbrush public: bool operator() ( string& SalesRecord ) return SalesRecord.substr(0,4)=ToothbrushCode; ; int main (void) list SalesRecords; SalesRecords.p

25、ush_back(0001 Soap); SalesRecords.push_back(0002 Shampoo); SalesRecords.push_back(0003 Toothbrush); SalesRecords.push_back(0004 Toothpaste); SalesRecords.push_back(0003 Toothbrush); int NumberOfToothbrushes(0); count_if (SalesRecords.begin(), SalesRecords.end(), IsAToothbrush(), NumberOfToothbrushes

26、); cout There were NumberOfToothbrushes toothbrushes sold endl; 這是這個程序的輸出： There were 2 toothbrushes sold（一共賣了兩把牙刷） 這個程序是這樣工作的：定義一個函數(shù)對象類IsAToothbrush，這個類的對象能判斷出賣出的是否是牙刷。如果這個記錄是賣出牙刷的記錄的話，函數(shù)調(diào)用operator()返回一個true，否則返回false。 count_if()算法由第一和第二兩個iterator參數(shù)指出的范圍來處理容器對象。它將對每個 IsAToothbrush()返回true的容器中的對象增加N

27、umberOfToothbrushes的值。 最后的結(jié)果是NumberOfToothbrushes這個變量保存了產(chǎn)品代碼域為0003的記錄的個數(shù)，也就是牙刷的個數(shù)。 注意count_if()的第三個參數(shù)IsAToothbrush()，它是由它的構(gòu)造函數(shù)臨時構(gòu)造的一個對象。你可以把IsAToothbrush類的一個臨時對象傳遞給count_if()函數(shù)。count_if()將對該容器的每個對象調(diào)用這個函數(shù)。 -使用count_if()的一個更加復(fù)雜的函數(shù)對象。 我們可以更進(jìn)一步的研究一下函數(shù)對象。假設(shè)我們需要傳遞更多的信息給一個函數(shù)對象。我們不能通過調(diào)用operator來作到這點(diǎn)，因為必須定義為

28、一個list的中的對象的類型。 然而我們通過為IsAToothbrush指出一個非缺省的構(gòu)造函數(shù)就可以用任何我們所需要的信息來初始化它了。 例如，我們可能需要每個牙刷有一個不定的代碼。我們可以把這個信息加到下面的函數(shù)對象中： /* | Using a more complex function object */ #include #include #include #include class IsAToothbrush public: IsAToothbrush(string& InToothbrushCode) : ToothbrushCode(InToothbrushCode) boo

29、l operator() (string& SalesRecord) return SalesRecord.substr(0,4)=ToothbrushCode; private: string ToothbrushCode; ; int main (void) list SalesRecords; SalesRecords.push_back(0001 Soap); SalesRecords.push_back(0002 Shampoo); SalesRecords.push_back(0003 Toothbrush); SalesRecords.push_back(0004 Toothpa

30、ste); SalesRecords.push_back(0003 Toothbrush); string VariableToothbrushCode(0003); int NumberOfToothbrushes(0); count_if (SalesRecords.begin(), SalesRecords.end(), IsAToothbrush(VariableToothbrushCode), NumberOfToothbrushes); cout There were NumberOfToothbrushes toothbrushes matching code VariableT

31、oothbrushCode sold endl; 程序的輸出是： There were 2 toothbrushes matching code 0003 sold 這個例子演示了如何向函數(shù)對象傳遞信息。你可以定義任意你想要的構(gòu)造函數(shù)，你可以再函數(shù)對象中做任何你想做的處理，都可以合法編譯通過。 你可以看到函數(shù)對象真的擴(kuò)展了基本記數(shù)算法。 到現(xiàn)在為止，我們都學(xué)習(xí)了：定義一個list向list中加入元素如何知道list是否為空如何使用for循環(huán)來遍歷一個list如何使用STL的通用算法for_each來遍歷listlist成員函數(shù)begin() 和 end() 以及它們的意義iterator范圍的

32、概念和一個范圍的最后一個位置實際上并不被處理這一事實如何使用STL通用算法count()和count_if()來對一個list中的對象記數(shù)如何定義一個函數(shù)對象 我選用這些例子來演示list的一般操作。如果你懂了這些基本原理，你就可以毫無疑問的使用STL了建議你作一些練習(xí)。我們現(xiàn)在用一些更加復(fù)雜的操作來擴(kuò)展我們的知識，包括list成員函數(shù)和STL通用算法。 -使用STL通用算法find()在list中查找對象我們?nèi)绾卧趌ist中查找東西呢？STL的通用算法find()和find_if()可以做這些。就象for_each(), count(), count_if() 一樣，這些算法也使用itera

33、tor范圍，這個范圍指出一個list或任意其他容器中的一部分來處理。通常首iterator指著開始的位置，次iterator指著停止處理的地方。由次iterator指出的元素不被處理。 這是find()如何工作： /* | How to find things in an STL list */ #include #include #include int main (void) list Fruit; list:iterator FruitIterator; Fruit.push_back(Apple); Fruit.push_back(Pineapple); Fruit.push_back

34、(Star Apple); FruitIterator = find (Fruit.begin(), Fruit.end(), Pineapple); if (FruitIterator = Fruit.end() cout Fruit not found in list endl; else cout *FruitIterator endl; 輸出是： Pineapple 如果沒有找到指出的對象，就會返回Fruit.end()的值，要是找到了就返回一個指著找到的對象i使用STL通用算法find_if()在list中搜索對象 這是find()的一個更強(qiáng)大的版本。這個例子演示了find_if()

35、，它接收一個函數(shù)對象的參數(shù)作為參數(shù)，并使用它來做更復(fù)雜的評價對象是否和給出的查找條件相付。 假設(shè)我們的list中有一些按年代排列的包含了事件和日期的記錄。我們希望找出發(fā)生在1997年的事件。 /* | How to find things in an STL list MkII */ #include #include #include class EventIsIn1997 public: bool operator () (string& EventRecord) / year field is at position 12 for 4 characters in EventRecord

36、return EventRecord.substr(12,4)=1997; ; int main (void) list Events; / string positions 0123456789012345678901234567890123456789012345 Events.push_back(07 January 1995 Draft plan of house prepared); Events.push_back(07 February 1996 Detailed plan of house prepared); Events.push_back(10 January 1997

37、Client agrees to job); Events.push_back(15 January 1997 Builder starts work on bedroom); Events.push_back(30 April 1997 Builder finishes work); list:iterator EventIterator = find_if (Events.begin(), Events.end(), EventIsIn1997(); / find_if completes the first time EventIsIn1997()() returns true / fo

38、r any object. It returns an iterator to that object which we / can dereference to get the object, or if EventIsIn1997()() never / returned true, find_if returns end() if (EventIterator=Events.end() cout Event not found in list endl; else cout *EventIterator endl; 這是程序的輸出： 10 January 1997 Client agre

39、es to job-使用STL通用算法search在list中找一個序列一些字符在STL容器中很好處理，讓我們看一看一個難處理的字符序列。我們將定義一個list來放字符。 list Characters; 現(xiàn)在我們有了一個字符序列，它不用任何幫助就知道然后管理內(nèi)存。它知道它是從哪里開始、到哪里結(jié)束。它非常有用。我不知道我是否說過以null結(jié)尾的字符數(shù)組。 讓我們加入一些我們喜歡的字符到這個list中： Characters.push_back(0); Characters.push_back(0); Characters.push_back(1); Characters.push_back(2

40、); 我們將得到多少個空字符呢？ int NumberOfNullCharacters(0); count(Characters.begin(), Characters.end(), 0, NumberOfNullCharacters); cout We have NumberOfNullCharacters endl;讓我們找字符1 list:iterator Iter; Iter = find(Characters.begin(), Characters.end(), 1); cout We found *Iter endl; 這個例子演示了STL容器允許你以更標(biāo)準(zhǔn)的方法來處理空字符。現(xiàn)在

41、讓我們用STL的search算法來搜索容器中的兩個null。 就象你猜的一樣，STL通用算法search()用來搜索一個容器，但是是搜索一個元素串，不象find()和find_if() 只搜索單個的元素。 /* | How to use the search algorithm in an STL list */ #include #include #include int main ( void ) list TargetCharacters; list ListOfCharacters; TargetCharacters.push_back(0); TargetCharacters.pus

42、h_back(0); ListOfCharacters.push_back(1); ListOfCharacters.push_back(2); ListOfCharacters.push_back(0); ListOfCharacters.push_back(0); list:iterator PositionOfNulls = search(ListOfCharacters.begin(),ListOfCharacters.end(),TargetCharacters.begin(), TargetCharacters.end(); if (PositionOfNulls!=ListOfC

43、haracters.end() cout We found the nulls endl; The output of the program will be 這是程序的輸出： We found the nulls search算法在一個序列中找另一個序列的第一次出現(xiàn)的位置。在這個例子里我們在ListOfCharacters中找TargetCharacters這個序列的第一次出現(xiàn)，TargetCharacters是包含兩個null字符的序列。 search的參數(shù)是兩個指著查找目標(biāo)的iterator和兩個指著搜索范圍的iterators。因此我們我們在整個的ListOfCharacters的范圍

44、內(nèi)查找TargetCharacters這個list的整個序列。 如果TargetCharacters被發(fā)現(xiàn)，search就會返回一個指著ListOfCharacters中序列匹配的第一個字符的iterator。如果沒有找到匹配項，search返回ListOfCharacters.end()的值。 -使用list的成員函數(shù)sort()排序一個list。 要排序一個list，我們要用list的成員函數(shù)sort()，而不是通用算法sort()。所有我們用過的算法都是通用算法。然而，在STL中有時容器支持它自己對一個特殊算法的實現(xiàn)，這通常是為了提高性能。 在這個例子中，list容器有它自己的sort算

45、法，這是因為通用算法僅能為那些提供隨機(jī)存取里面元素的容器排序，而由于list是作為一個連接的鏈表實現(xiàn)的，它不支持對它里面的元素隨機(jī)存取。所以就需要一個特殊的 sort()成員函數(shù)來排序list。 由于各種原因，容器在性能需要較高或有特殊效果需求的場合支持外部函數(shù)(extra functions)， 這通過利用構(gòu)造函數(shù)的結(jié)構(gòu)特性可以作到。 /* | How to sort an STL list */ #include #include #include PrintIt (string& StringToPrint) cout StringToPrint endl; int main (void

46、) list Staff; list:iterator PeopleIterator; Staff.push_back(John); Staff.push_back(Bill); Staff.push_back(Tony); Staff.push_back(Fidel); Staff.push_back(Nelson); cout The unsorted list endl; for_each(Staff.begin(), Staff.end(), PrintIt ); Staff.sort(); cout The sorted list endl; for_each(Staff.begin

47、(), Staff.end(), PrintIt); 輸出是： The unsorted list John Bill Tony Fidel Nelson The sorted list Bill Fidel John Nelson Tony-用list的成員函數(shù)插入元素到list中 list的成員函數(shù)push_front()和push_back()分別把元素加入到list的前面和后面。你可以使用insert() 把對象插入到list中的任何地方。 insert()可以加入一個對象，一個對象的若干份拷貝，或者一個范圍以內(nèi)的對象。這里是一些插入對象到list中的例子： /* | Using insert to insert elements into a list. */ #include int main (void) list list1; /* | Put integers 0 to 9 in the list */ for (int i = 0; i 10; +i) list1.push_back(i); /* | Insert -1 using the insert member function | Our list will contain -1,0,1,2,3,4,5,6,7,8,9 */ list1.insert(list1.begin(), -1); /*