C++標準模板庫-STL庫基本算法
16.4 STL庫基本算法
標準C++STL庫中算法組件為一個很重要的組成部分，該組件提供了大多數最常見的通用算法的實現，并且這些實現是經過很多測試試驗并被公認在處理上是高效的。將這些最常見的算法通用化實現，最大的優勢就是開發者在應用中不需要為具體的常見算法的實現而費神，只需要包含相應的頭文件直接使用即可，不僅僅提高的軟件開發的效率，同時還有助于軟件重用性的提高。
16.4.1 STL庫基本算法簡介
根據STL標準庫提供的文檔，該庫中的算法組件主要由于4個部分組成，即通用算法的實現劃分為4類，分別應用對不同需求下的處理。
按照不同的特征處理劃分第一類算法稱之為非修正算法，其實就是提供的算法實現中不會涉及修改對應操作的容器中的任何元素，包括其位置等操作。這類算法主要為一些查找、統計、比較類操作實現，主要包含find()、find_first()、find_end()、count()、equal()等不需要進行操作的容器元素變動的算法。
第二類自然是與之對應的修正類算法，該類算法是在實際使用與具體的容器上時，需要通過適當的改變容器中內容從而實現相應的功能。這類針對容器處理需要修該的算法主要包括一些交換元素、替換元素、刪除等操作實現，STL中主要包含copy()、swap()、remove()以及replace()等算法實現。
第三類自然是平時實際應用中較頻繁的排序算法的提供，排序算法在實際應用中尤其是大數據量處理的軟件中應用尤其突出，算法的處理效率適用場合決定著軟件處理大數據量排序時的處理效率。STL庫中針對排序提供了比較完備的算法實現，其中sort()、table_sort()等算法都以較高處理效率而著稱。
最后一類是針對容器中元素的計算提出的數值計算算法，主要提供了容器內元素乘積之和、元素加法之和以及相鄰的元素之差等算法基本操作。
STL標準庫提供的通用算法實現基本都是高效穩定的，對于初學者來講理解這些不同類算法的基本實現功能、基本操作應用，另外需要了解的即在應用開發中遇到問題時會分析從而采用最適合的算法來解決相應的問題即可。隨著逐步深入學習，為了更加理解相應庫算法的具體實現，從而更好地利好用STL庫中算法，可以逐步的學會分析該庫提供的算法組件實現的源碼，從中獲取組件設計實現的思路，提高編程修養。
下面將會按照算法組件中4個類別的算法，分為4個小節對應著講述STL庫算法組件提供的算法操作基本實現原理，以及在實際應用中使用方法，初學者可以參照并在實踐中盡可能的思考更多的應用情況。另由于STL庫提供的算法約70多種之多，篇幅限制的情況下會根據不同類別的算法挑部分作為典型作詳細的講述，其它類別的算法可以采用觸類旁通根據演示的基本使用方式，從而掌握其應用。
16.4.2 非修正算法
通過前面介紹STL庫中算法組件提供了不需要修改容器內元素的算法操作實現，算法組件中非修正算法主要包括了adjacent_find()、find()、find_end()、find_first()、count()、equal()、for_each()以及serch()等操作接口。
這類算法操作主要針對不需要修改容器序列操作的情況下提供的，其中最常見的要算在容器之上的查找操作了。STL算法組件針對查找操作提供了幾種不同的操作算法接口，分別為adjacent_find()、find()、find_end()和find_first()。
其中adjacent_find()算法操作主要用于查找容器中是否存在相鄰元素，該方法接口返回找到的一對容器中指向相同臨近元素之一的迭代器，該方法需要提供操作容器的范圍迭代器。
find()操作算法主要用于查找容器中某個特定元素，找到則返回該容器中第一個找到特殊元素位置的迭代器。同時通過find()算法，可以根據需要擴展出多個如find_end()、find_first()、find_first_of()等算法操作接口，分別在find()算法基礎上增加不同的限制實現的算法操作接口。
同時修正類算法還提供如equal()這樣比較容器對象的算法操作，允許使用同類型容器不同對象之間比較，內部實際實現了不同的對象比較運算，以及for_each()算法在迭代器指定范圍內循環執行相應參數提供的方法的操作，供實際應用中使用。下面將會通過一個完整實例，演示部分非修正算法的使用情況，通過這部分算法接口的操作應用了解STL庫算法組件的常見使用方法。
1.準備實例
打開UE工具，創建新的空文件并且另存為chapter1613.cpp。該代碼文件隨后會同makefile文件一起通過FTP工具傳輸至Linux服務器端，客戶端通過scrt工具訪問操作。程序代碼文件編輯如下所示。
/**
* 實例chapter1613
* 源文件chapter1613.cpp
* 非修正類算法應用實例
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
//第一部分代碼
vector<int>testVector; //定義int整型類型vector容器testVector
vector<int>::iteratorfirstIter; //定義int整型類型迭代器firstIter
vector<int>::iteratorendIter; //定義int整型類型迭代器endIter
vector<int>::iteratortempIter; //定義int整型類型迭代器tempIter
for(inti = 0;i < 10;i++) //通過循環控制結構，變量i值從0到10循環10次
{
testVector.push_back(i); //通過容器提供的push_back方法將i變量值放入testVector
}
//find()算法演示
firstIter= testVector.begin(); //通過begin()方法將容器testVector首個元素賦值firstIter指向
endIter= testVector.end(); //通過end()方法將容器testVector末元素賦值endIter指向
tempIter = find(firstIter,endIter,8); //通過find()方法從容器首元素到尾元素之間查找元素值為8的元素
if(tempIter== testVector.end()) //判斷是否遍歷至容器尾部
{
cout<<"Don'tfind element value's 8!"<<endl; //提示沒有找到相應元素
}
else
cout<<"Findthis element:"<<*tempIter<<endl; //提示找到相應元素
//第二部分代碼
//adjacent_find()算法演示
testVector.insert(++firstIter,2,10); //通過insert()方法向容器testVector中插入元素值
cout<<"vectorelements:"; //提示打印輸出容器元素
for(firstIter= testVector.begin();firstIter != testVector.end();firstIter++) //循環遍歷容器testVector
{
cout<<*firstIter<<""; //輸出迭代器指向元素值
}
cout<<endl;
firstIter= testVector.begin(); //通過begin()方法將容器testVector首個元素賦值firstIter指向
endIter = testVector.end(); //通過end()方法將容器testVector末元素賦值endIter指向
tempIter= adjacent_find(firstIter,endIter); //通過adjacent_find()方法查找相鄰相同元素
if(tempIter!= testVector.end()) //判斷是否遍歷至容器尾部
{
cout<<"Findpair elements:"<<"(" //找到則輸出提示
<<*tempIter<<","<<*(tempIter+1)<<")"
<<"atloc:"<<tempIter - firstIter<<endl;
}
else
cout<<"notfind pair elements!"<<endl; //未找到，輸出提示
//第三部分代碼
//count()算法演示
firstIter= testVector.begin(); //通過begin()方法將容器testVector首個元素賦值firstIter指向
endIter = testVector.end(); //通過end()方法將容器testVector末元素賦值endIter指向
cout<<"countelement's 10:"<<count(firstIter,endIter,10)<<endl; //通過count方法計算容器中元素10的個數
return0;
}
2.編輯makefile
Linux平臺下需要編譯源文件為chapter1613.cpp，相關makefile工程文件編譯命令編輯如下所示。
OBJECTS=chapter1613.o
CC=g++
chapter1613: $(OBJECTS)
$(CC)$(OBJECTS) -g -o chapter1613
clean:
rm-f chapter1613 core $(OBJECTS)
submit:
cp-f -r chapter1613 ../bin
上述makefile文件套用前面的模板格式，主要替換了代碼文件、程序編譯中間文件、可執行程序等。在編譯命令部分-g選項的加入，表明程序編譯同時加入了可調式信息。
3.編譯運行程序
當前shell下執行make命令，生成可執行程序文件，隨后通過make submit命令提交程序文件至本實例bin目錄，通過cd命令定位至bin目錄，執行該程序文件運行結果如下所示。
[developer@localhost src]$ make
g++ -c -ochapter1613.o chapter1613.cpp
g++ chapter1613.o -g -o chapter1613
[developer @localhost src]$ make submit
cp -f -r chapter1613../bin
[developer @localhost src]$ cd ../bin
[developer @localhost bin]$ ./chapter1613
Find this element:8
vector elements:0 10 10 1 2 3 4 5 6 7 8 9
Find pair elements:(10,10)at loc:1
count element's 10:2
4.剖析程序
本實例程序主要演示了非修正算法中find()、adjacent_find()以及count算法接口的操作應用。STL庫中算法組件通過頭文件#include<algorithm>包含，即可以在應用程序中使用提供的相應的算法接口操作。
第一部分代碼在主程序中只要定義整型空的序列容器vector對象testVector，隨后定義三個該類型的迭代器分別表示指向容器首位置、尾位置以及作為臨時結果的迭代器。
隨后的for循環控制結構中，通過push_back方法向向量容器尾部循環添加對應的元素，將定義的兩個迭代器通過容器提供的begin()與end()方法分別定位到vector容器的首部和尾部。隨后直接調用算法操作接口find()，該算法接口共三個參數，兩個迭代器分別表示所要查找的元素區間，最后一個參數則表示所要查找的元素值。該方法調用中迭代器定位至容器首部與尾部，同時查找元素為整型值8，調用返回找到元素的指向迭代器，將其結果賦給結果迭代器tempIter。
調用find方法之后將方法結果返回值賦給結果迭代器tempIter，之后判斷該迭代器，并根據該結果迭代器的判斷情況來說明是否找到相應的元素，以及通過解引用直接打印輸出找到的元素。由于元素8存在于容器隊列testVector中，if判斷條件不成立，直接打印輸出找到的元素值。
第二部分代碼主要演示adjacent_find方法查找相鄰相同元素，首先通過testVector調用insert方法在指定的首部之后的元素位置插入2個值為10的元素。此時通過迭代器firstIter遍歷容器并打印輸出容器中的內容為“0 10 10 1 2 3 4 5 6 7 8 9”。
隨后迭代器firstIter與endIter重新定位至容器的首部與尾部，通過調用adjacent_find方法演示相鄰相同元素查找的算法操作，該算法接口主要包含兩個參數，分別為需要查找的元素范圍迭代器。程序中傳入重新定位的兩個迭代器，即表明查找操作將會在該容器的首部到尾部區間之間進行。由于該方法將會返回指向相鄰相同元素的一個迭代器，將該方法結果直接賦給結果迭代器tempIter，隨后開始判斷該迭代器是否指向了容器的尾部，如果指向尾部則說明沒找到相鄰相同的元素，如果沒有則打印相鄰的兩個元素值以及該元素所處的位置。
第三部分代碼演示非修正算法中count統計序列相同元素個數的算法操作，將迭代器重新定位后，直接在流輸出中調用count方法查找元素為10的個數，統計范圍自然為從容器首部到尾部區間。
16.4.3 修正算法
STL庫中修正算法主要針對數據元素序列處理可能涉及修改的情況，主要包括序列中元素的填充、交換、拷貝、刪除與替換等。部分修正算法可以通過表格16.6作一個簡單的說明，如下所示。
表格16.6 STL部分修正算法簡介
|
算法接口 |
說明 |
|
fill(firstIter,endIter,value) |
將元素值value填補到迭代器所指向區間中 |
|
copy(firstiter,endIter,firstIter1) |
將迭代器firstIter與endIter區間元素拷貝至迭代器firstIter1所指向的序列的開始之處 |
|
copy_backward(firstIter,endIter,firstIter1) |
將迭代器firstIter與endIter區間元素拷貝至迭代器firstiter1所指向的序列開始之初，但是從最后一個元素往前逐個拷貝賦值 |
|
remove(firstIter,endIter,value) |
刪除迭代器firstIter與endIter區間內值為value的所有元素 |
|
replace(firstIter,endIter,value1,value2) |
區間firstIter與endIter之間元素，用value1替換所有的value2 |
|
reverse(firstIter,endIter) |
將迭代器區間firstIter與endIter之間的元素反向排列 |
|
swap(iter1,iter2) |
交換迭代器iter1與iter2所指向的元素 |
|
unique(firstIter,endIter) |
去除迭代器firstIter與endIter區間內重復的相鄰元素 |
上述表格大致列出了STL庫中修正類算法常用的幾個算法操作，并作了簡單的操作說明。修正類算法主要針對序列中刪除、修改、交換等操作作了高效算法的實現，下面將會通過一個完整操作修正類算法的實例，根據STL中提供的算法的基本接口配合簡單的說明在實際程序中應用這些算法。
1.準備實例
打開UE工具，創建新的空文件并且另存為chapter1614.cpp。該代碼文件隨后會同makefile文件一起通過FTP工具傳輸至Linux服務器端，客戶端通過scrt工具訪問操作。程序代碼文件編輯如下所示。
/**
* 實例chapter1614
* 源文件chapter1614.cpp
* 修正算法應用實例
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
//第一部分代碼
vector<int>testVector; //定義int整型類型vector容器對象testVector
vector<int>::iteratorfirstIter; //定義int整型類型容器迭代器firstIter
vector<int>::iteratorendIter; //定義int整型類型容器迭代器endIter
for(inti = 0;i < 10;i++) //循環控制結構，從變量i為0開始到10，循環10次
{
testVector.push_back(i); //通過push_back將元素值i放入容器testVector
}
cout<<"vectorelements:"; //提示打印輸出容器內容
for(firstIter= testVector.begin();firstIter != testVector.end();firstIter++) //通過for循環控制遍歷容器內容
{
cout<<*firstIter<<""; //輸出迭代器指向元素值
}
cout<<endl;
firstIter= testVector.begin(); //通過begin()將容器testVector首元素賦值給firstIter指向
endIter = testVector.end(); //通過end()將容器testVector首元素賦值給endIter指向
fill(firstIter,firstIter+3,8); //通過fill()方法在容器指定位置填充元素值8
cout<<"vectorelements:"; //提示輸出容器內容
for(firstIter= testVector.begin();firstIter != testVector.end();firstIter++) //通過for循環遍歷容器
{
cout<<*firstIter<<""; //打印輸出迭代器指向值
}
cout<<endl;
//第二部分代碼
firstIter= testVector.begin(); //通過begin()將容器testVector首元素賦值給firstIter指向
endIter = testVector.end(); //通過end()將容器testVector首元素賦值給endIter指向
reverse(firstIter,endIter); //通過reverse()方法顛倒容器中的元素
cout<<"vector elements:"; //提示輸出容器內容
for(firstIter = testVector.begin();firstIter!= testVector.end();firstIter++) //通過for循環遍歷容器
{
cout<<*firstIter<<""; //打印輸出迭代器指向值
}
cout<<endl;
//第三部分代碼
endIter =unique(testVector.begin(),testVector.end()); //通過unique()方法過濾相鄰相同元素
cout<<"vector elements:"; //提示輸出容器內容
for(firstIter = testVector.begin();firstIter !=endIter;firstIter++) //通過for循環遍歷容器
{
cout<<*firstIter<<""; //打印輸出迭代器指向值
}
cout<<endl;
return0;
}
2.編輯makefile
Linux平臺下需要編譯源文件為chapter1614.cpp，相關makefile工程文件編譯命令編輯如下所示。
OBJECTS=chapter1614.o
CC=g++
chapter1614: $(OBJECTS)
$(CC)$(OBJECTS) -g -o chapter1614
clean:
rm-f chapter1614 core $(OBJECTS)
submit:
cp-f -r chapter1614 ../bin
上述makefile文件套用前面的模板格式，主要替換了代碼文件、程序編譯中間文件、可執行程序等。在編譯命令部分-g選項的加入，表明程序編譯同時加入了可調式信息。
3.編譯運行程序
當前shell下執行make命令，生成可執行程序文件，隨后通過make submit命令提交程序文件至本實例bin目錄，通過cd命令定位至bin目錄，執行該程序文件運行結果如下所示。
[developer@localhost src]$ make
g++ -c -ochapter1614.o chapter1614.cpp
g++ chapter1614.o -g -o chapter1614
[developer @localhost src]$ make submit
cp -f -r chapter1614../bin
[developer @localhost src]$ cd ../bin
[developer @localhost bin]$ ./chapter1614
vector elements:0 1 2 3 4 5 6 7 8 9
vector elements:8 8 8 3 4 5 6 7 8 9
vector elements:9 8 7 6 5 4 3 8 8 8
vector elements:9 8 7 6 5 4 3 8
4.程序剖析
本實例主要演示了STL算法組件中fill()、reverse()以及unique()三個方法操作應用，三個方法分別表示針對當前序列的填充、顛倒序列元素以及清除序列中相鄰的同元素操作。
第一部分代碼與前面實例相同首先定義空整型向量對象testVector，以及兩個同等類型的迭代器分別表示區間頭與尾。采用for循環結構向該容器中填入0～10的整型數據，隨后通過迭代器遍歷訪問該容器序列并打印輸出。隨后將迭代器定位，firstIter與enditer兩個迭代器分別指向容器首部和尾部。調用算法組件中的fill方法，區間參數為firstIter所指位置到往后3個元素的位置處，填充值為8的元素。并且隨后打印輸出驗證結果，容器序列中前3個元素被值為8的元素填充替換，此時的序列為“8 8 8 3 4 5 6 7 8 9”。
第二部分代碼重新定位迭代器位置，調用reverse方法顛倒序列中的元素，參數區間為整個容器從首部到尾部之間。此時打印輸出驗證容器序列中的元素因為調用reverse方法而發生顛倒，序列為“9 8 7 6 5 4 3 8 8 8”。
第三部分代碼算法演示則調用unique算法，去除了容器中相鄰相同的元素，調用該方法直接傳入容器調用begin與end方法返回的迭代器區間參數，表明將在整個容器的首部與尾部來作該操作，打印輸出驗證，此時序列中的元素為“9 8 7 6 5 4 3 8”，相鄰重復的元素8被刪除只剩下一個。
16.4.4 排序算法
STL組件針對排序提供了超過20多種之多的算法實現，通常應用程序處理大數據量中排序算法的選擇應用也是最普遍的。由于該類算法種類龐雜而多，下面將會通過介紹幾種最常用的排序算法操作，從而了解算法組件中排序算法的一般操作規律。
排序算法中比較重要的幾類算法包括sort()、stable_sort()以及partial_sort()。其中sort算法原型為sort(firstIter,endIter)，主要按照規定排序迭代器firstIter到enditer區間內的元素。stable_sort算法同樣擁有sort操作兩個參數，但是該算法保持序列中相等元素的相對位置，從而減少因為移動而帶來的處理時間消耗。
而partial_sort算法原型為partial_sort(firstIter,midIter,endIter)，主要排序的元素區間為firstIter到endIter之間，將排序好的部分元素首先放置到firstIter與midIter之間，其余未經過排序的部分放置到midIter與endIter之間。
下面將通過完整實例演示其中sort()與partial_sort()算法操作的應用情況，根據不同的需求從而選擇不同的算法調用，實例中依然采用向量容器作為基本序列操作的對象。
1.準備實例
打開UE工具，創建新的空文件并且另存為chapter1615.cpp。該代碼文件隨后會同makefile文件一起通過FTP工具傳輸至Linux服務器端，客戶端通過scrt工具訪問操作。程序代碼文件編輯如下所示。
/**
* 實例chapter1615
* 源文件chapter1615.cpp
* 排序算法應用實例
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
//第一部分代碼
vector<int>testVector; //定義int整型類型vector容器對象testVector
vector<int>::iteratorfirstIter; //定義int整型類型迭代器firstIter
vector<int>::iteratorendIter; //定義int整型類型迭代器endIter
testVector.push_back(2); //通過push_back()方法將元素2放入容器
testVector.push_back(3); //通過push_back()方法將元素3放入容器
testVector.push_back(1); //通過push_back()方法將元素1放入容器
testVector.push_back(6); //通過push_back()方法將元素6放入容器
testVector.push_back(8); //通過push_back()方法將元素8放入容器
testVector.push_back(10); //通過push_back()方法將元素10放入容器
cout<<"vectorelements:"; //提示輸出容器內容
for(firstIter = testVector.begin();firstIter !=testVector.end();firstIter++) //通過循環遍歷容器
{
cout<<*firstIter<<""; //輸出迭代器指向內容
}
cout<<endl;
//第二部分代碼
firstIter = testVector.begin(); //通過begin()方法將容器testVector首元素賦值給firstIter指向
endIter = testVector.end(); //通過end ()方法將容器testVector首元素賦值給endIter指向
sort(firstIter,endIter); //通過sort()方法對容器元素進行排序
cout<<"vector elements:"; //提示輸出容器內容
for(firstIter = testVector.begin();firstIter !=testVector.end();firstIter++) //通過循環遍歷容器
{
cout<<*firstIter<<""; //輸出迭代器指向內容
}
cout<<endl;
//第三部分代碼
firstIter = testVector.begin(); //通過begin()方法將容器testVector首元素賦值給firstIter指向
endIter = testVector.end(); //通過end ()方法將容器testVector首元素賦值給endIter指向
random_shuffle(firstIter,endIter); //通過random_shuffle方法隨機打亂容器內元素
cout<<"vector elements:"; //提示輸出容器內容
for(firstIter = testVector.begin();firstIter !=testVector.end();firstIter++) //通過循環遍歷容器
{
cout<<*firstIter<<""; //輸出迭代器指向內容
}
cout<<endl;
partial_sort(testVector.begin(),testVector.begin()+4,testVector.end());//通過partial_sort方法對容器排序
cout<<"vectorelements:"; //提示輸出容器內容
for(firstIter = testVector.begin();firstIter !=testVector.end();firstIter++) //通過循環遍歷容器
{
cout<<*firstIter<<""; //輸出迭代器指向內容
}
cout<<endl;
return0;
}
2.編輯makefile
Linux平臺下需要編譯源文件為chapter1615.cpp，相關makefile工程文件編譯命令編輯如下所示。
OBJECTS=chapter1615.o
CC=g++
chapter1615: $(OBJECTS)
$(CC)$(OBJECTS) -g -o chapter1615
clean:
rm-f chapter1615 core $(OBJECTS)
submit:
cp-f -r chapter1615 ../bin
上述makefile文件套用前面的模板格式，主要替換了代碼文件、程序編譯中間文件、可執行程序等。在編譯命令部分-g選項的加入，表明程序編譯同時加入了可調式信息。
3.編譯運行程序
當前shell下執行make命令，生成可執行程序文件，隨后通過make submit命令提交程序文件至本實例bin目錄，通過cd命令定位至bin目錄，執行該程序文件運行結果如下所示。
[developer@localhost src]$ make
g++ -c -ochapter1615.o chapter1615.cpp
g++ chapter1615.o -g -o chapter1615
[developer @localhost src]$ make submit
cp -f -r chapter1615../bin
[developer @localhost src]$ cd ../bin
[developer @localhost bin]$ ./chapter1615
vector elements:2 3 1 6 8 10
vector elements:1 2 3 6 8 10
vector elements:8 6 2 3 1 10
vector elements:1 2 3 6 8 10
4.程序剖析
本實例主要演示了vector容器中操作排序基本算法的方法，下面將會將代碼分為三個部分進行分析。
第一部分代碼實例中定義空的整型向量對象testVector，同時定義兩個迭代器分別表示容器首尾。隨后通過調用其push_back方法，在容器尾部添加不同的元素。此時容器中的元素序列根據迭代器遍歷打印輸出結果為“2 3 1 6 8 10”。
第二部分代碼將兩個迭代器分別定位到向量testVector首部與尾部位置，調用sort算法操作排序參數區間的元素，其排序結果打印輸出為“1 2 3 6 8 10”。默認情況下sort算法操作按照升序方式排序序列中的元素，當然也可以通過第三個參數來指定排序方式。
第三部分代碼首先通過random_shuffle方法將首尾迭代器之間的元素進行隨機排列，之后演示partial_sort算法操作，其傳入的第一個參數為testVector向量首部元素的迭代器，第二個參數則指定為指向首部元素向后挪4個位置的迭代器表示中間位置，第三個參數則為指向向量尾部的迭代器。跟據該算法操作的基本描述，該方法應該將已經排序的元素放入中間迭代器位置之前，未排序的則放置之后。最后通過迭代器遍歷打印輸出結果驗證，該容器中結果為“1 2 3 6 10 8”，此時從第4個元素位置開始前面都是已經排序的元素，而從第4個元素之后兩個元素則未排序。
16.4.5 數值算法
STL標準庫算法組件針對數值處理提供了4個算法實現，分別為accumulate()、inner_product()、partial_sum()以及adjacent_difference()。四個算法基本原型與接口說明如表格16.7所示。
表格16.7 STL標準庫數值算法接口說明
|
算法接口 |
說明 |
|
accumulate(firstIter,endIter,value) |
計算序列中從firstIter到endIter區間內每個元素與value之和 |
|
inner_product(firstIter,endIter,firstIter1,value) |
計算序列中value與從firstIter到endIter區間內每個元素與firstIter1所指范圍內元素乘積之和 |
|
partial_sum(firstIter,enditer,result) |
計算迭代器firstiter與enditer區間中元素的部分之和，結果放入result中，即該區間的第一個元素作為結果result第一個元素，隨后前面相鄰兩個元素相加作為第二個元素，以此遞歸下去 |
|
adjacent_difference(firstIter,endIter,result) |
同上描述，僅僅是計算了元素相鄰差而已 |
下面將會通過實例演示4種數值算法在應用程序中的實際使用方式，實例如下所示。
1.準備實例
打開UE工具，創建新的空文件并且另存為chapter1616.cpp。該代碼文件隨后會同makefile文件一起通過FTP工具傳輸至Linux服務器端，客戶端通過scrt工具訪問操作。程序代碼文件編輯如下所示。
/**
* 實例chapter1616
* 源文件chapter1616.cpp
* 數值算法應用實例
*/
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int main()
{
//第一部分代碼
vector<int>testVector; //定義int整型類型vector容器對象testVector
vector<int>testVector1(6); //定義int整型類型vector容器對象testVector1
vector<int>::iteratorfirstIter; //定義int整型類型迭代器firstIter
vector<int>::iteratorendIter; //定義int整型類型迭代器endIter
vector<int>::iteratortempIter; //定義int整型類型迭代器tempIter
testVector.push_back(2); //通過push_back方法將元素2放入容器testVector
testVector.push_back(3); //通過push_back方法將元素3放入容器testVector
testVector.push_back(1); //通過push_back方法將元素1放入容器testVector
testVector.push_back(6); //通過push_back方法將元素6放入容器testVector
testVector.push_back(8); //通過push_back方法將元素8放入容器testVector
testVector.push_back(10); //通過push_back方法將元素10放入容器testVector
cout<<"vectorelements:"; //提示輸出容器內容
for(firstIter= testVector.begin();firstIter != testVector.end();firstIter++) //通過循環遍歷容器元素
{
cout<<*firstIter<<""; //輸出迭代器指向元素值
}
cout<<endl;
firstIter= testVector.begin(); //通過begin()方法將容器testVector首元素賦值給迭代器firstIter
endIter = testVector.end(); //通過end ()方法將容器testVector首元素賦值給迭代器endIter
intresult; //定義整型結果變量result
result= accumulate(firstIter,endIter,2); //通過accumulate方法計算容器內元素，同時計算元素2和
cout<<"result= "<<result<<endl; //輸出該計算結果值
//第二部分代碼
firstIter= testVector.begin(); //通過begin()方法將容器testVector首元素賦值給迭代器firstIter
endIter = testVector.end(); //通過end ()方法將容器testVector首元素賦值給迭代器endIter
result= inner_product(firstIter,endIter,firstIter+2,8); //通過inner_product方法做容器元素內乘積計算
cout<<"result= "<<result<<endl; //輸出容器乘積結果
//第三部分代碼
firstIter= testVector.begin(); //通過begin()方法將容器testVector首元素復制給迭代器firstIter
endIter =testVector.end(); //通過end()方法將容器testVector尾元素復制給迭代器endIter
partial_sum(firstIter,endIter,testVector1.begin()); //通過partial_sum()方法將容器內元素實現迭代和計算
cout<<"vectorelements:"; //提示輸出容器結果
for(firstIter= testVector1.begin();firstIter != testVector1.end();firstIter++) //通過循環遍歷該容器內部元素
{
cout<<*firstIter<<""; //輸出迭代器指向元素值
}
cout<<endl;
//第四部分代碼
firstIter= testVector.begin(); //通過begin()方法將容器testVector首元素復制給迭代器firstIter
endIter = testVector.end(); //通過end()方法將容器testVector尾元素復制給迭代器endIter
adjacent_difference(firstIter,endIter,testVector1.begin()); //通過adjacent_difference方法實現容器元素迭減
cout<<"vectorelements:"; //提示輸出計算結果
for(firstIter= testVector1.begin();firstIter != testVector1.end();firstIter++) //通過循環遍歷該容器內部元素
{
cout<<*firstIter<<""; //輸出迭代器指向元素值
}
cout<<endl;
return0;
}
2.編輯makefile
Linux平臺下需要編譯源文件為chapter1616.cpp，相關makefile工程文件編譯命令編輯如下所示。
OBJECTS=chapter1616.o
CC=g++
chapter1616: $(OBJECTS)
$(CC)$(OBJECTS) -g -o chapter1616
clean:
rm-f chapter1616 core $(OBJECTS)
submit:
cp-f -r chapter1616 ../bin
上述makefile文件套用前面的模板格式，主要替換了代碼文件、程序編譯中間文件、可執行程序等。在編譯命令部分-g選項的加入，表明程序編譯同時加入了可調式信息。
3.編譯運行程序
當前shell下執行make命令，生成可執行程序文件，隨后通過make submit命令提交程序文件至本實例bin目錄，通過cd命令定位至bin目錄，執行該程序文件運行結果如下所示。
[developer@localhost src]$ make
g++ -c -ochapter1616.o chapter1616.cpp
g++ chapter1616.o -g -o chapter1616
[developer @localhost src]$ make submit
cp -f -r chapter1616../bin
[developer @localhost src]$ cd ../bin
[developer @localhost bin]$ ./chapter1616
vector elements:2 3 1 6 8 10
result = 32
result = 96
vector elements:2 5 6 12 20 30
vector elements:2 1 -2 5 2 2
4.剖析程序
本實例演示了上述4種數值算法操作，分別為accumulate、inner_product、partial_sum和adjacent_difference。程序將會分為四個部分進行剖析講解。
第一部分代碼程序中首先定義兩個vector向量對象，一個為空另一個為大小指定6個元素。隨后將向量對象testVector調用push_back方法添加元素進入容器中，打印輸出該容器中元素為“2 3 1 6 8 10”。
定位兩個迭代器對象的位置為testVector容器的首部與尾部，同時定義整型變量result作為調用accumulate算法計算的結果。該算法中以區間firstIter到endIter之間的元素累加并加上第三個元素值之和作為計算結果返回賦給result，打印輸出該結果為32，內部實現“2+3+1+6+8+10+2”的計算。
第二部分代碼將迭代器重新定位到testVector向量首尾部位置，隨后調用inner_product方法根據傳入的參數將計算結果賦值給result變量打印輸出。由于計算區間為firstiter到enditer之間，同時指定另一個參數為firstIter+2的位置開始往后的元素，兩邊元素相乘最后相加結果加上第四個元素值8。該算法內部計算為序列一“2 3 1 6 8 10”，序列二“1 6 8 10 0 0”，計算為“2*1+3*6+1*8+6*10+8*0+10*0+8”最后結果為96。
第三部分代碼算法操作partial_sum接口的調用中，參數區間為容器對象testVector首尾部迭代器指定的區間，第三個參數即計算結果則存放入另一個容器對象testVector1，所以該參數為指向該容器首部的迭代器。根據該方法算法描述，該操作將testVector中第一個元素作為結果容器中第一個元素，隨后的每個元素都為前兩個元素之和，即計算過程為第一個元素為“2”，隨后“2+3”、“1+2+3”、“6+1+2+3”、“8+6+1+2+3”“10+1+2+3+6+8”，最后計算結果存放入容器testVector1中，打印輸出該容器中內容結果為“2 5 6 12 20 30”。
第四部分代碼與partial_sum算法計算想反，adjacent_difference算法操作則將相鄰兩個元素相減的結果放入結果容器中，容器testVector中存放元素為“2 3 1 6 8 10”，調用該方法后計算結果容器中存放的元素為“2”、“3-2”、“1-3”、“6-1”、“8-6”、“10-8”，最后結果容器中打印輸出序列為“2 1 -2 5 2 2”。
16.5 小結
STL標準庫提供的內容主要分為六個部分，由于篇幅限制本書只向初學者介紹其中最常用的前三個部分。其中函數對象、內存分配器以及配接器隨著深入學習模板部分編程時再逐步講述。STL模板庫包含內容非常的豐富，詳細講述需要通過一本書都介紹不完全部內容，本章的宗旨在于通過講述其中部分常見模板庫的應用情況，通過一些操作實例實踐希望初學者能夠掌握STL庫一般使用方法，從而觸類旁通進而掌握使用STL庫的方法。