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 的容器，迭代器，算法基本知識(shí)與基本理論， 使用方式, 并拿出幾 個(gè)典型的容器，迭代器，算法進(jìn)行講述，并分析出特性及應(yīng)注意的地方。為理解,使用 stl 作好了鋪墊,最后舉實(shí)例說明了如何在編程中使用 stl 的容器，迭代器，算法進(jìn)行程序設(shè)計(jì) 關(guān)鍵詞：標(biāo)準(zhǔn)模板庫, 容器，算法，迭代器中圖分類號(hào)：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ì)變算法.另一種是按操作的對(duì)象可分為數(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 迭代器迭代器是一種行為類似指針的對(duì)象, 而指針的各種行為中最常見也最重要的便是內(nèi)容 提領(lǐng)和成員訪問.因些迭代器重要編程工作就是對(duì) operator*和 operator-進(jìn)行重載工作迭代器的主要內(nèi)容就是迭代器型別, 迭代器的型別有五種:value type, difference type, reference, iterator category.第一種型別 value type 表示迭代器所指類型的類型.第二種型別 difference type 表示兩個(gè)迭代器之間的距離的類型. 第三種型別 reference type 表示是否可改 變所指對(duì)象的內(nèi)容.第四種類型表示所指之物的地址的類型.第五種類型表示迭代器的類型， 這個(gè)反映了迭代器的特性.13 stl 的應(yīng)用3.1 stl 的常用方式stl 中全是模板的實(shí)現(xiàn)方式，所以使用時(shí)要特化, 指明類型. 對(duì)于一般層次的程序員來 說, 平時(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)式容器.它是鍵值對(duì)的集合.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è)鍵值對(duì)，所以可來存放更多的信息，且效率高，所以也是程序員常用的容器之一.3.1.3 iterator, const_iterator, reverse_iterator 以及 const_reverse_iteratorstl 中的所有標(biāo)準(zhǔn)容器都提供了 4 種迭代器類型.對(duì)容器類 container而言，iterator 類型的功效相當(dāng)于 t*, 而 const_iterator 則相當(dāng)于 const t*.對(duì)一個(gè) iterator 或者 const_iterator 進(jìn)行遞增則可以移動(dòng)到容器中的下一個(gè)元素，通過這種方式可以從容器的頭部一直遍歷到尾部.reverse_iterator 與 const_reverse_iterator 同樣分別對(duì)應(yīng)于 t*和 const t*, 所不同的是， 對(duì) 這兩個(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 不可以改變?cè)貎?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 可用來存放套接字和地址元素對(duì)，這樣也便于查找, 在實(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ā)送.對(duì)于客戶端，控制臺(tái)與服務(wù)器端的連接及 ip 地址， 可用 map 來保存, 對(duì)于連接的查找可用 find 來查找。結(jié)構(gòu)圖如圖 2.clientcontrolserver圖 2 程序結(jié)構(gòu)圖4.2 程序的基本流程, 基本代碼服務(wù)器的存入鏈接與 ip 的變量定義為:map sockip;控制臺(tái)發(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 的三大主要部分容器，算法，迭代器基本知識(shí)和特性,接著分析了 stl 的常用容器，算法，迭代器的使用方式及范圍，最后通過一個(gè)實(shí)例介始了在實(shí)際編程中 使用 stl 的方法.這樣就能更加深刻地認(rèn)識(shí) 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