?? 筆記整理：stl in acm--greedy hawk 焚書煲粥.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0036)http://yxhome.bokee.com/5057457.html -->
<HTML><HEAD><TITLE>筆記整理：STL in ACM--Greedy Hawk | 焚書煲粥</TITLE>
<META http-equiv=Content-Type content="text/html; charset=GBK">
<META http-equiv=Pragma content=no-cache>
<META http-equiv=Cache-Control content=no-cache>
<META http-equiv=Expires content=0>
<META
content="5.13 訪問量突破20000筆記整理：STL in ACMTOJ Weekly Contest 1 總結 博客 博客中國 博客動力 blog blogdriver blogger 中國"
name=description>
<META
content="Greedy Hawk | 焚書煲粥 5.13 訪問量突破20000筆記整理：STL in ACMTOJ Weekly Contest 1 總結 博客 博客中國 博客動力 blog blogdriver blogger 中國"
name=keywords><LINK href="筆記整理：STL in ACM--Greedy Hawk 焚書煲粥.files/diary.css"
type=text/css rel=stylesheet>
<SCRIPT language=JavaScript
src="筆記整理：STL in ACM--Greedy Hawk 焚書煲粥.files/UBB.js"></SCRIPT>
<SCRIPT src="筆記整理：STL in ACM--Greedy Hawk 焚書煲粥.files/blog.js"
type=text/javascript></SCRIPT>
<META content="MSHTML 6.00.2900.2802" name=GENERATOR></HEAD>
<BODY>
<DIV id=container>
<DIV id=header>
<H1 class=title><A href="http://yxhome.bokee.com/index.html">Greedy Hawk |
焚書煲粥</A></H1></DIV>
<DIV id=category><A title=上一篇 href="http://yxhome.bokee.com/5047229.html">5.13
訪問量突破20000</A>- -| <A href="http://yxhome.bokee.com/index.html">回首頁</A> | <A
href="http://yxhome.bokee.com/catalog_2006.html">2006年索引</A> | - -<A title=下一篇
href="http://yxhome.bokee.com/5086024.html">TOJ Weekly Contest 1 總結</A></DIV>
<DIV class=entity>
<H2 class=diaryTitle>筆記整理：STL in
ACM</H2>
<P>
<P><FONT face=宋體,sans-serif>C++筆記整理（2006.5.15）</FONT></P>
<P><FONT face=宋體,sans-serif>昨天晚上聽了RoBa講的< STL in ACM
>，感覺收獲頗豐。此前一直想自己看STL，但每每看到那玄之又玄的術語，如“容器”，“迭代器”等等，總是看得云里霧里，昨天聽他一講，有恍然大悟的感覺。<BR>把筆記整理了一下，以后便于以后查閱。</FONT></P>
<P><FONT face=宋體,sans-serif>STL : Standard Template Library
標準模版庫<BR>//有人說：這是給C++中最激動人心的東西，取了一個最無聊的名字。</FONT></P>
<P><FONT face=宋體,sans-serif>重要的概念：</FONT></P>
<P><FONT face=宋體,sans-serif>容器(container): <BR><VECTOR /><LIST /><SET
/><MAP>…<BR>//容器一詞聽上去很高深，其實說白了也是類似于對象的東西，但又和對象有點區別。<BR>迭代器(iterator):
指針<BR>//這個名詞就更玄了，其實就是類似于指針的東西。</MAP></FONT></P>
<P><FONT face=宋體,sans-serif><VECTOR />內部實現: 數組 //
就是沒有固定大小的數組，vector直接翻譯是向量的意思<BR>vector <T, alloc="" /><BR>// T
就是數據類型，Alloc是關于內存的一個什么東西，RoBa沒有仔細講，一般是使用默認參數。<BR>支持操作:<BR>begin(),
//取首個元素，返回一個iterator<BR>end(), //取末尾（最后一個元素的下一個存儲空間的地址）<BR>size(),
//就是數組大小的意思<BR>clear(), //清空<BR>empty(), //判斷vector是否為空<BR>[ ]
//很神奇的東東，可以和數組一樣操作<BR>//舉例： vector <INT />a;
//定義了一個vector<BR>//然后我們就可以用a[i]來直接訪問a中的第i + 1個元素！和數組的下標一模一樣！<BR>push_back(),
pop_back() //從末尾插入或彈出<BR>insert() O(N)
//插入元素，O(n)的復雜度<BR>erase() O(N)
//刪除某個元素，O(n)的復雜度<BR>可以用于數組大小不定且空間緊張的情況</FONT></P>
<P><FONT face=宋體,sans-serif>Sample: TOJ1743 King’s Treasure
//這題如果直接開數組的話，需要開到一個240,000 * 240,000的二維數組<BR>代碼：<BR>#include <CSTDIO
/><BR>#include <VECTOR /><BR>using namespace std;</FONT></P>
<P><FONT face=宋體,sans-serif>vector <INT />a[240010]; //一個vector組成的數組！</FONT></P>
<P><FONT face=宋體,sans-serif>int main()<BR>{<BR> int
cases,n,i,t,head,tail,src,pans;<BR> scanf("%d",&cases);<BR> while
(cases--) {<BR> scanf("%d",&n);<BR> for (i = 1 ; i
<= n ; i++) a[i].clear();<BR> for (i = 2 ; i <= n ; i++)
{<BR> scanf("%d",&t);<BR> a[i].push_back(t);<BR> a[t].push_back(i);<BR> }<BR>............</FONT></P>
<P><FONT face=宋體,sans-serif>Iterator用法舉例:<BR>#include <VECTOR /><BR>#include
<CSTDIO /><BR>using namespace std;<BR>int main()<BR>{<BR> int
n,i;<BR> vector <INT />vi; //類似于我們定義一個數組，同 int vi[1000];
但vector的大小是自動調整的<BR> vector <INT />::iterator itr;
//兩個冒號，很怪的定義方式，但就是這么定義的<BR> while (scanf("%d",&n) !=
EOF)<BR> vi.push_back(n);<BR> for (i = 0 ; i < vi.size() ;
i++)<BR> printf("%d\n",vi[i]);<BR> for (itr = vi.begin() ; itr
!= vi.end() ; itr++)
//也支持++操作<BR> printf("%d\n",*itr);<BR> return
0; <BR>}</FONT></P>
<P><FONT face=宋體,sans-serif><DEQUE />類似<VECTOR />
//雙端隊列，兩頭都支持進出<BR>支持push_front()和pop_front() <BR><STACK />是<VECTOR
/>的精簡版:) //棧，只支持從末尾進出<BR>支持push(), pop(), top()<BR><QUEUE />是<DEQUE
/>的精簡版 //單端隊列，就是我們平時所說的隊列，一頭進，另一頭出<BR>支持push(), pop(), front(),
back()</FONT></P>
<P><FONT face=宋體,sans-serif><LIST />內部實現: 雙向鏈表
//作用和vector差不多，但內部是用鏈表實現<BR>list<T, alloc="" /> <BR>支持操作:<BR>begin(), end(),
size(), clear(), empty()<BR>push_back(), pop_back() //從末尾插入或刪除元素
<BR>push_front(), pop_front() <BR>insert() O(1)
//鏈表實現，所以插入和刪除的復雜度的O(1)<BR>erase() O(1)<BR>sort() O(nlogn),不同于<ALGORITHM
/>中的sort<BR>//不支持[ ]操作！</FONT></P>
<P><FONT face=宋體,sans-serif><SET />內部實現: 紅黑樹 //Red-Black
Tree，一種平衡的二叉排序樹<BR>set<KEY, alloc="" compare,="" />
//又是一個Compare函數，類似于qsort函數里的那個Compare函數，作為紅黑樹在內部實現的比較方式<BR>insert()
O(logn)<BR>erase() O(logn)<BR>find() O(logn) 找不到返回a.end()<BR>lower_bound()
O(logn) 查找第一個不小于k的元素<BR>upper_bound() O(logn) 查找第一個大于k的元素<BR>equal_range()
O(logn) 返回pair<LOWER,UPPER /></FONT></P>
<P><FONT face=宋體,sans-serif><MULTISET />允許重復元素的<SET /></FONT></P>
<P><FONT face=宋體,sans-serif><SET />的用法及Compare函數示例:<BR>struct SS {int
x,y;};<BR>struct ltstr { <BR> bool operator() (SS a, SS b)<BR> {return
a.x < b.x;} //注意，按C語言習慣，double型要寫成這樣：return a.x < b.x ? 1 :
0;<BR>};<BR>int main() <BR>{ <BR> set <SS, ltstr=""
/>st;<BR> …<BR>}</FONT></P>
<P><FONT face=宋體,sans-serif><MAP>內部實現: pair<KEY,VALUE />組成的紅黑樹
//map中文意思：印射！！<BR>map<KEY, alloc="" compare,="" data,="" /> //就是很多pair <KEY,
data="" />組成一個紅黑樹<BR>insert() O(logn)<BR>erase() O(logn)<BR>find() O(logn)
找不到返回a.end()<BR>lower_bound() O(logn) 查找第一個不小于k的元素<BR>upper_bound() O(logn)
查找第一個大于k的元素<BR>equal_range() O(logn) 返回pair<LOWER,UPPER /><BR>[key]運算符 O(logn)
***
//這個..太猛了，怎么說呢，數組有一個下標，如a[i],這里i是int型的。數組可以認為是從int印射到另一個類型的印射，而map是一個任意的印射，所以i可以是任何類型的！</MAP></FONT></P>
<P><FONT face=宋體,sans-serif><MULTIMAP />允許重復元素, 沒有[]運算符</FONT></P>
<P><FONT face=宋體,sans-serif>Sample : TOJ 1378 Babelfish </FONT></P>
<P><FONT face=宋體,sans-serif>Code: (0.4k) //只有0.4K的代碼....<BR>#include
<CSTDIO /><BR>#include <STRING /><BR>#include <MAP><BR>using namespace
std;</MAP></FONT></P>
<P><FONT face=宋體,sans-serif>map <STRING,STRING />mp;</FONT></P>
<P><FONT face=宋體,sans-serif>int main()<BR>{<BR> char
buf[100],s1[100],s2[100];<BR> while (gets(buf)) {<BR> if
(strlen(buf) == 0)
break;<BR> sscanf(buf,"%s%s",s1,s2);<BR> mp[(string)s2] =
(string)s1; //這里的string s2，起到了類似于數組下標的作用！！<BR> } <BR> while
(gets(buf)) {<BR> if (mp.find((string)buf) !=
mp.end())<BR> printf("%s\n",mp[(string)buf].c_str());
//mp[(string)buf]返回值是string類型，要轉化成C語言能識別的字符串數組，加上.c_str()即可<BR> else
printf("eh\n");<BR> }<BR>return 0;<BR>}</FONT></P>
<P><FONT face=宋體,sans-serif><PRIORITY_QUEUE />內部實現: 堆
//優先隊列，聽RoBa講得，似乎知道原理了，但不明白干什么用的<BR>priority_queue<T, compare="" sequence,=""
/><BR>支持操作:<BR>push() O(n)<BR>pop() O(n)<BR>top() O(1)<BR>See also: push_heap(),
pop_heap() … in<BR><ALGORITHM /></FONT></P>
<P><FONT face=宋體,sans-serif>用法舉例:<BR>#include <QUEUE /><BR>#include <VECTOR
/><BR>using namespace std;</FONT></P>
<P><FONT face=宋體,sans-serif>priority_queue <INT
/>maxheap; //int最大堆</FONT></P>
<P><FONT face=宋體,sans-serif>struct ltstr {
//又是這么個Compare函數，重載運算符？？？不明白為什么要這么寫...反正這個Compare函數對我來說是相當之神奇。RoBa說了，照著這么寫就是了。<BR> bool
operator()(int a,int b) <BR> {return a > b;}<BR>};<BR>priority_queue
<INT,VECTOR<INT />,ltstr> minheap; //int最小堆</FONT></P>
<P><FONT face=宋體,sans-serif><HASH_MAP />內部實現: Hash表, of course
//內部用哈希表實現的map，據說還不是現在的C++標準，但因為太好用了，所以估計早晚要成為標準的~<BR>hash_map<KEY, alloc=""
data,="" equalkey,="" hashfcn,=""
/><BR>重載HashFcn和EqualKey<BR>支持操作:<BR>insert(); O(1)<BR>earse(); O(1)<BR>[
]; O(1)<BR>示例：Again TOJ 1378 Babelfish <BR>See also: <HASH_SET
/><HASH_MULTIMAP /><HASH_MULTISET /></FONT></P>
<P><FONT face=宋體,sans-serif>#include <CSTDIO /><BR>#include <HASH_MAP.H
/> //?? //因為不是C++標準，所以要加.h <BR>#include <STRING /><BR>using
namespace std;</FONT></P>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -