|
|
24 September 没办法,在学校访问space太慢,我都懒得来更新了.
还记得我的亲戚朋友们多来捧捧场啦 14 April 堆(heap)和栈(stack)有什么区别??简单的可以理解为: heap:是由malloc之类函数分配的空间所在地。地址是由低向高增长的。 stack:是自动分配变量,以及函数调用的时候所使用的一些空间。地址是由高向低减少的。预备知识—程序的内存分配一个由c/C++编译的程序占用的内存分为以下几个部分1、栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。2、堆区(heap) — 一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表,呵呵。3、全局区(静态区)(static)—,全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域, 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放4、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放5、程序代码区—存放函数体的二进制代码。二、例子程序这是一个前辈写的,非常详细//main.cppint a = 0; 全局初始化区char *p1; 全局未初始化区main(){int b; 栈char s[] = "abc"; 栈char *p2; 栈char *p3 = "123456"; 123456在常量区,p3在栈上。static int c =0; 全局(静态)初始化区p1 = (char *)malloc(10);p2 = (char *)malloc(20);分配得来得10和20字节的区域就在堆区。strcpy(p1, "123456"); 123456放在常量区,编译器可能会将它与p3所指向的"123456"优化成一个地方。} 二、栈的理论知识2.1申请方式stack:由系统自动分配。 例如,声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间heap:需要程序员自己申请,并指明大小,在c中malloc函数如p1 = (char *)malloc(10);在C++中用new运算符如p2 = (char *)malloc(10);但是注意p1、p2本身是在栈中的。2.2申请后系统的响应栈:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序,另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的delete语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。2.3申请大小的限制栈:在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在 WINDOWS下,栈的大小是2M(也有的说是1M,总之是一个编译时就确定的常数),如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间较小。堆:堆是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。2.4申请效率的比较:栈由系统自动分配,速度较快。但程序员是无法控制的。堆是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便.另外,在WINDOWS下,最好的方式是用VirtualAlloc分配内存,他不是在堆,也不是在栈是直接在进程的地址空间中保留一快内存,虽然用起来最不方便。但是速度也最灵活2.5堆和栈中的存储内容栈: 在函数调用时,第一个进栈的是主函数中后的下一条指令(函数调用语句的下一条可执行语句)的地址,然后是函数的各个参数,在大多数的C编译器中,参数是由右往左入栈的,然后是函数中的局部变量。注意静态变量是不入栈的。当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,也就是主函数中的下一条指令,程序由该点继续运行。堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。2.6存取效率的比较char s1[] = "aaaaaaaaaaaaaaa";char *s2 = "bbbbbbbbbbbbbbbbb";aaaaaaaaaaa是在运行时刻赋值的;而bbbbbbbbbbb是在编译时就确定的;但是,在以后的存取中,在栈上的数组比指针所指向的字符串(例如堆)快。比如:#include void main(){char a = 1;char c[] = "1234567890";char *p ="1234567890";a = c[1];a = p[1];return;}对应的汇编代码10: a = c[1];00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]0040106A 88 4D FC mov byte ptr [ebp-4],cl11: a = p[1];0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]00401070 8A 42 01 mov al,byte ptr [edx+1]00401073 88 45 FC mov byte ptr [ebp-4],al第一种在读取时直接就把字符串中的元素读到寄存器cl中,而第二种则要先把指针值读edx中,在根据edx读取字符,显然慢了。 2.7小结:堆和栈的区别可以用如下的比喻来看出:使用栈就象我们去饭馆里吃饭,只管点菜(发出申请)、付钱、和吃(使用),吃饱了就走,不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处是快捷,但是自由度小。使用堆就象是自己动手做喜欢吃的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大。堆和栈的区别主要分:操作系统方面的堆和栈,如上面说的那些,不多说了。还有就是数据结构方面的堆和栈,这些都是不同的概念。这里的堆实际上指的就是(满足堆性质的)优先队列的一种数据结构,第1个元素有最高的优先权;栈实际上就是满足先进后出的性质的数学或数据结构。虽然堆栈,堆栈的说法是连起来叫,但是他们还是有很大区别的,连着叫只是由于历史的原因。 02 April 鉴于本人在szucpc上的惨痛失败.为了在GDCPC上不再郁闷,特进行此特训.在PKU上做题,主要针对自己比较弱的搜索和DP,分析gdcpc上难的题不会太多,一般是考查基本功,所以这次训练不针对难题,只针对一些应该牢牢掌握的基础知识.
第一期训练题目如下(主要是搜索)可能有重复,争取两个星期能割完大部分吧
回溯搜索:1979(和迷宫类似) 1980(对剪枝要求较高)
递归: 1664
搜索 容易: 1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 18 47, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426, 不易: 1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 2349, 推荐: 1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 1714, 17 53, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170, 2288, 2331 , 2339, 2340
1315(学会搜索) 1321(同1315)
2413(高精度基础)
1011(搜索好题)
1240(直到一棵树的先序和后序遍历,那么有几种中序遍历呢?dp)
Search: 1011(*) 1129 2078(*) 2362(similar to 1011)
2051: 堆
递归枚举搜索: 1010,1011,1018,1020,1054,1062,1256,1321,1363,1501 1650,1659,1664,1753,2078,2083,2303,2310,2329
概率统计: 1037,1050
枚举 1012 1046 1387 1411 2245 2326 2363 2381 搜索、回溯、遍历 1010 1011 1022 1054 1111 1118 1129 1190 1562 1564 1573 1655 2078 2184 2225 2243 2312 2362 2378 2386 14 March 在计算机中数据有两种特征:类型和长度。所谓数据类型就是以数据的表现方式和存储方式来划分的数据的种类。 在SQL Server 中每个变量、参数、表达式等都有数据类型。系统提供的数据类型分为几大类,如表4-2 所示。 其中,BIGINT、 SQL_VARIANT 和TABLE 是SQL Server 2000 中新增加的3 种数据类型。下面分类讲述各种数据类型。
4.3.1 整数数据类型 整数数据类型是最常用的数据类型之一。 1、INT (INTEGER) INT (或INTEGER)数据类型存储从-2的31次方 (-2 ,147 ,483 ,648) 到2的31次方-1 (2 ,147 ,483,647) 之间的所有正负整数。
每个INT 类型的数据按4 个字节存储,其中1 位表示整数值的正负号,其它31 位表示整数值的长度和大小。 2、SMALLINT SMALLINT 数据类型存储从-2的15次方( -32, 768) 到2的15次方-1( 32 ,767 )之间的所有正负整数。每个SMALLINT 类型的数据占用2
个字节的存储空间,其中1 位表示整数值的正负号,其它15 位表示整数值的长度和大小。 3、TINYINT TINYINT数据类型存储从0 到255 之间的所有正整数。每个TINYINT类型的数据占用1 个字节的存储空间。 4、BIGINT BIGINT 数据类型存储从-2^63 (-9 ,223, 372, 036, 854, 775, 807) 到2^63-1( 9, 223, 372, 036 ,854 ,775, 807) 之间
的所有正负整数。每个BIGINT 类型的数据占用8个字节的存储空间。
4.3.2 浮点数据类型 浮点数据类型用于存储十进制小数。浮点数值的数据在SQL Server 中采用上舍入(Round up 或称为只入不舍)方式进行存储。所谓上舍
入是指,当(且仅当)要舍入的数是一个非零数时,对其保留数字部分的最低有效位上的数值加1 ,并进行必要的进位。若一个数是上舍入数
,其绝对值不会减少。如:对3.14159265358979 分别进行2 位和12位舍入,结果为3.15 和3.141592653590。 1、REAL 数据类型 REAL数据类型可精确到第7 位小数,其范围为从-3.40E -38 到3.40E +38。 每个REAL类型的数据占用4 个字节的存储空间。 2、FLOAT FLOAT数据类型可精确到第15 位小数,其范围为从-1.79E -308 到1.79E +308。 每个FLOAT 类型的数据占用8 个字节的存储空间。 FLOAT数据
类型可写为FLOAT[ n ]的形式。n 指定FLOAT 数据的精度。n 为1到15 之间的整数值。当n 取1 到7 时,实际上是定义了一个REAL 类型的数据
,系统用4 个字节存储它;当n 取8 到15 时,系统认为其是FLOAT 类型,用8 个字节存储它。 3、DECIMAL DECIMAL数据类型可以提供小数所需要的实际存储空间,但也有一定的限制,您可以用2 到17 个字节来存储从-10的38次方-1 到10的38次方-1
之间的数值。可将其写为DECIMAL[ p [s] ]的形式,p 和s 确定了精确的比例和数位。其中p 表示可供存储的值的总位数(不包括小数点),
缺省值为18; s 表示小数点后的位数,缺省值为0。 例如:decimal (15 5),表示共有15 位数,其中整数10 位,小数5。 位表4-3 列出了
各精确度所需的字节数之间的关系。 4、NUMERIC NUMERIC数据类型与DECIMAL数据类型完全相同。 注意:SQL Server 为了和前端的开发工具配合,其所支持的数据精度默认最大为28位。但可以通过使用命令来执行sqlserver.exe程序以启动
SQL Server,可改变默认精度。命令语法如下:SQLSERVR[/D master_device_path][/P precisim_leve1] 例4-4: 用最大数据精度38 启动SQL Server sqlservr /d c:\ Mssql2000\data\master.dat /p38 /*在使用了/P 参数后,如果其后没有指定具体的精度数值,则默认为38 位./*
4.3.3 二进制数据类型 1、BINARY BINARY 数据类型用于存储二进制数据。其定义形式为BINARY( n), n 表示数据的长度,取值为1 到8000 。在使用时必须指定BINARY 类型
数据的大小,至少应为1 个字节。BINARY 类型数据占用n+4 个字节的存储空间。在输入数据时必须在数据前加上字符“0X” 作为二进制标识
,如:要输入“abc ”则应输入“0xabc ”。若输入的数据过长将会截掉其超出部分。若输入的数据位数为奇数,则会在起始符号“0X ”后添
加一个0,如上述的“0xabc ”会被系统自动变为“0x0abc”。 2、VARBINARY VARBINARY数据类型的定义形式为VARBINARY(n)。 它与BINARY 类型相似,n 的取值也为1 到8000, 若输入的数据过长,将会截掉其超出部
分。不同的是VARBINARY数据类型具有变动长度的特性,因为VARBINARY数据类型的存储长度为实际数值长度+4个字节。当BINARY数据类型允许
NULL 值时,将被视为VARBINARY数据类型。 一般情况下,由于BINARY 数据类型长度固定,因此它比VARBINARY 类型的处理速度快。
4.3.4 逻辑数据类型 BIT: BIT数据类型占用1 个字节的存储空间,其值为0 或1 。如果输入0 或1 以外的值,将被视为1。 BIT 类型不能定义为NULL 值(所
谓NULL 值是指空值或无意义的值)。
4.3.5 字符数据类型 字符数据类型是使用最多的数据类型。它可以用来存储各种字母、数字符号、特殊符号。一般情况下,使用字符类型数据时须在其前后加
上单引号’或双引号” 。 1 CHAR CHAR 数据类型的定义形式为CHAR[ (n) ]。 以CHAR 类型存储的每个字符和符号占一个字节的存储空间。n 表示所有字符所占的存储空间,n
的取值为1 到8000, 即可容纳8000 个ANSI 字符。若不指定n 值,则系统默认值为1。 若输入数据的字符数小于n,则系统自动在其后添加空
格来填满设定好的空间。若输入的数据过长,将会截掉其超出部分。 2、NCHAR NCHAR数据类型的定义形式为NCHAR[ (n) ]。 它与CHAR 类型相似。不同的是NCHAR数据类型n 的取值为1 到4000。 因为NCHAR 类型采用
UNICODE 标准字符集(CharacterSet)。 UNICODE 标准规定每个字符占用两个字节的存储空间,所以它比非UNICODE 标准的数据类型多占用一
倍的存储空间。使用UNICODE 标准的好处是因其使用两个字节做存储单位,其一个存储单位的容纳量就大大增加了,可以将全世界的语言文字
都囊括在内,在一个数据列中就可以同时出现中文、英文、法文、德文等,而不会出现编码冲突。 3、VARCHAR VARCHAR数据类型的定义形式为VARCHAR [ (n) ]。 它与CHAR 类型相似,n 的取值也为1 到8000, 若输入的数据过长,将会截掉其超出部分
。不同的是,VARCHAR数据类型具有变动长度的特性,因为VARCHAR数据类型的存储长度为实际数值长度,若输入数据的字符数小于n ,则系统
不会在其后添加空格来填满设定好的空间。 一般情况下,由于CHAR 数据类型长度固定,因此它比VARCHAR 类型的处理速度快。 4、NVARCHAR NVARCHAR数据类型的定义形式为NVARCHAR[ (n) ]。 它与VARCHAR 类型相似。不同的是,NVARCHAR数据类型采用UNICODE 标准字符集
(Character Set), n 的取值为1 到4000。
4.3.6 文本和图形数据类型 这类数据类型用于存储大量的字符或二进制数据。 1、TEXT TEXT数据类型用于存储大量文本数据,其容量理论上为1 到2的31次方-1 (2, 147, 483, 647)个字节,在实际应用时需要视硬盘的存储空
间而定。 SQL Server 2000 以前的版本中,数据库中一个TEXT 对象存储的实际上是一个指针,它指向一个个以8KB (8192 个字节)为单位的数据页
(Data Page)。 这些数据页是动态增加并被逻辑链接起来的。在SQL Server 2000 中,则将TEXT 和IMAGE 类型的数据直接存放到表的数据行
中,而不是存放到不同的数据页中。 这就减少了用于存储TEXT 和IMA- GE 类型的空间,并相应减少了磁盘处理这类数据的I/O 数量。 2 NTEXT NTEXT数据类型与TEXT.类型相似不同的,是NTEXT 类型采用UNICODE 标准字符集(Character Set), 因此其理论容量为230-1(1, 073, 741, 823)
个字节。 3 IMAGE IMAGE数据类型用于存储大量的二进制数据Binary Data。 其理论容量为2的31次方-1(2,147,483,647)个字节。其存储数据的模式与TEXT 数据
类型相同。通常用来存储图形等OLE Object Linking and Embedding,对象连接和嵌入)对象。在输入数据时同BINARY数据类型一样,必须在
数据前加上字符“0X”作为二进制标识
4.3.7 日期和时间数据类型 1 DATETIME DATETIME 数据类型用于存储日期和时间的结合体。它可以存储从公元1753 年1 月1 日零时起到公元9999 年12 月31 日23 时59 分59 秒之间
的所有日期和时间,其精确度可达三百分之一秒,即3.33 毫秒。DATETIME 数据类型所占用的存储空间为8 个字节。其中前4 个字节用于存储
1900 年1 月1 日以前或以后的天数,数值分正负,正数表示在此日期之后的日期,负数表示在此日期之前的日期。后4 个字节用于存储从此日
零时起所指定的时间经过的毫秒数。如果在输入数据时省略了时间部分,则系统将12:00:00:000AM作为时间缺省值:如果省略了日期部分,则
系统将1900 年1 月1 日作为日期缺省值。 2 SMALLDATETIME SMALLDATETIME 数据类型与DATETIME 数据类型相似,但其日期时间范围较小,为从1900 年1 月1 日到2079 年6 月6:日精度较低,只能精确
到分钟,其分钟个位上为根据秒数四舍五入的值,即以30 秒为界四舍五入。如:DATETIME 时间为14:38:30.283 时SMALLDATETIME 认为是14:39:00 SMALLDATETIME 数据类型使用4 个字节存储数据。其中前2 个字节存储从基础日期1900 年1 月1 日以来的
天数,后两个字节存储此日零时起所指定的时间经过的分钟数。 下面介绍日期和时间的输入格式 日期输入格式 日期的输入格式很多大致可分为三类:
英文+数字格式 此类格式中月份可用英文全名或缩写,且不区分大小写;年和月日之间可不用逗号; 年份可为4 位或2 位;当其为两位时,若值小于50 则视为20xx 年,若大于或等于50 则 视为19xx 年;若日部分省略,则视为当月的1号。以下格式均为正确的日期格式: June 21 2000 Oct 1 1999 January 2000 2000 February 2000 May 1 2000 1 Sep 99 June July 00 数字+分隔符格式 允许把斜杠(/)、连接符(-)和小数点(.)作为用数字表示的年、月、日之间的分 隔符。如: YMD:2000/6/22 2000-6-22 2000.6.22 MDY:3/5/2000 3-5-2000 3.5.2000 DMY:31/12/1999 31-12-1999 31.12.2000 纯数字格式 纯数字格式是以连续的4 位6、位或8 位数字来表示日期。如果输入的是6 位或8 位 数字,系统将按年、月、日来识别,即YMD 格式,并且月和日都是用两位数字来表示: 如果输入的数字是4 位数,系统认为这4 位数代表年份,其月份和日缺省为此年度的1 月 1 日。如: 20000601---2000 年6 月1 日 991212---1999 年12 月12 日 1998---1998 年
时间输入格式 在输入时间时必须按“小时、分钟、秒、毫秒”的顺序来输入。在其间用冒号“:”隔开。但可将毫秒部分用小数点“.” 分,隔其后第一位
数字代表十分之一秒,第二位数字代表百分之一秒,第三位数字代表千分之一秒。当使用12 小时制时用AM。am 和PM(pm)分别指定时间是午
前或午后,若不指定,系统默认为AM。AM 与PM 均不区分大小写。如: 3:5:7.2pm---下午3 时5 分7 秒200 毫秒 10:23:5.123Am---上午10 时23 分5 秒123 毫秒 可以使用SET DATEFORMAT 命令来设定系统默认的日期-时间格式。
4.3.8 货币数据类型 货币数据类型用于存储货币值。在使用货币数据类型时,应在数据前加上货币符号,系统才能辨识其为哪国的货币,如果不加货币符号,则默
认为“¥”。各货币符号如图4-2所示。 1 MONEY MONEY 数据类型的数据是一个有4 位小数的DECIMAL 值,其取值从-2的63次方(-922,337,203,685,477.5808到2的63次方-1(+922,337,
203,685,477.5807),数据精度为万分之一货币单位。MONEY 数据类型使用8个字节存储。 2 SMALLMONEY SMALLMONEY数据类型类似于MONEY 类型,但其存储的货币值范围比MONEY数据类型小,其取值从-214,748.3648到+214,748.3647,存储空间为4 个
字节。
08 March re: Visual Studio .NET已检测到指定的WEB服务运行的不是ASP.NET 1.1版 2004-11-18 18:39 | lx
server is not running asp.net version 1.1 When you try to create a new ASP.NET 1.1 project or try to open, you may receive the following error message
visual studio has detected that the specified web server is not running asp.net version 1.1
If you have already googled and come across Microsoft knowledge base article 817267. PRB: "The Specified Web Server Is Not Running ASP.NET Version 1.1" Error Message When You Create ASP.NET 1.1 Application ( MKB817267 )
don't get confused by this article, the article applies to windows 2003 server.
You can actually fix this problem in less than 5 minutes and in 3 steps:
1) Open Add/Remove program and uninstall dot net version 1.0.
2) If dot net version 1.0 is not in the list of installed programs, find the following folder and delete it if found C:\WINDOWS\Microsoft.NET\Framework\v1.0.3705
3) run the executable with the following option from command window: C:\WINDOWS\Microsoft.NET\Framework\v1.1.xxxx\aspnet_regiis.exe -i
And you should be back in business. 24 February 帮广州的一家公司分析P2P的源码。他主要是做P2P的流媒体播放的,让我帮他分析源码并和播放器代码组合起来。给的酬劳还不错,3K,呵呵。其实我也不清楚市场行情的,我让他说价钱,我也没还就答应了!-_-也不知道有没被人骗了.....反正这也是一个锻炼的机会,也不必要太计较啦。这份酬劳也够我用的了。啊哈哈~~~希望加油,做好一点,说不定以后还有合作的机会($$$$$)钱啊钱~我都晕了。呵呵~~ 22 February 回到学校了。一切又要从新开始,我想一切都应该和以前不一样,迫切地希望自己的生命轨迹会在今年有个不同的轨道。bless me & bless my honey & bless all my friends~~~~~
Target:
1,完成p2p的流媒体播放器。
计划:争取每天至少看两篇论文,阅读一段代码。并提出自己的想法。最好能通过自己写的代码体现出来。争取5月份前完成这个Project。
2,ACM。在完成针对某一算法的题目的前提下,完成POJ上ULM Local Contest 的题目。每天应该至少AC两题。
3,雅思。每天做一篇模拟题。卡表,在考试的时间范围内完成,并估分。争取2,3天一篇作文。除了要把阅读中的生词消化之外至少背诵20个单词。
4,暂时没想到...(不断更新中....) 18 February 看Blog不回可是不厚道滴-.-
偶已经好努力写blog了哇~~~~
大家多踩两下哇~~~~ 17 February
| 2005男人感悟100条,男人,请认真阅读![转帖] |
|
|
1:能不抽烟最好不抽,它或许可以帮助你吸引一些女生,但不抽绝不会招来厌烦,表现男子气概的途径有很多,没必要拿健康做赌注。
2:给自己定目标,一年,两年,五年,也许你出生不如别人好,通过努力,往往可以改变70%的命运。破罐子破摔只能和懦弱做朋友。
3:找女朋友外表是第一关,但要了解她的品行之后再做打算也不迟。
4:不要在乎小钱,工作的人都后悔从前对自己的GF不够好。记住你们的重要日子,你们的谈话,女生要敏感得多,这样做,至少可以证明你对她的重视。
5:爱她,但别怕她,你们是恋人,也是朋友,她要的不是宠物,这样的感情,走不长远。
6:她要是病了,带她去医院,她害怕时,找个人少的地方抱着她,给她勇气,帮她排队,挂号,放下你那点可悲的面子,周围人只会向她投来羡慕的眼光,不会对你说三道四。
7:别把两个人的生活绞在一起,空间才是爱情的长寿药。不要经常吃醋,谁都有异性朋友,该吃的时候才吃,并且让她知道。
8:善待她的朋友,即使她讨厌的人,你也没资格说坏话,你要做的,就是静静的听她倾诉。适当给她安慰。有时候,她们更需要依靠,即使你们都还是学生。
9:不要问她过去,时机到了,她会毫无保留的告诉你。她要是想见从前那位,让她去,原因是你不让她去,她也会去。为何不表现得大度点,但要让她知道你相当的郁闷。
10:珍惜身边人,不要见异思迁,大家都需要安定。即使对方比你GF漂亮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:少玩游戏,这不是韩国,你打不出房子车子还有女人。进了大学,就进了社会,这是场马拉松。北京现在一个砖头抛上去,砸下来7,8个研究生受伤,现在的你是否该有点打算。
36:拿出极限,尽力而为。你要想的是成功,而不是失败。所以面对困难首先就是拿出信心。除了你心爱女人的鼓励,这应该是最有用的东西。
37:定时整理书桌书柜,良好的精神面貌可以让你事半功倍。
38:学好英语,那些说学英语没用的暂时可以不去管,他们要么年纪大了,要么就是自己早过了CET6准备托福了,在这里哗众取宠。你可以不拿证,但一定要学好。
39:不是足够热爱你的专业,并且学出来前途不够光明,趁早转业。现在更多人更看重“钱途”
40:知道自己要干什么,寝室的卧谈会的确可以帮你磨嘴皮子,夜深人静,问问自己,将来的打算,并朝着那个方向去实现。
41:偶尔翻翻时尚类的杂志,女朋友和女性朋友都可以从中受益。
42:尽量少看A片,正常的男人即使是单身,也不会成天迷恋肉欲。而每次你SY后都会有大量锌元素流失,此元素与你大脑活动有密切联系。
43:坚持做运动,俯卧撑可以锻炼你的胸肌和腹肌,请记住游泳圈是成功人事才有资格拥有的奢侈品。
44:每天早上一杯水,预防胆结实。睡前一小时不要喝水,否则会过早出现眼袋。
45:宁愿要深色袜子也少买白色的,这样会让人觉得你不够成熟,学生朋友自便。
46:新同事或新朋友请你吃饭,不要觉得理所当然,请礼尚往来,否则你的名声会越来越臭。无论是大学还是公司,很多故事都是听来的。
47:有男友的女人不要碰,即便你想one night stand 也要做好心理准备。后果同上,严重时会出现体肤之痛。
48:朋友的女人不要碰,无论是现在的还是曾经的,后果同上。要知道,男人经营自己就像经营一个公司,要树立品牌文化。想问为什么的朋友请先做个你是受害者的假设,再跟我发短消息讨论。
49:博爱的女人不要碰,往往这种女人连自己要什么都不知道,我想没人愿意和若干成年男性分享自己的爱。天作孽,犹可活,自作孽,不可活。
50:没主见,不上进,懒惰的女人不要碰。就算你有钱,你有的是钱,最终你也会厌烦其中。何况不见得她们个个都是花瓶,何况你还有审美疲劳。
51:不以物喜,不以己悲,我知道这很难,但要成功,这是必修课。
52:空闲时间不要全拿去泡BAR,读点文学作品,学习一些经营流程,管理规范,国际时事,法律常识。这能保证你在任何聚会都有谈资。
53:每年回母校看看那些为你付出过的老师,走上社会你才了解她们才是无私的,比起那点学费,她们简直太伟大了。学会感恩。
54:回家帮父母做点简单家务,陪他们买菜,做饭,逛街,冬天送他们一人一件羽绒服,他们并不奢望什么,但他们需要得到你的承认,中国的父母是最苦的,孩子是最幸福的。(离婚除外)
55:大家都年轻,没什么钱,不用太在意谁谁又穿AD ,NIKE ,或者其他。而GF对于PRADA,蓝寇,CD,LV,的热恋,你也不必放在心上,女人天生和美挂上了勾,她们只是宁愿相信你能够为她们买一样昂贵的礼物,以满足她们的虚荣心,然后在同伴面前炫耀一番。实则她们也是热爱生活的,而当你有能力完成时,也会觉得把她包装得漂漂亮亮的很是欣慰。
56:告诉她,你喜欢的内衣。或者在UNDERWEAR店要打佯时陪她去买。
57:欺负她时,请带上套子,如不习惯,请自行解决,直到无法忍受为止,或者泼自己一身冷水。流产很痛苦,我只是听说。
58:有正义感,但请更理智,你父母不希望养育二十多年的儿子化为泡影。但当她遇到流氓时,请你勇敢的挡在她前面。大声说话可以让你的勇气迅速提升。(这是我答辩时认识到的)
59:最好不要在她面前玩天真,多数MM都不喜欢,除非她要求。
60:接吻前先嚼块口香糖,接吻时请闭上眼睛,睁开时,告诉你有多爱她。
61:尊重每一个人,包括为你擦鞋的,卖报的,环卫工人...等等。
62:接到陌生电话请先说,“你好,找哪位”
63:想发脾气时,尽量忍,忍不住就去厕所蹲半个小时,或是找个海拔较高的地方站半个小时。
64:如果GF要跟你吵,尽量克制,不能避免时,跟她吵,吵架是最好的交流方式。你们互相可以得到心里渴望已久的答案。但别带脏字,别把对方的亲戚带出来,最后尽量妥协,有些事,只能暂时妥协。不要把问题留过夜。
65:出差回来给她一个惊喜,并带上礼物。(想在这条上跟我开玩笑的朋友,请私下跟我开)
66:在她兜里放些零钱,在她不常用的兜里放张一百。
67:尊老爱幼,帮助别人后,你会感到无比轻松快乐。
68:去市场买东西,杀价先杀四分之三,现在杀一半行不通了。
69:如果可以,给你的对手留条生路,钱是赚不完的。这个世界上,没有天生的敌人。
70:饮水思源,永远做一个有思想的人,即使你不会有大成就,钱也会足够花。
71:为她学一首歌,如果可能,结婚时当着大家的面唱给她听。
72:要做一件事,成功之前,没必要告诉其他人,成功之后,和他们分享快乐。
73:每年去寺庙为家人点几盏油灯,告诉自己的良心,你不在的时候,同样是爱他们的。
74:学会察言观色,不要意气用事,否则会有许多不必要的麻烦。
75:享受孤独,地球不会因为只有你一个人而停止转动,也许她会很晚才出现,在此之前,你要学会正确利用时间,并且让自己发光发亮。
76:从前的她,深夜给你打电话,如果你还爱她,接电话。如果你不爱她,关机。(没听见不在讨论范围之内)
77:夜里的约会最好不要选择偏僻的地方,有些突发事件,会让你痛不欲生。如果你还爱她的话。
78:公司的东西不要带回家,即使有小便宜,也别参与,在你成为领导前,也别指责,这是你管不到的。
79:开发你的另外一个情感宣泄功能,倾听。
80:朋友之间不要合作做生意,或者办公司。麻烦会接踵而来。你要减轻负担,减小风险,可以,找陌生人。
81:今日事,今日毕,不要日复一日,年复一年。不然到你60岁,你还告诉孙子,爷爷明年一定要毕业!
82:感谢曾经爱过你的人,她祝福你的短信,一定要回。
83:朋友之间发生争执,不要次次都是忍让,每个人都有坚持自己的权利,让他们知道你的想法,你所坚持的。没关系,不出两天,你们又是好朋友。
84:说该说的,不说不该说的。对朋友,也应当有所保留。对她,不要把她和从前那个相提并论,谁都受不了。
85:头发,指甲,胡子,打理好。社会是个排斥性的接受体,这个星球所需要的艺术家极其有限,请不要冒这个险,就算你留长头发比较好看,也要尽量给人干净的感觉。
86:牌局可有可无,那不是年轻人该干的,除非工作需要,否则不要培养这种兴趣。当你看见GF坐在赌博机面前聚精会神的呐喊着某张牌时,你是什么感觉?
87:每学期给自己写总结,上课认真学习,所谓的好好学习,天天向上,学好了,就是最管用的绝招。机会常常伪装成麻烦,从你身边路过,也只会留给做好准备的人。上班的朋友同理。
88:不要整天把国家大事摆在嘴上,去改变你能改变的,接受你无法改变的。
89:选一个生日陪你母亲过,那也是她的受难日。不要年年都和同样一群人过。到头来,全心为你的,只有她。
90:有了手机,尽量少上网,就算你仅仅是看新闻,读文章,大把时间也会不经意从你身边流失。
91:不要以为你是个男人,就不需要保养。至少饮食方面不能太随便,多吃番茄,海产品,韭菜,香蕉,都是对男性健康有益处的食物。你要是看不到价值,我可以告诉你。至少你能把看病节约下来的钱给她多买几盒DIOR。
92:善待小动物,你以后也有子子孙孙,同样是生命,培养一下自己的爱心吧。这并不表示你懦弱。
93:如果考公务员,要有十足的心理准备。早点开始托关系吧,还不见得一定就有收效。
94:力求上进的人,不要总想着靠谁谁,人都是自私的,自己才是最靠得住的人。
95:如果你们相处几年下来,她开始冷落你,对你不闻不问,请别怪她,让她离开。给不了她幸福,给她自由。
96:如果你想和她说分手,请在考试之后,人都是脆弱的。
97:她给你买礼物,你可以高兴,但不要太高兴。人生就是场经营,有人经营感情,有人经营利益,有人经营幸福,而有人经营阴谋。
98:面对失败,不要太计较,天将降大任于斯人也,必先苦其心志,劳其筋骨,饿起体肤....但要学会自责,找到原因,且改掉坏习惯。二十岁没钱,那很正常,三十岁没钱,那是宿命。
99:学会微笑,以后在很多场合都用得上它。如何让微笑好看,首先你得拥有健康的牙齿。如何保证牙齿健康,一,早晚,饭后刷牙;二,每年去探望一次牙科医生;三,少管闲事。
100:凡事要坚持,就像我写这篇文章一样。 | 16 February 题记:google 的成功除了一个个出色的创意外,还因为有 Jeff Dean 这样的软件架构天才。
------ 编者
官方的 Google Reader blog 中有对BigTable 的解释。这是Google 内部开发的一个用来处理大数据量的系统。这种系统适合处理半结构化的数据比如 RSS 数据源。 以下发言 是 Andrew Hitchcock 在 2005 年10月18号 基于: Google 的工程师 Jeff Dean 在华盛顿大学的一次谈话 (Creative Commons License).
首先,BigTable 从 2004 年初就开始研发了,到现在为止已经用了将近8个月。(2005年2月)目前大概有100个左右的服务使用BigTable,比如: Print,Search History,Maps和 Orkut。根据Google的一贯做法,内部开发的BigTable是为跑在廉价的PC机上设计的。BigTable 让Google在提供新服务时的运行成本降低,最大限度地利用了计算能力。BigTable 是建立在 GFS ,Scheduler ,Lock Service 和 MapReduce 之上的。
每个Table都是一个多维的稀疏图 sparse map。Table 由行和列组成,并且每个存储单元 cell 都有一个时间戳。在不同的时间对同一个存储单元cell有多份拷贝,这样就可以记录数据的变动情况。在他的例子中,行是URLs ,列可以定义一个名字,比如:contents。Contents 字段就可以存储文件的数据。或者列名是:”language”,可以存储一个“EN”的语言代码字符串。
为了管理巨大的Table,把Table根据行分割,这些分割后的数据统称为:Tablets。每个Tablets大概有 100-200 MB,每个机器存储100个左右的 Tablets。底层的架构是:GFS。由于GFS是一种分布式的文件系统,采用Tablets的机制后,可以获得很好的负载均衡。比如:可以把经常响应的表移动到其他空闲机器上,然后快速重建。
Tablets在系统中的存储方式是不可修改的 immutable 的SSTables,一台机器一个日志文件。当系统的内存满后,系统会压缩一些Tablets。由于Jeff在论述这点的时候说的很快,所以我没有时间把听到的都记录下来,因此下面是一个大概的说明:
压缩分为:主要和次要的两部分。次要的压缩仅仅包括几个Tablets,而主要的压缩时关于整个系统的压缩。主压缩有回收硬盘空间的功能。Tablets的位置实际上是存储在几个特殊的BigTable的存储单元cell中。看起来这是一个三层的系统。
客户端有一个指向METAO的Tablets的指针。如果METAO的Tablets被频繁使用,那个这台机器就会放弃其他的tablets专门支持METAO这个Tablets。METAO tablets 保持着所有的META1的tablets的记录。这些tablets中包含着查找tablets的实际位置。(老实说翻译到这里,我也不太明白。)在这个系统中不存在大的瓶颈,因为被频繁调用的数据已经被提前获得并进行了缓存。
现在我们返回到对 列的说明:列是类似下面的形式: family:optional_qualifier。在他的例子中,行:www.search-analysis.com 也许有列:”contents:其中包含html页面的代码。 “ anchor:cnn.com/news” 中包含着 相对应的url,”anchor:www.search-analysis.com/” 包含着链接的文字部分。列中包含着类型信息。
(翻译到这里我要插一句,以前我看过一个关于万能数据库的文章,当时很激动,就联系了作者,现在回想起来,或许google的 bigtable 才是更好的方案,切不说分布式的特性,就是这种建华的表结构就很有用处。)
注意这里说的是列信息,而不是列类型。列的信息是如下信息,一般是:属性/规则。 比如:保存n份数据的拷贝 或者 保存数据n天长等等。当 tablets 重新建立的时候,就运用上面的规则,剔出不符合条件的记录。由于设计上的原因,列本身的创建是很容易的,但是跟列相关的功能确实非常复杂的,比如上文提到的 类型和规则信息等。为了优化读取速度,列的功能被分割然后以组的方式存储在所建索引的机器上。这些被分割后的组作用于 列 ,然后被分割成不同的 SSTables。这种方式可以提高系统的性能,因为小的,频繁读取的列可以被单独存储,和那些大的不经常访问的列隔离开来。
在一台机器上的所有的 tablets 共享一个log,在一个包含1亿的tablets的集群中,这将会导致非常多的文件被打开和写操作。新的log块经常被创建,一般是64M大小,这个GFS的块大小相等。当一个机器down掉后,控制机器就会重新发布他的log块到其他机器上继续进行处理。这台机器重建tablets然后询问控制机器处理结构的存储位置,然后直接对重建后的数据进行处理。
这个系统中有很多冗余数据,因此在系统中大量使用了压缩技术。
Dean 对压缩的部分说的很快,我没有完全记下来,所以我还是说个大概吧:压缩前先寻找相似的 行,列,和时间 数据。
他们使用不同版本的: BMDiff 和 Zippy 技术。
BMDiff 提供给他们非常快的写速度: 100MB/s – 1000MB/s 。Zippy 是和 LZW 类似的。Zippy 并不像 LZW 或者 gzip 那样压缩比高,但是他处理速度非常快。
Dean 还给了一个关于压缩 web 蜘蛛数据的例子。这个例子的蜘蛛 包含 2.1B 的页面,行按照以下的方式命名:“com.cnn.www/index.html:http”.在未压缩前的web page 页面大小是:45.1 TB ,压缩后的大小是:4.2 TB , 只是原来的 9.2%。Links 数据压缩到原来的 13.9% , 链接文本数据压缩到原来的 12.7%。
Google 还有很多没有添加但是已经考虑的功能。
1. 数据操作表达式,这样可以把脚本发送到客户端来提供修改数据的功能。 2. 多行数据的事物支持。 3. 提高大数据存储单元的效率。 4. BigTable 作为服务运行。 好像:每个服务比如: maps 和 search history 历史搜索记录都有他们自己的集群运行 BigTable。 他们还考虑运行一个全局的 BigTable 系统,但这需要比较公平的分割资源和计算时间。
15 February 打算20号回学校了,可是在回学校前的这几天里却感到莫名的烦躁.不知为什么,总是做什么都提不起劲来,想做题,却不想思考.想学点东西,却静不下心来.
哎~~其实我是恨渴望回到学校去的,下学期有很多事情要做,有很多东西要学,有很多东西需要我很努力地去维持,去继续.有使命等待我回去完成~~~ 
但是不知为什么这一切我在家里就是提不起精神去做.哎~~~好烦好烦啊.有很多事情都没有解决啊...郁闷死我了,好想哭:((((~~ 14 February 不管是否要逃避点什么,我都要写一点东西了.刚才为了她一句话,我们又吵了起来,而且这次我的反应还特别地强烈,手机也关掉了.是否我太小气了?还是为了别的什么?每次这种时候我就特别地控制不了自己,总要做点伤害彼此双方的事.
实在不愿意在今天情人节说起这些不愉快的事,当是一个教训吧.记一下,希望以后我们可以更加快乐~~
咳咳.
不过虽然是情人节,我们始终不能在一起过:( 成本太大,不过打算推后庆祝吧.一个节日过得是否开心,关键不是什么时候过,是和什么人一起过吧.嘿嘿.也许今天每个人都会有自己的故事,希望所有的人都开开心心,有情人终成眷属^_^ 11 February 自己都还没仔细看看,发在spaces上作参考.顺便也可以学习一下.努力ing...... Singleton 的实现
////////////////////////////////////////////////////////////////////// // Singleton 的实现 //////////////////////////////////////////////////////////////////////
//这种作为类的静态对象实现的单件模式无法控制该静态对象的初始化时间. //因为初始化顺序是未定义的. //如果要控制初始化时间. 可以用函数内的静态变量的方法. 它的初始化就是在函数首次被调用时进行了.
class Singleton { private: static Singleton _instance;
Singleton(){} Singleton(const Singleton &){};
public: ~Singleton(){}
static Singleton & get() { return _instance; } void Singleton::run() { cout << "The _instance is Running !" << endl; } };
Singleton Singleton::_instance;
int main() {
Singleton::get().run();
return 0; }
//用另一种方法实现
//单件模式 #include <iostream.h> class point {
public: static point * getinstance() { if (p == NULL) p = new point(); return p; } private: point() { cout<<"hello!"; }
static point * p; };
point * point::p = NULL; void main() { point * pt = point::getinstance(); }
第16章 Container Classes 容器类
第16章 Container Classes 容器类
分为序列式容器和关联式容器. 另外STL还提供了3种Container adapters 它们自身并不是容器.
16.1 序列 (Sequences)
STL定义了3种序列 vector list deque
16.1.1 vector vector<T , Allocator> 支持随机访问. 方便的在尾端插入/删除元素. vector的size和capacity是两个概念. vector会自动管理内存. 它典型的有三个成员变量指针. start finish end_of_storage
没有成员函数可以缩小vector的容量(capacity). 但可以把其元素拷贝至另一个 小容量的容器.然后用容器间赋值的办法间接实现.
构造函数: expilcit vector :: vector( const Allocator& A = Allocator() ); // 产生一个空的vector
expilcit vector :: vector( size_type n, const T & x = T() , const Allocator & A = Allocator() ); // 产生的vector中具有n个元素. 且 n 个元素都是 x 的复制品.
template<class InputIterator> vector:: vector(InputIterator f, InputIterator l, const Allocator& A = Allocator() ); //产生的vector 包含 [ f , l) 的元素的复制品. 其他的一些函数: allocator_type vector :: get_allocator() const ; // 返回vector构造时所用的allocator
void vector :: reserve(size_type n); // 增加容量. 若n <= 当前capacity() . 则此函数不作任何事.
reference vector:: front() //返回第一个元素.
reference vector:: back() //返回最后一个元素.
void vector:: pop_back() //删除最后一个元素.
iterator vector:: insert(iterator pos, const T& x); //在pos的前一个位置插入x.
template < class InputIterator> void vector :: insert (iterator pos , InputIteartor f, InputIterator l); //在pos的前一个位置插入[f, l)
void vector:: insert(iterator pos, size_type n, const T& x) //在pos前一个位置插入n个x的复制品
iterator vector::erase(iterator pos) // 删除pos所指元素.
iterator vector::erase(iterator f, iterator l) // 删除[f,l)内的元素.
void vector :: clear() //删除所有元素.
void vector::resize(size_type n, const T& t = T() ); // 将容器内元素的数量改变为n .新增的元素为t的复制品.
16.1.2 list list<T, Allocator> list是一种双向链表. 所以它能支持双向移动. 对它的插入/删除/连接不会造成指向该list的iterator失效.
构造函数: expilcit list::list(const Allocator& A = Allocator() ) //产生一个空的list
expilcit list::list(size_type n, const T& x = T(), const Allocator& A=Allocator() ); //产生的list包含n个x的复制品.
//拷贝构造函数
template<class InputIterator> list::list(InputIteator f, InputIterator l , const Allocator& A = Allocator() ); // 产生的list包含[f , l)
其他一些成员函数: size_type list::size() const ; //返回list的元素的个数. 它要遍历一遍链表.
size_type list::max_size() const ; //返回list的最大可能的元素个数;
reference list::front() ; //返回第一个元素 reference list::back(); // 返回最后一个元素.
void list::push_front(const T& t) ; //在开头插入元素;
void list::pop_front() ; //删除开头元素;
void list::push_back(const T& t) ; //在结尾插入元素;
void list::pop_back() ; //删除结尾元素;
iterator list::insert(iterator pos , const T& x); //在pos的前一个位置插入x
template<class InputIterator> void list :: insert(iterator pos, InputIterator f, InputIterator l); //在pos前插入[f,l)
void list::insert(iterator pos, size_type n, const T& x) //在pos前插入n个x的复制品.
iterator list::erase(iterator pos); //删除pos所指元素;
iterator list::erase(iterator f, iterator l) //删除[f , l)的元素
void list:: clear()
void list::resize(size_type n, const T& t = T() );
16.1.3 slist //单向链表. stl中不支持
16.1.4 deque deque<T, Allocator> 双向队列.它和vector类似. 支持随机访问. 支持在常量时间内在序列尾端插入/删除元素. 但它还支持在常量时间内在序列开头插入删除元素. 它在序列中间插入元素的时间开销取决 于插入位置距离deque开头或结尾中较短的距离. deque的实现比较复杂.所以一般开销都比较大.一般需要排序的时候把所有元素都复制到vector中 排序后再复制回来. 但是它支持在序列的开头和结尾快速的插入/删除元素.
16.2 Associative Containers (关联式容器) STL提供4种关联容器. set map multiset multimap
16.2.1 set set<Key, Compare, Allocator>
set 中的key_type型元素都是以递增排序的.(参数 Compare 定义这种顺序关系缺省为 less<Key>) . 而且没有重复key. 在set中插入/删除元素不会造成指向它的Iterator 失效.
构造函数: expilcit set::set( const key_compar& comp=key_compare() , const Allocator& A = Allocator() ); template <class InputIteartor> set :: set (InputIterator f, InputIterator l, const key_compar& comp=key_compare() , const Allocator& A = Allocator() )
其他一些成员函数: begin() / end() rbegin() / rend() size() max_size() empty() key_comp() //比较key的函数对象 value_comp() get_allocator() pair<iterator, bool> set:: insert(const value_type& x); //插入x. 若插入成功(即原set中没有该key). 返回true
template<class InputIterator> void set::insert(InputIterator f, InputIteraor l); //将[f,l)插入set
void set::erase(Iteartor pos); void set::erase(const key_type & k); void set::erase(iterator f, iterator l);
iterator set::find(const key_type& k) const;
size_type set::count(const value_type& k) const ; //返回键值为k的元素个数 . 非0即1.
16.2.2 map map<Key, T, Compare, Allocator> 它和set类似. 但它存储的式(键,值)对. 它可以方便的用 [键] 的形式取一个元素. 但这只是它的方便的写法. 代替find / insert 等函数.
构造函数: expilcit map::map(const key_compare& comp = key_compare(), const Allocator& A = Allocator() ); //产生一个空的map
template <class InputIteartor> map :: map (InputIterator f, InputIterator l, const key_compar& comp=key_compare() , const Allocator& A = Allocator() )
其他一些成员函数: begin() / end() rbegin() / rend() size() max_size() empty() key_comp() //比较key的函数对象 value_comp() get_allocator() swap()
iterator map:: insert(iterator pos, const value_type& x);
template<class InputIterator> void map::insert(InputIterator f, InputIteraor l); //将[f,l)插入set
void map::erase(Iteartor pos); size_type map::erase(const key_type & k); void map::erase(iterator f, iterator l);
iterator map::find(const key_type& k) const;
size_type set::count(const value_type& k) const ; //返回键值为k的元素个数 . .
mapped_type& operator[ ] (const key_type&); //由于同一个键在一个map中最多出现一次. 所以它返回该键关联的对象的引用. 若map中没有该对象. //则先将一个缺省的对象插入. //注意: 返回的是map元素的值的引用.而不是value_type&
16.2.3 multiset multiset<Key, Compare, Allocator> 它与set的区别是它可以容纳相同key值的元素在一个对象里.参考set.
16.2.4 multimap multimap<Key, T, Compare, Allocator> 它与map的区别是它可以容纳相同的key值的多个元素在一个对象里. 参考map.
16.3 Container Adapters
包括stack queue priority_queue三个类. 他们都是只提供容器的有限的操作.
16.3.1 stack stack< T , Sequence > //第2个参数类型为stack底层实现所用的容器的类型. 缺省为 deque<T> 它声明于 <stack> 代表栈数据结构. 它只允许在栈顶 访问/插入/删除元素. 但不能访问栈内的其他元素. 构造函数: stack(); stack(Sequence& s) ; //用s初始化栈内底层实现时所用的容器. 其他函数: size() empty() top() push(const value_type& x) void pop();
16.3.2 queue queue < T , Sequence > //第2个参数类型为queue 底层实现所用的容器的类型. 缺省为 deque<T> 它声明于 <queue > 代表队列数据结构. 它只允许访问队列两端的元素. 在队列结尾插入元素. 以及在队列开始删除元素.
构造函数: queue (); queue (Sequence& s) ; //用s初始化栈内底层实现时所用的容器. 其他函数: size() empty() front() back() push(const value_type& x) void pop();
16.3.3 priority_queue priority_queue < T , Sequence , Compare> //第二个类型参数是它底层实现用到的容器.缺省是vector<T>.通常用堆来实现. //第三个参数提供T型对象的大小比较,缺省为less<T>. 优先级队列. 它只能插入/查看/删除最顶端的元素. 不能修改任何一个元素. 也不能遍历这些元素. 它最顶端的元素是元素中的最大值的一个.
stl中它声明于<queue>
构造函数: priority_queue (const Compare& c = Compare() ); //构造一个空的优先级队列 template<class InputIterator> priority_queue (InputIterator f, InputIterator l , const Compare& c = Compare() ); 构造的优先级队列包含了[f , l) 的元素.
priority_queue (const Compare& c, const Sequence& s); //先用s构造优先级队列中内部实现所用的容器对象. 在根据 c 指定的比较对其排序.
template<class InputIterator> priority_queue (InputIterator f, InputIterator l , const Compare& c, const Sequence& s); 构造的优先级队列包含了s中的元素, 以及[f , l) 的元素. 并已经排序.
其他函数: size() empty() top() //返回的是最顶端元素的const型引用. push(const value_type& x) void pop();
第15章 Function Object Classes 函数对象类
第15章 Function Object Classes 函数对象类
在<functional>
15.1 Function Object Base Classes
15.1.1 unary_function //单参 unary_function<Arg, Result> 它是一个空基类. 没有任何成员数据或成员函数. 只有类型定义信息. 两个typedef: argument_type //参数的类型 result_type //返回值类型
15.1.2 binary_function binary_function<Arg1, Arg2, Result> 它是一个空基类. 没有任何成员数据或成员函数. 只有类型定义信息. 三个typedef: first_argument_type //参数1的类型 second_argument_type //参数2的类型 result_type //返回值类型
15.2 算术运算 (Arithmetic Operations)
15.2.1 plus 类 plus<T> binary_function<T,T,T>的子类. 该类的函数对象计算两个参数的和. 例如: plus<int>( ) 构造了一个该类的对象. plus<int>() ( 2, 3 ); //得到5.
15.2.2 minus 类 minus<T> 类似plus类. 它计算两个参数的差. x-y
15.2.3 multiplies multiplies<T> 类似plus类. 它计算两个参数的积. x*y
15.2.4 divides divides<T> 类似plus类. 它计算两参数的商. x/y
15.2.5 modulus modulus<T> 类似plus类. 它计算两参数的余数. x%y
15.2.6 negate negate<T> 该类的对象做函数时.只有一个参数. 计算参数的相反数. -x
15.3 大小比较 ( Comparisons )
15.3.1 equal_to equal_to<T> 其result_type为bool 该类的对象做函数时.判断两个参数是否相等. x == y 返回true
15.3.2 not_equal_to not_equal_to<T> 类似equal_to.判断两个参数是否不等. x != y 返回true
15.3.3 less less<T> 类似equal_to. 判断 x < y
15.3.4 greater greater<T> 类似equal_to . 判断 x > y
15.3.5 less_equal less_equal<T> 类似equal_to. 判断 x <= y
15.3.6 greater_equal greater_equal<T> 类似equal_to . 判断 x >= y
15.4 逻辑运算 (Logical Operations)
15.4.1 logical_and logical_and<T> 计算 x && y .
15.4.2 logical_or logical_or<T> 计算 x || y .
15.4.3 logical_not logical_not<T> 计算 !x
15.5 证同( Identity ) 与 投射( Projection )
15.5.1 identity identity<T> 该类的函数对象只有一个参数.返回值还是该参数.
15.5.2 project1st project1st<Arg1, Arg2> 它接受两个参数. 返回第一个参数并忽略第二个参数. 是identity的一般化形式.
15.5.3 project2nd project2nd<Arg1, Arg2> 它接受两个参数. 返回第二个参数并忽略第一个参数. 是identity的一般化形式.
15.5.4 select1st select1st<Pair> 接受一个pair参数. 返回pair的第一个元素.
15.5.5 select2nd select2nd<Pair> 接受一个pair参数. 返回pair的第二个元素.
15.6 特殊的函数对象
15.6.1 hash hash<T> 其中类型T.在stl中只能是char* . const char* . string 以及内建的整型. 如果你要 搭配其他的类型就要提供自己的Hash函数类. 使用例子: hash<const char*> H; cout << H("foo") << endl;
15.7 Member Function Adapters
15.8 其他的 Adapters
15.8.1 binder1st 第14章 Iterator Classes (迭代器类)
第14章 Iterator classes 迭代器类
在头文件<iterator>
14.1 Insert Iterators 是一种Output Iterator.
14.1.1 front_insert_iterator front_insert_iterator<FrontInsertionSequence> 这个类是具有Output Iterator功能的一个迭代器适配器类.通过该类型完成的赋值动作.可以将对象 插入到序列的开头(原第一个元素之前). 使用例子: list<int> l; l.push_front(3); front_insert_iterator<list<int> > ii(l); *ii ++ = 0; //将0安插到l最前边. *ii++ = 1; // 将1安插到0前边; ................ 再看一个例子. 它将一个序列的元素反序拷贝到另一序列中了: vector<int> v; ...... list<int> l; copy(v.begin(), v.end(), front_inserter(l)); //不明确写出front_insert_iterator类型. //而是用辅助函数front_inserter . 这样比较方便.
front_insert_iterator 类的一些成员函数: front_insert_iterator::front_insert_iterator(FrontInsertionSequence & s); //构造函数.接受一个容器类的对象的参数. //拷贝构造函数. //析构函数 front_insert_iterator& front_insert_iterator:: operator* (); //用来实现 *i = x. 在序列前插入. front_insert_iterator& front_insert_iterator:: operator++(); //重载++ 包括前缀后缀的. 还有一个非成员的函数: template <class FrontInsertionSequence> front_insert_iterator <FrontInsertionSequence> front_inserter(FrontInsertionSequence& s) ; //等价于 front_insert_iterator <FrontInsertionSequence>(s); 构造函数. 但使用更方便.
14.1.2 back_insert_iterator back_insert_iterator <BackInsertionSequence> 它和上一个迭代器适配器类相似. 在序列后边插入元素. 如果ii是一个back_insert_iterator<Seq> 则 *ii = x 就相当于 seq.push_back(x);
14.1.3 insert_iterator insert_iterator <Container> 迭代器适配器类. 它的构造函数要两个参数: insert_iterator::insert_iterator(Container& c, Container::iterator i); //赋值时会在i所指元素之前插入元素. 此外还有一个返回该类对象的非成员函数inserter : template<class Container, class Iterator> insert_iterator<Container> inserter(Container& c, Iterator p); 这个函数相当于insert_iterator<container>(c, i); 但更方便.
14.2 Stream Iterators 配合输入输出流类工作.
14.2.1 istream_iterator istream_iterator<T, charT, traits, Distance> 是一种Input Iterator. 它能为"来自某个basic_istream"的对象执行格式化 输入动作. 一旦stream结束. istream_iterator便呈现一个特别的"stream终结值". 它的模板参数分别为: T istream_iterator的value_type. 即*运算返回值的类型. CharT InputStream的chartype . 缺省为char. traits InputStream 的char traits class . 缺省为 char_traits<charT>. Distance Iterator的difference type. 缺省为 ptrdiff_t. 在这个类中定义的还有: char_type : charT traits_type: traits istream_type : basic_istream<charT, traits> 构造函数: istream_iterator( istream_type& s); //当s到达stream终点时. 这个迭代器和end-of-stream iterator比较结果会相等. 缺省构造函数: istream_iterator() //它产生一个end-of-stream iterator .那是个past-the-end(结尾之后)的iterator.
14.2.2 ostream_iterator ostream_iterator<T , charT , traits> 它是一个Output Iterator. 能将一个T object格式化输出到某个指定的basic_ostream中. 模板参数: T: 被写到ostream的那些对象的类型. charT: Output stream 的chartype . 缺省为char traits: Output stream 的chartrais class . 缺省为 char_traits<charT> 在这个类中定义的还有: char_type : charT traits_type: traits ostream_type : basic_ostream<charT, traits> 构造函数: ostream_iterator(ostream_type& s); //它产生一个osteram_iterator .使得对这个迭代器的赋值就像 s << t 一样. ostream_iterator(ostream_type& s, const charT* delim); // 这个构造函数具有定界符号(delimiter). 它产生的osteram_iterator. 使得通过对该迭代器的赋值就像 s << t << delim 一样.
14.2.3 istreambuf_iterator istreambuf_iterator<chatT, traits> 这个类和istream_iterator非常相似. 但它只是从input stream读入单个字符. 它是一种Input Iterator. 在遇到stream终结时. 会以一个past-the-end值表示之. 模板参数: charT: istreambuf_iterator的valuetype. 表示这个迭代器会读入类型为charT的字符. traits: InputStream的char_traits class . 缺省为 char_traits<charT>
使用例子: istreambuf_iterator<char> first(cin); istreambuf_iterator<char> end; vector<char> buffer(first, end); .....
14.2.4 ostreambuf_iterator ostreambuf_iterator <charT, traits> 和上一个类似.
14.3 reverse_iterator reverse_iterator<Iterator> 这是一个迭代器适配器类. 它能够在区间上逆向移动.它的++相当于原迭代器的-- 例如有 list<int> l; 把l的end()转换成该类迭代器用 reverse_iterator< list<int> :: iterator> ( l.end());
第13章 排序和查找
第13章 排序和查找 Sorting and Searching
13.1 对某个区间排序 Sorting Ranges
13.1.1 sort //将元素以非递减顺序排序 //排序后相等的元素之间的前后关系不保持. (1)用operator< template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); (2)用指定的函数比较代替< template <class RandomAccessIterator, class StrictWeakOrdering> void sort (RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
13.1.2 stable_sort //与sort的区别是它对排序后相等的元素之间的前后关系保持. 1)用operator< template <class RandomAccessIterator> void stable_sort (RandomAccessIterator first, RandomAccessIterator last); (2)用指定的函数比较代替< template <class RandomAccessIterator, class StrictWeakOrdering> void stable_sort (RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
13.1.3 partial_sort // 部分的排序. 应用与 要求序列中前n个(n为middle - first)最小的元素的情况. // 因为没有必要对整个序列排序. 所以这里用它比用sort快. 1)用operator< template <class RandomAccessIterator> void stable_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); (2)用指定的函数比较代替< template <class RandomAccessIterator, class StrictWeakOrdering> void stable_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, StrictWeakOrdering comp);
13.1.4 partial_sort_copy //将排序后的元素复制至另一序列中. //复制的元素的个数为源序列长度和目的序列长度之小者 (1)用operator< template<class InputIterator, class RandomAccessIterator > void partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); (2)用指定的函数比较代替< template<class InputIterator, class RandomAccessIterator , class StrictWeakOrdering > void partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, StrictWeakOrdering comp);
13.1.5 nth_element //与partial_sort部分排序类似, 它也是部分的排序. // 区别是. 它只对小于(*nth)的部分排序.也就是在没排序的元素中找一个值.只排小于这个值的元素. (1)用operator< template <class RandomAccessIterator > void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); (2)用指定的函数比较代替< template <class RandomAccessIterator , class StrictWeakOrdering> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, StrictWeakOrdering comp);
13.1.6 is_sorted //检查一个序列是否已排序 1)用operator< template <class ForwardIterator> void is_sorted (ForwardIterator first, ForwardIterator last); (2)用指定的函数比较代替< template <class ForwardIterator, class StrictWeakOrdering> void is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrdering comp);
13.2 sorted ranges 上的操作行为
13.2.1 二分查找法 Binary Search
13.2.1.1 binary_search //2分法查找序列中是否有指定元素. 找到返回true. (1)2分查找时用 < template <class ForwardIterator, class StrictWeaklyComparable> bool binary_search(ForwardIterator first, ForwardIterator last, const StrictWeaklyComparable& value); (2)用指定的函数对象代替 < template <class ForwardIterator, class T, class StrictWeakOrdering> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);
13.2.1.2 lower_bound //用2分法查找一个位置. 返回值为"在不破坏顺序的前提下"的第一个可以插入value的位置. (1)2分查找时用 < template <class ForwardIterator, class StrictWeaklyComparable> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const StrictWeaklyComparable& value); (2)用指定的函数对象代替 < template <class ForwardIterator, class T, class StrictWeakOrdering> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);
13.2.1.3 upper_bound //用2分法查找一个位置. 返回值为"在不破坏顺序的前提下"的最后一个可以插入value的位置. (1)2分查找时用 < template <class ForwardIterator, class StrictWeaklyComparable> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const StrictWeaklyComparable& value); (2)用指定的函数对象代替 < template <class ForwardIterator, class T, class StrictWeakOrdering> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);
13.2.1.4 equal_range //用2分法查找一个元素. 返回值为"在不破坏顺序的前提下"的第一个和最后一个可以插入value的位置. (1)2分查找时用 < template <class ForwardIterator, class StrictWeaklyComparable> pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const StrictWeaklyComparable& value); (2)用指定的函数对象代替 < template <class ForwardIterator, class T, class StrictWeakOrdering> pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);
13.2.2 合并(Merging)两个Sorted Ranges
13.2.2.1 merge //合并两个区间为一个区间. 并且保持相对顺序. 对相等的元素.序列1中的在2的前面. (1) 用 < template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); (1) 用comp代替 < template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp);
13.2.2.2 inplace_merge //对一个序列.如果他的前半部分和后半部分是排过序的. 则这个函数将其变为整体序列有序的. //并且排序后的序列保持源序列的顺序. (1) 用 < template <class BidirectionalIterator> inline void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); (2) 用 comp 代替 < template <class BidirectionalIterator, class StrictWeakOrdering> inline void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, StrictWeakOrdering comp);
使用例子: //排序算法 merge sort template <class BidirectionalIterator> void mergesort(BidirectionalIterator first, BidirectionalIterator last){ typename iterator_traits<BidirectionalIterator> :: difference_type n = distance(first, last); if (n == 0 || n==1) return; else { BidirectionalIterator mid = first + n /2; mergesort(first, mid); mergesort(mid, last); inplace_merge(first, mid, last); } }
13.2.3 在已序序列(Sorted Ranges) 上执行集合(Set) 相关操作
13.2.3.1 includes //对于两个已序集合. 判断序列2是否是序列1的子集. (1)用 < template <class InputIterator1, class InputIterator2> bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); (1) 用comp代替 < template <class InputIterator1, class InputIterator2, class StrictWeakOrdering> bool merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, StrictWeakOrdering comp);
13.2.3.2 set_union //计算两个已序序列的并集. 把结果保存在另一个序列中.结果序列也有序. (1) 用< template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); (1) 用comp代替 < template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering> OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp);
13.2.3.3 set_intersection //计算两个已序序列的交集. 把结果保存在另一个序列中.结果序列也有序.
(1) 用< template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); (1) 用comp代替 < template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering> OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp);
13.2.3.4 set_difference //计算两个已序序列S1和S2. 只在S1而不在S2的元素够成的集合. 把结果保存在另一个序列中. (1) 用< template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); (1) 用comp代替 < template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering> OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp);
13.2.3.4 set_symmetric_difference //计算两个已序序列的对称差集.即只在一个序列中而不在另一个中的元素够成的集合. // 把结果保存在另一个序列中.结果序列也有序. (1) 用< template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); (1) 用comp代替 < template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering> OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp);
13.3 堆的相关操作 Heap Operations 堆并不是以顺序排列的序列. 而是以树状的方式表现序列的.其每个节点都小于或等于其父节点.
13.3.1 make_heap // 将一个序列排序成堆方式的. (1) 用 < template <class RandomAccessIterator> void make_heap(RandomAccessIterator first, RandomAccessIterator last); (2) 用 comp 代替 < template <class RandomAccessIterator, class StrictWeakOrdering comp> void make_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp comp);
13.3.2 push_heap // 前提是序列[first, last-1)是一个有效的堆.则这个函数将一个对 // 象添加到堆中.所要添加的对象就是序列中最后那个元素*(last-1). (1) 用 < template <class RandomAccessIterator> void push_heap(RandomAccessIterator first, RandomAccessIterator last); (2) 用 comp 代替 < template <class RandomAccessIterator, class StrictWeakOrdering comp> void push_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp comp);
13.3.3 pop_heap // 前提是序列[first, last)是一个有效的堆.则这个函数将堆中最大的一个对 // 象从堆中删除.所要删除的对象就是序列中第一个元素*first; 删除后堆将"缩小"为[first, last-1) (1) 用 < template <class RandomAccessIterator> void pop_heap(RandomAccessIterator first, RandomAccessIterator last); (2) 用 comp 代替 < template <class RandomAccessIterator, class StrictWeakOrdering comp> void pop_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp comp);
13.3.4 sort_heap // 前提是序列[first, last)是一个有效的堆.则这个函数将序列[first, last)变为顺序排列的. // 它的算法实际就是一直调用pop_heap()而得到一个有序序列. (1) 用 < template <class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last); (2) 用 comp 代替 < template <class RandomAccessIterator, class StrictWeakOrdering comp> void sort_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp comp);
13.3.5 is_heap //如果[first, last)是一个堆.返回true . 否则返回false. (1) 用 < template <class RandomAccessIterator> bool is_heap(RandomAccessIterator first, RandomAccessIterator last); (2) 用 comp 代替 < template <class RandomAccessIterator, class StrictWeakOrdering comp> bool is_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp comp); 第12章 "会改变操作对象内容" 的算法
第12章 "会改变操作对象内容"的算法 Basic Mutating Algorithms
12.1 拷贝某个区间 ( Copying Ranges )
12.1.1 copy // 返回值为目标区间的"last". 即写完后的下一个位置 template <class InputIterator, class OutputIterator> OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result);
12.1.2 copy_backward //和copy不同的是这个函数的第三个参数result指向的目标的尾端而不是开始. //并且复制时.是从最后一个元素开始复制. *(result -1) = *(last - 1) ..... template<class BidirectionalIterator1, class BidirectionalIterator Iterator2> BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last , BidirectionalIterator2 result);
12.2 互换元素 Swapping Elements
12.2.1 swap // 交换两元素. 但是STL中的容器之间交换时不用这个函数.而是定制了自己的swap.(效率); template <class Assignable> void swap(Assignable& a, Assignable& b);
12.2.2 iter_swap //交换两个迭代器所指对象的值. 但是很少用.因为可以用swap实现相同的功能. template <class ForwardIterator1, class ForwardIterator2> inline void iter_swap(ForwardIterator a, ForwardIterator2 b>;
12.2.3 swap_ranges //交换两个区间的元素的值. 交换last1-first1 个元素. 返回值为序列2交换过的元素段的下一个位置. template <class ForwardIterator1, class ForwardIteator2> ForwardIterator2 swap_ranges(ForwardIterator1 first, ForwardIterator last, ForwardIterator2 first2);
12.3 transform //和for_each类似. 区别是for_each用每个元素做为参数调用指定的函数. 但是函数 //返回的结果并不保存下来. 这个却将每次调用op时的结果保存在result 开始的区间中. (1) template <class InputIterator, class OutputIteratro, class UnaryFunction> OutputIterator transform(InputIteratorfirst, InputIterator last, OutputIterator result, UnaryFunction op); (2) 区别是:上个版本是每次用序列1的一个元素调用op. 这个版本每次用序列1中相邻的两个元素调用op. template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction> OutputIterator transform (InputIterator1 first, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction binary_op);
12.4 元素替换 Replacing Elements
12.4.1 replace //将序列中所有值为old_value的元素用new_value替换. template <class ForwardIterator, class T> void replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
12.4.2 replace_if //和replace区别是. replace函数有一个指定的old_value值. 本函数不指定某个值. //而是根据一个函数对象返回的值来判断是否替换 template <class ForwardIterator , class Predicate, class T> void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T&new_value);
12.4.3 replace_copy //前边的函数是替换源序列中的元素. 这个不改变源序列. 只是把源序列复制到 //目标序列时替换old_value template<class InputIterator, class OutputIterator, class T> OutputIterator replace_copy (InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value);
12.4.4 replace_copy_if //和replace_copy作用类似. 只是不指定要替换的值.而是指定一个函数. template<class InputIterator, class OutputIterator, class Predicate, class T> OutputIterator replace_copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);
12.5 填充整个区间 (Filling Ranges)
12.5.1 fill // template <class ForwardIterator , class T> void fill (ForwardIterator first, ForwardIterator last, const T&value);
12.5.2 fill_n // template <class OutputIterator , class Size, class T> OutputIterator fill_n(OutputIterator first, Size n , const T& value);
12.5.3 generate //对区间的每个元素赋值. *first = gen(); ..... *(last-1) = gen(); // 共调用gen() last-first次 template <class ForwardIterator, class Generator> void generate(ForwardIteator first, ForwardIteator last, Generator gen); //gen为无参函数对象.
12.5.4 generate_n //类似generate .参考一下. template <class OutputIteator , class Size, class Generator> OutputIterator generate_n (OutputIterator first, Size n , const Generator gen);
12.6 移除元素 Removing Elements
12.6.1 remove //删除序列中等于value的元素. //注意.要真正改变序列的大小. 要用erase来配合使用. template <class ForwardIteator, class T> ForwardIterator remove(ForwardIterator first, ForwardIterator last, cosnt T &vaule);
12.6.2 remove_if // template <class ForwardIterator , class Predicate> ForwardIterator remove_if(ForwardIteator first, ForwardIterator last, Predicate pred);
12.6.3 remove_copy template <class InputIterator , class OutputIterator , class T> OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIteator result, const T& value);
12.6.4 remove_copy_if template <class InputIterator , class OutputIterator , class Predicate> OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIteator result, Predicate pred);
12.6.5 unique // 删除序列中相邻且相等的元素 (1) template <class ForwardIterator> ForwardIterator unique ( ForwardIterator first, ForwardIterator last); (2)//用给定的2参函数对象替换 == template <class ForwardIterator, class BinaryPredicate> ForwardIterator unique (ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);
12.6.6 unique_copy // 复制序列1到序列2, 若序列1中存在相邻且相等的元素.则只复制重复元素中的第一个. (1) template <class InputIterator, class OutputIterator> OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result); (2) template <class InputIterator, class OutputIterator, class BinaryPredicate> OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred);
12.7 排列算法 Permuting Algorithms
用来改变序列内元素的排列顺序
12.7.1 reverse // 翻转序列 template<class BidirectionalIterator> void reverse(BidirectionalIterator first, BidirectionalIterator last>
12.7.2 reverse_copy //把翻转后的结果存入另一个序列 template <class BidirectionalIterator, class OutputIterator> OutputIteator reverse_copy (BidirectionalIterator first, BidirectionalIterator last, OutputIteator result);
12.7.3 rotate //将[middle, last) 的元素移到序列最前端(first处) . 而把[first, middle) 的元素放到后边. //例如将数组的最后三个元素移到开始处. template <class ForwardIterator> inline void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last);
12.7.4 rotate_copy //把移动的结果存入另一序列. template<class ForwardIterator, class OutputIterator> OutputIteartor rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);
12.7.5 next_permutation //考虑求n个数的全排列的那个题.其中有个解法是通过交换两个位置上的数字得到下一个 //序列. 这个函数的作用就是求下一个序列的.请参考那个题. (1) template <class BidirectionalIterator> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last); (2) template <class BidirectionalIterator, class StrictWeakOrdering> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp);
12.7.6 prev_permutation //没看明白呀.
12.8 分割 Partitions
12.8.1 partition //根据pred函数重新排列序列中的元素. 使满足pred的排在不满足pred的元素之前. //函数返回这两者的分界处的迭代器middle. //对[first, middle)的元素来说, pred(*iter) 一定返回true. 而[middle, last)的元素,pred(*iter)返回false //重排后. 原来的相对顺序并不保持. 这个函数只把他们分为两部分而已. template <class BidirectionalIterator, class Predicate> BidirectionalIterator partition (BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
12.8.2 stable_partition // 上面的partition函数在重排区间后. 并不保持原来元素的相对顺序. // 为了保持原来的相对顺序. 即假如分割前a在b之前,且分割后a b都在[first , middle) 中. 排序后a仍要在b之前. template<class ForwardIterator class Predicate> ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
12.9 随机重排与抽样 Random Shuffling and Sampling
12.9.1 random_shuffle //对一个可以随机存取的序列洗牌. (1) //洗牌调用内部的随机数函数 template <class RandomAccessIterator > void random_shuffle( RandomAccessIterator first, RandomAccessIterator last); (2)// 指定一个随机数函数. template <class RandomAccessIterator , class RandomNumberGenerator > void random_shuffle( RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator & rand);
12.9.2 random_sample //把洗牌后的结果存入另一序列. //一共存入n个元素.此处n为两个序列长度的小者. (1)//使用缺省的随机数发生器 template <class InputIterator, class RandomAccessIterator> RandomAccessIterator random_sample( InputIterator first, InputIterator last, RandomAccessIterator outfirst, RandomAccessIterator outlast); (2)//指定一个随机数发生器 template <class InputIterator, class RandomAccessIterator, class RandomNumberGenerator > RandomAccessIterator random_sample( InputIterator first, InputIterator last, RandomAccessIterator outfirst, RandomAccessIterator outlast, RandomNumberGenerator & rand);
12.9.3 random_sample_n // (1) template<class ForwardIterator , class OutputIterator, class Distance) OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last, OutputIterator out, Distance n); (2) template<class ForwardIterator , class OutputIterator, class Distance, class RandomNumberGenerator ) OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last, OutputIterator out, Distance n, RandomNumberGenerator &rand);
12.10 一般化之数值算法 Generalized Numeric Algorithms
12.10.1 accumulate //计算init + 序列中所有元素的和. //参数多了init 是为了对付空序列 (1) template <class InputIterator, class T> T accumulate(InputIterator first, InputIterator last, T init); (2) 也可以不是计算序列的和.而用其他双参函数对象代替+ template <class InputIterator, class T, class BinaryFunction> T accumulate(InputIterator first, InputIterator last, T init, BinaryFunction binary_op);
12.10.2 inner_product //计算内积 (1) template <class InputIterator1, class InputIterator2, class T> T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init); (2) template <class InputIterator1, class InputIterator2, class T, class BinaryFunction1, class BinaryFunction2> T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init, BinaryFunction1 binary_op1, BinaryFunction2 binary_op2);
12.10.3 partial_sum
12.10.4 adjacent_difference 第11章 "不改变所操作对象" 的算法
第11章 "不改变操作对象"的算法 Nonmutating Algorithms
11.1 线性查找 ( linear Search)
11.1.1 find // 值查找 template <class InputIterator, class EqualityComparable> InputIterator find(InputIterator first, InputIterator last, const EqualityComparable &value); // 参数为要查找的区间. 和要查找的值.
11.1.2 find_if // 条件查找 template <class InputIterator , class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred); // 参数为要查找的区间和一个函数对象
11.1.3 adjacent_find //在指定的区间查找相邻且相等的元素. 返回相等的两个元素中前者的iterator (1) //普通版本.查找时比较相等性 template <class ForwardIteraor> Forwarditerator adjacent_find(ForwardIterator first, ForwardIterator last); (2) //这个版本查看相邻的两个元素是否满足给定的条件(不一定比较相等性). //条件由第3个参数指定(一个双参数的函数对象) template <class ForwardIterator, class BinaryPredicate> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate Bindary_pred);
11.1.4 find_first_of //在区间[first1, last1) 中查找[first2, last2)中任何一个元素第一次出现的位置 (1) //一般版本.比较区间1中的某个元素是否在区间2中.若找到第一个在区间2中的元素.返回它的迭代器. template <class InputIterator , class ForwardIterator> InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2); (2) //这个版本不是比较区间1中的某个元素是否在区间2中,而是它是否和区间2中 //某个元素有指定的关系. 该关系由第5个参数指定(一个双参函数对象) template <class InputIterator, class ForwardIterator , class BinaryPredicate> InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate comp);
11.2 子序列匹配 Subsequence Matching
11.2.1 search //查找序列2在序列1中首次出现的位置. 返回迭代器指向匹配的位置的开始处. (1)一般版本. template <class ForwardIterator1, class ForwardIteraotr2> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); (2)这个版本在匹配比较两个序列中元素的相等性时不用== ,而用第五个参数指定的双参函数对象 template <class ForwardIterator1, class ForwardIteraotr2, class BinaryPredicate> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);
11.2.2 find_end //它和search的作用一样. 区别是 search 查找的是序列2第一次出现的位置. 而 //find_end查找的序列2最后一次出现的位置. 若查找失败返回序列1的last; //函数的用法同search那两个版本..
11.2.3 search_n //查找连续的count个相等的元素. 且这些元素的值都等于value (1) // 一般版本 template <class ForwardIterator , class Integer, class T> ForwardIterator search_n (ForwardIteator first, ForwardIterator last, Integer count, const T& value); (2) // 不比较值相等. 用指定函数对象替代 == template <class ForwardIterator, class Integer, class T, class BinaryPredicate> ForwardIterator search_n (ForwardIterator first , ForwardIterator last, Integer count, const T& value, BinaryPredicate binary_pred);
11.3 计算元素个数 counting Elements
11.3.1 count // (1) //返回值为要统计的元素value的个数 template <class InputIterator, class EqualityComparable> typename iterator_traits<InputIterator>::difference_type count (InputIterator first, InputIterator last, const EqualityComparable& value); (2) // 统计出的元素的个数由参数 n 返回. template <class InputIterator, class EqualityComparable, class Size> void count (InputIterator first, InputIterator last, const EqualityComparable& value, Size &n);
11.3.2 count_if // 统计符合给定条件的对象的个数 (1) template <class InputIterator, class Predicate> typename iterator_traits<InputIterator>::difference_type count_if (InputIterator first, InputIterator last, Predicate pred); (2) template <class InputIterator, class Predicate, class Size> void count_if (InputIterator first, InputIterator last, Predicate pred, Size n);
11.4 for_each //用序列中的每个元素做参数调用指定的函数对象f template <class InputIterator, class UnaryFunction> UnaryFuntion //返回值. 为参数中指定的那个函数对象. 通常不使用该返回值. for_each (InputIterator first, InputIterator last, UnaryFunction f);
11.5 比较两个区间
11.5.1 equal // 比较相等性.从first1 == first2 ..... 若都相等返回true (1)一般版本 template <class InputIterator1, class InputIterator2> bool equal (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); (2)//比较是不用== , 而是用指定的函数对象代替== template <class InputIterator1, class InputIterator2, class BinaryPredicate> bool equal (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);
11.5.2 mismatch //依次比较两个序列中的元素. 从A[0] B[0]开始比到 A[N] B[N] . //函数返回第一对不想等元素的迭代器的pair (1)//一般版本 template<class InputIterator1, class InputIterator2> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIteator2 first2); (2)//这个版本 不是比较相等性.而是用一个指定的双参函数对象代替== template<class InputIterator1, class InputIterator2, class BinaryPredicate> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIteator2 first2 ,BinaryPredicate binary_pred);
11.5.3 lexicographical_compare // 按字典式比较两个序列. 即 *first1 < *first2 则序列1<序列2 . // 若*first1 == *first2 则比较下两个元素. // 若所有序列1中的元素都==序列2中对应的元素.但序列2比序列1长. 则序列1<序列2 // 最后函数返回 序列1 < 序列2 ? 1 : 0; (1) // 一般版本. 比较使用== template <class InputIterator1, class InputIterator2> bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); (2) // 比较时用指定的2参函数对象替代== template <class InputIterator1, class InputIterator2, class BinaryPredicate> bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate comp);
11.6 最大值与最小值
11.6.1 min (1) 比较两对象时使用 < template <class LessThanComparable> const LessThanComparable& min(const LessThanComparable& a, const LessThanComparable& b); (2) 比较两对象时用指定的双参函数对象代替 < template <class T, class BinaryPredicate> const T& min(const T&a, const T& b, BinaryPredicate comp);
11.6.2 max (1) 比较两对象时使用 < .若两对象相等则返回第一个 template <class LessThanComparable> const LessThanComparable& max(const LessThanComparable& a, const LessThanComparable& b); (2) 比较两对象时用指定的双参函数对象代替 < template <class T, class BinaryPredicate> const T& max(const T&a, const T& b, BinaryPredicate comp);
11.6.3 min_element //返回序列中最小的元素. 若有几个相等的元素都是最小的. 返回第一个. 若序列是空的. 返回last. (1) // 用< template <class ForwardIterator> ForwardIterator min_element(ForwardIterator first, ForwardIterator last); (2) // 用指定函数对象替代 < template <class ForwardIterator, class BinaryPredicate> ForwardIterator min_element(ForwardIterator first, ForwardIterator last, BinaryPredicate comp);
11.6.4 max_element //返回序列中最大的元素. 若有几个相等的元素都是最大的. 返回第一个. 若序列是空的. 返回last. (1) // 用< template <class ForwardIterator> ForwardIterator max_element(ForwardIterator first, ForwardIterator last); (2) // 用指定函数对象替代 < template <class ForwardIterator, class BinaryPredicate> ForwardIterator max_element(ForwardIterator first, ForwardIterator last, BinaryPredicate comp);
|