第五章C＋＋與STL入門

1、第五章 C與STL入門5.1 從C到C C版的“ab程序”： #includeint main() int a, b;while(scanf(%d%d, &a, &b) = 2) printf(%dn, a+b); return 0; stdio.h cstdio string.h cstringmath.h cmathctype.h cctype 5.1 從C到C#include#includeusing namespace std;const int maxn = 100 + 10;int Amaxn;int main() long long a, b; while(cin

2、 a b) cout min(a,b) a的含義是從標(biāo)注輸入中讀取a，它的返回值是一個“已經(jīng)讀取了a的新流”，然后從這個新流中繼續(xù)讀取b。 如果流已經(jīng)讀完，while循環(huán)將退出。 注意：C流 最大缺點(diǎn)就是運(yùn)行太慢，以至于很多競賽題目會在題面中的顯著位置注明：本題的輸入量很大，請不要使用C的流輸入 5.1 從C到C#includeusing namespace std;void swap2(int& a, int& b) int t = a; a = b; b = t; int main() int a = 3, b = 4; swap2(a, b); cout a b n; r

3、eturn 0; 使用引用交換兩個變量 ：如果在參數(shù)名之前加一個“&”符號，就表示這個參數(shù)按照傳引用（by reference）的方式傳遞，而不是C語言里的傳值（by value）方式傳遞。 這樣，在函數(shù)內(nèi)改變參數(shù)的值,也會修改到函數(shù)的實(shí)參。 5.1 從C到C#include#include#includeusing namespace std;int main() string line; while(getline(cin, line) int sum = 0, x; stringstream ss(line); while(ss x) sum += x; cout sum n;

4、return 0; String相關(guān)的函數(shù)和運(yùn)算符 用getline函數(shù)讀一行數(shù)據(jù) 創(chuàng)建一個“字符串流”ss 提示：可以把string作為流進(jìn)行讀寫，定義在sstream頭文件中。雖然string sstream都很方便，但string很慢sstream更慢，應(yīng)謹(jǐn)慎使用 。5.1 從C到C#includeusing namespace std;struct Point int x, y; Point(int x=0, int y=0):x(x),y(y) ;Point operator + (const Point& A, const Point& B) return Poin

5、t(A.x+B.x, A.y+B.y);ostream& operator (ostream &out, const Point& p) out ( p.x , p.y ); return out; int main() Point a, b(1,2); a.x = 3; cout a+b n; return 0; C中的結(jié)構(gòu)體： C中的結(jié)構(gòu)體除了可以擁有成員變量（用a.x的方式訪問）之外，還可以擁有成員函數(shù)。5.1 從C到C回顧第4章中介紹過的sum函數(shù)：int sum(int* begin, int* end) int *p = begin; int ans = 0

6、; for(int *p = begin; p != end; p+) ans += *p; return ans; 這個函數(shù)沒有錯誤，但比較局限只能求整數(shù)數(shù)組的和，不能求double數(shù)組的和，更不能求Point數(shù)組的和。 這樣就可以用sum函數(shù)給double數(shù)組和Point數(shù)組求和了 templateT sum(T* begin, T* end) T *p = begin; T ans = 0; for(T *p = begin; p != end; p+) ans = ans + *p; return ans; 5.1 從C到Cint main() double a = 1.1, 2.2,

7、 3.3, 4.4; cout sum(a, a+4) n; Point b = Point(1,2), Point(3,4), Point(5,6), Point(7,8) ; cout sum(b, b+4) n; return 0; 用sum函數(shù)給double數(shù)組和Point數(shù)組求和：5.1 從C到CtemplateT sum(T* begin, T* end) T *p = begin;T ans = 0;for(T *p = begin; p != end; p+)ans = ans + *p;return ans; 上述sum函數(shù)和第4章中寫的有點(diǎn)不同：把“ans*p”改成了“an

8、s=ans*p”。 這樣做的原因是Point結(jié)構(gòu)體中只定義了“”運(yùn)算符，沒有定義“”。 template struct Point T x, y;Point(T x=0, T y=0):x(x),y(y) ;template Point operator + (const Point& A, const Point& B) return Point(A.x+B.x, A.y+B.y); template ostream& operator (ostream &out, const Point& p) out ( p.x , p.y );return ou

9、t; 把Point變成模板“+”和“”的代碼也稍加改變 利用修改過的代碼同時使用int型和double 型的Point ：int main() Point a(1,2), b(3,4); Point c(1.1,2.2), d(3.3,4.4); cout a+b c+d n; return 0; 5.1 從C到C5.2 STL初步 STL是指C的標(biāo)準(zhǔn)模板庫（Standard Template Library）。 它很好用，但也很復(fù)雜。 本節(jié)將介紹STL中的一些常用算法和容器，在后面的章節(jié)中還會繼續(xù)介紹本節(jié)沒有涉及的其他內(nèi)容。 大理石大理石在哪兒在哪兒 #include#include usi

10、ng namespace std; const int maxn = 10000;int main() int n, q, x, amaxn, kase = 0; while(scanf(“%d%d”, &n, &q) = 2 & n) printf(“CASE# %d:n”, +kase); for(int i = 0; i n; i+) scanf(“%d”, &ai); sort(a, a+n); /排序 while(q-) scanf(%d, &x); int p = lower_bound(a, a+n, x) - a; /在已排序數(shù)組a中尋找

11、x if(ap = x) printf(%d found at %dn, x, p+1); else printf(%d not foundn, x); return 0; 5.2 STL初步 sort是一個模板函數(shù)，可以對任意對象進(jìn)行排序。因此可以省略一個compare函數(shù)，比第4章中的排序代碼簡單很多。 不定長數(shù)組：vectorvector就是一個不定長數(shù)組。 不僅如此，它把一些常用操作“封裝”在了vector類型內(nèi)部。例如，若a是一個vector，可以用a.size( )讀取它的大小a.resize( )改變大小，a.push_back( )向尾部添加元素，a.pop_back( )刪除

12、最后一個元素。 vector是一個模板類，所以需要用vectora或者vectorb這樣的方式來聲明一個vector。 Vector是一個類似于inta的整數(shù)數(shù)組，而vector就是一個類似于stringa 的字符串?dāng)?shù)組。5.2 STL初步 5.2 STL初步 集合：set集合與映射也是兩個常用的容器。 set就是數(shù)學(xué)上的集合每個元素最多只出現(xiàn)一次。和sort一樣，自定義類型也可以構(gòu)造set，但同樣必須定義“小于”運(yùn)算符。 5.2 STL初步 映射：mapmap就是從鍵（key）到值（value）的映射。 因?yàn)橹剌d了 運(yùn)算符，map像是數(shù)組的“高級版”。 例如可以用一個mapmonth_nam

13、e來表示“月份名字到月份編號”的映射，然后用month_nameJuly=7這樣的方式來賦值 5.2 STL初步 棧、 隊(duì)列與優(yōu)先隊(duì)列STL還提供3種特殊的數(shù)據(jù)結(jié)構(gòu)：棧、 隊(duì)列與優(yōu)先隊(duì)列。 所謂棧，就是符合“后進(jìn)先出”（Last In First Out，LIFO）規(guī)則的數(shù)據(jù)結(jié)構(gòu)，有PUSH和POP兩種操作，其中PUSH把元素壓入“棧頂”，而POP從棧頂把元素“彈出”，如圖所示。 5.3 應(yīng)用：大整數(shù)類 大整數(shù)類BigInteger：結(jié)構(gòu)體BigInteger可用于儲存高精度非負(fù)整數(shù)。struct BigInteger static const int BASE = 100000000; st

14、atic const int WIDTH = 8; vector s; BigInteger(long long num = 0) *this = num; /構(gòu)造函數(shù) BigInteger operator = (long long num) /賦值運(yùn)算符 s.clear(); do s.push_back(num % BASE); num /= BASE; while(num 0); return *this; BigInteger operator = (const string& str) /賦值運(yùn)算符 s.clear(); int x, len = (str.length()

15、 - 1) / WIDTH + 1; for(int i = 0; i = s.size() & i = b.s.size() break; int x = g; if(i s.size() x += si; if(i (const BigInteger& b) const if(s.size() != b.s.size() return s.size() = 0; i-) if(si != b.si) return si (const BigInteger& b) const return b *this; bool operator = (const BigInte

16、ger& b) const return !(b = (const BigInteger& b) const return !(*this b); bool operator != (const BigInteger& b) const return b *this | *this b; bool operator = (const BigInteger& b) const return !(b *this) & !(*this b) 5.5 習(xí)題 類別 題號 題目名稱（英文） 備注例題5-1 UVa10474 Where is the Marble? 排序和查找例題5-2 UVa101 The Blocks Problem vector的使用例題5-3 UVa10815 Andys First Dictionary set的使用例題5-4 UVa156 Ananagrams map的使用例題5-5 UVa12096 The SetStack Comput