【導(dǎo)讀】計(jì)算機(jī)科學(xué)與技術(shù)系。賽的第一名獲參加決賽的資格。作為資料保存下去，每年都得以增加更多更新的內(nèi)容。郁香寫(xiě)了模擬類部分，許嵩罡寫(xiě)了畫(huà)法幾何部分，周晉寫(xiě)了密碼部分，許松罡和沈揚(yáng)合寫(xiě)。現(xiàn)在大家使用的后由許嵩罡負(fù)責(zé)整理并增加了動(dòng)。本次修訂版有阮政、王洪剛和陳昊參與修訂，重寫(xiě)了。STL和組合數(shù)學(xué)部分，并增加了算法優(yōu)化專題。全書(shū)由徐本柱審校，

　　

【正文】 st_iterator find(const Keyamp。 key) const。 size_type count(const Keyamp。 key) const。 iterator lower_bound(const Keyamp。 key)。 const_iterator lower_bound(const Keyamp。 key) const。 iterator upper_bound(const Keyamp。 key)。 const_iterator upper_bound(const Keyamp。 key) const。 pairiterator, iterator equal_range(const Keyamp。 key)。 pairconst_iterator, const_iterator equal_range(const Keyamp。 key) const。 }。 下面是實(shí)例程序： include iostream include map using namespace std。 int main() { typedef mapint, double,lessint mid。 mid pairs。 (mid::value_type(15,))。 (mid::value_type(30,))。 (mid::value_type(15,))。 (mid::value_type(5,))。 (mid::value_type(10,))。 (mid::value_type(25,))。 (mid::value_type(5,))。 (mid::value_type(20,))。 (mid::value_type(15,))。 //ingore for key has exsit mid::iterator iter。 for(iter=()。iter!=()。iter++) coutiterfirst39。\t39。itersecondendl。 pairs[25]=。 pairs[40]=。 cout\nAfter subscript operations, pairs contains: \nkey\tvalue\n。 for(iter=()。iter!=()。iter++) coutiterfirst\titersecond\tendl。 coutendl。 14 system(PAUSE)。 return 0。 } 輸出為： 5 10 15 20 25 30 After subscript operations, pairs contains: key value 5 10 15 20 25 30 40 請(qǐng)按任意鍵繼續(xù) . . . 需要注意的是，在使用 map 的查抄 (find)函數(shù)的時(shí)候，如果該關(guān)鍵字沒(méi)找到則插入，即如果不 存在的話查找與插入同步完成。 【算法 Algorithm】 STL 的數(shù)據(jù)結(jié)構(gòu)很大程度上是為通用算法的建立而設(shè)計(jì)的。 STL 將具有很強(qiáng)通用性的算法如查找、排序、拷貝、反序、替換等許多基本算法寫(xiě)成通用函數(shù)，提供了方便、簡(jiǎn)捷的接口。例如，你不必花費(fèi)好大力氣去寫(xiě)一個(gè)排序算法還要校驗(yàn)它的正確性，你只要調(diào)用STL 中的 sort 函數(shù)即可。 Sort templateclass RanIt void sort(RanIt first, RanIt last)。 templateclass RanIt, class Pred void sort(RanIt first, RanIt last, Pred pr)。 sort 函數(shù)的第一個(gè)版本是將 operator排序，即由小到大排序。第二個(gè)版本是以所傳遞函數(shù)的返回值來(lái)確定順序。前兩個(gè)參數(shù)是要排序結(jié)構(gòu)的首元素和尾元素的迭代器。如果要將數(shù)組 int tt[20]前十個(gè)數(shù)由小到大排序則為： include algorithm include iostream using namespace std。 15 int tt[20]。 int main() { int i。 for(i=0。i20。i++) tt[i]=20i。 sort(tt,tt+10)。 for(i=0。i10。i++) couttt[i]“ ”； return 0。 } 如果要將 vectorint gg。由大到小排序： include iostream include vector include algorithm using namespace std。 vectorint gg。 bool sortspecial(int v1,int v2) { return v1v2。 } int main() { int i。 for(i=0。i20。i++) (i)。 sort((),(),sortspecial)。 for(i=0。i20。i++) coutgg[i]“ ”； } 要注意的是這個(gè)排序算法是不穩(wěn)定的，即具有相同鍵值的元素的最終位置于開(kāi)始的相對(duì)位置并不一定相同，例如 7, 7,5，如果按前一個(gè)值排序 則最終兩個(gè) pair 的最終位置無(wú)法確定。如果需要保持穩(wěn)定的話則可以使用 stable_sort 函數(shù)。 同時(shí)在 文件中由一個(gè)快排函數(shù) qsort，原型為： void qsort( void *base, size_t num, size_t width, int (__cdecl *pare )(const void *elem1, const void *elem2 ) )。 用法如下： include iostream 16 include cstdlib using namespace std。 int a[9]={1,2,4,5,8,12,23,4,3}。 int pare( const void *arg1, const void *arg2 )。 int main( ) { int i。 qsort( (void *)a, 9, sizeof(int), pare )。 /* Output sorted list: */ for(i=0。i9。i++) couta[i] 。 coutendl。 system(PAUSE)。 return 0。 } int pare( const void *arg1, const void *arg2 ) { return *((int *)arg2)*((int *)arg1)。 } 輸出為： 23 12 8 5 4 4 3 2 1 請(qǐng)按任意鍵繼續(xù) . . . 查找 : 有兩個(gè)版本，一個(gè)直接查找特定值的元素，另一個(gè)按照函數(shù)的返回值來(lái)查找。 templateclass InIt, class T InIt find(InIt first, InIt last, const Tamp。 val)。 include algorithm include iostream using namespace std。 int main() { const int ARRAY_SIZE = 8 。 int IntArray[ARRAY_SIZE] = { 1, 2, 3, 4, 4, 5, 6, 7 } 。 int *location 。 // stores the position of the first // matching element. int i 。 int value = 4 。 // print content of IntArray cout IntArray { 。 for(i = 0。 i ARRAY_SIZE。 i++) 17 cout IntArray[i] , 。 cout } endl 。 // Find the first element in the range [first, last + 1) // that matches value. location = find(IntArray, IntArray + ARRAY_SIZE, value) 。 //print the matching element if any was found if (location != IntArray + ARRAY_SIZE) // matching element found cout First element that matches value is at location location IntArray endl。 else // no matching element was // found cout The sequence does not contain any elements with value value endl 。 system(PAUSE)。 return 0。 } Program Output is: IntArray { 1, 2, 3, 4, 4, 5, 6, 7, } First element that matches 4 is at location 3 templateclass InIt, class Pred InIt find_if(InIt first, InIt last, Pred pr)。 include algorithm include iostream using namespace std。 // returns true if n is an odd number int IsOdd( int n) { return n % 2 。 } int main() { const int ARRAY_SIZE = 8 。 int IntArray[ARRAY_SIZE] = { 1, 2, 3, 4, 4, 5, 6, 7 } 。 int *location 。 // stores the position of the first // element that is an odd number int i 。 // print content of IntArray cout IntArray { 。 for(i = 0。 i ARRAY_SIZE。 i++) cout IntArray[i] , 。 cout } endl 。 // Find the first element in the range [first, last 1 ] 18 // that is an odd number location = find_if(IntArray, IntArray + ARRAY_SIZE, IsOdd) 。 //print the location of the first element // that is an odd number if (location != IntArray + ARRAY_SIZE) // first odd element found cout First odd element *location is at location location IntArray endl。 else // no odd numbers in the range cout The sequence does not contain any odd numbers endl