-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathNote.html
More file actions
307 lines (266 loc) · 14.7 KB
/
Copy pathNote.html
File metadata and controls
307 lines (266 loc) · 14.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
<?xml version="1.0" encoding="gbk"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"
lang="en" xml:lang="en">
<head>
<title>OI学习笔记</title>
<meta http-equiv="Content-Type" content="text/html;charset=gbk"/>
<meta name="generator" content="Org-mode"/>
<meta name="generated" content="2012-02-24 20:12:44 CST"/>
<meta name="author" content="wlm"/>
<meta name="description" content=""/>
<meta name="keywords" content=""/>
<style type="text/css">
<!--/*--><![CDATA[/*><!--*/
html { font-family: Times, serif; font-size: 12pt; }
.title { text-align: center; }
.todo { color: red; }
.done { color: green; }
.tag { background-color: #add8e6; font-weight:normal }
.target { }
.timestamp { color: #bebebe; }
.timestamp-kwd { color: #5f9ea0; }
p.verse { margin-left: 3% }
pre {
border: 1pt solid #AEBDCC;
background-color: #F3F5F7;
padding: 5pt;
font-family: courier, monospace;
font-size: 90%;
overflow:auto;
}
table { border-collapse: collapse; }
td, th { vertical-align: top; }
dt { font-weight: bold; }
div.figure { padding: 0.5em; }
div.figure p { text-align: center; }
.linenr { font-size:smaller }
.code-highlighted {background-color:#ffff00;}
.org-info-js_info-navigation { border-style:none; }
#org-info-js_console-label { font-size:10px; font-weight:bold;
white-space:nowrap; }
.org-info-js_search-highlight {background-color:#ffff00; color:#000000;
font-weight:bold; }
/*]]>*/-->
</style>
<script type="text/javascript">
<!--/*--><![CDATA[/*><!--*/
function CodeHighlightOn(elem, id)
{
var target = document.getElementById(id);
if(null != target) {
elem.cacheClassElem = elem.className;
elem.cacheClassTarget = target.className;
target.className = "code-highlighted";
elem.className = "code-highlighted";
}
}
function CodeHighlightOff(elem, id)
{
var target = document.getElementById(id);
if(elem.cacheClassElem)
elem.className = elem.cacheClassElem;
if(elem.cacheClassTarget)
target.className = elem.cacheClassTarget;
}
/*]]>*///-->
</script>
</head>
<body>
<div id="content">
<h1 class="title">OI学习笔记</h1>
<div id="table-of-contents">
<h2>Table of Contents</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#sec-1">1 序 </a></li>
<li><a href="#sec-2">2 许可协议 </a></li>
<li><a href="#sec-3">3 STL </a>
<ul>
<li><a href="#sec-3.1">3.1 STL历史 </a></li>
<li><a href="#sec-3.2">3.2 STL内容 </a>
<ul>
<li><a href="#sec-3.2.1">3.2.1 Vector </a></li>
<li><a href="#sec-3.2.2">3.2.2 List </a></li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
</div>
<div id="outline-container-1" class="outline-2">
<h2 id="sec-1"><span class="section-number-2">1</span> 序 </h2>
<div class="outline-text-2" id="text-1">
<p>参加OI多年，我才发现自己的知识完全没有系统性，没有体系。知识胡乱地堆放在脑子里，做题时完全不知道该用哪些部分。这也是我写这些东西的初衷，整理自己所有的知识，仅此而已。
</p></div>
</div>
<div id="outline-container-2" class="outline-2">
<h2 id="sec-2"><span class="section-number-2">2</span> 许可协议 </h2>
<div class="outline-text-2" id="text-2">
<p>本笔记大部分摘自网络，所有文本均遵循其本身的许可协议。本笔记会标明出处。
</p></div>
</div>
<div id="outline-container-3" class="outline-2">
<h2 id="sec-3"><span class="section-number-2">3</span> STL </h2>
<div class="outline-text-2" id="text-3">
</div>
<div id="outline-container-3.1" class="outline-3">
<h3 id="sec-3.1"><span class="section-number-3">3.1</span> STL历史 </h3>
<div class="outline-text-3" id="text-3.1">
<p>STL系由Alexander Stepanov创造于1979年前后，这也正是比雅尼·斯特劳斯特鲁普创造C++的年代。
虽然David R. Musser于1971年开始即在计算机几何领域发展并倡导某些泛型程序设计观念，但早期并没有任何编程语言支持泛型程序设计。第一个支援泛型概念的语言是Ada。[来源请求] Alex和Musser曾于1987开发出一套相关的Ada library.
STL之设计人Stepanov早期从事教育工作，1970年代研究泛型程序设计，那时他与其同事一起在GE公司开发出一个新的程序语言——Tecton。
1983年，Stepanov先生转至Polytechnic大学教书，继续研究泛型程序设计，同时写了许多Scheme的程序，应用在graph与network的算法上，1985年又转至GE公司专门教授高阶程序设计，并将graph与network的Scheme程式，改用Ada写，用了Ada以后，他发现到一个动态（dynamically）类型的程序（如Scheme）与强制（strongly）类型的程序（如Ada）有多么的不同。
在动态类型的程序中，所有类型都可以自由的转换成别的类型，而强制类型的程序却不能。但是，强制类型在除错时较容易发现程序错误。
1988年Stepanov先生转至HP公司执行开发泛型程序库的工作。此时，他已经认识C语言中指针的威力，他表示一个程序员只要有些许硬件知识，就很容易接受C语言中指针的观念，同时也了解到C语言的所有数据结构均可以指针间接表示，这点是C与Ada、Scheme的最大不同。
Stepanov并认为，虽然C++中的继承功能可以表示泛型设计，但终究有个限制。虽然可以在基础类型（superclass）定义算法和接口，但不可能要求所有物件皆是继承这些，而且庞大的继承体系将减低虚拟（virtual）函数的执行效率，这便违反的前面所说的“效率”原则。
到了C++模版观念，Stepanov参加了许多有关的研讨会，与C++之父Bjarne讨论模版的设计细节。如，Stepanov认为C++的函数模版（function template）应该像Ada一样，在声明其函数原型后，应该显式的声明一个函数模版之实例（instance）；Bjarne则不然，他认为可以透过C++的重载（overloading）功能来表达。
Stepanov想像中的函数模版：
</p>
<pre class="example"><span class="linenr">1: </span>in *.hpp
<span class="linenr">2: </span>template<class T>
<span class="linenr">3: </span>T square(T x) { return x*x; }
<span class="linenr">4: </span>
<span class="linenr">5: </span>in *.cpp
<span class="linenr">6: </span>double square(double);
<span class="linenr">7: </span>cout << square(3.3);
<span class="linenr">8: </span>int square(int);
<span class="linenr">9: </span>cout << square(3);
</pre>
<p>
Bjarne认为的函数模版：
</p>
<pre class="example"><span class="linenr">1: </span>in *.hpp
<span class="linenr">2: </span>template<class T>
<span class="linenr">3: </span>T square(T x) { return x*x; }
<span class="linenr">4: </span>
<span class="linenr">5: </span>in *.cpp
<span class="linenr">6: </span>cout << square(3.3);
<span class="linenr">7: </span>cout << square(3);
</pre>
<p>
几经争辩，Stepanov发现Bjarne是对的（参考侯俊杰《STL讲座·第三章》）。事后Stepanov回想起来非常同意Bjarne的作法。
</p><blockquote>
<p>template 引数推导机制（arguments deduction ，在 STL中占非常重要的角色。Alexander Stepanov（STL 的创造者）在与Dr. Dobb's Journal进行的访谈中说道‘1992 我重回generic-library的开发工作。这时候C++有了template
我发现Bjarne完成了一个非常美妙的设计。之前我在Bell Lab曾参与数次template的相关设计讨论，并且非常粗暴地要求Bjarne应该将C++ template设计得尽可能像Ada generics那样。我想由于我的争辩是如此地粗暴，他决定反对。我了解到在C++中除了拥有template classes之外还拥有template functions的重要性。然而我认为template function应该像Ada generics一样，也就是说它们应该是显式实例，Bjarne没有听进我的话，他设计了一个template function机制，其中的template是以一个重载化机制 （overloading mechanism来进行隐式实例这项特殊的技术对我的工作具有关键性的影响，因为我发现它使我得以完成Ada不可能完成的许多动作。我非常高兴Bjarne当初没有听我的意见。’（DDJ 1995 年三月号）
</p>
</blockquote>
<p>事实上，C++的模版，本身即是一套复杂的宏语言（macro language），宏语言最大的特色为：所有工作在编译时期就已完成。显式的声明函数模版之实例，与直接透过C++的多载功能隐式声明，结果一样，并无很大区别，只是前者加重程序员的负担，使得程式变得累赘。
1992年Meng Lee加入Alex的专案，成为另一位主要贡献者。
1992年，HP泛型程序库计划结束，小组解散，只剩下Stepanov先生与Meng Lee小姐（她是东方人，STL的名称其实是取STepanov与Lee而来[来源请求]），Lee先前研究的是编译器的制作，对C++的模版很熟，第一版的STL中许多程式都是Lee的杰作。
1993年，Andy Koenig到斯坦福演讲，Stepanov便向他介绍STL，Koenig听后，随即邀请Stepanov参加1993年11月的ANSI/ISO C++标准化会议，并发表演讲。
Bell实验室的Andrew Koenig于1993年知道STL研究计划后，邀请Alex于是年11月的ANSI/ISO C++标准委员会会议上展示其观念。并获得与会者热烈的回应。
1994年1月6日，Koenig寄封电子邮件给Stepanov，表示如果Stepanov愿意将STL的说明文件撰写齐全，在1月25日前提出，便可能成为标准C++的一部份。Stepanov回信道："Andy, are you crazy?" 。 Koenig便说："Well, yes I am crazy,but why not try it?"。
Alex于是在次年夏天在Waterloo举行的会议前完成其正式的提案，并以百分之八十压倒性多数，一举让这个巨大的计划成为C++ Standard的一部份。
STL于1994年2月年正式成为ANSI/ISO C++的一部份，它的出现，促使C++程序员的思维方式更朝向泛型编程（generic program）发展。
</p></div>
</div>
<div id="outline-container-3.2" class="outline-3">
<h3 id="sec-3.2"><span class="section-number-3">3.2</span> STL内容 </h3>
<div class="outline-text-3" id="text-3.2">
</div>
<div id="outline-container-3.2.1" class="outline-4">
<h4 id="sec-3.2.1"><span class="section-number-4">3.2.1</span> Vector </h4>
<div class="outline-text-4" id="text-3.2.1">
<ul>
<li id="sec-3.2.1.1">简介 <br/>
vector 定义于 <vector> 头文件中。与其他STL元件一样，vector 属于std名称空间。
vector是C++标准库里最基本的容器，大多数状况下都很有效率。vector设计之初即是为了改善C语言原生阵列的种种缺失与不便，而欲提供一种更有效、更安全的阵列。vector的的使用接口刻意模拟C语言原生阵列，较明显的差异在于内存管理，原生阵列必须在宣告阵列的时候明确指定阵列长度(例如 int a<sup><a class="footref" name="fnr.1" href="#fn.1">1</a></sup>)，但是 vector 不需要指定，而是会在执行期依据状况自我调整长度，动态增大容量。
vector的表现一如数据结构中的阵列，允许随机存取(Random Access)，以索引值(index)存取任一元素只要花费常数时间 O(1)，在集合尾端增加或删除元素也是花费常数时间O(1)，若在vector集合中间增加或删除元素时间复杂度是线性时间O(n)，较为费时。虽然C++标准并没有规定实作方式，但大多数 vector 内部均使用动态阵列方式实作。
</li>
<li id="sec-3.2.1.2">操作 <br/>
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<caption></caption>
<colgroup><col align="left" /><col align="left" />
</colgroup>
<tbody>
<tr><td>访问元素方法</td><td></td></tr>
<tr><td>vec[i]</td><td>访问索引值为 I 的元素引用。 (索引值从零起算，故第一个元素是VEC<sup><a class="footref" name="fnr.2" href="#fn.2">2</a></sup>。)</td></tr>
<tr><td>vec.AT(I)</td><td>访问索引值为 I 的元素的引用，以 AT() 访问会做数组边界检查，如果访问越界将会抛出一个例外，这是与OPERATOR[]的唯一差异。</td></tr>
<tr><td>vec.FRONT()</td><td>回传 VECTOR 第一个元素的引用。</td></tr>
<tr><td>vec.BACK()</td><td>回传 VECTOR 最尾元素的引用。</td></tr>
<tr><td>新增或移除元素的方法</td><td></td></tr>
<tr><td>vec.push<sub>back</sub>()</td><td>新增元素至 vector 的尾端，必要时会进行存储器配置。</td></tr>
<tr><td>vec.pop<sub>back</sub>()</td><td>删除 vector 最尾端的元素。</td></tr>
<tr><td>vec.insert()</td><td>插入一个或多个元素至 vector 内的任意位置。</td></tr>
<tr><td>vec.erase()</td><td>删除 vector 中一个或多个元素。</td></tr>
<tr><td>vec.clear()</td><td>清空所有元素。</td></tr>
<tr><td>取得长度/容量</td><td></td></tr>
<tr><td>vec.size()</td><td>取得 vector 目前持有的元素个数。</td></tr>
<tr><td>vec.empty()</td><td>如果 vector 内部为空，则传回 true 值。</td></tr>
<tr><td>vec.capacity()</td><td>取得 vector 目前可容纳的最大元素个数。这个方法与存储器的配置有关，它通常只会增加，不会因为元素被删减而随之减少。</td></tr>
<tr><td>重新配置／重设长度</td><td></td></tr>
<tr><td>vec.reserve()</td><td>如有必要，可改变 vector 的容量大小（配置更多的存储器）。在众多的 STL 实做，容量只能增加，不可以减少。</td></tr>
<tr><td>vec.resize()</td><td>改变 vector 目前持有的元素个数。</td></tr>
<tr><td>迭代 (Iterator)</td><td></td></tr>
<tr><td>vec.begin()</td><td>回传一个Iterator，它指向 vector 第一个元素。</td></tr>
<tr><td>vec.end()</td><td>回传一个Iterator，它指向 vector 最尾端元素的下一个位置（请注意：它不是最末元素）。</td></tr>
<tr><td>vec.rbegin()</td><td>回传一个反向Iterator，它指向 vector 最尾端元素的。</td></tr>
<tr><td>vec.rend()</td><td>回传一个Iterator，它指向 vector 的第一个元素。</td></tr>
</tbody>
</table>
</li>
</ul>
</div>
</div>
<div id="outline-container-3.2.2" class="outline-4">
<h4 id="sec-3.2.2"><span class="section-number-4">3.2.2</span> List </h4>
<div class="outline-text-4" id="text-3.2.2">
<ul>
<li id="sec-3.2.2.1">简介 <br/>
list 被定义在 <list> 头文件中。如其他STL元件，list属于std名称空间。
list 内部以数据结构的双向连结串行实现，内部元素并非放置于连续大块内存中，而是散落于内存各处，互相以link串接起来，每个元素都只知道其前一个元素以及下一个元素的位置。故要走访整个list，必须从第一个元素开始逐个往下寻访，不支持随机存取(Random Access)。 list 的强项是高效的插入以及删除，于list插入或删除时只需要改动元素的link字段，不需要搬动元素，代价相对便宜。
list 在经常需要于集合内部任意位置(即除了头尾以外的其他位置) 频繁增删元素的工作上表现优秀。若仅需要于集合尾端增删元素，那应该优先考虑vector容器，若仅于头尾二端增删元素，那应该优先考虑deque容器。
</li>
<li id="sec-3.2.2.2">操作 <br/>
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<caption></caption>
<colgroup><col align="left" /><col align="left" />
</colgroup>
<tbody>
<tr><td>访问元素方法</td><td></td></tr>
<tr><td>list.begin()</td><td>回传指向第一个元素的 Iterator。</td></tr>
<tr><td>list.end()</td><td>回传指向最末元素的下一个位置的 Iterator。</td></tr>
<tr><td>list.rbegin()</td><td>回传指向最末个元素的反向 Iterator。</td></tr>
<tr><td>list.rend()</td><td>回传指向第一个元素的前一个位置的反向 Iterator。</td></tr>
<tr><td>取得长度/容量:</td><td></td></tr>
<tr><td>list.empty()</td><td>若list内部为空，则回传true值。</td></tr>
<tr><td>list.size()</td><td>回传list内实际的元素个数。</td></tr>
<tr><td>lsit.resize()</td><td>重新分派list的长度。</td></tr>
<tr><td>访问元素</td><td></td></tr>
<tr><td>list.front()</td><td>存取第一个元素。</td></tr>
<tr><td>list.back()</td><td>存取最末个元素。</td></tr>
<tr><td>修改元素</td><td></td></tr>
<tr><td>list.push<sub>front</sub>()</td><td>增加一个新的元素在 list 的前端。</td></tr>
<tr><td>list.pop<sub>front</sub>()</td><td>删除 list 的第一个元素。</td></tr>
<tr><td>list.push<sub>back</sub>()</td><td>增加一个新的元素在 list 的尾端。</td></tr>
<tr><td>list.pop<sub>back</sub>()</td><td>删除 list 的最末个元素。</td></tr>
</tbody>
</table>
</li>
</ul>
</div>
</div>
</div>
</div>
<div id="footnotes">
<h2 class="footnotes">Footnotes: </h2>
<div id="text-footnotes">
<p class="footnote"><sup><a class="footnum" name="fn.1" href="#fnr.1">1</a></sup> FOOTNOTE DEFINITION NOT FOUND: 5
</p>
<p class="footnote"><sup><a class="footnum" name="fn.2" href="#fnr.2">2</a></sup> FOOTNOTE DEFINITION NOT FOUND: 0
</p>
</div>
</div>
<div id="postamble">
<p class="author"> Author: wlm
<a href="mailto:wlm@wlm-P5QL-PRO"><wlm@wlm-P5QL-PRO></a>
</p>
<p class="date"> Date: 2012-02-24 20:12:44 CST</p>
<p class="creator">HTML generated by org-mode 6.33x in emacs 23</p>
</div>
</div>
</body>
</html>