本文面向的讀者:學習過C++程式設計語言(也就是說學習過Template),但是還沒有接觸過STL的STL的初學者。這實際上是我學習STL的一篇筆記,老鳥就不用看了。
什麼是泛型程式設計我們可以簡單的了解為:使用模闆的程式設計就是泛型程式設計。就像我們我們可以簡單的了解面向對象程式設計就是使用虛函數的程式設計一樣。
STL是什麼作為一個C++程式設計者,STL是一種不可忽視的技術。Sandard Template Library (STL):
标準模闆庫,更準确的說是 C++ 程式設計語言标準模闆庫。學習過MFC的人知道,MFC是微軟公司建立的 C++ 類庫。而與之類似的是 STL 是模闆庫,隻不過 STL 是 ANSI/ISO 标準的一部分,而 MFC 隻不過是微軟的一個産品而已。也就是說STL是所有C++編譯器和所有作業系統平台都支援的一種庫,說它是一種庫是因為,雖然STL是一種标準,也就是說對所有的編譯器來說,提供給C++程式設計者的接口都是一樣的。也就是說同一段STL代碼在不同編譯器和作業系統平台上運作的結果都是相同的,但是底層實作可以是不同的。 令人興奮的是,STL的使用者并不需要了解它的底層實作。 試想一下,如果我們有一把能打開所有鎖的鑰匙,那将是多麼令人瘋狂啊。嘎嘎。這個歪夢我做了20多年鳥。
STL的目的是标準化元件,這樣你就不用重新開發它們了。你可以僅僅使用這些現成的元件。STL現在是C++的一部分,是以不用額外安裝什麼。它被内建在你的編譯器之内。
為什麼我們需要學習STL- STL是 C++的ANSI/ISO 标準的一部分,可以用于所有C++語言編譯器和所有平台(Windows/Unix/Linux..)。STL的同一版本在任意硬體配置下都是可用的;
- STL 提供了大量的可複用軟體組織。例如,程式員再也不用自己設計排序,搜尋算法了,這些都已經是STL的一部分了。嘎嘎,有意思吧;
- 使用STL 的應用程式保證了得到的實作在處理速度和記憶體利用方面都是高效的,因為STL設計者們已經為我們考慮好了;
- 使用STL編寫的代碼更容易修改和閱讀,這是當然的鳥。因為代碼更短了,很多基礎工作代碼已經被元件化了;
- 使用簡單,雖然内部實作很複雜;
雖然,STL的優點甚多,但是STL的文法實在令初學者人頭疼,許多人望而卻步。可是STL是每個C++程式設計者遲早都要啃的一塊骨頭。因為越來越多的C++代碼是用STL編寫的,看不懂麻煩就大鳥。越來越多的人在用STL,不懂就無法和别人一起合作了。好事多磨嘛,早點學習早點解脫。
下面讓我們來看幾段代碼吧:(你覺得頭疼就不要看了)
//stl_cpp_1.cpp
#include <iostream>
double mean(double *array, size_t n)
{
double m=0;
for(size_t i=0; i<n; ++i){
m += array[i];
}
return m/n;
}
int main(void)
{
double a[] = {1, 2, 3, 4, 5};
std::cout<<mean(a, 5)<<std::endl; // will print 3
return 0;
}
好懂吧,除了那個std有點讓人不舒服以外?這是一段普通的沒有使用STL的C++代碼。再看下面一段:
//stl_cpp_2.cpp
#include <vector>
#include <iostream>
int main(void)
{
std::vector<double> a;
std::vector<double>::const_iterator i;
a.push_back(1);
a.push_back(2);
a.push_back(3);
a.push_back(4);
a.push_back(5);
for(i=a.begin(); i!=a.end(); ++i){
std::cout<<(*i)<<std::endl;
}
return 0;
}
如果你真的沒有接觸過STL的話,你會問,呀,vector 是啥呀?我會告訴你,那是一排美女。嘎嘎。這可不是個比喻,表想歪鳥。這是一段純種的STL代碼,看到尖括号了吧,知道那是模闆了吧。看到a.push_back(5),a.begin(),a.end()你不感覺奇怪麼?可是我們并沒有定義這些函數啊。
//stl_cpp_3.cpp
#include <vector>
#include <iostream>
int main(void)
{
std::vector<int> q;
q.push_back(10);
q.push_back(11);
q.push_back(12);
std::vector<int> v;
for(int i=0; i<5; ++i){
v.push_back(i);
}
std::vector<int>::iterator it = v.begin() + 1;
it = v.insert(it, 33);
v.insert(it, q.begin(), q.end());
it = v.begin() + 3;
v.insert(it, 3, -1);
it = v.begin() + 4;
v.erase(it);
it = v.begin() + 1;
v.erase(it, it + 4);
v.clear();
return 0;
}
這一段你又看到了新東西了吧,iterator???不羅嗦了,等你看完這篇文章,回頭再看就簡單了。在正式介紹STL之前,我們需要花點時間來了解一下模闆和命名空間。
關于模闆的其他細節,讀者可以參閱《C++ Templates 中文版》(有點費腦子哦)。在這裡,我隻簡單的介紹一下模闆類和函數模闆的概念。
模闆是C++中實作代碼重用機制的一種工具,可以實作類型參數化,把類型定義為參數。函數模闆和類模闆允許使用者構造模闆函數和模闆類。
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiInBnauQzLcdjMxEDOwAjMvw1cldWYtlUeyRnbF9CXn5WYpF3bhlXalB3LcRXZu9lbkN3Yfd2bsJ2Xw9CXzV2Zh1WavwFdl5mLuR2cj5yZvxmYtA3Lc9CX6MHc0RHaiojIsJye.jpg)
下面我們來看一段函數模闆的例子:
//stl_cpp_4.cpp
#include<iostream.h>
#include<string.h>
//定義函數模闆
template<class T> //template 是關鍵字,T 表示一種待執行個體化的類型
//template<typename T> 也是對的
T max(T a, T b)//函數模闆,函數名為 max,此函數有2個T類型的參數,傳回類型為T
{
return (a>b)?a:b;
}
//在此例執行個體化的時候,T可以是多種類型的,int,char,string…
int main(void)
{
int x=2,y=6;
double x1=9.123,y1=12.6543;
cout<<"把T執行個體化為int:"<<max(x,y)<<endl;//執行個體化函數模闆,把T執行個體化為int
cout<<"把T執行個體化為double:"<<max(x1,y1)<<endl;
//執行個體化函數模闆,把T執行個體化為double
getchar(); //這一行代碼用來在dos下檢視結果,也可以用cin.get();
}
下面再看看,類模闆:
//stl_cpp_5.cpp
#include<iostream.h>
//定義名為ex_class的類模闆
template < typename T> class ex_class
{
T value;
public:
ex_class(T v) { value=v; }
void set_value(T v) { value=v; }
T get_value(void) {return value;}
};
//main()函數中測試ex_class類模闆
int main(void)
{
//測試int類型資料
ex_class <int> a(5),b(10);
cout<<"a.value:"<<a.get_value()<<endl;
cout<<"b.value:"<<b.get_value()<<endl;
//測試char類型資料
ex_class <char> ch(''A'');
cout<<"ch.value:"<<ch.get_value()<<endl;
ch.set_value(''a'');
cout<<"ch.value:"<<ch.get_value()<<endl;
//測試double類型資料
ex_class <double> x(5.5);
cout<<"x.value:"<<x.get_value()<<endl;
x.set_value(7.5);
cout<<"x.value:"<<x.get_value()<<endl;
}
命名空間(名字空間) 命名空間是C++的一種機制,用來把單個辨別符下的大量有邏輯聯系的程式實體組合到一起。此辨別符作為此組群的名字。命名空間用關鍵字namespace 來定義:
//stl_cpp_6.cpp
#include <iostream>
using namespace std;
namespace printA
{
print() {cout<<"using namespace printA….."<<endl; };
}
namespace printB
{
print() {cout<<"using namespace printB….."<<endl; };
}
int main(void)
{
printA::print(); //測試命名空間printA, ::是作用域解析運算符
printB::print();
}
命名空間可以嵌套定義:
namespace A
{
functiong1(){};
namespace B
{ }
}
一個namespace是指一個具名的範圍(named scope)。namespace被用來将相關的聲明劃歸在一起,将不相關的代碼部分隔開。命名空間隻是命名了一個特殊的作用域,當程式很大,而且需要多人合作的時候,命名空間就顯得特别的重要。比如2個程式員A,B 在同一個程式中定義了函數 pop(),如果沒有使用命名空間,則會出錯,而且這種錯誤難以檢測出來。為了安全起見,他們可以定義不同的命名空間 A和B,在用的時候可以使用A::pop()和B::pop()來區分。
在STL中,标準庫的全部成員在預先定義的命名空間std中。如果要用類模闆vector ,有兩種方法:一是在程式的前面添加預處理指令:
#include <vector>
using namespace std;
第二種方法是:
#include <vector>
using std::vector;
動态綁定和靜态綁定 所謂綁定是指,對于參與多态行為的類型,他們具有多态行為的接口是在公共基類的設計中就預先确定的。而非綁定則對于參與多态行為的類型,他們的接口沒有預先定義。
在C++中通過繼承實作的多态是動态綁定,通過模闆實作的多态是靜态綁定。動态綁定的接口是在運作期間(動态)完成的,靜态綁定的接口是在編譯期間(靜态)完成的。好了,有了以上的知識我們可以來學習STL 了。
STL 的組成STL有三大核心部分:容器(Container)、算法(Algorithms)、疊代器(Iterator),容器擴充卡(container adaptor),函數對象(functor),除此之外還有STL其他标準元件。
- 容器:裝東西的東西,裝水的杯子,裝鹹水的大海,裝人的教室……STL裡的容器是可容納一些資料的模闆類;
- 算法:就是往杯子裡倒水,往大海裡排污,從教室裡攆人……STL裡的算法,就是處理容器裡面資料的方法,操作;
- 疊代器:往杯子裡倒水的水壺,排污的管道,攆人的那個物業管理人員……STL裡的疊代器:周遊容器中資料的對象;
對存儲于容器中的資料進行處理時,疊代器能從一個成員移向另一個成員。他能按預先定義的順序在某些容器中的成員間移動。對普通的一維數組、向量、雙端隊列和清單來說,疊代器是一種指針。
知道了吧?嘎嘎,當然了,你猜到了,那是我在瞎扯蛋。
下面讓我們來看看專家是怎麼說的:
- 容器(container):容器是資料在記憶體中組織的方法,例如,數組、堆棧、隊列、連結清單或二叉樹(不過這些都不是STL标準容器)。STL中的容器是一種存儲T(Template)類型值的有限集合的資料結構,容器的内部實作一般是類。這些值可以是對象本身,如果資料類型T代表的是Class的話。
- 算法(algorithm):算法是應用在容器上以各種方法處理其内容的行為或功能。例如,有對容器内容排序、複制、檢索和合并的算法。在STL中,算法是由模闆函數表現的。這些函數不是容器類的成員函數。相反,它們是獨立的函數。令人吃驚的特點之一就是其算法如此通用。不僅可以将其用于STL容器,而且可以用于普通的C++數組或任何其他應用程式指定的容器。
- 疊代器(iterator):一旦標明一種容器類型和資料行為(算法),那麼剩下唯一要他做的就是用疊代器使其互相作用。可以把達代器看作一個指向容器中元素的普通指針。可以如遞增一個指針那樣遞增疊代器,使其依次指向容器中每一個後繼的元素。疊代器是STL的一個關鍵部分,因為它将算法和容器連在一起。
下面我将依次介紹STL的這三個主要元件。
容器STL中的容器有隊列容器和關聯容器,容器擴充卡(congtainer adapters:stack,queue,priority queue),位集(bit_set),串包(string_package)等等。
在本文中,我将介紹list,vector,deque等隊列容器,和set和multisets,map和multimaps等關聯容器,一共7種基本容器類。
隊列容器(順序容器):隊列容器按照線性排列來存儲T類型值的集合,隊列的每個成員都有自己的特有的位置。順序容器有向量類型、雙端隊列類型、清單類型三種。
基本容器——順序容器
向量(vector容器類):#include <vector>,vector是一種動态數組,是基本數組的類模闆。其内部定義了很多基本操作。既然這是一個類,那麼它就會有自己的構造函數。vector 類中定義了4中種構造函數:
預設構造函數,構造一個初始長度為0的空向量,
如:vector<int> v1;
帶有單個整形參數的構造函數,此參數描述了向量的初始大小。這個構造函數還有一個可選的參數,這是一個類型為T的執行個體,描述了各個向量種各成員的初始值;
如:vector<int> v2(init_size,0); 如果預先定義了:int init_size;他的成員值都被初始化為0;
複制構造函數,構造一個新的向量,作為已存在的向量的完全複制,
如:vector<int> v3(v2);
帶兩個常量參數的構造函數,産生初始值為一個區間的向量。區間由一個半開區間[first,last](MS word的顯示可能會有問題,first前是一個左方括号,last後面是一個右圓括号)來指定。
如:vector<int> v4(first,last)
下面一個例子用的是第四種構造方法,其它的方法讀者可以自己試試。
//stl_cpp_7.cpp
//程式:初始化示範
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
int ar[10] = { 12, 45, 234, 64, 12, 35, 63, 23, 12, 55 };
char* str = "Hello World";
int main(void)
{
vector <int> vec1(ar, ar+10); //first=ar,last=ar+10,不包括ar+10
vector <char> vec2(str, str+strlen(str)); //first=str,last= str+strlen(str),不包括最後一個
cout<<"vec1:"<<endl;
//列印vec1和vec2,const_iterator是疊代器,後面會講到
//當然,也可以用for (int i=0; i<vec1.size(); i++)cout << vec[i];輸出
//size()是vector的一個成員函數
for(vector<int>::const_iterator p=vec1.begin();p!=vec1.end(); ++p)
cout<<*p;
cout<<''/n''<<"vec2:"<<endl;
for(vector<char>::const_iterator p1=vec2.begin();p1!=vec2.end(); ++p1)
cout<<*p1;
getchar();
return 0;
}
為了幫助了解向量的概念,這裡寫了一個小例子,其中用到了vector的成員函數:begin(),end(),push_back(),assign(),front(),back(),erase(),empty(),at(),size()。
//stl_cpp_8.cpp
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> INTVECTOR;//自定義類型INTVECTOR
//測試vector容器的功能
void main(void)
{
//vec1對象初始為空
INTVECTOR vec1;
//vec2對象最初有10個值為6的元素
INTVECTOR vec2(10,6);
//vec3對象最初有3個值為6的元素,拷貝構造
INTVECTOR vec3(vec2.begin(),vec2.begin()+3);
//聲明一個名為i的雙向疊代器
INTVECTOR::iterator i;
//從前向後顯示vec1中的資料
cout<<"vec1.begin()--vec1.end():"<<endl;
for (i =vec1.begin(); i !=vec1.end(); ++i)
cout << *i << " ";
cout << endl;
//從前向後顯示vec2中的資料
cout<<"vec2.begin()--vec2.end():"<<endl;
for (i =vec2.begin(); i !=vec2.end(); ++i)
cout << *i << " ";
cout << endl;
//從前向後顯示vec3中的資料
cout<<"vec3.begin()--vec3.end():"<<endl;
for (i =vec3.begin(); i !=vec3.end(); ++i)
cout << *i << " ";
cout << endl;
//測試添加和插入成員函數,vector不支援從前插入
vec1.push_back(2);//從後面添加一個成員
vec1.push_back(4);
vec1.insert(vec1.begin()+1,5);//在vec1第一個的位置上插入成員5
//從vec1第一的位置開始插入vec3的所有成員
vec1.insert(vec1.begin()+1,vec3.begin(),vec3.end());
cout<<"after push() and insert() now the vec1 is:" <<endl;
for (i =vec1.begin(); i !=vec1.end(); ++i)
cout << *i << " ";
cout << endl;
//測試指派成員函數
vec2.assign(8,1); // 重新給vec2指派,8個成員的初始值都為1
cout<<"vec2.assign(8,1):" <<endl;
for (i =vec2.begin(); i !=vec2.end(); ++i)
cout << *i << " ";
cout << endl;
//測試引用類函數
cout<<"vec1.front()="<<vec1.front()<<endl;//vec1第零個成員
cout<<"vec1.back()="<<vec1.back()<<endl;//vec1的最後一個成員
cout<<"vec1.at(4)="<<vec1.at(4)<<endl;//vec1的第五個成員
cout<<"vec1[4]="<<vec1[4]<<endl;
//測試移出和删除
vec1.pop_back();//将最後一個成員移出vec1
vec1.erase(vec1.begin()+1,vec1.end()-2);//删除成員
cout<<"vec1.pop_back() and vec1.erase():" <<endl;
for (i =vec1.begin(); i !=vec1.end(); ++i)
cout << *i << " ";
cout << endl;
//顯示序列的狀态資訊
cout<<"vec1.size(): "<<vec1.size()<<endl;//列印成員個數
cout<<"vec1.empty(): "<<vec1.empty()<<endl;//清空
}
push_back()是将資料放入vector(向量)或deque(雙端隊列)的标準函數。Insert()是一個與之類似的函數,然而它在所有容器中都可以使用,但是用法更加複雜。end()實際上是取末尾加一,以便讓循環正确運作--它傳回的指針指向最靠近數組界限的資料。
在Java裡面也有向量的概念。Java中的向量是對象的集合。其中,各元素可以不必同類型,元素可以增加和删除,不能直接加入原始資料類型。
雙端隊列(qeque容器類):#include <deque>deque(讀音:deck,意即:double queue)容器類與vector類似,支援随機通路和快速插入删除,它在容器中某一位置上的操作所花費的是線性時間。與vector不同的是,deque還支援從開始端插入資料:
push_front()。此外deque也不支援與vector的capacity()、reserve()類似的操作。
//stl_cpp_9.cpp
#include <iostream>
#include <deque>
using namespace std;
typedef deque<int> INTDEQUE;//有些人很讨厭這種定義法,呵呵
//從前向後顯示deque隊列的全部元素
void put_deque(INTDEQUE deque, char *name)
{
INTDEQUE::iterator pdeque;//仍然使用疊代器輸出
cout << "The contents of " << name << " : ";
for(pdeque = deque.begin(); pdeque != deque.end(); pdeque++)
cout << *pdeque << " ";//注意有 "*"号哦,沒有"*"号的話會報錯
cout<<endl;
}
//測試deqtor容器的功能
void main(void)
{
//deq1對象初始為空
INTDEQUE deq1;
//deq2對象最初有10個值為6的元素
INTDEQUE deq2(10,6);
//deq3對象最初有3個值為6的元素
//聲明一個名為i的雙向疊代器變量
INTDEQUE::iterator i;
//從前向後顯示deq1中的資料
put_deque(deq1,"deq1");
//從前向後顯示deq2中的資料
put_deque(deq2,"deq2");
//從deq1序列後面添加兩個元素
deq1.push_back(2);
deq1.push_back(4);
cout<<"deq1.push_back(2) and deq1.push_back(4):"<<endl;
put_deque(deq1,"deq1");
//從deq1序列前面添加兩個元素
deq1.push_front(5);
deq1.push_front(7);
cout<<"deq1.push_front(5) and deq1.push_front(7):"<<endl;
put_deque(deq1,"deq1");
//在deq1序列中間插入資料
deq1.insert(deq1.begin()+1,3,9);
cout<<"deq1.insert(deq1.begin()+1,3,9):"<<endl;
put_deque(deq1,"deq1");
//測試引用類函數
cout<<"deq1.at(4)="<<deq1.at(4)<<endl;
cout<<"deq1[4]="<<deq1[4]<<endl;
deq1.at(1)=10;
deq1[2]=12;
cout<<"deq1.at(1)=10 and deq1[2]=12 :"<<endl;
put_deque(deq1,"deq1");
//從deq1序列的前後各移去一個元素
deq1.pop_front();
deq1.pop_back();
cout<<"deq1.pop_front() and deq1.pop_back():"<<endl;
put_deque(deq1,"deq1");
//清除deq1中的第2個元素
deq1.erase(deq1.begin()+1);
cout<<"deq1.erase(deq1.begin()+1):"<<endl;
put_deque(deq1,"deq1");
//對deq2指派并顯示
deq2.assign(8,1);
cout<<"deq2.assign(8,1):"<<endl;
put_deque(deq2,"deq2");
}
上面我們示範了deque如何進行插入删除等操作,像erase(),assign()是大多數容器都有的操作。關于deque的其他操作請參閱附錄。
表(List容器類):#include <list>List又叫連結清單,是一種雙線性清單,隻能順序通路(從前向後或者從後向前),圖2是list的資料組織形式。與 前面兩種容器類有一個明顯的差別就是:它不支援随機通路。要通路表中某個下标處的項需要從表頭或表尾處(接近該下标的一端)開始循環。而且缺少下标預算符:operator[]。
同時,list仍然包涵了erase(),begin(),end(),insert(),push_back(),push_front()這些基本函數,下面我們來示範一下list的其他函數功能。
merge():合并兩個排序清單;
splice():拼接兩個清單;
sort():清單的排序;
//stl_cpp_10.cpp
#include <iostream>
#include <string>
#include <list>
using namespace std;
void PrintIt(list<int> n)
{
for(list<int>::iterator iter=n.begin(); iter!=n.end(); ++iter)
cout<<*iter<<" ";//用疊代器進行輸出循環
}
int main(void)
{
list<int> listn1,listn2;
//給listn1,listn2初始化
listn1.push_back(123);
listn1.push_back(0);
listn1.push_back(34);
listn1.push_back(1123);
//now listn1:123,0,34,1123
listn2.push_back(100);
listn2.push_back(12);
//now listn2:12,100
listn1.sort();
listn2.sort();
//給listn1和listn2排序
//now listn1:0,34,123,1123 listn2:12,100
PrintIt(listn1);
cout<<endl;
PrintIt(listn2);
listn1.merge(listn2);
//合并兩個排序清單後,listn1:0,12,34,100,123,1123
cout<<endl;
PrintIt(listn1);
cin.get();
}
上面并沒有示範splice()函數的用法,這是一個拗口的函數。用起來有點麻煩。圖3所示是splice函數的功能。将一個清單插入到另一個清單當中。list容器類定義了splice()函數的3個版本:
splice(position,list_value);
splice(position,list_value,ptr);
splice(position,list_value,first,last);
list_value是一個已存在的清單,它将被插入到源清單中,position是一個疊代參數,他目前指向的是要進行拼接的清單中的特定位置。
listn1:123,0,34,1123 listn2:12,100
執行listn1.splice(find(listn1.begin(),listn1.end(),0),listn2);之後,listn1将變為:123,12,100,34,1123。即把listn2插入到listn1的0這個元素之前。其中,find()函數找到0這個元素在listn1中的位置。值得注意的是,在執行splice之後,list_value将不複存在了。這個例子中是listn2将不再存在。
第二個版本當中的ptr是一個疊代器參數,執行的結果是把ptr所指向的值直接插入到position目前指向的位置之前.這将隻向源清單中插入一個元素。
第三個版本的first和last也是疊代器參數,并不等于list_value.begin(),list_value.end()。First指的是要插入的列的第一個元素,last指的是要插入的列的最後一個元素。
如果listn1:123,0,34,1123 listn2:12,43,87,100 執行完以下函數之後
listn1.splice(find(listn1.begin(),listn1.end(),0),++listn2.begin(),--listn2.end());
listn1:123,43,87,0,34,1123 listn2:12,100
以上,我們學習了vector,deque,list三種基本順序容器,其他的順序容器還有:slist,bit_vector等等。
另一種容器——關聯容器(有點費解哦,出去讓腦子清醒一下再回來看)與前面講到的順序容器相比,關聯容器更注重快速和高效地檢索資料的能力。這些容器是根據鍵值(key)來檢索資料的,鍵可以是值也可以是容器中的某一成員。這一類中的成員在初始化後都是按一定順序排好序的。
集和多集(set 和multiset 容器類):#include <set>一個集合(set)是一個容器,它其中所包含的元素的值是唯一的。這在收集一個資料的具體值的時候是有用的。集合中的元素按一定的順序排列,并被作為集合中的執行個體。如果你需要一個鍵/值對(pair)來存儲資料,map(也是一個關聯容器,後面将馬上要講到)是一個更好的選擇。一個集合通過一個連結清單來組織,在插入操作和删除操作上比向量(vector)快,但查找或添加末尾的元素時會有些慢。
在集中,所有的成員都是排列好的。如果先後往一個集中插入:12,2,3,123,5,65
則輸出該集時為:2,3,5,12,65,123
集和多集的差別是:set支援唯一鍵值,set中的值都是特定的,而且隻出現一次;而multiset中可以出現副本鍵,同一值可以出現多次。
Set和multiset的模闆參數:
template<class key, class compare, class Allocator=allocator>
第一個參數key是所存儲的鍵的類型,第二個參數是為排序值而定義的比較函數的類型,第三個參數是被實作的存儲配置設定符的類型。在有些編譯器的具體實作中,第三個參數可以省略。第二個參數使用了合适形式的疊代器為鍵定義了特定的關系操作符,并用來在容器中周遊值時建立順序。集的疊代器是雙向,同時也是常量的,是以疊代器在使用的時候不能修改元素的值。
Set定義了三個構造函數:
預設構造函數:
explicit set(const Compare&=compare());
如:set<int,less<int> > set1;
less<int>是一個标準類,用于形成降序排列函數對象。升序排列是用greater<int>。通過指定某一預先定義的區間來初始化set對象的構造函數:
template<class InputIterator> set(InputIterator, InputIterator,/ const Compare&=compare());
如:set<int ,less<int> >set2(vector1.begin(),vector1.end());
複制構造函數:
set(const set<Key,Compare&>);
如:set<int ,less<int> >set3(set2);
下面我們來看一個簡單的集和多集的插入例程:
//stl_cpp_11.cpp
#include <iostream>
#include <set>
using namespace std;
int main(void)
{
set<int> set1;
for(int i=0; i<10; ++i)
set1.insert(i);
for(set<int>::iterator p=set1.begin();p!=set1.end();++p)
cout<<*p<<"";
if(set1.insert(3).second)//把3插入到set1中
//插入成功則set1.insert(3).second傳回1,否則傳回0
//此例中,集中已經有3這個元素了,是以插入将失敗
cout<<"set insert success";
else
cout<<"set insert failed";
int a[] = {4, 1, 1, 1, 1, 1, 0, 5, 1, 0};
multiset<int> A;
A.insert(set1.begin(),set1.end());
A.insert(a,a+10);
cout<<endl;
for(multiset<int>::iterator p=A.begin();p!=A.end();++p)
cout<<*p<<" ";
cin.get();
return 0;
}
在集之間可以進行并集(set_union())、交集(set_intersection())、差集(set_diffrence())d等操作,功能強大。
映射和多重映射(map 和multimap):#include <map>映射和多重映射基于某一類型Key的鍵集的存在,提供對T類型的資料進行快速和高效的檢索。對map而言,鍵隻是指存儲在容器中的某一成員。Map不支援副本鍵,multimap支援副本鍵。Map和multimap對象包涵了鍵和各個鍵有關的值,鍵和值的資料類型是不相同的,這與set不同。set中的key和value是Key類型的,而map中的key和value是一個pair結構中的兩個分量。Map支援下表運算符operator[],用通路普通數組的方式通路map,不過下标為map的鍵。在multimap中一個鍵可以對應多個不同的值。
下面的例程說明了map中鍵與值的關系。
//stl_cpp_12.cpp
#include <iostream>
#include <map>
using namespace std;
int main(void)
{
map<char,int,less<char> > map1;
map<char,int,less<char> >::iterator mapIter;
//char 是鍵的類型,int是值的類型
//下面是初始化,與數組類似
//也可以用map1.insert(map<char,int,less<char> >::value_type(''c'',3));
map1[''c'']=3;
map1[''d'']=4;
map1[''a'']=1;
map1[''b'']=2;
for(mapIter=map1.begin();mapIter!=map1.end();++mapIter)
cout<<" "<<(*mapIter).first<<": "<<(*mapIter).second;
//first對應定義中的char鍵,second對應定義中的int值
//檢索對應于d鍵的值是這樣做的:
map<char,int,less<char> >::const_iterator ptr;
ptr=map1.find(''d'');
cout<<''/n''<<" "<<(*ptr).first<<" 鍵對應于值:"<<(*ptr).second;
cin.get();
return 0;
}
從以上例程中,我們可以看到map對象的行為和一般數組的行為類似。Map允許兩個或多個值使用比較操作符。下面我們再看看multimap:
//stl_cpp_13.cpp
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main(void)
{
multimap<string,string,less<string> >mulmap;
multimap<string,string,less<string> >::iterator p;
//初始化多重映射mulmap:
typedef multimap<string,string,less<string> >::value_type vt;
typedef string s;
mulmap.insert(vt(s("Tom "),s("is a student")));
mulmap.insert(vt(s("Tom "),s("is a boy")));
mulmap.insert(vt(s("Tom "),s("is a bad boy of blue!")));
mulmap.insert(vt(s("Jerry "),s("is a student")));
mulmap.insert(vt(s("Jerry "),s("is a beatutiful girl")));
mulmap.insert(vt(s("DJ "),s("is a student")));
//輸出初始化以後的多重映射mulmap:
for(p=mulmap.begin();p!=mulmap.end();++p)
cout<<(*p).first<<(*p).second<<endl;
//檢索并輸出Jerry鍵所對應的所有的值
cout<<"find Jerry :"<<endl;
p=mulmap.find(s("Jerry "));
while((*p).first=="Jerry ")
{
cout<<(*p).first<<(*p).second<<endl;
++p;
}
cin.get();
return 0;
}
在map中是不允許一個鍵對應多個值的,在multimap中,不支援operator[],也就是說不支援map中允許的下标操作。
算法(algorithm):#inlcude <algorithm>STL中算法的大部分都不作為某些特定容器類的成員函數,他們是泛型的,每個算法都有處理大量不同容器類中資料的使用。值得注意的是,STL中的算法大多有多種版本,使用者可以依照具體的情況選擇合适版本。中在STL的泛型算法中有4類基本的算法:
- 變序型隊列算法,可以改變容器内的資料;
- 非變序型隊列算法,處理容器内的資料而不改變他們;
- 排序值算法,包涵對容器中的值進行排序和合并的算法,還有二叉搜尋算法 $$通用數值算法;
注:STL的算法并不隻是針對STL容器,對一般容器也是适用的。
變序型隊列算法(mutating algorithms):又叫可修改的序列算法。這類算法有複制(copy)算法、交換(swap)算法、替代(replace)算法、删除(remove)算法,移動(transfer)算法、翻轉(reverse)算法等等。這些算法可以改變容器中的資料(資料值和值在容器中的位置)。下面介紹2個比較常用的算法reverse()和copy()。
//stl_cpp_14.cpp
#include <iostream>
#include <algorithm>
#include <iterator>//下面用到了輸出疊代器ostream_iterator
using namespace std;
int main(void)
{
int arr[6]={1,12,3,2,1215,90};
int arr1[7];
int arr2[6]={2,5,6,9,0,-56};
copy(arr,(arr+6),arr1);//将數組aar複制到arr1
cout<<"arr[6] copy to arr1[7],now arr1: "<<endl;
for(int i=0;i<7;i++)
cout<<" "<<arr1[i];
reverse(arr,arr+6);//将排好序的arr翻轉
cout<<''/n''<<"arr reversed ,now arr:"<<endl;
copy(arr,arr+6,ostream_iterator<int>(cout, " "));//複制到輸出疊代器
swap_ranges(arr,arr+6,arr2);//交換arr和arr2序列
cout<<''/n''<<"arr swaped to arr2,now arr:"<<endl;
copy(arr,arr+6,ostream_iterator<int>(cout, " "));
cout<<''/n''<<"arr2:"<<endl;
copy(arr2,arr2+6,ostream_iterator<int>(cout, " "));
cin.get();
return 0;
}
revese()的功能是将一個容器内的資料順序翻轉過來,它的原型是:
template<class Bidirectional >
void reverse(Bidirectional first, Bidirectional last);
将first和last之間的元素翻轉過來,上例中你也可以隻将arr中的一部分進行翻轉:
reverse(arr+3,arr+6);這也是有效的。First和last需要指定一個操作區間。
Copy()是要将一個容器内的資料複制到另一個容器内,它的原型是:
Template<class InputIterator ,class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);
它把[first,last-1]内的隊列成員複制到區間[result,result+(last-first)-1]中。泛型交換算法:Swap()操作的是單值交換,它的原型是:
template<class T>
void swap(T& a,T& b);
swap_ranges()操作的是兩個相等大小區間中的值,它的原型是:
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(ForwardIterator1 first1,ForwardIterator1 last1, /
ForwardIterator1 first2);
交換區間[first1,last1-1]和[first2, first2+(last1-first1)-1]之間的值,并假設這兩個區間是不重疊的。
非變序型隊列算法(Non-mutating algorithm):
又叫不可修改的序列算法。這一類算法操作不影響其操作的容器的内容,包括搜尋隊列成員算法,等價性檢查算法,計算隊列成員個數的算法。我将用下面的例子介紹其中的find(),search(),count():
//stl_cpp_15.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
int a[10]={12,31,5,2,23,121,0,89,34,66};
vector<int> v1(a,a+10);
vector<int>::iterator result1,result2;//result1和result2是随機通路疊代器
result1=find(v1.begin(),v1.end(),2);
//在v1中找到2,result1指向v1中的2
result2=find(v1.begin(),v1.end(),8);
//在v1中沒有找到8,result2指向的是v1.end()
cout<<result1-v1.begin()<<endl; //3-0=3或4-1=3,螢幕結果是3
cout<<result2-v1.end()<<endl;
int b[9]={5,2,23,54,5,5,5,2,2};
vector<int> v2(a+2,a+8);
vector<int> v3(b,b+4);
result1=search(v1.begin(),v1.end(),v2.begin(),v2.end());
cout<<*result1<<endl;
//在v1中找到了序列v2,result1指向v2在v1中開始的位置
result1=search(v1.begin(),v1.end(),v3.begin(),v3.end());
cout<<*(result1-1)<<endl;
//在v1中沒有找到序列v3,result指向v1.end(),螢幕列印出v1的最後一個元素66
vector<int> v4(b,b+9);
int i=count(v4.begin(),v4.end(),5);
int j=count(v4.begin(),v4.end(),2);
cout<<"there are "<<i<<" members in v4 equel to 5"<<endl;
cout<<"there are "<<j<<" members in v4 equel to 2"<<endl;
//計算v4中有多少個成員等于 5,2
cin.get();
return 0;
}
find()的原型是:
template<class InputIterator,class EqualityComparable>
InputIterator find(InputIterator first, InputIterator last,/
const EqualityComparable& value);
其功能是在序列[first,last-1]中查找value值,如果找到,就傳回一個指向value在序列中第一次出現的疊代,如果沒有找到,就傳回一個指向last的疊代(last并不屬于序列)。 search()的原型是:
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,/
ForwardIterator2 first2, ForwardIterator2 last2);
其功能是在源序列[first1,last1-1]查找目标序列[first2,last2-1]如果查找成功,就傳回一個指向源序列中目标序列出現的首位置的疊代。查找失敗則傳回一個指向last的疊代。 Count()的原型是:
template <class InputIterator, class EqualityComparable>
iterator_traits<InputIterator>::difference_type count(InputIterator first,/
InputIterator last, const EqualityComparable& value);
其功能是在序列[first,last-1]中查找出等于value的成員,傳回等于value得成員的個數。
排序算法(sort algorithm):
這一類算法很多,功能強大同時也相對複雜一些。這些算法依賴的是關系運算。在這裡我隻介紹其中比較簡單的幾種排序算法:sort(),merge(),includes()
//stl_cpp_16.cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
int a[10]={12,0,5,3,6,8,9,34,32,18};
int b[5]={5,3,6,8,9};
int d[15];
sort(a,a+10);
for(int i=0;i<10;i++)
cout<<" "<<a[i];
sort(b,b+5);
if(includes(a,a+10,b,b+5))
cout<<''/n''<<"sorted b members are included in a."<<endl;
else
cout<<"sorted a dosn`t contain sorted b!";
merge(a,a+10,b,b+5,d);
for(int j=0;j<15;j++)
cout<<" "<<d[j];
cin.get();
return 0;
}
sort()的原型是:
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
功能是對[first,last-1]區間内的元素進行排序操作。與之類似的操作還有:partial_sort(), stable_sort(),partial_sort_copy()等等。 merge()的原型是:
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,/
InputIterator2 first2, InputIterator2 last2,OutputIterator result);
将有序區間[first1,last1-1]和[first2,last2-1]合并到[result, result + (last1 - first1) + (last2 - first2)-1]區間内。
Includes()的原型是:
template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,/
InputIterator2 first2, InputIterator2 last2);
其功能是檢查有序區間[first2,last2-1]内元素是否都在[first1,last1-1]區間内,傳回一個bool值。
通用數值算法(generalized numeric algorithms)這一類算法還不多,涉及到專業領域中有用的算術操作,獨立包涵于頭檔案<numeric>中(HP版本的STL中是<algo.h>)。這裡不作介紹。
STL中的算法大都有多種版本,常見的版本有以下4中:
- 預設版本,假設給出了特定操作符;
- 一般版本,使用了成員提供的操作符;
- 複制版本,對原隊列的副本進行操作,常帶有 _copy 字尾;
- 謂詞版本,隻應用于滿足給定謂詞的隊列成員,常帶有 _if 字尾;
以上我們學習了STL容器和算法的概念,以及一些簡單的STL容器和算法。在使用算法處理容器内的資料時,需要從一個資料成員移向另一個資料成員,疊代器恰好實作了這一功能。下面我們來學習STL疊代器 。
疊代器(itertor):#include<iterator>疊代器實際上是一種泛化指針,如果一個疊代器指向了容器中的某一成員,那麼疊代器将可以通過自增自減來周遊容器中的所有成員。疊代器是聯系容器和算法的媒介,是算法操作容器的接口。在運用算法操作容器的時候,我們常常在不知不覺中已經使用了疊代器。
STL中定義了6種疊代器:
- 輸入疊代器,在容器的連續區間内向前移動,可以讀取容器内任意值;
- 輸出疊代器,把值寫進它所指向的隊列成員中;
- 前向疊代器,讀取隊列中的值,并可以向前移動到下一位置(++p,p++);
- 雙向疊代器,讀取隊列中的值,并可以向前向後周遊容器;
- 随機通路疊代器, vector<T>::iterator,list<T>::iterator等都是這種疊代器 ;
- 流疊代器,可以直接輸出、輸入流中的值;
實際上,在前面的例子中,我們不停的在用疊代器。下面我們用幾個例子來幫助了解這些疊代器的用法。
下面的例子用到了輸入輸出疊代器:
// stl_cpp_17.cpp
#include <iostream>
#include <fstream>
#include <iterator>
#include <vector>
#include <string>
using namespace std;
int main(void)
{
vector<string> v1;
ifstream file("Text1.txt");
if(file.fail())
{
cout<<"open file Text1.txt failed"<<endl;
return 1;
}
copy(istream_iterator<string>(file),istream_iterator<string>(),inserter(v1,/
v1.begin()));
copy(v1.begin(),v1.end(),ostream_iterator<string>(cout," "));
cout<<endl;
cin.get();
return 0;
}
這裡用到了輸入疊代器istream_iterator,輸出疊代器ostream_iterator。程式完成了将一個檔案輸出到螢幕的功能,先将檔案讀入,然後通過輸入疊代器把檔案内容複制到類型為字元串的向量容器内,最後由輸出疊代器輸出。Inserter是一個輸入疊代器的一個函數(疊代器擴充卡),它的使用方法是:
inserter (container ,pos);
congtainer是将要用來存入資料的容器,pos是容器存入資料的開始位置。上例中,是把檔案内容存入(copy())到向量v1中。
現在我們已經對STL的三大基本元件有了一個大概的了解,下面讓我們一起來看看STL的其他标準元件。
函數對象(functor或者funtion objects):#include <function>函數對象又稱之為仿函數。函數對象将函數封裝在一個對象中,使得它可作為參數傳遞給合适的STL算法,進而使算法的功能得以擴充。可以把它當作函數來使用。使用者也可以定義自己的函數對象。下面讓我們來定義一個自己的函數對象。
// stl_cpp_18.cpp
#include <iostream>
using namespace std;
struct int_max{
int operator()(int x,int y){return x>y?x:y; }
};//operator() 重載了"()", (int x,int y)是參數清單
int main(void)
{
cout<<int_max()(3,4)<<endl;
cin.get();
return 0;
}
這裡的int_max()就是一個函數對象,struct關鍵字也可以用class來代替,隻不過struct預設情況下是公有通路權限,而class定義的是預設私有通路權限。下面我們來定義一個STL風格的函數對象:
// stl_cpp_19.cpp
#include <iostream>
#include <vector>
using namespace std;
struct adder : public unary_function<double, void>
{
adder() : sum(0) {}
double sum;
void operator()(double x) { sum += x; }
};
int main(void)
{
double a[5]={0.5644,1.1,6.6,8.8,9.9};
vector<double> V(a,a+5);
adder result = for_each(V.begin(), V.end(), adder());
cout << "The sum is " << result.sum << endl;
cin.get();
return 0;
}
在這裡,我們定義了一個函數對象adder(),這也是一個類,它的基類是unary_function函數對象。unary_function是一個空基類,不包涵任何操作或變量。隻是一種格式說明,它有兩個參數,第一個參數是函數對象的使用資料類型,第二個參數是它的傳回類型。基于它所定義的函數對象是一進制函數對象。(注:用關鍵字struct或者class定義的類型實際上都是"類")
STL内定義了各種函數對象,否定器、限制器、一進制謂詞、二進制謂詞都是常用的函數對象。函數對象對于程式設計來說很重要,因為他如同對象類型的抽象一樣作用于操作。
擴充卡(adapter):
擴充卡是用來修改其他元件接口的STL元件,是帶有一個參數的類模闆(這個參數是操作的值的資料類型)。STL定義了3種形式的擴充卡:容器擴充卡,疊代器擴充卡,函數擴充卡。
- 容器擴充卡:包括棧(stack)、隊列(queue)、優先(priority_queue)。使用容器擴充卡,stack就可以被實作為基本容器類型(vector,dequeue,list)的适配。可以把stack看作是某種特殊的vctor,deque或者list容器,隻是其操作仍然受到stack本身屬性的限制。queue和priority_queue與之類似。容器擴充卡的接口更為簡單,隻是受限比一般容器要多;
- 疊代器擴充卡:修改為某些基本容器定義的疊代器的接口的一種STL元件。反向疊代器和插入疊代器都屬于疊代器擴充卡,疊代器擴充卡擴充了疊代器的功能;
- 函數擴充卡:通過轉換或者修改其他函數對象使其功能得到擴充。這一類擴充卡有否定器(相當于"非"操作)、幫定器、函數指針擴充卡。
如果你了解了算法、疊代器、容器,那麼你幾乎就了解了 STL。關于STL的其他方面,新手都是不常用的,可以暫時以了解STL的組成的程式設計思想為主。這篇文章裡用到了19個cpp代碼,每個代碼都在Windows 2000+ Dev-C++ 4.9.9.0和windows 2000+VC環境下通過編譯運作。讀者可以通過copy/paste到任何一款C++編譯器中運作。無論你想不想學STL,先運作一下STL代碼吧。程式設計快樂,好好學習,天天向上。
我是新手,歡迎高手批評,歡迎STL學習者交流: Email:[email protected] QQ:370679790