有關(guān)STL應(yīng)用論文
STL是Standard Template Library的簡稱,中文名標(biāo)準(zhǔn)模板庫,惠普實驗室開發(fā)的一系列軟件的統(tǒng)稱。下面是關(guān)于有關(guān)STL應(yīng)用論文的內(nèi)容,歡迎閱讀!
STL提供六大組件,彼此可以組合套用
1、容器(containers):各種數(shù)據(jù)結(jié)構(gòu),如vertor,list,deque,set,map.從實現(xiàn)的角度來看,STL容器是一種class template
2、算法(algorithms):各種算法如sort,search,copy,earse。STL算法是一種 function template。
3、迭代器(iterators):扮演容器與算法之間的膠合劑,是所謂的“泛型指針”。所有STL容器都有自己的專屬的迭代器。
4、仿函數(shù)(functors):行為類似函數(shù),可以作為算法的某些策略。從實現(xiàn)的角度來看,仿函數(shù)是一種重載了operator()的class或class template。
5、配接器(adapters):一種用來修飾容器或仿函數(shù)或迭代器借口的東西。例如queue和stack
6、配置器(allocators):負(fù)責(zé)空間的配置與管理。配置器是一個實現(xiàn)了動態(tài)空間分配、空間管理、空間釋放的class template。
STL是建立在泛化之上的。數(shù)組泛化為容器,參數(shù)化了所包含的對象的類型。函數(shù)泛化為算法,參數(shù)化了所用的迭代器的類型。指針泛化為迭代器,參數(shù)化了所指向的對象的類型。
vector、string、deque和list被稱為標(biāo)準(zhǔn)序列容器,
set、multiset、map和multimap是標(biāo)準(zhǔn)關(guān)聯(lián)容器。
非標(biāo)準(zhǔn)序列容器slist和rope。slist是一個單向鏈表,rope本質(zhì)上是一個重型字符串。
非標(biāo)準(zhǔn)關(guān)聯(lián)容器hash_set、hash_multiset、hash_map和hash_multimap。
標(biāo)準(zhǔn)非STL容器,包括數(shù)組、bitset、valarray、stack、queue和priority_queue。
迭代器被分成五個種類:
輸入迭代器是每個迭代位置只能被讀一次的只讀迭代器。
輸出迭代器是每個迭代位置只能被寫一次的只寫迭代器。
輸入和輸出迭代器被塑造為讀和寫輸入和輸出流(例如,文件)。
前向迭代器有輸入和輸出迭代器的能力,但是它們可以反復(fù)讀或?qū)懸粋位置。
雙向迭代器就像前向迭代器,除了它們的后退可以像前進(jìn)一樣容易。標(biāo)準(zhǔn)關(guān)聯(lián)容器都提供雙向迭代器。list也有。
連續(xù)內(nèi)存容器(也叫做基于數(shù)組的容器)在一個或多個(動態(tài)分配)的內(nèi)存塊中保存它們的元素。如果一個新元素被查入或者已存元素被刪除,其他在同一個內(nèi)存塊的元素就必須向上或者向下移動來為新元素提供空間或者填充原來被刪除的元素所占的空間。這種移動影響了效率和異常安全。標(biāo)準(zhǔn)的連續(xù)內(nèi)存容器是vector、string和deque。非標(biāo)準(zhǔn)的rope也是連續(xù)內(nèi)存容器。
基于節(jié)點的容器在每個內(nèi)存塊(動態(tài)分配)中只保存一個元素。容器元素的插入或刪除只影響指向節(jié)點的指針,而不是節(jié)點自己的內(nèi)容。所以當(dāng)有東西插入或刪除時,元素值不需要移動。表現(xiàn)為鏈表的容器——比如list和slist——是基于節(jié)點的,所有的標(biāo)準(zhǔn)關(guān)聯(lián)容器也是(它們的典型實現(xiàn)是平衡樹)。非標(biāo)準(zhǔn)的散列容器使用不同的基于節(jié)點的實現(xiàn)。
1、vector
vector和數(shù)組類似,它擁有一段連續(xù)的內(nèi)存空間,并且起始地址不變,因此它能非常好的支持隨機(jī)存。词褂肹]操作符訪問其中的元素),但由于它的內(nèi)存空間是連續(xù)的,所以在中間進(jìn)行插入和刪除會造成內(nèi)存塊的拷貝(復(fù)雜度是O(n)),另外,當(dāng)該數(shù)組后的內(nèi)存空間不夠時,需要重新申請一塊足夠大的內(nèi)存并進(jìn)行內(nèi)存的拷貝。這些都大大影響了vector的效率。
vector不是一種數(shù)據(jù)類型,而只是一個類模板,可用來定義任意多種數(shù)據(jù)類型。vector類型的每一種都指定了其保存元素的類型。因此,vector和vector都是數(shù)據(jù)類型。
vector對象的定義和初始化
vectorv1;
vector保存類型為T的對象。默認(rèn)構(gòu)造函數(shù)v1為空。
vectorv2(v1);
v2是v1的一個副本。
vectorv3(n,i);
v3包含n個值為i的.元素。
vectorivec4(10, -1); // 10 elements, each initialized to -1
vectorsvec(10, "hi!"); // 10 strings, each initialized to "hi!"
vector的操作
v.empty()
如果v為空,則返回true,否則返回false。
v.size()
返回v中元素的個數(shù)。
v.push_back(t)
在v的末尾增加一個值為t的元素。
v[n]
返回v中位置為n的元素。
v1=v2
把v1的元素替換為v2中元素的副本。
v1==v2
如果v1與v2相等,則返回true。
!=, <, <=,>, >=
保持這些操作符慣有的含義。
向vector添加元素:
復(fù)制代碼 代碼如下:
string word;
vectortext; // empty vector
while (cin >> word) {
text.push_back(word); // append word to text
}
vector的下標(biāo)操作:
for (vector::size_type ix = 0; ix != ivec.size(); ++ix)
ivec[ix] = 0;
vector迭代器
每種容器都定義了一對命名為begin和end的函數(shù),用于返回迭代器。如果容器中有元素的話,由begin返回的迭代器指向第一個元素:
復(fù)制代碼 代碼如下:
vector::iterator iter = ivec.begin();
由end操作返回的迭代器指向vector的“末端元素的下一個”。通常稱為超出末端迭代器(off-the-end iterator),表明它指向了一個不存在的元素。如果vector為空,begin返回的迭代器與end返回的迭代器相同。
復(fù)制代碼 代碼如下:
for (vector::iterator iter = ivec.begin(); iter != ivec.end(); ++iter)
*iter = 0; // set element to which iter refers to 0
const_iterator
前面的程序用vector::iterator改變vector中的元素值。每種容器類型還定義了一種名為const_iterator的類型,該類型只能訪問容器內(nèi)元素,但不能改變其值。
復(fù)制代碼 代碼如下:
for (vector::const_iterator iter = text.begin(); iter != text.end(); ++ iter)
*iter = " "; // error: *iter is const
2、list
list是由數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表實現(xiàn)的,因此它的內(nèi)存空間可以是不連續(xù)的。因此只能通過指針來進(jìn)行數(shù)據(jù)的訪問,這個特點使得它的隨機(jī)存取變的非常沒有效率,需要遍歷中間的元素,搜索復(fù)雜度O(n),因此它沒有提供[]操作符的重載。但由于鏈表的特點,它可以以很好的效率支持任意地方的刪除和插入。
list::iterator與vector::iterator的一些不同:
復(fù)制代碼 代碼如下:
#include
#include
#include
using namespace std;
int main( void )
{
vectorv;
listl;
for (int i=0; i<8; i++) //往v和l中分別添加元素
{
v.push_back(i);
l.push_back(i);
}
cout << "v[2] = " << v[2] << endl;
//cout << "l[2] = " << l[2] << endl; //編譯錯誤,list沒有重載[]
cout << (v.begin() < v.end()) << endl;
//cout << (l.begin() < l.end()) << endl; //編譯錯誤,list::iterator沒有重載<或>
cout << *(v.begin() + 1) << endl;
vector::iterator itv = v.begin();
list::iterator itl = l.begin();
itv = itv + 2;
//itl = itl + 2; //編譯錯誤,list::iterator沒有重載+
itl++;itl++; //list::iterator中重載了++,只能使用++進(jìn)行迭代訪問。
cout << *itv << endl;
cout << *itl << endl;
return 0;
}
由于vector擁有一段連續(xù)的內(nèi)存空間,能非常好的支持隨機(jī)存取,因此vector::iterator支持“+”、“+=”、“<”等操作符。
而list的內(nèi)存空間可以是不連續(xù),它不支持隨機(jī)訪問,因此list::iterator則不支持“+”、“+=”、“<”等操作符運算,因此代碼20、26行會有編譯錯誤。只能使用“++”進(jìn)行迭代,例如代碼27行,使用兩次itl++來移動itl。還有l(wèi)ist也不支持[]運算符,因此代碼18行出現(xiàn)編譯錯誤。
總之,如果需要高效的隨即存取,而不在乎插入和刪除的效率,使用vector;如果需要大量的插入和刪除,而不關(guān)心隨即存取,則應(yīng)使用list。
vector擁有一段連續(xù)的內(nèi)存空間,因此支持隨機(jī)存取,如果需要高效的隨即存取,而不在乎插入和刪除的效率,使用vector。
list擁有一段不連續(xù)的內(nèi)存空間,因此支持隨機(jī)存取,如果需要大量的插入和刪除,而不關(guān)心隨即存取,則應(yīng)使用list。當(dāng)大部分插入和刪除發(fā)生在序列的頭或尾時可以選擇deque這種數(shù)據(jù)結(jié)構(gòu)。
【STL應(yīng)用論文】相關(guān)文章:
EVA的含義與應(yīng)用論文06-19
論文:色彩空間的應(yīng)用07-02
信息檢索與應(yīng)用論文04-11
應(yīng)用林業(yè)科技論文06-25
ERP開發(fā)的應(yīng)用論文04-13