📄 笔记整理：stl in acm--greedy hawk 焚书煲粥.htm
字号:
<P><FONT face=宋体,sans-serif>struct calc_hash {<BR> size_t operator()(string
str) const {<BR> unsigned long h = 0; <BR> int
i;<BR> for (i = 0 ; i < str.size() ; i++) {<BR> h
<<= 5; //这个就是哈希函数，从字符串到int的印射函数，可以去网上找<BR> h |=
str[i] - 'a';<BR> }<BR> return
(size_t)h; //h%M??
//h是否需要一个上限？据说系统会自动处理，不必人工添加<BR> }<BR>};</FONT></P>
<P><FONT face=宋体,sans-serif>struct eqstr {<BR> bool
operator()(string s1, string s2) <BR> {return s1 ==
s2;}<BR>}; //本题此处可省略
//可以省略？？ 因为string作为一个常用类型，系统中有默认的比较函数，不必自己写<BR>int main()
{<BR> hash_map<STRING,STRING,CALC_HASH /> hp;<BR> char
buf[100],s1[20],s2[20];<BR> while (gets(buf)) {<BR> if
(strlen(buf) == 0)
break;<BR> sscanf(buf,"%s%s",s1,s2);<BR> hp[s2] =
s1; <BR> } <BR> while (gets(buf)) {<BR> if
(hp.find((string)buf) !=
hp.end())<BR> printf("%s\n",hp[(string)buf].c_str());<BR> else
printf("eh\n");<BR> }<BR> return 0; <BR>}</FONT></P>
<P><FONT face=宋体,sans-serif></FONT></P>
<P><FONT face=宋体,sans-serif><ALGORITHM />
//更神奇的东西！<BR>1.sort()<BR>void sort(RandomAccessIterator first,
RandomAccessIterator last); <BR>void sort(RandomAccessIterator first,
RandomAccessIterator last, StrictWeakOrdering comp);
<BR>区间[first,last)<BR>Quicksort,复杂度O(nlogn)
<BR>(n=last-first,平均情况和最坏情况)</FONT></P>
<P><FONT face=宋体,sans-serif>用法举例:<BR>1.从小到大排序(int, double, char, string,
etc)<BR>const int N = 5;<BR>int main()<BR>{<BR> int a[N] =
{4,3,2,6,1};<BR> string str[N] =
{“TJU”,”ACM”,”ICPC”,”abc”,”kkkkk”};<BR> sort(a,a+N);<BR> sort(str,str+N);<BR> return
0;<BR>}<BR>2.从大到小排序（需要自己写comp函数)<BR>const int N = 5;<BR>int cmp(int a,int b)
{return a > b;}<BR>int main()<BR>{<BR> int a[N] =
{4,3,2,6,1};<BR> sort(a,a+N,cmp);<BR> return 0;<BR>}<BR>3.
对结构体排序<BR>struct SS {int first,second;}; <BR>int cmp(SS a,SS b) {<BR> if
(a.first != b.first) return a.first < b.first;<BR> return a.second <
b.second;<BR>}</FONT></P>
<P><FONT face=宋体,sans-serif>v.s. qsort() in C
(平均情况O(nlogn)，最坏情况O(n^2)) //qsort中的cmp函数写起来就麻烦多了！<BR>int
cmp(const void *a,const void *b) {<BR> if (((SS*)a)->first !=
((SS*)b)->first)<BR> return ((SS*)a)->first –
((SS*)b)->first;<BR> return ((SS*)a)->second –
((SS*)b)->second;<BR>}<BR>qsort(array,n,sizeof(array[0]),cmp);</FONT></P>
<P><FONT
face=宋体,sans-serif>sort()系列:<BR>stable_sort(first,last,cmp); //稳定排序<BR>partial_sort(first,middle,last,cmp);//部分排序<BR>将前(middle-first)个元素放在[first,middle)中，其余元素位置不定<BR>e.g.<BR>int
A[12] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5}; <BR>partial_sort(A, A + 5, A +
12); <BR>// 结果是 "1 2 3 4 5 11 12 10 9 8 7 6". <BR>Detail: Heapsort
,<BR>O((last-first)*log(middle-first))</FONT></P>
<P><FONT face=宋体,sans-serif>sort()系列:<BR>partial_sort_copy(first, last,
result_first, result_last, cmp);<BR>//输入到另一个容器，不破坏原有序列<BR>bool is_sorted(first,
last, cmp);<BR>//判断是否已经有序<BR>nth_element(first, nth, last,
cmp);<BR>//使[first,nth)的元素不大于[nth,last), O(N)<BR>e.g. input: 7, 2, 6, 11, 9, 3,
12, 10, 8, 4, 1, 5 <BR>nth_element(A,A+6,A+12);<BR>Output: 5 2 6 1 4 3 7 8 9 10
11 12 </FONT></P>
<P><FONT face=宋体,sans-serif><ALGORITHM /><BR>2. binary_search()<BR>bool
binary_search(ForwardIterator first, ForwardIterator last, const
LessThanComparable& value); <BR>bool binary_search(ForwardIterator first,
ForwardIterator last, const T& value, StrictWeakOrdering comp);
<BR>在[first,last)中查找value，如果找到返回Ture,否则返回False<BR>二分检索，复杂度O(log(last-first))<BR>v.s.
bsearch() in C</FONT></P>
<P><FONT face=宋体,sans-serif>Binary_search()系列<BR>itr upper_bound(first, last,
value, cmp);<BR>//itr指向大于value的第一个值(或容器末尾)<BR>itr lower_bound(first, last,
value, cmp);<BR>//itr指向不小于valude的第一个值(或容器末尾)<BR>pair<ITR,ITR />
equal_range(first, last, value, cmp);<BR>//找出等于value的值的范围 O(2*log(last –
first))<BR>int A[N] = {1,2,3,3,3,5,8}<BR>*upper_bound(A,A+N,3) ==
5<BR>*lower_bound(A,A+N,3) == 3 </FONT></P>
<P><FONT face=宋体,sans-serif><ALGORITHM
/><BR>make_heap(first,last,cmp) O(n)<BR>push_heap(first,last,cmp) O(logn)<BR>pop_heap(first,last,cmp) O(logn)<BR>is_heap(first,last,cmp) O(n)<BR>e.g:<BR>vector
<INT />vi;<BR>while (scanf(“%d”,&n) != EOF)
{<BR> vi.push_back(n);<BR> push_heap(vi.begin(),vi.end());<BR>}</FONT></P>
<P><FONT face=宋体,sans-serif><ALGORITHM /><BR>Others
interesting:<BR>next_permutation(first, last, cmp)<BR>prev_permutation(first,
last, cmp) <BR>//both O(N)<BR>min(a,b);<BR>max(a,b);<BR>min_element(first, last,
cmp);<BR>max_element(first, last, cmp);</FONT></P>
<P><FONT face=宋体,sans-serif><ALGORITHM /><BR>Others interesting:<BR>fill(first,
last, value)<BR>reverse(first, last)<BR>rotate(first,middle,last);<BR>itr
unique(first, last);<BR>//返回指针指向合并后的末尾处<BR>random_shuffle(first, last,
rand)</FONT></P>
<P><FONT face=宋体,sans-serif>Some Others:<BR>More container: Rope, Slist, Bitset
…<BR>More about iterator<BR>Memory allocation<BR>Function object<BR>…</FONT></P>
<P><FONT face=宋体,sans-serif></FONT></P>
<P></P>
<P class=diaryFoot>【作者: <A
onclick="window.open('http://publishblog.blogchina.com/blog/postMessage.b?receiver=493341','发送短消息','width=520, height=455')"
href="javascript:void(0);">焚书煲粥</A>】【访问统计:
<SCRIPT language=JavaScript
src="笔记整理：STL in ACM--Greedy Hawk 焚书煲粥.files/PageServlet.htm"></SCRIPT>
】【2006年05月15日 星期一 20:48】【 <A
href="javascript:void(keyit=window.open('http://blogmark.blogchina.com/jsp/key/quickaddkey.jsp?k='+encodeURI('笔记整理：STL in ACM')+'&u='+encodeURI('http://yxhome.blogchina.com/yxhome/5057457.html')+'&c='+encodeURI(''),'keyit','scrollbars=no,width=500,height=430,status=no,resizable=yes'));keyit.focus();">加入博采</A>】【<A
href="javascript:window.print();">打印</A>】 </TD></P></DIV>
<DIV class=operation><A name=trackback>
<H3>Trackback</H3></A>
<P class=trackback>你可以使用这个链接引用该篇文章
http://publishblog.blogchina.com/blog/tb.b?diaryID=5057457 </P></DIV>
<DIV class=operation><A name=relatedDiary>
<H3>博客手拉手</H3></A>
<TABLE>
<TBODY></TBODY></TABLE></DIV>
<DIV class=operation><A name=comment>
<H3>回复</H3></A>
<TABLE cellSpacing=0 cellPadding=0 width=700 border=0>
<TBODY></TBODY></TABLE></DIV>
<DIV class=operation>
<TABLE class=comment cellSpacing=0 cellPadding=0 width=700 border=0>
<FORM id=replyForm method=post><INPUT type=hidden value=493852 name=blogID>
<INPUT type=hidden value=5057457 name=diaryID> <INPUT type=hidden value=yxhome
name=blogDomino>
<SCRIPT>
if(getCookie('userID') == null){
document.write('<tr><td width="70">发布人：</td>');
document.write('<td width="150"> <input name="remark.authorNameFUI" type="text" size="20" class="inputStyle" maxlength="20"></td>');
document.write('<td width="70">邮箱：</td>');
document.write('<td width="435"> <input name="remark.authorEmail" type="text" size="20" class="inputStyle" maxlength="40"></td>');
document.write('</tr><tr><td>主 页：</td>');
document.write('<td colspan="3"> <input name="remark.authorURL" type="text" class="inputStyle" value="HTTP://" size="63" maxlength="100"></td></tr>');
}else{
document.write('<input type="hidden" name="remark.authorNameFUI" value="Blogchina网友">');
}
</SCRIPT>
<TBODY>
<TR>
<TD width=70>验证码：</TD>
<TD><INPUT class=inputStyle maxLength=4 name=validateCode></TD>
<TD> <IMG
src="笔记整理：STL in ACM--Greedy Hawk 焚书煲粥.files/getValidateImg.jpg"
border=0></TD></TR>
<TR align=left>
<TD colSpan=4>评论内容：<BR><TEXTAREA class=textStyle id=remark name=remark.remarkFUI rows=8 cols=60> </TEXTAREA>
</TD></TR>
<TR align=left>
<TD colSpan=4> <INPUT onclick=reply() type=button value=提交>
<INPUT type=reset value=重置> </TD></TR></FORM></TBODY></TABLE></DIV></DIV>
<SCRIPT src="笔记整理：STL in ACM--Greedy Hawk 焚书煲粥.files/extend3.js"
type=text/javascript></SCRIPT>
<DIV id=footer><A href="http://blog.bokee.com/">2003-2004 BOKEE.COM All rights
reserved</A><BR><A href="http://www.blogdriver.com/">Powered by BlogDriver
2.1</A> </DIV></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -