標(biāo)準(zhǔn)模板庫(kù)(STL)介紹
作者： Scott Field
來(lái)源：
最優(yōu)秀的STL學(xué)習(xí)網(wǎng)站
本文以List容器為例子，介紹了STL的基本內(nèi)容，從容器到迭代器，再到普通函數(shù)，而且例子豐富，通俗易懂。不失為STL的入門(mén)文章，新手不容錯(cuò)過(guò)!
0 前言.
這篇文章是關(guān)于C++語(yǔ)言的一個(gè)新的擴(kuò)展——標(biāo)準(zhǔn)模板庫(kù)的（Standard Template Library），也叫STL。
當(dāng)我第一次打算寫(xiě)一篇關(guān)于STL的文章的時(shí)候，我不得不承認(rèn)我當(dāng)時(shí)低估了這個(gè)話(huà)題的深度和廣度。有很多內(nèi)容要含蓋，也有很多詳細(xì)描述STL的書(shū)。因此我重新考慮了一下我原來(lái)的想法。我為什么要寫(xiě)這篇文章，又為什么要投稿呢？這會(huì)有什麼用呢？有再來(lái)一篇關(guān)于STL的文章的必要嗎？
當(dāng)我翻開(kāi)Musser and Saini的頁(yè)時(shí)，我看到了編程時(shí)代在我面前消融。我能看到深夜消失了， 目標(biāo)軟件工程出現(xiàn)了。我看到了可維護(hù)的代碼。一年過(guò)去了，我使用STL寫(xiě)的軟件仍然很容易維護(hù)。 讓人吃驚的是其他人可以沒(méi)有我而維護(hù)的很好！
然而，我也記得在一開(kāi)始的時(shí)候很難弄懂那些技術(shù)術(shù)語(yǔ)。一次，我買(mǎi)了Musser&Saini，每件事都依次出現(xiàn)，但是在那以前我最渴望得到的東西是一些好的例子。
當(dāng)我開(kāi)始的時(shí)候，作為C++一部分的Stroustrup還沒(méi)出來(lái)，它覆蓋了STL。
因此我想寫(xiě)一篇關(guān)于一個(gè)STL程序員的真實(shí)生活的文章可能會(huì)有用。如果我手上有一些好的例子的話(huà)，特別是象這樣的新題目，我會(huì)學(xué)的更快。
另外一件事是STL應(yīng)該很好用。因此，理論上說(shuō)，我們應(yīng)該可以馬上開(kāi)始使用STL。
什麼是STL呢？STL就是Standard Template Library，標(biāo)準(zhǔn)模板庫(kù)。這可能是一個(gè)歷史上最令人興奮的工具的最無(wú)聊的術(shù)語(yǔ)。從根本上說(shuō)，STL是一些“容器”的集合，這些“容器”有l(wèi)ist, vector,set,map等，STL也是算法和其他一些組件的集合。這里的“容器”和算法的集合指的是世界上很多聰明人很多年的杰作。
STL的目的是標(biāo)準(zhǔn)化組件，這樣你就不用重新開(kāi)發(fā)它們了。你可以?xún)H僅使用這些現(xiàn)成的組件。STL現(xiàn)在是C++的一部分，因此不用額外安裝什麼。它被內(nèi)建在你的編譯器之內(nèi)。因?yàn)镾TL的list是一個(gè)簡(jiǎn)單的容器，所以我打算從它開(kāi)始介紹STL如何使用。如果你懂得了這個(gè)概念，其他的就都沒(méi)有問(wèn)題了。另外， list容器是相當(dāng)簡(jiǎn)單的，我們會(huì)看到這一點(diǎn)。
這篇文章中我們將會(huì)看到如何定義和初始化一個(gè)list，計(jì)算它的元素的數(shù)量，從一個(gè)list里查找元素，刪除元素，和一些其他的操作。要作到這些，我們將會(huì)討論兩個(gè)不同的算法，STL通用算法都是可以操作不止一個(gè)容器的，而list的成員函數(shù)是list容器專(zhuān)有的操作。
這是三類(lèi)主要的STL組件的簡(jiǎn)明綱要。STL容器可以保存對(duì)象，內(nèi)建對(duì)象和類(lèi)對(duì)象。它們會(huì)安全的保存對(duì)象，并定義我們能夠操作的這個(gè)對(duì)象的接口。放在蛋架上的雞蛋不會(huì)滾到桌上。它們很安全。因此，在STL容器中的對(duì)象也很安全。我知道這個(gè)比喻聽(tīng)起來(lái)很老土，但是它很正確。
STL算法是標(biāo)準(zhǔn)算法，我們可以把它們應(yīng)用在那些容器中的對(duì)象上。這些算法都有很著名的執(zhí)行特性。它們可以給對(duì)象排序，刪除它們，給它們記數(shù)，比較，找出特殊的對(duì)象，把它們合并到另一個(gè)容器中，以及執(zhí)行其他有用的操作。
STL iterator就象是容器中指向?qū)ο蟮闹羔槨TL的算法使用iterator在容器上進(jìn)行操作。Iterator設(shè)置算法的邊界 ，容器的長(zhǎng)度，和其他一些事情。舉個(gè)例子，有些iterator僅讓算法讀元素，有一些讓算法寫(xiě)元素，有一些則兩者都行。 Iterator也決定在容器中處理的方向。
你可以通過(guò)調(diào)用容器的成員函數(shù)begin()來(lái)得到一個(gè)指向一個(gè)容器起始位置的iterator。你可以調(diào)用一個(gè)容器的 end() 函數(shù)來(lái)得到過(guò)去的最后一個(gè)值（就是處理停在那的那個(gè)值）。
這就是STL所有的東西，容器、算法、和允許算法工作在容器中的元素上的iterator。 算法以合適、標(biāo)準(zhǔn)的方法操作對(duì)象，并可通過(guò)iterator得到容器精確的長(zhǎng)度。一旦做了這些，它們就在也不會(huì)“跑出邊界”。 還有一些其他的對(duì)這些核心組件類(lèi)型有功能性增強(qiáng)的組件，例如函數(shù)對(duì)象。我們將會(huì)看到有關(guān)這些的例子，現(xiàn)在 ，我們先來(lái)看一看STL的list。
1 定義一個(gè)list
我們可以象這樣來(lái)定義一個(gè)STL的list：
#include <string>
#include <list>
using namespace std;
int main (void)
{
list<string> Milkshakes;
return 0;
}
這就行了，你已經(jīng)定義了一個(gè)list。簡(jiǎn)單嗎？list<string> Milkshakes這句是你聲明了list<string>模板類(lèi) 的一個(gè)實(shí)例，然后就是實(shí)例化這個(gè)類(lèi)的一個(gè)對(duì)象。但是我們別急著做這個(gè)。在這一步其實(shí)你只需要知道你定義了 一個(gè)字符串的list。你需要包含提供STL list類(lèi)的頭文件。我用gcc 2.7.2在我的Linux上編譯這個(gè)測(cè)試程序，例如：
g++ test1.cpp -o test1
注意iostream.h這個(gè)頭文件已經(jīng)被STL的頭文件放棄了。這就是為什么這個(gè)例子中沒(méi)有它的原因。
現(xiàn)在我們有了一個(gè)list，我們可以看實(shí)使用它來(lái)裝東西了。我們將把一個(gè)字符串加到這個(gè)list里。有一個(gè)非常 重要的東西叫做list的值類(lèi)型。值類(lèi)型就是list中的對(duì)象的類(lèi)型。在這個(gè)例子中,這個(gè)list的值類(lèi)型就是字符串,string ， 這是因?yàn)檫@個(gè)list用來(lái)放字符串。
2 使用list的成員函數(shù)push_back和push_front插入一個(gè)元素到list中
#include <string>
#include <list>
using namespace std;
int main (void)
{
list<string> Milkshakes;
Milkshakes.push_back("Chocolate");
Milkshakes.push_back("Strawberry");
Milkshakes.push_front("Lime");
Milkshakes.push_front("Vanilla");
return 0;
}
我們現(xiàn)在有個(gè)4個(gè)字符串在list中。list的成員函數(shù)push_back()把一個(gè)對(duì)象放到一個(gè)list的后面，而 push_front()把對(duì)象放到前面。我通常把一些錯(cuò)誤信息push_back()到一個(gè)list中去，然后push_front()一個(gè)標(biāo)題到list中， 這樣它就會(huì)在這個(gè)錯(cuò)誤消息以前打印它了。
3 list的成員函數(shù)empty()
知道一個(gè)list是否為空很重要。如果list為空，empty()這個(gè)成員函數(shù)返回真。 我通常會(huì)這樣使用它。通篇程序我都用push_back()來(lái)把錯(cuò)誤消息放到list中去。然后，通過(guò)調(diào)用empty() 我就可以說(shuō)出這個(gè)程序是否報(bào)告了錯(cuò)誤。如果我定義了一個(gè)list來(lái)放信息，一個(gè)放警告，一個(gè)放嚴(yán)重錯(cuò)誤， 我就可以通過(guò)使用empty()輕易的說(shuō)出到底有那種類(lèi)型的錯(cuò)誤發(fā)生了。
我可以整理這些list，然后在打印它們之前，用標(biāo)題來(lái)整理它們，或者把它們排序成類(lèi)。
這是我的意思：
/*
|| Using a list to track and report program messages and status
*/
//不要使用#include <iostream.h>
#include <iostream>
#include <string>
#include <list>
using namespace std;
int main (void)
{
#define OK 0
#define INFO 1
#define WARNING 2
int return_code;
list<string> InfoMessages;
list<string> 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.empty()) { // there were info messages
InfoMessages.push_front("Informational Messages:");
// ... print the info messages list, we'll see how later
return_code = INFO;
}
if (!WarningMessages.empty()) { // there were warning messages
WarningMessages.push_front("Warning Messages:");
// ... print the warning messages list, we'll 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;
}
4 用for循環(huán)來(lái)處理list中的元素
我們想要遍歷一個(gè)list，比如打印一個(gè)中的所有對(duì)象來(lái)看看list上不同操作的結(jié)果。要一個(gè)元素一個(gè)元素的遍歷一個(gè)list， 我們可以這樣做：
/*
|| How to print the contents of a simple STL list. Whew!
*/
//不要使用#include <iostream.h>
#include <iostream>
#include <string>
#include <list>
using namespace std;
void main (void)
{
list<string> Milkshakes;
list<string>::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 Milkshake Menu");
Milkshakes.push_back("*** Thats the end ***");
for (MilkshakeIterator=Milkshakes.begin();
MilkshakeIterator!=Milkshakes.end();
++MilkshakeIterator)
{
// dereference the iterator to get the element
cout << *MilkshakeIterator << endl;
}
}
這個(gè)程序定義了一個(gè)iterator，MilkshakeIterator。我們把它指向了這個(gè)list的第一個(gè)元素。 這可以調(diào)用Milkshakes.begin()來(lái)作到，它會(huì)返回一個(gè)指向list開(kāi)頭的iterator。然后我們把它和Milkshakes.end()的 返回值來(lái)做比較，當(dāng)我們到了那兒的時(shí)候就停下來(lái)。
容器的end()函數(shù)會(huì)返回一個(gè)指向容器的最后一個(gè)位置的iterator。當(dāng)我們到了那里，就停止操作。 我們不能不理容器的end()函數(shù)的返回值。我們僅知道它意味著已經(jīng)處理到了這個(gè)容器的末尾，應(yīng)該停止處理了。 所有的STL容器都要這樣做。
在上面的例子中，每一次執(zhí)行for循環(huán)，我們就重復(fù)引用iterator來(lái)得到我們打印的字符串。
在STL編程中，我們?cè)诿總€(gè)算法中都使用一個(gè)或多個(gè)iterator。我們使用它們來(lái)存取容器中的對(duì)象。 要存取一個(gè)給定的對(duì)象，我們把一個(gè)iterator指向它，然后間接引用這個(gè)iterator。
這個(gè)list容器，就象你所想的，它不支持在iterator加一個(gè)數(shù)來(lái)指向隔一個(gè)的對(duì)象。 就是說(shuō)，我們不能用Milkshakes.begin()+2來(lái)指向list中的第三個(gè)對(duì)象，因?yàn)镾TL的list是以雙鏈的list來(lái)實(shí)現(xiàn)的， 它不支持隨機(jī)存取。vector和deque(向量和雙端隊(duì)列)和一些其他的STL的容器可以支持隨機(jī)存取。
上面的程序打印出了list中的內(nèi)容。任何人讀了它都能馬上明白它是怎麼工作的。它使用標(biāo)準(zhǔn)的iterator和標(biāo)準(zhǔn) 的list容器。沒(méi)有多少程序員依賴(lài)它里面裝的東西， 僅僅是標(biāo)準(zhǔn)的C++。這是一個(gè)向前的重要步驟。這個(gè)例子使用STL使我們的軟件更加標(biāo)準(zhǔn)。
5 用STL的通用算法for_each來(lái)處理list中的元素
使用STL list和 iterator，我們要初始化、比較和給iterator增量來(lái)遍歷這個(gè)容器。STL通用的for_each 算法能夠減輕我們的工作。
/*
|| How to print a simple STL list MkII
*/
//不要使用#include <iostream.h>
#include <iostream>
#include <string>
#include <list>
#include <algorithm>
using namespace std;
PrintIt (string& StringToPrint) {
cout << StringToPrint << endl;
}
void main (void) {
list<string> FruitAndVegetables;
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);
}
在這個(gè)程序中我們使用STL的通用算法for_each()來(lái)遍歷一個(gè)iterator的范圍，然后調(diào)用PrintIt()來(lái)處理每個(gè)對(duì)象。 我們不需要初始化、比較和給iterator增量。for_each()為我們漂亮的完成了這些工作。我們執(zhí)行于對(duì)象上的 操作被很好的打包在這個(gè)函數(shù)以外了，我們不用再做那樣的循環(huán)了，我們的代碼更加清晰了。
for_each算法引用了iterator范圍的概念，這是一個(gè)由起始iterator和一個(gè)末尾iterator指出的范圍。 起始iterator指出操作由哪里開(kāi)始，末尾iterator指明到哪結(jié)束，但是它不包括在這個(gè)范圍內(nèi)。用STL的通用算法count()來(lái)統(tǒng)計(jì)list中的元素個(gè)數(shù)。
STL的通用算法count()和count_it()用來(lái)給容器中的對(duì)象記數(shù)。就象for_each()一樣，count()和count_if() 算法也是在iterator范圍內(nèi)來(lái)做的。
讓我們?cè)谝粋€(gè)學(xué)生測(cè)驗(yàn)成績(jī)的list中來(lái)數(shù)一數(shù)滿(mǎn)分的個(gè)數(shù)。這是一個(gè)整型的List。
/*
|| How to count objects in an STL list
*/
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
void main (void)
{
list<int> Scores; Scores.push_back(100); Scores.push_back(80);
Scores.push_back(45); Scores.push_back(75);
Scores.push_back(99); Scores.push_back(100);
int NumberOf100Scores(0);
//此行有錯(cuò)count (Scores.begin(), Scores.end(), 100, NumberOf100Scores);
NumberOf100Scores=count (Scores.begin(), Scores.end(), 100)
cout << "There were " << NumberOf100Scores << " scores of 100" << endl;
}
count()算法統(tǒng)計(jì)等于某個(gè)值的對(duì)象的個(gè)數(shù)。上面的例子它檢查list中的每個(gè)整型對(duì)象是不是100。每次容器中的對(duì)象等于100，它就給NumberOf100Scores加1。這是程序的輸出：
There were 2 scores of 100
zbf批注：count的算法如下
template<class _II, class _Ty> inline
_CNTSIZ(_II) count(_II _F, _II _L, const _Ty& _V)
{_CNTSIZ(_II) _N = 0;
for (; _F != _L; ++_F)
if (*_F == _V)
++_N;
return (_N); }
6 用STL的通用算法count_if()來(lái)統(tǒng)計(jì)list中的元素個(gè)數(shù)
count_if()是count()的一個(gè)更有趣的版本。他采用了STL的一個(gè)新組件，函數(shù)對(duì)象。count_if() 帶一個(gè)函數(shù)對(duì)象的參數(shù)。函數(shù)對(duì)象是一個(gè)至少帶有一個(gè)operator()方法的類(lèi)。有些STL算法作為參數(shù)接收 函數(shù)對(duì)象并調(diào)用這個(gè)函數(shù)對(duì)象的operator()方法。
函數(shù)對(duì)象被約定為STL算法調(diào)用operator時(shí)返回true或false。它們根據(jù)這個(gè)來(lái)判定這個(gè)函數(shù)。舉個(gè)例子會(huì) 說(shuō)的更清楚些。count_if()通過(guò)傳遞一個(gè)函數(shù)對(duì)象來(lái)作出比count()更加復(fù)雜的評(píng)估以確定一個(gè)對(duì)象是否應(yīng)該被 記數(shù)。在這個(gè)例子里我們將數(shù)一數(shù)牙刷的銷(xiāo)售數(shù)量。我們將提交包含四個(gè)字符的銷(xiāo)售碼和產(chǎn)品說(shuō)明的銷(xiāo)售記錄。
/*
|| Using a function object to help count things
*/
#include <string>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
const string ToothbrushCode("0003");
class IsAToothbrush
{
public:
bool operator() ( string& SalesRecord )
{
return SalesRecord.substr(0,4)==ToothbrushCode;
}
};
void main (void)
{
list<string> SalesRecords;
SalesRecords.push_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);
NumberOfToothbrushes=count_if (SalesRecords.begin(), SalesRecords.end(),
IsAToothbrush());
cout << "There were "
<< NumberOfToothbrushes
<< " toothbrushes sold" << endl;
}
這是這個(gè)程序的輸出：
There were 2 toothbrushes sold
這個(gè)程序是這樣工作的：定義一個(gè)函數(shù)對(duì)象類(lèi)IsAToothbrush，這個(gè)類(lèi)的對(duì)象能判斷出賣(mài)出的是否是牙刷 。如果這個(gè)記錄是賣(mài)出牙刷的記錄的話(huà)，函數(shù)調(diào)用operator()返回一個(gè)true，否則返回false。
count_if()算法由第一和第二兩個(gè)iterator參數(shù)指出的范圍來(lái)處理容器對(duì)象。它將對(duì)每個(gè) IsAToothbrush?()返回true的容器中的對(duì)象增加NumberOfToothbrushes的值。
最后的結(jié)果是NumberOfToothbrushes這個(gè)變量保存了產(chǎn)品代碼域?yàn)?0003"的記錄的個(gè)數(shù)，也就是牙刷的個(gè)數(shù)。
注意count_if()的第三個(gè)參數(shù)IsAToothbrush()，它是由它的構(gòu)造函數(shù)臨時(shí)構(gòu)造的一個(gè)對(duì)象。你可以把IsAToothbrush類(lèi)的一個(gè)臨時(shí)對(duì)象 傳遞給count_if()函數(shù)。count_if()將對(duì)該容器的每個(gè)對(duì)象調(diào)用這個(gè)函數(shù)。
7 使用count_if()的一個(gè)更加復(fù)雜的函數(shù)對(duì)象。
我們可以更進(jìn)一步的研究一下函數(shù)對(duì)象。假設(shè)我們需要傳遞更多的信息給一個(gè)函數(shù)對(duì)象。我們不能通過(guò) 調(diào)用operator來(lái)作到這點(diǎn)，因?yàn)楸仨毝x為一個(gè)list的中的對(duì)象的類(lèi)型。 然而我們通過(guò)為IsAToothbrush指出一個(gè)非缺省的構(gòu)造函數(shù)就可以用任何我們所需要的信息來(lái)初始化它了。 例如，我們可能需要每個(gè)牙刷有一個(gè)不定的代碼。我們可以把這個(gè)信息加到下面的函數(shù)對(duì)象中：
/*
|| Using a more complex function object
*/
#include <iostream>
#include <string>
#include <list>
#include <algorithm>
using namespace std;
class IsAToothbrush
{
public:
IsAToothbrush(string& InToothbrushCode) :
ToothbrushCode(InToothbrushCode) {}
bool operator() (string& SalesRecord)
{
return SalesRecord.substr(0,4)==ToothbrushCode;
}
private:
string ToothbrushCode;
};
void main (void)
{
list<string> SalesRecords;
SalesRecords.push_back("0001 Soap");
SalesRecords.push_back("0002 Shampoo");
SalesRecords.push_back("0003 Toothbrush");
SalesRecords.push_back("0004 Toothpaste");
SalesRecords.push_back("0003 Toothbrush");
string VariableToothbrushCode("0003");
int NumberOfToothbrushes(0);
NumberOfToothbrushes=count_if (SalesRecords.begin(), SalesRecords.end(),
IsAToothbrush(VariableToothbrushCode));
cout << "There were "
<< NumberOfToothbrushes
<< " toothbrushes matching code "
<< VariableToothbrushCode
<< " sold"
<< endl;
}
程序的輸出是：
There were 2 toothbrushes matching code 0003 sold
這個(gè)例子演示了如何向函數(shù)對(duì)象傳遞信息。你可以定義任意你想要的構(gòu)造函數(shù)，你可以在函數(shù)對(duì)象中做任何你 想做的處理，都可以合法編譯通過(guò)。
你可以看到函數(shù)對(duì)象真的擴(kuò)展了基本記數(shù)算法。
到現(xiàn)在為止，我們都學(xué)習(xí)了：
- 定義一個(gè)list
- 向list中加入元素
- 如何知道list是否為空
- 如何使用for循環(huán)來(lái)遍歷一個(gè)list
- 如何使用STL的通用算法for_each來(lái)遍歷list
- list成員函數(shù)begin() 和 end() 以及它們的意義
- iterator范圍的概念和一個(gè)范圍的最后一個(gè)位置實(shí)際上并不被處理這一事實(shí)
- 如何使用STL通用算法count()和count_if()來(lái)對(duì)一個(gè)list中的對(duì)象記數(shù)
- 如何定義一個(gè)函數(shù)對(duì)象
我選用這些例子來(lái)演示list的一般操作。如果你懂了這些基本原理，你就可以毫無(wú)疑問(wèn)的使用STL了 建議你作一些練習(xí)。我們現(xiàn)在用一些更加復(fù)雜的操作來(lái)擴(kuò)展我們的知識(shí)，包括list成員函數(shù)和STL通用算法。
8 使用STL通用算法find()在list中查找對(duì)象
我們?nèi)绾卧趌ist中查找東西呢？STL的通用算法find()和find_if()可以做這些。 就象for_each(), count(), count_if() 一樣，這些算法也使用iterator范圍，這個(gè)范圍指出一個(gè)list或任意 其他容器中的一部分來(lái)處理。通常首iterator指著開(kāi)始的位置，次iterator指著停止處理的地方。 由次iterator指出的元素不被處理。這是find()如何工作：
/*
|| How to find things in an STL list
*/
#include <string>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
void main (void) {
list<string> Fruit;
list<string>::iterator FruitIterator;
Fruit.push_back("Apple");
Fruit.push_back("Pineapple");
Fruit.push_back("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
如果沒(méi)有找到指出的對(duì)象，就會(huì)返回Fruit.end()的值，要是找到了就返回一個(gè)指著找到的對(duì)象的iterator
9 使用STL通用算法find_if()在list中搜索對(duì)象
這是find()的一個(gè)更強(qiáng)大的版本。這個(gè)例子演示了find_if()，它接收一個(gè)函數(shù)對(duì)象的參數(shù)作為參數(shù)， 并使用它來(lái)做更復(fù)雜的評(píng)價(jià)對(duì)象是否和給出的查找條件相付。假設(shè)我們的list中有一些按年代排列的包含了事件和日期的記錄。我們希望找出發(fā)生在1997年的事件。
/*
|| How to find things in an STL list MkII
*/
#include <string>
#include <list>
#include <algorithm>
class EventIsIn1997 {
public:
bool operator () (string& EventRecord) {
// year field is at position 12 for 4 characters in EventRecord
return EventRecord.substr(12,4)=="1997";
}
};
void main (void) {
list<string> 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 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<string>::iterator EventIterator = find_if (Events.begin(), Events.end(), EventIsIn1997());
// find_if completes the first time EventIsIn1997()() returns true
// for 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 agrees to job
10 使用STL通用算法search在list中找一個(gè)序列
一些字符在STL容器中很好處理，讓我們看一看一個(gè)難處理的字符序列。我們將定義一個(gè)list來(lái)放字符。
list<char> Characters;
現(xiàn)在我們有了一個(gè)字符序列，它不用任何幫助就知道然后管理內(nèi)存。它知道它是從哪里開(kāi)始、到哪里結(jié)束。 它非常有用。我不知道我是否說(shuō)過(guò)以null結(jié)尾的字符數(shù)組。
讓我們加入一些我們喜歡的字符到這個(gè)list中：
Characters.push_back('\0');
Characters.push_back('\0');
Characters.push_back('1');
Characters.push_back('2');
我們將得到多少個(gè)空字符呢？
int NumberOfNullCharacters(0);
count(Characters.begin(), Characters.end(), '\0', NumberOfNullCharacters);
cout << "We have " << NumberOfNullCharacters << endl;
讓我們找字符'1'
list<char>::iterator Iter;
Iter = find(Characters.begin(), Characters.end(), '1');
cout << "We found " << *Iter << endl;
這個(gè)例子演示了STL容器允許你以更標(biāo)準(zhǔn)的方法來(lái)處理空字符。現(xiàn)在讓我們用STL的search算法來(lái)搜索容器中 的兩個(gè)null。就象你猜的一樣，STL通用算法search()用來(lái)搜索一個(gè)容器，但是是搜索一個(gè)元素串，不象find()和find_if() 只搜索單個(gè)的元素。
/*
|| How to use the search algorithm in an STL list
*/
#include <string>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
void main ( void){
list<char> TargetCharacters;
list<char> ListOfCharacters;
TargetCharacters.push_back('\0');
TargetCharacters.push_back('\0');
ListOfCharacters.push_back('1');
ListOfCharacters.push_back('2');
ListOfCharacters.push_back('\0');
ListOfCharacters.push_back('\0');
list<char>::iterator PositionOfNulls = search(ListOfCharacters.begin(), ListOfCharacters.end(), TargetCharacters.begin(), TargetCharacters.end());
if (PositionOfNulls!=ListOfCharacters.end())
cout << "We found the nulls" << endl;
}
The output of the program will be 這是程序的輸出：
We found the nulls
search算法在一個(gè)序列中找另一個(gè)序列的第一次出現(xiàn)的位置。在這個(gè)例子里我們?cè)贚istOfCharacters中 找TargetCharacters這個(gè)序列的第一次出現(xiàn)，TargetCharacters是包含兩個(gè)null字符的序列。 search的參數(shù)是兩個(gè)指著查找目標(biāo)的iterator和兩個(gè)指著搜索范圍的iterators。 因此我們我們?cè)谡麄€(gè)的ListOfCharacters的范圍內(nèi)查找TargetCharacters這個(gè)list的整個(gè)序列。
如果TargetCharacters被發(fā)現(xiàn)，search就會(huì)返回一個(gè)指著ListOfCharacters中序列匹配的第一個(gè) 字符的iterator。如果沒(méi)有找到匹配項(xiàng)，search返回ListOfCharacters.end()的值。
11 使用list的成員函數(shù)sort()排序一個(gè)list。
要排序一個(gè)list，我們要用list的成員函數(shù)sort()，而不是通用算法sort()。所有我們用過(guò)的算法都是 通用算法。然而，在STL中有時(shí)容器支持它自己對(duì)一個(gè)特殊算法的實(shí)現(xiàn)，這通常是為了提高性能。
在這個(gè)例子中，list容器有它自己的sort算法，這是因?yàn)橥ㄓ盟惴▋H能為那些提供隨機(jī)存取里面元素 的容器排序，而由于list是作為一個(gè)連接的鏈表實(shí)現(xiàn)的，它不支持對(duì)它里面的元素隨機(jī)存取。所以就需要一個(gè)特殊的 sort()成員函數(shù)來(lái)排序list。
由于各種原因，容器在性能需要較高或有特殊效果需求的場(chǎng)合支持外部函數(shù)(extra functions)， 這通過(guò)利用構(gòu)造函數(shù)的結(jié)構(gòu)特性可以作到。
/*
|| How to sort an STL list
*/
#include <string>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
PrintIt (string& StringToPrint) { cout << StringToPrint << endl;}
void main (void) {
list<string> Staff;
list<string>::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(), Staff.end(), PrintIt);
}
輸出是：
The unsorted list
John
Bill
Tony
Fidel
Nelson
The sorted list
Bill
Fidel
John
Nelson
Tony
12 用list的成員函數(shù)插入元素到list中
list的成員函數(shù)push_front()和push_back()分別把元素加入到list的前面和后面。你可以使用insert() 把對(duì)象插入到list中的任何地方。
insert()可以加入一個(gè)對(duì)象，一個(gè)對(duì)象的若干份拷貝，或者一個(gè)范圍以?xún)?nèi)的對(duì)象。這里是一些 插入對(duì)象到list中的例子：
/*
|| Using insert to insert elements into a list.
*/
#include <string>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
void main (void) {
list<int> list1;
list<int> ::iterator List1Itetator;
/*
|| 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);
/*
|| Insert an element at the end using insert
|| Our list will contain -1,0,1,2,3,4,5,6,7,8,9,10
*/
list1.insert(list1.end(), 10);
/*
|| Inserting a range from another container
|| Our list will contain -1,0,1,2,3,4,5,6,7,8,9,10,11,12
*/
int IntArray[2] = {11,12};
list1.insert(list1.end(), &IntArray[0], &IntArray[2]);
/*
|| As an exercise put the code in here to print the lists!
|| Hint: use PrintIt and accept an interger
*/
//output
for(List1Itetator=list1.begin();List1Itetator!=list1.end();
List1Itetator++)
{
cout<<*List1Itetator<<endl;
}
}
注意，insert()函數(shù)把一個(gè)或若干個(gè)元素插入到你指出的iterator的位置。你的元素將出現(xiàn)在 iterator指出的位置以前。
13 List 構(gòu)造函數(shù)
我們已經(jīng)象這樣定義了list：
list<int> Fred;
你也可以象這樣定義一個(gè)list，并同時(shí)初始化它的元素：
// define a list of 10 elements and initialise them all to 0
list<int> Fred(10, 0);
// list now contains 0,0,0,0,0,0,0,0,0,0
或者你可以定義一個(gè)list并用另一個(gè)STL容器的一個(gè)范圍來(lái)初始化它，這個(gè)STL容器不一定是一個(gè)list， 僅僅需要是元素類(lèi)型相同的的容器就可以。
vector<int> Harry;
Harry.push_back(1);
Harry.push_back(2);
#
// define a list and initialise it with the elements in Harry
list<int> Bill(Harry.begin(), Harry.end());
// Bill now contains 1,2
14 使用list成員函數(shù)從list中刪除元素
list成員函數(shù)pop_front()刪掉list中的第一個(gè)元素，pop_back()刪掉最后一個(gè)元素。 函數(shù)erase()刪掉由一個(gè)iterator指出的元素。還有另一個(gè)erase()函數(shù)可以刪掉一個(gè)范圍的元素。
/*
|| Erasing objects from a list
*/
#include <list>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
void main (void) {
list<int> list1; // define a list of integers
/*
|| Put some numbers in the list
|| It now contains 0,1,2,3,4,5,6,7,8,9
*/
for (int i = 0; i < 10; ++i) list1.push_back(i);
list1.pop_front(); // erase the first element 0
list1.pop_back(); // erase the last element 9
list1.erase(list1.begin()); // erase the first element (1) using an iterator
list1.erase(list1.begin(), list1.end()); // erase all the remaining elements
cout << "list contains " << list1.size() << " elements" << endl;
}
輸出是：
list contains 0 elements
15 用list成員函數(shù)remove()從list中刪除元素。
list的成員函數(shù)remove()用來(lái)從list中刪除元素。
/*
|| Using the list member function remove to remove elements
*/
#include <string>
#include <list>
#include <algorithm>
#include<iostream>
using namespace std;
PrintIt (const string& StringToPrint) {
cout << StringToPrint << endl;
}
void main (void) {
list<string> Birds;
Birds.push_back("cockatoo");
Birds.push_back("galah");
Birds.push_back("cockatoo");
Birds.push_back("rosella");
Birds.push_back("corella");
cout << "Original list with cockatoos" << endl;
for_each(Birds.begin(), Birds.end(), PrintIt);
Birds.remove("cockatoo");
cout << "Now no cockatoos" << endl;
for_each(Birds.begin(), Birds.end(), PrintIt);
}
輸出是：
Original list with cockatoos
cockatoo
galah
cockatoo
rosella
corella
Now no cockatoos
galah
rosella
corella
16 使用STL通用算法remove()從list中刪除元素
通用算法remove()使用和list的成員函數(shù)不同的方式工作。一般情況下不改變?nèi)萜鞯拇笮 ?
/*
|| Using the generic remove algorithm to remove list elements
*/
#include <string>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
PrintIt(string& AString) { cout << AString << endl; }
void main (void) {
list<string> Birds;
list<string>::iterator NewEnd;
Birds.push_back("cockatoo");
Birds.push_back("galah");
Birds.push_back("cockatoo");
Birds.push_back("rosella");
Birds.push_back("king parrot");
cout << "Original list" << endl;
for_each(Birds.begin(), Birds.end(), PrintIt);
NewEnd = remove(Birds.begin(), Birds.end(), "cockatoo");
cout << endl << "List according to new past the end iterator" << endl;
for_each(Birds.begin(), NewEnd, PrintIt);
cout << endl << "Original list now. Care required!" << endl;
for_each(Birds.begin(), Birds.end(), PrintIt);//zbf.不能用此種方法打印
}
輸出結(jié)果將為：
Original list
cockatoo
galah
cockatoo
rosella
king parrot
List according to new past the end iterator
galah
rosella
king parrot
Original list now. Care required!
galah
rosella
king parrot
rosella
king parrot
通用remove()算法返回一個(gè)指向新的list的結(jié)尾的iterator。從開(kāi)始到這個(gè)新的結(jié)尾（不含新結(jié)尾元素）的范圍 包含了remove后剩下所有元素。你可以用list成員函數(shù)erase函數(shù)來(lái)刪除從新結(jié)尾到老結(jié)尾的部分。
17 使用STL通用算法stable_partition()和list成員函數(shù)splice()來(lái)劃分一個(gè)list
我們將完成一個(gè)稍微有點(diǎn)復(fù)雜的例子。它演示STL通用算法stable_partition()算法和一個(gè)list成員函數(shù) splice()的變化。注意函數(shù)對(duì)象的使用和沒(méi)有使用循環(huán)。 通過(guò)簡(jiǎn)單的語(yǔ)句調(diào)用STL算法來(lái)控制。
stable_partition()是一個(gè)有趣的函數(shù)。它重新排列元素，使得滿(mǎn)足指定條件的元素排在 不滿(mǎn)足條件的元素前面。它維持著兩組元素的順序關(guān)系。
splice 把另一個(gè)list中的元素結(jié)合到一個(gè)list中。它從源list中刪除元素。
在這個(gè)例子中，我們想從命令行接收一些標(biāo)志和四個(gè)文件名。文件名必須’按順序出現(xiàn)。通過(guò)使用stable_partition() 我們可以接收和文件名混為任何位置的標(biāo)志，并且不打亂文件名的順序就把它們放到一起。
由于記數(shù)和查找算法都很易用，我們調(diào)用這些算法來(lái)決定哪個(gè)標(biāo)志被設(shè)置而哪個(gè)標(biāo)志未被設(shè)置。 我發(fā)現(xiàn)容器用來(lái)管理少量的象這樣的動(dòng)態(tài)數(shù)據(jù)。
/*
|| Using the STL stable_partition algorithm
|| Takes any number of flags on the command line and
|| four filenames in order.
*/
#include <string>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
PrintIt ( string& AString { cout << AString << endl; }
class IsAFlag {
public:
bool operator () (string& PossibleFlag) {
return PossibleFlag.substr(0,1)=="-";
}
};
class IsAFileName {
public:
bool operator () (string& StringToCheck) {
return !IsAFlag()(StringToCheck);
}
};
class IsHelpFlag {
public:
bool operator () (string& PossibleHelpFlag) {
return PossibleHelpFlag=="-h";
}
};
void main (int argc, char *argv[]) {
list<string> CmdLineParameters; // the command line parameters
list<string>::iterator StartOfFiles; // start of filenames
list<string> Flags; // list of flags
list<string> FileNames; // list of filenames
for (int i = 0; i < argc; ++i) CmdLineParameters.push_back(argv[i]);
CmdLineParameters.pop_front(); // we don't want the program name
// make sure we have the four mandatory file names
int NumberOfFiles(0);
count_if(CmdLineParameters.begin(), CmdLineParameters.end(), IsAFileName(), NumberOfFiles);
cout << "The " << (NumberOfFiles == 4 ? "correct " : "wrong ") << "number (" << NumberOfFiles << ") of file names were specified" << endl;
// move any flags to the beginning
StartOfFiles = stable_partition(CmdLineParameters.begin(), CmdLineParameters.end(), IsAFlag());
cout << "Command line parameters after stable partition" << endl;
for_each(CmdLineParameters.begin(), CmdLineParameters.end(), PrintIt);
// Splice any flags from the original CmdLineParameters list into Flags list.
Flags.splice(Flags.begin(), CmdLineParameters, CmdLineParameters.begin(), StartOfFiles);
if (!Flags.empty()) {
cout << "Flags specified were:" << endl;
for_each(Flags.begin(), Flags.end(), PrintIt);
}
else {
cout << "No flags were specified" << endl;
}
// parameters list now contains only filenames. Splice them into FileNames list.
FileNames.splice(FileNames.begin(), CmdLineParameters, CmdLineParameters.begin(), CmdLineParameters.end());
if (!FileNames.empty()) {
cout << "Files specified (in order) were:" << endl;
for_each(FileNames.begin(), FileNames.end(), PrintIt);
}
else {
cout << "No files were specified" << endl;
}
// check if the help flag was specified
if (find_if(Flags.begin(), Flags.end(), IsHelpFlag())!=Flags.end()) {
cout << "The help flag was specified" << endl;
}
// open the files and do whatever you do
}
給出這樣的命令行：
//zbf:在vc6IDE下可以模擬出一樣的結(jié)果
test17 -w linux -o is -w great
輸出是：
The wrong number (3) of file names were specified
Command line parameters after stable partition
-w
-o
-w
linux
is
great
Flags specified were:
-w
-o
-w
Files specified (in order) were:
linux
is
great
18 結(jié)論
我們僅僅簡(jiǎn)單的談了談你可以用list做的事情。我們沒(méi)有說(shuō)明一個(gè)對(duì)象的用戶(hù)定義類(lèi)，雖然這個(gè)不難。
如果你懂了剛才說(shuō)的這些算法背后的概念，那么你使用剩下的那些算法就應(yīng)該沒(méi)有問(wèn)題了。使用STL 最重要的東西就是得到基本理論。
STL的關(guān)鍵實(shí)際上是iterator。STL算法作為參數(shù)使用iterator，他們指出一個(gè)范圍，有時(shí)是一個(gè)范圍， 有時(shí)是兩個(gè)。STL容器支持iterator，這就是為什么我們說(shuō) list<int>::iterator, 或 list<char>::iterator, 或 list<string>::iterator.
iterator有很好的定義繼承性。它們非常有用。某些iterator僅支持對(duì)一個(gè)容器只讀，某些 僅支持寫(xiě)，還有一些僅能向前指，有一些是雙向的。有一些iterator支持對(duì)一個(gè)容器的隨機(jī)存取。
STL算法需要某個(gè)iterator作為“動(dòng)力” 如果一個(gè)容器不提供iterator作為“動(dòng)力”，那么這個(gè)算法將無(wú)法編譯。例如，list容器僅提供雙向的 iterator。通常的sort()算法需要隨機(jī)存取的iterator。這就是為什么我們需要一個(gè)特別的list成員函數(shù)sort()。
要合適的實(shí)際使用STL，你需要仔細(xì)學(xué)習(xí)各種不同的iterator。你需要知道每種容器都支持那類(lèi)iterator。 你還需要知道算法需要那種iterator，你當(dāng)然也需要懂得你可以有那種iterator。
在field中使用STL
去年，我曾用STL寫(xiě)過(guò)幾個(gè)商業(yè)程序。它在很多方面減少了我的工作量，也排除了很多邏輯錯(cuò)誤。
最大的一個(gè)程序有大約5000行。可能最驚人的事情就是它的速度。它讀入并處理一個(gè)1-2兆的 報(bào)告文件僅花大約20秒。我是在linux上用gcc2.7.2開(kāi)發(fā)的，現(xiàn)在運(yùn)行在HP-UX機(jī)器上。 它一共用了大約50和函數(shù)對(duì)象和很多容器，這些容器的大小從小list到一個(gè)有14,000個(gè)元素的map都有。
一個(gè)程序中的函數(shù)對(duì)象是處于一個(gè)繼承樹(shù)中，頂層的函數(shù)對(duì)象調(diào)用低層的函數(shù)對(duì)象。我大量的使用STL算法for_each() ,find(),find_if(),count()和count_if()，我盡量減少使用程序內(nèi)部的函數(shù)，而使用STL的算法調(diào)用。
STL傾向于自動(dòng)的把代碼組織成清晰的控制和支持模塊。通過(guò)小心使用函數(shù)對(duì)象并給它們 起有意義的名字，我使它們?cè)谖业能浖目刂屏髦辛鲃?dòng)。
還有很多關(guān)于STL編程要知道的東西，我希望你通過(guò)這些例子可以愉快的工作。
參考數(shù)目中的兩本書(shū)在web上都有勘誤表，你可以自己改正它們。
Stroustrup在每一章后面都有個(gè)建議欄，特別是對(duì)于出學(xué)者有用。正本書(shū)比早期的版本更加健談。 它也更大了。書(shū)店里還可以找到其他幾本關(guān)于STL的教科書(shū)。去看看，也許你能發(fā)現(xiàn)什么。
19 參考書(shū)目：
- The STL Tutorial and Reference Guide, David Musser and Atul Saini. Addison Wesley 1996. 《STL教程和參考手冊(cè)》
- The C++ Programming Language 3e, Bjarne Stroustrup. Addison Wesley 1997