📄 笔记整理：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 + -