STL 在編程中的應(yīng)用.doc

精品論文stl 在編程中的應(yīng)用高慶，張能立 武漢理工大學(xué)計(jì)算機(jī)學(xué)院, 武漢(430073) e-mail: 摘要:stl 作為 c+標(biāo)準(zhǔn)的重要一部分，在很大程序上改變了 c+程序的結(jié)構(gòu)與使用方式，stl 大大提高了軟件開發(fā)的效率，降低了開發(fā)成本成維護(hù)成本，降低了開發(fā)時(shí)間與維護(hù)時(shí)間， 提高了軟件穩(wěn)定性與可移植性。隨著軟件行業(yè)的迅速發(fā)展, stl 在 c+程序中得到了廣泛的 應(yīng)用。本文講述了 stl 的容器，迭代器，算法基本知識與基本理論， 使用方式, 并拿出幾 個(gè)典型的容器，迭代器，算法進(jìn)行講述，并分析出特性及應(yīng)注意的地方。為理解,使用 stl 作好了鋪墊,最后舉實(shí)例說明了如何在編程中使用 stl 的容器，迭代器，算法進(jìn)行程序設(shè)計(jì) 關(guān)鍵詞：標(biāo)準(zhǔn)模板庫, 容器，算法，迭代器中圖分類號：tp3131 stl 簡介stl(標(biāo)準(zhǔn)模板庫)是一個(gè)可復(fù)用組件庫，也是一個(gè)包算法與數(shù)據(jù)結(jié)構(gòu)的軟件框架. stl 在1994 年走入 c+標(biāo)準(zhǔn),使得原本即將推出的 c+標(biāo)準(zhǔn)延遲 4 年問世, 由于 stl 包含很多高效 穩(wěn)定的數(shù)據(jù)結(jié)構(gòu)與算法, 所以在程序開發(fā)人員中得到了廣泛的使用1.stl 的實(shí)現(xiàn)版本主要有五種，分別為 hp 實(shí)現(xiàn)版本，p.j.plauger 實(shí)現(xiàn)版本,rouge wave 實(shí)現(xiàn)版本,stlport 實(shí)現(xiàn)版本,sgi stl 實(shí)現(xiàn)版本，它們所提供的功能一樣，只是版權(quán)及代碼的 風(fēng)格不同stl 主要分容器，算法, 迭代器三大塊。容器與迭代器是以類的形式提供，容器類包含 很多數(shù)據(jù)結(jié)構(gòu)及其上的操作.算法是一些常用的操作的集合，包含排序，查找，拷貝，數(shù)學(xué) 運(yùn)算等. 迭代器是 stl 的關(guān)鍵部分，它在容器與算法之間起橋梁作用, 類似于 c 語言中的指 針, 但比指針復(fù)雜2 容器，算法，迭代器2.1 容器stl 的容器主要有兩種分類方式, 一種是按容器的規(guī)范來分,可分為標(biāo)準(zhǔn)容器與非標(biāo)準(zhǔn) 容器.另一種可按照容器內(nèi)部的存儲(chǔ)特性來分，可分為序列式容器與關(guān)聯(lián)式容器. 所以 stl 容器一般分為以下四類:標(biāo)準(zhǔn) stl 序列容器:vector, string, deque 和 list. 標(biāo)準(zhǔn) stl 關(guān)聯(lián)容器:set, multiset, map 和 multimap. 非標(biāo)準(zhǔn)序列容器: slist 和 rope.非標(biāo)準(zhǔn)的關(guān)聯(lián)容器 hash_set,hash_multiset. hash_map 和 hash_multimap.22.2 算法stl 的算法也主要有兩種分類方式，一種是按是否改變?nèi)萜髦袩o素內(nèi)容來分，可分為質(zhì) 變算法與非質(zhì)變算法.另一種是按操作的對象可分為數(shù)值算法,基本算法，set 相關(guān)算法,heap 算法, 常用操作算法. 下面以第三種分類法介紹 stl 的算法:數(shù)值算法有 accumute, adjacent_difference, inner_product, partial_sum, power, iota.- 6 -基本算法有 equal, fill, fill_n, iter_swap, lexicographical_compare, max, min, mismatch,swap, copy, copy_backward.set 相關(guān)算法有 set_union, set_intersection, set_difference, set_symmetric_difference.heap 算法有 make_heap, pop_heap, push_heap, sort_heap常用操作算法有 :adjacent_find, count, count_if, find, find_if, find_end, find_first_of, for_each, generate, generate_n, includes, max_element, merge, min_element, partition, remove, remove_copy, remove_if, remove_copy_if, replace, replace_copy, replace_if, replace_copy_if, reverse, reverse_copy, rotate, rotate_copy, search, search_n, swap_ranges, transform, unique, unique_copy, lower_bound, upper_bound, binary_search, next_permutation, prev_permutation,random_shuffle, partial_sort, partial_sort_copy.等2.3 迭代器迭代器是一種行為類似指針的對象, 而指針的各種行為中最常見也最重要的便是內(nèi)容 提領(lǐng)和成員訪問.因些迭代器重要編程工作就是對 operator*和 operator-進(jìn)行重載工作迭代器的主要內(nèi)容就是迭代器型別, 迭代器的型別有五種:value type, difference type, reference, iterator category.第一種型別 value type 表示迭代器所指類型的類型.第二種型別 difference type 表示兩個(gè)迭代器之間的距離的類型. 第三種型別 reference type 表示是否可改 變所指對象的內(nèi)容.第四種類型表示所指之物的地址的類型.第五種類型表示迭代器的類型， 這個(gè)反映了迭代器的特性.13 stl 的應(yīng)用3.1 stl 的常用方式stl 中全是模板的實(shí)現(xiàn)方式，所以使用時(shí)要特化, 指明類型. 對于一般層次的程序員來 說, 平時(shí)使用較多的是容器。容器也成為程序員的主要幫手。下面介紹一下一些容器，迭代 器，算法的特性.3.1.1 vectorvector 容器就像 c 語言中的數(shù)組, 其元素存放在連續(xù)的空間里，但它的空間是可以動(dòng)態(tài) 伸縮的,即隨著元素的增加而增加.這一點(diǎn)上又不同于普通的數(shù)組.vector 的的常用成員函數(shù)有 begin, end, size, capacity, empty, front, back, push_back , pop_back, erase, resize, clear, 這些含蓋了 vector 的基本操作.vector 支持隨機(jī)存取，所以 vector 支持的是 random access iterator.就像數(shù)組在程序設(shè)計(jì)中的廣泛性一樣，程序員在使用 stl 時(shí)，vector 容器也是程序員常 用的一種容器3.1.2 mapmap 是一種關(guān)聯(lián)式容器.它是鍵值對的集合.map 類型通常可理解為關(guān)聯(lián)數(shù)組：可使用 鍵作為下標(biāo)來獲取一個(gè)值, 正如內(nèi)置數(shù)組類型一樣.而關(guān)聯(lián)的本質(zhì)在于元素的值與某個(gè)特定 的鍵相關(guān)聯(lián), 而并非通過元素在數(shù)組中的位置來獲取.3.map 的的特性是， 所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)被排序.map 的所有元素都是 pair, 同時(shí)擁有實(shí)值(value)和鍵值(key).pair 的第一元素被視為鍵值, 第二元素被視為實(shí)值.map 不 允許兩個(gè)元素?fù)碛邢嗤逆I值3.map 的常見操作有 key_comp, value_comp, begin, end, rbegin, rend, empty, size, max_size,swap, insert, erase, clear, find, count, lower_bound, upper_bound, equal_range.因?yàn)?map 的每個(gè)元素都是一個(gè)鍵值對，所以可來存放更多的信息，且效率高，所以也是程序員常用的容器之一.3.1.3 iterator, const_iterator, reverse_iterator 以及 const_reverse_iteratorstl 中的所有標(biāo)準(zhǔn)容器都提供了 4 種迭代器類型.對容器類 container而言，iterator 類型的功效相當(dāng)于 t*, 而 const_iterator 則相當(dāng)于 const t*.對一個(gè) iterator 或者 const_iterator 進(jìn)行遞增則可以移動(dòng)到容器中的下一個(gè)元素，通過這種方式可以從容器的頭部一直遍歷到尾部.reverse_iterator 與 const_reverse_iterator 同樣分別對應(yīng)于 t*和 const t*, 所不同的是， 對 這兩個(gè)迭代器進(jìn)行遞增的效果是由容器的尾部反向遍歷容器頭部2圖 1 反映了 4 種 iterator 之間的轉(zhuǎn)換關(guān)系.箭頭表示轉(zhuǎn)化關(guān)系.從中可以發(fā)現(xiàn)不能從const_iterator 轉(zhuǎn)化為 iterator, 也不能從 const_reverse_iterator 轉(zhuǎn)化為 reverse_iterator.以為選迭 代器的類型時(shí)優(yōu)先選擇 iterator,以免類型無法相互匹配。圖 1 4 種迭代器的轉(zhuǎn)換關(guān)系3.1.4 find 算法find 算法是 stl 中較為常見的一種算法，它是循環(huán)查找一個(gè)區(qū)間first, last內(nèi)的所有元 素, 找出第一個(gè)與待查元素相等的元素.如果找到，就返回一個(gè) inputiterator 指向該元素, 否 則返回迭代器 last.其函數(shù)原型為:template inputiterator find(inputiterator first, inputiterator last, const t& value);3.1.5 for_each 算法for_each 的函數(shù)原型為 template function for_each(inputiterator first, inputiterator last, function f);此函數(shù) f 會(huì)施行于first, last區(qū)間內(nèi)的每一個(gè)元素身上。f 不可以改變元素內(nèi)容， 因?yàn)?first和 last 都是 inputiterators，不保證接受賦值行為,3.1.6 copy 算法copy 的函數(shù)原型為template inline outputiterator copy(inputiterator first, inputiterator last, outputiterator result)copy 是一個(gè)常常被調(diào)用的函數(shù)。由于 copy 進(jìn)行的是復(fù)制操作，而復(fù)制操作不外乎運(yùn)用assignment operator 或 copy constructor, 但是某些元素型別擁有的是 trivial assignment operator,因些能夠使用內(nèi)存直接復(fù)制行為(比如 c 中的 memmove 或 memcpy)， 便能夠節(jié)省大量時(shí)間3.2 stl 的應(yīng)用行業(yè)stl 作為一種通用的程序組件庫,幾乎任何行業(yè)都能應(yīng)用它來提高開發(fā)效率, stl 已廣 泛應(yīng)用在通信行業(yè)，網(wǎng)絡(luò)游戲, windows 與 linux 應(yīng)用程序設(shè)計(jì)中, 大大提高了開發(fā)的時(shí)間， 而且這些穩(wěn)定的組件庫的應(yīng)用，相比自已親手寫的函數(shù)來說，在穩(wěn)定性與可移植性方面要 好 很多.比如在通信及網(wǎng)絡(luò)游戲行業(yè)中，map 可用來存放套接字和地址元素對，這樣也便于查找, 在實(shí)際中的效果好.而 copy 算法常用在消息包的組合與解析之中,用起來非常方便，不和自已 重新開發(fā)。又比如在搜索行業(yè)，哈希表與紅黑樹就用得較好，這些容器本身實(shí)現(xiàn)就非常復(fù)雜，查找 效率很高。如果是自已開發(fā)這些東西的話，僅僅手工實(shí)現(xiàn)這數(shù)據(jù)結(jié)構(gòu)就要花很多時(shí)間， 更不談手工實(shí)現(xiàn)的代碼的穩(wěn)定性了，而且如果不穩(wěn)定的話，組后期的維護(hù)也帶來了麻煩。 由此可看出 stl 的重要性了較常用的容器 vector, list, stack, pair 會(huì)廣泛用來各個(gè)行業(yè)之中，而常用算法find, for_each,count, reverse, sort, search 也是常用在日常程序設(shè)計(jì)之中4 一個(gè)實(shí)例本節(jié)以一個(gè)實(shí)例展示 stl 在網(wǎng)絡(luò)編程中的應(yīng)用，會(huì)用到 vector, map 容器，find， for_each算法.從中也可看出基本 stl 的使用方式.4.1 程序的應(yīng)用結(jié)構(gòu)程序分為服務(wù)器端, 客戶端, 控制端三個(gè)部分，服務(wù)器與客戶關(guān)可以互通基本消息，而 控制端則控制服務(wù)器向客戶端的消息發(fā)送.對于客戶端，控制臺與服務(wù)器端的連接及 ip 地址， 可用 map 來保存, 對于連接的查找可用 find 來查找。結(jié)構(gòu)圖如圖 2.clientcontrolserver圖 2 程序結(jié)構(gòu)圖4.2 程序的基本流程, 基本代碼服務(wù)器的存入鏈接與 ip 的變量定義為:map sockip;控制臺發(fā)送一個(gè)含有客戶端 ip 的消息到服務(wù)器后(此 ip 的變量為 srcip, 可使用 map 的基本操作查找此 ip 的客戶端與服務(wù)器的套接字，從而可以向客戶端發(fā)送消息.查找的代碼為:iterator first = sockip.begin(); iterator last = sockip.end(); for(;first!=last&first-second!=srcip;first +)客戶端的姓名與 ip 的變量定義為: map nameip;可通過 find 算法查找是否 nameip 中是否有些用戶, 從而判斷該客戶是否在線,查找的代碼為iterator first = nameip.begin();iterator last = nameip.end();iterator clientiterator = find(first, last, make_pair(srcname, strip);還可使用 for_each 在輸出在線客戶的姓名，地址信息. template struct displaymapvoid operator()(const t& x)cout x.first “” x.second endl;iterator first = nameip.begin();iterator last = nameip.end();for_each(first, last, displaymap);5 總結(jié)本文開始介紹了 stl 的三大主要部分容器，算法，迭代器基本知識和特性,接著分析了 stl 的常用容器，算法，迭代器的使用方式及范圍，最后通過一個(gè)實(shí)例介始了在實(shí)際編程中 使用 stl 的方法.這樣就能更加深刻地認(rèn)識 stl 的基本理論及使用方法.stl 作為一個(gè) c+ 中重要的一部分，學(xué)習(xí) stl 也成為程序員的一門重要的課程參考文獻(xiàn)1候捷. stl 源碼剖析,華中科技大學(xué)出版社,2002.6 2潘愛民，陳銘，鄒開紅譯.effectivie stl 中文版, 2006.4 3李師賢，蔣愛軍，梅曉勇，林瑛譯.c+ primer 中文版, 從民郵電出版社, 2008.7use stl in program desinggao qing，zhang nenglicompute