icpc讲义20xx(编辑修改稿)

icpc讲义20xx(编辑修改稿)内容摘要：

一个功能强大的 STL 库。 STL 的一个重大成就在于，它提供了相当多的有用算法。 它是在一个有效的框架中完成这些算法的。 STL 提供了大约 100 个实现算法的模板函数。 熟悉了STL 之后，你就会发现：以前所写的许多 “有趣功能 ”的代码现在只需要用短短几行主能完全替换了。 “The Art of Computer Programming”书中强调 算法 + 数据结构 = 程序 在过去，一般来说程序皆由算法加数据结构，互相配合、一起工作，完成程序的功能。 但如此一来便将数据结构与算法绑再一起，不能分离，缺乏弹性。 Stepanov 先生便针对此问题，采通用型设计的思维，使得程式师可以  以效率高的算法解决问题，此算法可处理各种数据结构即算法与数据结构互为独立  各种数据结构使用一致的接口 (interface)，让各种算法可以透过此接口处理各种数据结构 如何做到这点。 下面就简单介绍一下 STL 的组成。 STL 有五 个组成部分： 容器、迭代器、算法、适配器、函数对象。  容器 (container)－用来储存其他物件  迭代器 (iterator)－好比传统 C 语言的指针，可藉之来处理容器对象  算法 (algorithm)－算法通过迭代器来操作容器对象  适配器 (adaptor)－利用基础容器对象，加以包装，改变其接口，以适应另一种需求  函数对象 (function object)－为 STL 中较低阶的对象，用来代替传统的 函数指针(function pointer) STL 的简单结构可用下图表示：其中容器类表示通常意义上的数 据结构，和算法通过迭代器连接起来，做到上面的两点。 实际上，为了做到数据结构和算法之间的独立并保持相当的灵活性， STL 的实际结构容 器类 (container) 算法 (Algotithms) Iterator 3 要比上图表示复杂的多，下面给出 STL 的实际组成图。 三、 STL 的应用 标准的 C++库包含一个 INCLUDE 库和一个 LIB 库。 Include 库里的函数和类都是以源文件的形式给出的，用户可以查看它的源代码，而 LIB 库中则以二进制的形式给出。 STL都是以源码的形式给出 的，各个编译器有不同的版本。 VC++中的 STL 可读性很差，变量和内部函数名完全没有真实意义，如果要看源码的话建议看其他编译器的版本。 在做题目的时候可以选用 VC++或 DEV C++，但是 VC++用的不是 g++内核，而现在的JUDER一般都用 g++来编译测试，所以从适应比赛角度来说用 DEV C++比较合适，它也用很好的编辑环境，而且比较小，容易存储。 不过如果严格按照标准 C++的格式来编制程序的话，一般不会遇到因编译器而出错的问题。 现在大多数编译器都包含新旧两个版本的头文件，旧版本的头文件是以 .h 为扩展名的，新版本的头文件则不带扩展名，两者都可以用记事本打开来查看。 例如在 C/C++中使用标准输入输出流为： include include 而使用新版头文件则为： include iostream include stdio using namespace std。 上面的 using namespace std。 一句是使用名字域 std，在 std声明了所有 stl中的接口，在Algorithms Function Objects Adapter Iterators Containers STL 4 文件中声明一次即可。 此外，新旧文件的文件名不尽相同，例如 cmath，一般情况下名字不同时在原文件名前加 c 即可。 在介绍 STL 具体的数据结构之前，我们必须先了解一种叫迭代器的结构。 用户不必在意它的内部实现，但在使用 STL 的时候却无论如何都不能忽略它的存在。 迭代器 (Iterator)可以看成是一种特殊的指针，即一个指针类，它包含一类对象的指针和可以对这种指针进行的操作，也就是说迭代器保存所操作的特定容器需要的状态信息。 例如一个数组 int array[N]的迭代器可以为 int *p＝ array，现在 p 指向的是数组的首地址，我们可以对 p 进行加减操作来改变它所指的元素，如： p++是将指针 p 的值直接加上整形的字长而指向数组的下一个元素。 但是对于链表来说，如果 pit 是它的迭代器并且指向链表中的某个元素 T，如果要使 pit 指向链表的下一个元素则必须将 pit 内部用于定位的指针指向 Tnext。 其实我们可以像操作指针一样方便的操作迭代器，所不同地就是迭代器的功能比较完善，限制了对一些特殊结构类型的操作，包括随机迭代器，顺序迭代器 (重载 ++)，双向迭代器 (重载 ++和)等。 第一类容器提供成员函数 begin()和 end()来返回容器的首尾迭代器。 例如： include iostream include vector using namespace std。 vectorint vint。 int main() { int i。 for(i=0。 i10。 i++) (i)。 vectorint::iterator pit。 for(pit=()。 pit!=()。 pit++) cout(*pit)“ ”。 return 0。 } 上述代码只是让读者了解一下迭代器的 使用，我们将在以后详细地介绍中具体地分析各个数据结构迭代器的用法。 请看下面 STL 中的一段代码： templateclass T, class U struct pair { typedef T first_type。 typedef U second_type T first。 U second。 pair()。 pair(const Tamp。 x, const Uamp。 y)。 templateclass V, class W pair(const pairV, Wamp。 pr)。 5 }。 STL 中最简单地数据结构应属于 utility中定义地 pairTYPE,TYPE,它包含两个内部变量 first,second，用来将两个相关的数据配对，并重载了比较大小、判等、转化等函数，使用它可以方便地实例化自己地结构，如要建立一个坐标的数据结构则可以： include utility using namespace std。 typedef pairint,int POINT。 这样在下边的代码中我们就可以使用 POINT 这个结构了。 如果要使用它的判断函数，则所传递的类型必须已经重载了比较运算符或者使系统自定义类型。 例如： include iostream include utility using namespace std。 typedef pairint,int POINT。 int main() { POINT p1,p2。 cin。 if(p1==p2)cout“ Equal!”endl。 else cout“ Not Equal”endl。 return 0。 } 此外， utility 中还有一个 pairT, U make_pair(const T amp。 x, const U amp。 y)函数，用来将两个数据组成一个 pair 对象返回。 C++标准模板库提供三种顺序容器： vector、 list 和 deque。 Vector 类和 deque 类都是基于数组的， list 类实现链表数据结构。 【 vector类】 vector 类是一个线性数组类，内部用线性空间来存放元素，内部有两个不同 的变量来标识当前元素个数 _size 和当前共分配的空间数 _capacity，通常情况下 _size 要小于 _capacity，这样当在数组中添加元素时就不用每次都重新分配空间，从而提高了时间效率，直到分配的空间使用完时才重新分配。 至于每次分配空间的大小则与数组元素的个数有关，可以用capacity()函数得到。 Vector 类元素最多一般可以为 1073741823 个。 Vector 类重载了下标运算符，可以像数组一样访问容器中的元素，而且 vector 可以相互赋值，这是 C 语言的数组所不能实现的。 Vector 不进行下标检查 ，但是它通过成员函数 at 提供这个功能。 使用 vector可以方便的实现线性多维数组。 例如要分别建立坐标的一维和二维数组： 6 include utility include vector using namespace std。 typedef pairint,intPOINT； typedef vectorPOINT Array1D。 typedef vectorvectorPOINT Array2D。 在上面我们定义了一维坐标类 Array1D 和二维坐标类 Array2D，值得注 意的是在定义Array2D 的时候，后面的尖括号中间要用空格隔开，否则编译器可能误认为是移位运算符而报错。 Vector 类常用的接口如下： 函数名 返回值 参数 功能 at 元素的引用 要取元素的位置 (int pos) 如果该位置元素存在则返回它的引用，否则进行一场处理 back 元素的引用 无 返回容器最后一个元素的引用，如果容器为空则出错 begin 迭代器 无 取得元素的首迭代器 end 迭代器 无 取得元素的尾迭代器 clear 无 无 将容器清空 empty bool值 无 如果容器为空则 为真，否则为假 erase 迭代器 要删除元素的迭代器 要删除容器段的首尾迭代器 第一个版本删除指定的元素 第二个版本删除指定的容器段 不存在则出错 front 元素的引用 无 返回首元素的引用，为空则出错 insert 无 iterator it, const Tamp。 x iterator it, const_iterator first, const_iterator last 在 it 这个位置插入元素 T 从 it 位置开始，依次插入 first 到 last所指的元素 pop_back 无 无 删除 最后一个元素 push_back 无 const Tamp。 x 从最后插入一个元素 resize 无 size_type n 将容器大小重设置为 n size int 无 返回容器中元素的个数 请看下面的实例程序： include iostream include vector using namespace std。 typedef vectorint Array1D。 7 typedef vectorvectorint Array2D。 int main() { int i,j。 Array1D sz。 for(i=0。 i10。 i++) (i)。 for(i=0。 i10。 i++) coutsz[i]。 cout\n() ()endl。 (()+3)。 for(i=0。 i()。 i++) coutsz[i]。 coutendl。 (()+2,()+5)。 for(i=0。 i()。 i++) coutsz[i]。 coutendl。 ((),())。 //()。 Array2D tw。 (5)。 for(i=0。 i5。 i++) tw[i].resize(5)。 for(i=0。 i5。 i++) for(j=0。 j5。 j++) tw[i][j]=i*5+j。 for(i=0。 i()。 i++) { for(j=0。 jtw[i].size()。 j++) couttw[i][j]。 coutendl。 } system(PAUSE)。 //press any key to continue...... return 0。 } 对应的输 出应当为： 0 1 2 3 4 5 6 7 8 9 0 9 0 1 2 4 5 6 7 8 9 0 1 6 7 8 9 0 1 2 3 4 8 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 请按任意键继续 . . . 读者对照输出可体会各函数的用法 【 list 类】 lsit 顺序容器提供在容器中任意位置进行插入。