STL 簡介，標準模板庫[2]

/*接上篇：   

   我選用這些例子來演示list的一般操作。如果你懂了這些基本原理，你就可以毫無疑問的使用STL了, 建議你作一些練習。我們現在用一些更加復雜的操作來擴展我們的知識，包括list成員函數和STL通用算法。 
*/

--------------------------------------------------------------------------------

使用STL通用算法find()在list中查找對象
    我們如何在list中查找東西呢？STL的通用算法find()和find_if()可以做這些。 就象for_each(), count(), count_if() 一樣，這些算法也使用iterator范圍，這個范圍指出一個list或任意 其他容器中的一部分來處理。通常首iterator指著開始的位置，次iterator指著停止處理的地方。 由次iterator指出的元素不被處理。 
這是find()如何工作： 

/* 
|| How to find things in an STL list 
*/ 
#include <string> 
#include <list> 
#include <algorithm> 
# 
int 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 

   如果沒有找到指出的對象，就會返回Fruit.end()的值，要是找到了就返回一個指著找到的對象的iterator 



--------------------------------------------------------------------------------

使用STL通用算法find_if()在list中搜索對象
    這是find()的一個更強大的版本。這個例子演示了find_if()，它接收一個函數對象的參數作為參數， 并使用它來做更復雜的評價對象是否和給出的查找條件相付。 
    假設我們的list中有一些按年代排列的包含了事件和日期的記錄。我們希望找出發生在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";
  }  
};
#
int 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

--------------------------------------------------------------------------------

   使用STL通用算法search在list中找一個序列
一些字符在STL容器中很好處理，讓我們看一看一個難處理的字符序列。我們將定義一個list來放字符。 
  list<char> Characters; 

       現在我們有了一個字符序列，它不用任何幫助就知道然后管理內存。它知道它是從哪里開始、到哪里結束。 它非常有用。我不知道我是否說過以null結尾的字符數組。 

讓我們加入一些我們喜歡的字符到這個list中： 

  Characters.push_back(´\0´); 
  Characters.push_back(´\0´); 
  Characters.push_back(´1´); 
  Characters.push_back(´2´); 

我們將得到多少個空字符呢？ 

 
  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;
    這個例子演示了STL容器允許你以更標準的方法來處理空字符?，F在讓我們用STL的search算法來搜索容器中 的兩個null。 
    就象你猜的一樣，STL通用算法search()用來搜索一個容器，但是是搜索一個元素串，不象find()和find_if() 只搜索單個的元素。 

 
/*
|| How to use the search algorithm in an STL list
*/
#include <string>
#include <list>
#include <algorithm>
#
int 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算法在一個序列中找另一個序列的第一次出現的位置。在這個例子里我們在ListOfCharacters中 找TargetCharacters這個序列的第一次出現，TargetCharacters是包含兩個null字符的序列。 
    search的參數是兩個指著查找目標的iterator和兩個指著搜索范圍的iterators。 因此我們我們在整個的ListOfCharacters的范圍內查找TargetCharacters這個list的整個序列。 

    如果TargetCharacters被發現，search就會返回一個指著ListOfCharacters中序列匹配的第一個 字符的iterator。如果沒有找到匹配項，search返回ListOfCharacters.end()的值。 



--------------------------------------------------------------------------------

使用list的成員函數sort()排序一個list。
    要排序一個list，我們要用list的成員函數sort()，而不是通用算法sort()。所有我們用過的算法都是 通用算法。然而，在STL中有時容器支持它自己對一個特殊算法的實現，這通常是為了提高性能。 
    在這個例子中，list容器有它自己的sort算法，這是因為通用算法僅能為那些提供隨機存取里面元素 的容器排序，而由于list是作為一個連接的鏈表實現的，它不支持對它里面的元素隨機存取。所以就需要一個特殊的 sort()成員函數來排序list。 

    由于各種原因，容器在性能需要較高或有特殊效果需求的場合支持外部函數(extra functions)， 這通過利用構造函數的結構特性可以作到。 

 
/*
|| How to sort an STL list
*/
#include <string>
#include <list>
#include <algorithm>
#
PrintIt (string& StringToPrint) { cout << StringToPrint << endl;}
#
int 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

--------------------------------------------------------------------------------

用list的成員函數插入元素到list中
    list的成員函數push_front()和push_back()分別把元素加入到list的前面和后面。你可以使用insert() 把對象插入到list中的任何地方。 
    insert()可以加入一個對象，一個對象的若干份拷貝，或者一個范圍以內的對象。這里是一些 插入對象到list中的例子： 

 
/*
|| Using insert to insert elements into a list.
*/
#include <list>
#
int main (void) {
  list<int> 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); 
#
  /*
  || 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 aclearcase/" target="_blank" >ccept an interger
  */
}
    注意，insert()函數把一個或若干個元素插入到你指出的iterator的位置。你的元素將出現在 iterator指出的位置以前。 


--------------------------------------------------------------------------------

List 構造函數
我們已經象這樣定義了list： 
  list<int> Fred;
你也可以象這樣定義一個list，并同時初始化它的元素： 
  // 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
或者你可以定義一個list并用另一個STL容器的一個范圍來初始化它，這個STL容器不一定是一個list， 僅僅需要是元素類型相同的的容器就可以。 
 
  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

--------------------------------------------------------------------------------

使用list成員函數從list中刪除元素
    list成員函數pop_front()刪掉list中的第一個元素，pop_back()刪掉最后一個元素。 函數erase()刪掉由一個iterator指出的元素。還有另一個erase()函數可以刪掉一個范圍的元素。 
/*
|| Erasing objects from a list
*/
#include <list>
#
int 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

--------------------------------------------------------------------------------

用list成員函數remove()從list中刪除元素。
list的成員函數remove()用來從list中刪除元素。 
 
/*
|| Using the list member function remove to remove elements
*/
#include <string>
#include <list>
#include <algorithm>
#
PrintIt (const string& StringToPrint) {
  cout << StringToPrint << endl;
}
#
int 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

--------------------------------------------------------------------------------

使用STL通用算法remove()從list中刪除元素
通用算法remove()使用和list的成員函數不同的方式工作。一般情況下不改變容器的大小。 
 
/*
|| Using the generic remove algorithm to remove list elements
*/
#include <string>
#include <list>
#include <algorithm>
#
PrintIt(string& AString) { cout << AString << endl; }
#
int 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);
}
The output will be 
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()算法返回一個指向新的list的結尾的iterator。從開始到這個新的結尾（不含新結尾元素）的范圍 包含了remove后剩下所有元素。你可以用list成員函數erase函數來刪除從新結尾到老結尾的部分。 


--------------------------------------------------------------------------------

使用STL通用算法stable_partition()和list成員函數splice()來劃分一個list
    我們將完成一個稍微有點復雜的例子。它演示STL通用算法stable_partition()算法和一個list成員函數 splice()的變化。注意函數對象的使用和沒有使用循環。 通過簡單的語句調用STL算法來控制。 
    stable_partition()是一個有趣的函數。它重新排列元素，使得滿足指定條件的元素排在 不滿足條件的元素前面。它維持著兩組元素的順序關系。 

    splice 把另一個list中的元素結合到一個list中。它從源list中刪除元素。 

    在這個例子中，我們想從命令行接收一些標志和四個文件名。文件名必須’按順序出現。通過使用stable_partition() 我們可以接收和文件名混為任何位置的標志，并且不打亂文件名的順序就把它們放到一起。 

    由于記數和查找算法都很易用，我們調用這些算法來決定哪個標志被設置而哪個標志未被設置。 我發現容器用來管理少量的象這樣的動態數據。 

 
/*
|| 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>
#
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";
  }
};
#
int 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
#
}
給出這樣的命令行： 
 
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

--------------------------------------------------------------------------------

 結論
    我們僅僅簡單的談了談你可以用list做的事情。我們沒有說明一個對象的用戶定義類，雖然這個不難。 
    如果你懂了剛才說的這些算法背后的概念，那么你使用剩下的那些算法就應該沒有問題了。使用STL 最重要的東西就是得到基本理論。 

    STL的關鍵實際上是iterator。STL算法作為參數使用iterator，他們指出一個范圍，有時是一個范圍， 有時是兩個。STL容器支持iterator，這就是為什么我們說 list<int>::iterator, 或 list<char>::iterator, 或 list<string>::iterator. 

    iterator有很好的定義繼承性。它們非常有用。某些iterator僅支持對一個容器只讀，某些 僅支持寫，還有一些僅能向前指，有一些是雙向的。有一些iterator支持對一個容器的隨機存取。 

    STL算法需要某個iterator作為“動力” 如果一個容器不提供iterator作為“動力”，那么這個算法將無法編譯。例如，list容器僅提供雙向的 iterator。通常的sort()算法需要隨機存取的iterator。這就是為什么我們需要一個特別的list成員函數sort()。 

    要合適的實際使用STL，你需要仔細學習各種不同的iterator。你需要知道每種容器都支持那類iterator。 你還需要知道算法需要那種iterator，你當然也需要懂得你可以有那種iterator。 



--------------------------------------------------------------------------------

在field中使用STL
    去年，我曾用STL寫過幾個商業程序。它在很多方面減少了我的工作量，也排除了很多邏輯錯誤。 
    最大的一個程序有大約5000行?？赡茏铙@人的事情就是它的速度。它讀入并處理一個1-2兆的 報告文件僅花大約20秒。我是在linux上用gcc2.7.2開發的，現在運行在HP-UX機器上。 它一共用了大約50和函數對象和很多容器，這些容器的大小從小list到一個有14,000個元素的map都有。 

    一個程序中的函數對象是處于一個繼承樹中，頂層的函數對象調用低層的函數對象。我大量的使用STL算法for_each() ,find(),find_if(),count()和count_if()，我盡量減少使用程序內部的函數，而使用STL的算法調用。 

    STL傾向于自動的把代碼組織成清晰的控制和支持模塊。通過小心使用函數對象并給它們 起有意義的名字，我使它們在我的軟件的控制流中流動。 

    還有很多關于STL編程要知道的東西，我希望你通過這些例子可以愉快的工作。 

    參考數目中的兩本書在web上都有勘誤表，你可以自己改正它們。 

    Stroustrup在每一章后面都有個建議欄，特別是對于出學者有用。正本書比早期的版本更加健談。 它也更大了。書店里還可以找到其他幾本關于STL的教科書。去看看，也許你能發現什么。 

 參考書目
The STL Tutorial and Reference Guide, David Musser and Atul Saini. Addison Wesley 1996. 《STL教程和參考手冊》 
The C++ Programming Language 3e, Bjarne Stroustrup. Addison Wesley 1997.  

原文轉自：http://www.kjueaiud.com