2005年11月25日
农历8月16是偶的生日,HOHO,自己先庆祝下先。偶是农村来的,过的都是农历生日啦,公司每次都在公历的那天发生日礼物给我,其实不是我的生日啦。其实也没什么,我又不是什么大人物,哪天过生日还不是一样。哈哈。想想上大学的时候,偶们寝室的兄弟们把生日表排在门后面,到了差不多有兄弟生日的时候大家就开始兴奋了,要为兄弟过生日嘛,其实也就是找一出去吃喝买醉的借口。往往那个时候经常就会有人提议把生日提前过了吧,先吃先喝为上,而往往这也会得到大家的赞同。那时候真好,一大桌的兄弟,喝啊!毕业都散了,在北京就偶和廖批还有小古,过生日的时候也就冷冷清清的三个人喝上几杯,顶多也就多一两个无关紧要的人,还是好怀念大家一起在学校喝酒的日子。来,我敬大家一杯(常德话,这可是有典故的,HOHO)!
昨天又喝多了,现在头还痛得厉害!真是自己找罪受,喝的时候为什么就不这样想呢,一杯一杯的喝啊,好像自己是个酒桶喝少了会吃亏似的,唉!不过想想,这一个多月来周末都没有清醒过了,好像都是醉着过日子的,我昏厥!嗯,以后要少喝点酒了,小喝一点点就可以了。身体重要啊!
这么久的生活还是没有什么变化,仍然是上班下班,晚上看看书看看代码看看碟。只是有一点小小的变化。上次去图书城,看到了那本曾听说过很有名的《达.芬奇的密码》,于是就买了本回来。很久没有看纸版的书了,晚上洗完澡,关了电脑,躺在床上打开台灯静静的看会书也是一种享受。
公司看起来很不平静,上面好像斗争的非常厉害哦。靠,公司是越来越没前途了,唉。两年了,多少有点感情,现在我想该是走的时候了,何去何从呢。。。。。。
周未去和同事们一起玩球,赌晚餐,我们胜了。晚上又一起玩麻将,哈哈,我这个最不会玩的新手居然胜的最多,HOHO。不会是看我新手故意让我打的费的吧,哈哈。
今天看了李开复的一些文章,他说,做程序员的不要老是去学那些皮毛语言,要多看看操作系、数据结构、数据库这些东西,还说要多写写代码。嗯,有道理,语言这东西只要你有思想很快就可以学会的,我也是这样想的。HOHO。
这么久老是感觉时间安排的不好,一天到晚下来感觉都没个准,也不知道干了些什么东西,学习也没个计划,是要每天定好计划才行。
HOHO,看起来,我生活感悟还是太差,这么久才写一次都没写出什么东西来,就像写个流水帐似的,我想说,其实我的感悟也是很非富的,哈哈,只是表达不出来。以后多练练笔。
2005年11月24日
发贴心情

程序之美”-百度之星程序设计大赛 – 题目

第一题(共四题100分):连续正整数(10分)
   题目描述:
一个正整数有可能可以被表示为n(n>=2)个连续正整数之和,如:
    15=1+2+3+4+5
    15=4+5+6
    15=7+8
    请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列。
   输入数据:
一个正整数,以命令行参数的形式提供给程序。
   输出数据:

标准输出上打印出符合题目描述的全部正整数序列,每行一个序列,每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列,按各序
列的最小正整数的大小从小到大打印各序列。此外,序列不允许重复,序列内的整数用一个空格分隔。如果没有符合要求的序列,输出“NONE”。
    例如,对于15,其输出结果是:
    1 2 3 4 5
    4 5 6
    7 8
    对于16,其输出结果是:
    NONE

   评分标准:
程序输出结果是否正确。
   第二题(共四题100分):重叠区间大小(20分)
   题目描述:
请编写程序,找出下面“输入数据及格式”中所描述的输入数据文件中最大重叠区间的大小。
    对一个正整数n,如果n在数据文件中某行的两个正整数(假设为A和B)之间,即A<=n<=B或A>=n>=B,则n属于该行;如果n同时属于行i和j,则i和j有重叠区间;重叠区间的大小是同时属于行i和j的整数个数。
    例如,行(10 20)和(12 25)的重叠区间为[12 20],其大小为9;行(20 10)和(12 18)的重叠区间为[10 12],其大小为3;行(20 10)和(20 30)的重叠区间大小为1。
   输入数据:

序读入已被命名为input.txt的输入数据文本文件,该文件的行数在1到1,000,000之间,每行有用一个空格分隔的2个正整数,这2个正整数的
大小次序随机,每个数都在1和2^32-1之间。(为便于调试,您可下载测试input.txt文件,实际运行时我们会使用不同内容的输入文件。)
   输出数据:
在标准输出上打印出输入数据文件中最大重叠区间的大小,如果所有行都没有重叠区间,则输出0。
   评分标准:
程序输出结果必须正确,内存使用必须不超过256MB,程序的执行时间越快越好。
   第三题(共四题100分):字符串替换(30分)
   题目描述:
请编写程序,根据指定的对应关系,把一个文本中的字符串替换成另外的字符串。
   输入数据:

序读入已被命名为text.txt和dict.txt的两个输入数据文本文件,text.txt为一个包含大量字符串(含中文)的文本,以
whitespace为分隔符;dict.txt为表示字符串(s1)与字符串(s2)的对应关系的另一个文本(含中文),大约在1万行左右,每行两个字
符串(即s1和s2),用一个\t或空格分隔。dict.txt中各行的s1没有排序,并有可能有重复,这时以最后出现的那次s1所对应的s2为准。
text.txt和dict.txt中的每个字符串都可能包含除whitespace之外的任何字符。text.txt中的字符串必须和dict.txt
中的某s1完全匹配才能被替换。(为便于调试,您可下载测试text.txt和dict.txt文件,实际运行时我们会使用不同内容的输入文件。)
   输出数据:
在标准输出上打印text.txt被dict.txt替换后了的整个文本。
   评分标准:
程序输出结果必须正确,内存使用越少越好,程序的执行时间越快越好。
  第四题(共四题100分):低频词过滤(40分)
   题目描述:
请编写程序,从包含大量单词的文本中删除出现次数最少的单词。如果有多个单词都出现最少的次数,则将这些单词都删除。
   输入数据:
程序读入已被命名为corpus.txt的一个大数据量的文本文件,该文件包含英文单词和中文单词,词与词之间以一个或多个whitespace分隔。(为便于调试,您可下载测试corpus.txt文件,实际运行时我们会使用不同内容的输入文件。)
   输出数据:
在标准输出上打印删除了corpus.txt中出现次数最少的单词之后的文本(词与词保持原来的顺序,仍以空格分隔)。
   评分标准:
程序输出结果必须正确,内存使用越少越好,程序的执行时间越快越好。

Linux下的多线程编程


作者:姚继锋 2001-08-11 09:05:00 来自:http://www.china-pub.com

1 引言
 
 线程(thread)技术早在60年代就被提出,但真正应用多线程到操作系统中去,是在80年代中期,solaris是这方面的佼佼者。传统的Unix
也支持线程的概念,但是在一个进程(process)中只允许有一个线程,这样多线程就意味着多进程。现在,多线程技术已经被许多操作系统所支持,包括
Windows/NT,当然,也包括Linux。
  为什么有了进程的概念后,还要再引入线程呢?使用多线程到底有哪些好处?什么的系统应该选用多线程?我们首先必须回答这些问题。
 
 使用多线程的理由之一是和进程相比,它是一种非常"节俭"的多任务操作方式。我们知道,在Linux系统下,启动一个新的进程必须分配给它独立的地址空
间,建立众多的数据表来维护它的代码段、堆栈段和数据段,这是一种"昂贵"的多任务工作方式。而运行于一个进程中的多个线程,它们彼此之间使用相同的地址
空间,共享大部分数据,启动一个线程所花费的空间远远小于启动一个进程所花费的空间,而且,线程间彼此切换所需的时间也远远小于进程间切换所需要的时间。
据统计,总的说来桓鼋痰目笤际且桓鱿叱炭?0倍左右,当然,在具体的系统上,这个数据可能会有较大的区别。
  使用多线程的理由之二
是线程间方便的通信机制。对不同进程来说,它们具有独立的数据空间,要进行数据的传递只能通过通信的方式进行,这种方式不仅费时,而且很不方便。线程则不
然,由于同一进程下的线程之间共享数据空间,所以一个线程的数据可以直接为其它线程所用,这不仅快捷,而且方便。当然,数据的共享也带来其他一些问题,有
的变量不能同时被两个线程所修改,有的子程序中声明为static的数据更有可能给多线程程序带来灾难性的打击,这些正是编写多线程程序时最需要注意的地
方。
  除了以上所说的优点外,不和进程比较,多线程程序作为一种多任务、并发的工作方式,当然有以下的优点:
  1) 提高应用程序响应。这对图形界面的程序尤其有意义,当一个操作耗时很长时,整个系统都会等待这个操作,此时程序不会响应键盘、鼠标、菜单的操作,而使用多线程技术,将耗时长的操作(time consuming)置于一个新的线程,可以避免这种尴尬的情况。
  2) 使多CPU系统更加有效。操作系统会保证当线程数不大于CPU数目时,不同的线程运行于不同的CPU上。
  3) 改善程序结构。一个既长又复杂的进程可以考虑分为多个线程,成为几个独立或半独立的运行部分,这样的程序会利于理解和修改。
  下面我们先来尝试编写一个简单的多线程程序。

2 简单的多线程编程
 
 Linux系统下的多线程遵循POSIX线程接口,称为pthread。编写Linux下的多线程程序,需要使用头文件pthread.h,连接时需要
使用库libpthread.a。顺便说一下,Linux下pthread的实现是通过系统调用clone()来实现的。clone()是Linux所特
有的系统调用,它的使用方式类似fork,关于clone()的详细情况,有兴趣的读者可以去查看有关文档说明。下面我们展示一个最简单的多线程程序
example1.c。

/* example.c*/
#include <stdio.h>
#include <pthread.h>
void thread(void)
{
int i;
for(i=0;i<3;i++)
printf("This is a pthread.\n");
}

int main(void)
{
pthread_t id;
int i,ret;
ret=pthread_create(&id,NULL,(void *) thread,NULL);
if(ret!=0){
printf ("Create pthread error!\n");
exit (1);
}
for(i=0;i<3;i++)
printf("This is the main process.\n");
pthread_join(id,NULL);
return (0);
}

我们编译此程序:
gcc example1.c -lpthread -o example1
运行example1,我们得到如下结果:
This is the main process.
This is a pthread.
This is the main process.
This is the main process.
This is a pthread.
This is a pthread.
再次运行,我们可能得到如下结果:
This is a pthread.
This is the main process.
This is a pthread.
This is the main process.
This is a pthread.
This is the main process.

  前后两次结果不一样,这是两个线程争夺CPU资源的结果。上面的示例中,我们使用到了两个函数,  pthread_create和pthread_join,并声明了一个pthread_t型的变量。
  pthread_t在头文件/usr/include/bits/pthreadtypes.h中定义:
  typedef unsigned long int pthread_t;
  它是一个线程的标识符。函数pthread_create用来创建一个线程,它的原型为:
  extern int pthread_create __P ((pthread_t *__thread, __const pthread_attr_t *__attr,
  void *(*__start_routine) (void *), void *__arg));
 
 第一个参数为指向线程标识符的指针,第二个参数用来设置线程属性,第三个参数是线程运行函数的起始地址,最后一个参数是运行函数的参数。这里,我们的函
数thread不需要参数,所以最后一个参数设为空指针。第二个参数我们也设为空指针,这样将生成默认属性的线程。对线程属性的设定和修改我们将在下一节
阐述。当创建线程成功时,函数返回0,若不为0则说明创建线程失败,常见的错误返回代码为EAGAIN和EINVAL。前者表示系统限制创建新的线程,例
如线程数目过多了;后者表示第二个参数代表的线程属性值非法。创建线程成功后,新创建的线程则运行参数三和参数四确定的函数,原来的线程则继续运行下一行
代码。
  函数pthread_join用来等待一个线程的结束。函数原型为:
  extern int pthread_join __P ((pthread_t __th, void **__thread_return));
 
 第一个参数为被等待的线程标识符,第二个参数为一个用户定义的指针,它可以用来存储被等待线程的返回值。这个函数是一个线程阻塞的函数,调用它的函数将
一直等待到被等待的线程结束为止,当函数返回时,被等待线程的资源被收回。一个线程的结束有两种途径,一种是象我们上面的例子一样,函数结束了,调用它的
线程也就结束了;另一种方式是通过函数pthread_exit来实现。它的函数原型为:
  extern void pthread_exit __P ((void *__retval)) __attribute__ ((__noreturn__));
 
 唯一的参数是函数的返回代码,只要pthread_join中的第二个参数thread_return不是NULL,这个值将被传递给
thread_return。最后要说明的是,一个线程不能被多个线程等待,否则第一个接收到信号的线程成功返回,其余调用pthread_join的线
程则返回错误代码ESRCH。
  在这一节里,我们编写了一个最简单的线程,并掌握了最常用的三个函数pthread_create,pthread_join和pthread_exit。下面,我们来了解线程的一些常用属性以及如何设置这些属性。

3 修改线程的属性
  在上一节的例子里,我们用pthread_create函数创建了一个线程,在这个线程中,我们使用了默认参数,即将该函数的第二个参数设为NULL。的确,对大多数程序来说,使用默认属性就够了,但我们还是有必要来了解一下线程的有关属性。
 
 属性结构为pthread_attr_t,它同样在头文件/usr/include/pthread.h中定义,喜欢追根问底的人可以自己去查看。属性
值不能直接设置,须使用相关函数进行操作,初始化的函数为pthread_attr_init,这个函数必须在pthread_create函数之前调
用。属性对象主要包括是否绑定、是否分离、堆栈地址、堆栈大小、优先级。默认的属性为非绑定、非分离、缺省1M的堆栈、与父进程同样级别的优先级。
 
 关于线程的绑定,牵涉到另外一个概念:轻进程(LWP:Light Weight
Process)。轻进程可以理解为内核线程,它位于用户层和系统层之间。系统对线程资源的分配、对线程的控制是通过轻进程来实现的,一个轻进程可以控制
一个或多个线程。默认状况下,启动多少轻进程、哪些轻进程来控制哪些线程是由系统来控制的,这种状况即称为非绑定的。绑定状况下,则顾名思义,即某个线程
固定的"绑"在一个轻进程之上。被绑定的线程具有较高的响应速度,这是因为CPU时间片的调度是面向轻进程的,绑定的线程可以保证在需要的时候它总有一个
轻进程可用。通过设置被绑定的轻进程的优先级和调度级可以使得绑定的线程满足诸如实时反应之类的要求。
  设置线程绑定状态的函数为
pthread_attr_setscope,它有两个参数,第一个是指向属性结构的指针,第二个是绑定类型,它有两个取值:
PTHREAD_SCOPE_SYSTEM(绑定的)和PTHREAD_SCOPE_PROCESS(非绑定的)。下面的代码即创建了一个绑定的线程。
#include <pthread.h>
pthread_attr_t attr;
pthread_t tid;

/*初始化属性值,均设为默认值*/
pthread_attr_init(&attr);
pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);

pthread_create(&tid, &attr, (void *) my_function, NULL);

 
 线程的分离状态决定一个线程以什么样的方式来终止自己。在上面的例子中,我们采用了线程的默认属性,即为非分离状态,这种情况下,原有的线程等待创建的
线程结束。只有当pthread_join()函数返回时,创建的线程才算终止,才能释放自己占用的系统资源。而分离线程不是这样子的,它没有被其他的线
程所等待,自己运行结束了,线程也就终止了,马上释放系统资源。程序员应该根据自己的需要,选择适当的分离状态。设置线程分离状态的函数为
pthread_attr_setdetachstate(pthread_attr_t *attr, int
detachstate)。第二个参数可选为PTHREAD_CREATE_DETACHED(分离线程)和 PTHREAD
_CREATE_JOINABLE(非分离线程)。这里要注意的一点是,如果设置一个线程为分离线程,而这个线程运行又非常快,它很可能在
pthread_create函数返回之前就终止了,它终止以后就可能将线程号和系统资源移交给其他的线程使用,这样调用pthread_create的
线程就得到了错误的线程号。要避免这种情况可以采取一定的同步措施,最简单的方法之一是可以在被创建的线程里调用
pthread_cond_timewait函数,让这个线程等待一会儿,留出足够的时间让函数pthread_create返回。设置一段等待时间,是
在多线程编程里常用的方法。但是注意不要使用诸如wait()之类的函数,它们是使整个进程睡眠,并不能解决线程同步的问题。
  另外一个可能常
用的属性是线程的优先级,它存放在结构sched_param中。用函数pthread_attr_getschedparam和函数
pthread_attr_setschedparam进行存放,一般说来,我们总是先取优先级,对取得的值修改后再存放回去。下面即是一段简单的例子。
#include <pthread.h>
#include <sched.h>
pthread_attr_t attr;
pthread_t tid;
sched_param param;
int newprio=20;

pthread_attr_init(&attr);
pthread_attr_getschedparam(&attr, &param);
param.sched_priority=newprio;
pthread_attr_setschedparam(&attr, &param);
pthread_create(&tid, &attr, (void *)myfunction, myarg);
  
4 线程的数据处理
 
 和进程相比,线程的最大优点之一是数据的共享性,各个进程共享父进程处沿袭的数据段,可以方便的获得、修改数据。但这也给多线程编程带来了许多问题。我
们必须当心有多个不同的进程访问相同的变量。许多函数是不可重入的,即同时不能运行一个函数的多个拷贝(除非使用不同的数据段)。在函数中声明的静态变量
常常带来问题,函数的返回值也会有问题。因为如果返回的是函数内部静态声明的空间的地址,则在一个线程调用该函数得到地址后使用该地址指向的数据时,别的
线程可能调用此函数并修改了这一段数据。在进程中共享的变量必须用关键字volatile来定义,这是为了防止编译器在优化时(如gcc中使用-OX参
数)改变它们的使用方式。为了保护变量,我们必须使用信号量、互斥等方法来保证我们对变量的正确使用。下面,我们就逐步介绍处理线程数据时的有关知识。

4.1 线程数据
 
 在单线程的程序里,有两种基本的数据:全局变量和局部变量。但在多线程程序里,还有第三种数据类型:线程数据(TSD:
Thread-Specific
Data)。它和全局变量很象,在线程内部,各个函数可以象使用全局变量一样调用它,但它对线程外部的其它线程是不可见的。这种数据的必要性是显而易见
的。例如我们常见的变量errno,它返回标准的出错信息。它显然不能是一个局部变量,几乎每个函数都应该可以调用它;但它又不能是一个全局变量,否则在
A线程里输出的很可能是B线程的出错信息。要实现诸如此类的变量,我们就必须使用线程数据。我们为每个线程数据创建一个键,它和这个键相关联,在各个线程
里,都使用这个键来指代线程数据,但在不同的线程里,这个键代表的数据是不同的,在同一个线程里,它代表同样的数据内容。
  和线程数据相关的函数主要有4个:创建一个键;为一个键指定线程数据;从一个键读取线程数据;删除键。
  创建键的函数原型为:
  extern int pthread_key_create __P ((pthread_key_t *__key,
  void (*__destr_function) (void *)));
 
 第一个参数为指向一个键值的指针,第二个参数指明了一个destructor函数,如果这个参数不为空,那么当每个线程结束时,系统将调用这个函数来释
放绑定在这个键上的内存块。这个函数常和函数pthread_once ((pthread_once_t*once_control, void
(*initroutine)
(void)))一起使用,为了让这个键只被创建一次。函数pthread_once声明一个初始化函数,第一次调用pthread_once时它执行这
个函数,以后的调用将被它忽略。

  在下面的例子中,我们创建一个键,并将它和某个数据相关联。我们要定义一个函数
createWindow,这个函数定义一个图形窗口(数据类型为Fl_Window
*,这是图形界面开发工具FLTK中的数据类型)。由于各个线程都会调用这个函数,所以我们使用线程数据。
/* 声明一个键*/
pthread_key_t myWinKey;
/* 函数 createWindow */
void createWindow ( void ) {
Fl_Window * win;
static pthread_once_t once= PTHREAD_ONCE_INIT;
/* 调用函数createMyKey,创建键*/
pthread_once ( & once, createMyKey) ;
/*win指向一个新建立的窗口*/
win=new Fl_Window( 0, 0, 100, 100, "MyWindow");
/* 对此窗口作一些可能的设置工作,如大小、位置、名称等*/
setWindow(win);
/* 将窗口指针值绑定在键myWinKey上*/
pthread_setpecific ( myWinKey, win);
}

/* 函数 createMyKey,创建一个键,并指定了destructor */
void createMyKey ( void ) {
pthread_keycreate(&myWinKey, freeWinKey);
}

/* 函数 freeWinKey,释放空间*/
void freeWinKey ( Fl_Window * win){
delete win;
}

 
 这样,在不同的线程中调用函数createMyWin,都可以得到在线程内部均可见的窗口变量,这个变量通过函数
pthread_getspecific得到。在上面的例子中,我们已经使用了函数pthread_setspecific来将线程数据和一个键绑定在一
起。这两个函数的原型如下:
  extern int pthread_setspecific __P ((pthread_key_t __key,__const void *__pointer));
  extern void *pthread_getspecific __P ((pthread_key_t __key));
 
 这两个函数的参数意义和使用方法是显而易见的。要注意的是,用pthread_setspecific为一个键指定新的线程数据时,必须自己释放原有的
线程数据以回收空间。这个过程函数pthread_key_delete用来删除一个键,这个键占用的内存将被释放,但同样要注意的是,它只释放键占用的
内存,并不释放该键关联的线程数据所占用的内存资源,而且它也不会触发函数pthread_key_create中定义的destructor函数。线程
数据的释放必须在释放键之前完成。

4.2 互斥锁
  互斥锁用来保证一段时间内只有一个线程在执行一段代码。必要性显而易见:假设各个线程向同一个文件顺序写入数据,最后得到的结果一定是灾难性的。
  我们先看下面一段代码。这是一个读/写程序,它们公用一个缓冲区,并且我们假定一个缓冲区只能保存一条信息。即缓冲区只有两个状态:有信息或没有信息。

void reader_function ( void );
void writer_function ( void );

char buffer;
int buffer_has_item=0;
pthread_mutex_t mutex;
struct timespec delay;
void main ( void ){
pthread_t reader;
/* 定义延迟时间*/
delay.tv_sec = 2;
delay.tv_nec = 0;
/* 用默认属性初始化一个互斥锁对象*/
pthread_mutex_init (&mutex,NULL);
pthread_create(&reader, pthread_attr_default, (void *)&reader_function), NULL);
writer_function( );
}

void writer_function (void){
while(1){
/* 锁定互斥锁*/
pthread_mutex_lock (&mutex);
if (buffer_has_item==0){
buffer=make_new_item( );
buffer_has_item=1;
}
/* 打开互斥锁*/
pthread_mutex_unlock(&mutex);
pthread_delay_np(&delay);
}
}

void reader_function(void){
while(1){
pthread_mutex_lock(&mutex);
if(buffer_has_item==1){
consume_item(buffer);
buffer_has_item=0;
}
pthread_mutex_unlock(&mutex);
pthread_delay_np(&delay);
}
}
 
 这里声明了互斥锁变量mutex,结构pthread_mutex_t为不公开的数据类型,其中包含一个系统分配的属性对象。函数
pthread_mutex_init用来生成一个互斥锁。NULL参数表明使用默认属性。如果需要声明特定属性的互斥锁,须调用函数
pthread_mutexattr_init。函数pthread_mutexattr_setpshared和函数
pthread_mutexattr_settype用来设置互斥锁属性。前一个函数设置属性pshared,它有两个取值,
PTHREAD_PROCESS_PRIVATE和PTHREAD_PROCESS_SHARED。前者用来不同进程中的线程同步,后者用于同步本进程的
不同线程。在上面的例子中,我们使用的是默认属性PTHREAD_PROCESS_
PRIVATE。后者用来设置互斥锁类型,可选的类型有PTHREAD_MUTEX_NORMAL、PTHREAD_MUTEX_ERRORCHECK、
PTHREAD_MUTEX_RECURSIVE和PTHREAD
_MUTEX_DEFAULT。它们分别定义了不同的上所、解锁机制,一般情况下,选用最后一个默认属性。
  
pthread_mutex_lock声明开始用互斥锁上锁,此后的代码直至调用pthread_mutex_unlock为止,均被上锁,即同一时间只
能被一个线程调用执行。当一个线程执行到pthread_mutex_lock处时,如果该锁此时被另一个线程使用,那此线程被阻塞,即程序将等待到另一
个线程释放此互斥锁。在上面的例子中,我们使用了pthread_delay_np函数,让线程睡眠一段时间,就是为了防止一个线程始终占据此函数。
 
 上面的例子非常简单,就不再介绍了,需要提出的是在使用互斥锁的过程中很有可能会出现死锁:两个线程试图同时占用两个资源,并按不同的次序锁定相应的互
斥锁,例如两个线程都需要锁定互斥锁1和互斥锁2,a线程先锁定互斥锁1,b线程先锁定互斥锁2,这时就出现了死锁。此时我们可以使用函数
pthread_mutex_trylock,它是函数pthread_mutex_lock的非阻塞版本,当它发现死锁不可避免时,它会返回相应的信
息,程序员可以针对死锁做出相应的处理。另外不同的互斥锁类型对死锁的处理不一样,但最主要的还是要程序员自己在程序设计注意这一点。

4.3 条件变量
 
 前一节中我们讲述了如何使用互斥锁来实现线程间数据的共享和通信,互斥锁一个明显的缺点是它只有两种状态:锁定和非锁定。而条件变量通过允许线程阻塞和
等待另一个线程发送信号的方法弥补了互斥锁的不足,它常和互斥锁一起使用。使用时,条件变量被用来阻塞一个线程,当条件不满足时,线程往往解开相应的互斥
锁并等待条件发生变化。一旦其它的某个线程改变了条件变量,它将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程。这些线程将重新锁定互斥锁并
重新测试条件是否满足。一般说来,条件变量被用来进行线承间的同步。
  条件变量的结构为pthread_cond_t,函数pthread_cond_init()被用来初始化一个条件变量。它的原型为:
  extern int pthread_cond_init __P ((pthread_cond_t *__cond,__const pthread_condattr_t *__cond_attr));
 
 其中cond是一个指向结构pthread_cond_t的指针,cond_attr是一个指向结构pthread_condattr_t的指针。结构
pthread_condattr_t是条件变量的属性结构,和互斥锁一样我们可以用它来设置条件变量是进程内可用还是进程间可用,默认值是
PTHREAD_
PROCESS_PRIVATE,即此条件变量被同一进程内的各个线程使用。注意初始化条件变量只有未被使用时才能重新初始化或被释放。释放一个条件变量
的函数为pthread_cond_ destroy(pthread_cond_t cond)。 
  函数pthread_cond_wait()使线程阻塞在一个条件变量上。它的函数原型为:
  extern int pthread_cond_wait __P ((pthread_cond_t *__cond,
  pthread_mutex_t *__mutex));
 
 线程解开mutex指向的锁并被条件变量cond阻塞。线程可以被函数pthread_cond_signal和函数
pthread_cond_broadcast唤醒,但是要注意的是,条件变量只是起阻塞和唤醒线程的作用,具体的判断条件还需用户给出,例如一个变量是
否为0等等,这一点我们从后面的例子中可以看到。线程被唤醒后,它将重新检查判断条件是否满足,如果还不满足,一般说来线程应该仍阻塞在这里,被等待被下
一次唤醒。这个过程一般用while语句实现。
  另一个用来阻塞线程的函数是pthread_cond_timedwait(),它的原型为:
  extern int pthread_cond_timedwait __P ((pthread_cond_t *__cond,
  pthread_mutex_t *__mutex, __const struct timespec *__abstime));
  它比函数pthread_cond_wait()多了一个时间参数,经历abstime段时间后,即使条件变量不满足,阻塞也被解除。
  函数pthread_cond_signal()的原型为:
  extern int pthread_cond_signal __P ((pthread_cond_t *__cond));
 
 它用来释放被阻塞在条件变量cond上的一个线程。多个线程阻塞在此条件变量上时,哪一个线程被唤醒是由线程的调度策略所决定的。要注意的是,必须用保
护条件变量的互斥锁来保护这个函数,否则条件满足信号又可能在测试条件和调用pthread_cond_wait函数之间被发出,从而造成无限制的等待。
下面是使用函数pthread_cond_wait()和函数pthread_cond_signal()的一个简单的例子。

pthread_mutex_t count_lock;
pthread_cond_t count_nonzero;
unsigned count;
decrement_count () {
pthread_mutex_lock (&count_lock);
while(count==0)
pthread_cond_wait( &count_nonzero, &count_lock);
count=count -1;
pthread_mutex_unlock (&count_lock);
}

increment_count(){
pthread_mutex_lock(&count_lock);
if(count==0)
pthread_cond_signal(&count_nonzero);
count=count+1;
pthread_mutex_unlock(&count_lock);
}
  count值为0
时,
decrement函数在pthread_cond_wait处被阻塞,并打开互斥锁count_lock。此时,当调用到函数
increment_count时,pthread_cond_signal()函数改变条件变量,告知decrement_count()停止阻塞。读
者可以试着让两个线程分别运行这两个函数,看看会出现什么样的结果。
  函数pthread_cond_broadcast(pthread_cond_t *cond)用来唤醒所有被阻塞在条件变量cond上的线程。这些线程被唤醒后将再次竞争相应的互斥锁,所以必须小心使用这个函数。

4.4 信号量
 
 信号量本质上是一个非负的整数计数器,它被用来控制对公共资源的访问。当公共资源增加时,调用函数sem_post()增加信号量。只有当信号量值大于
0时,才能使用公共资源,使用后,函数sem_wait()减少信号量。函数sem_trywait()和函数pthread_
mutex_trylock()起同样的作用,它是函数sem_wait()的非阻塞版本。下面我们逐个介绍和信号量有关的一些函数,它们都在头文件
/usr/include/semaphore.h中定义。
  信号量的数据类型为结构sem_t,它本质上是一个长整型的数。函数sem_init()用来初始化一个信号量。它的原型为:
  extern int sem_init __P ((sem_t *__sem, int __pshared, unsigned int __value));
  sem为指向信号量结构的一个指针;pshared不为0时此信号量在进程间共享,否则只能为当前进程的所有线程共享;value给出了信号量的初始值。
  函数sem_post( sem_t *sem )用来增加信号量的值。当有线程阻塞在这个信号量上时,调用这个函数会使其中的一个线程不在阻塞,选择机制同样是由线程的调度策略决定的。
 
 函数sem_wait( sem_t *sem
)被用来阻塞当前线程直到信号量sem的值大于0,解除阻塞后将sem的值减一,表明公共资源经使用后减少。函数sem_trywait (
sem_t *sem )是函数sem_wait()的非阻塞版本,它直接将信号量sem的值减一。
  函数sem_destroy(sem_t *sem)用来释放信号量sem。
  下面我们来看一个使用信号量的例子。在这个例子中,一共有4个线程,其中两个线程负责从文件读取数据到公共的缓冲区,另两个线程从缓冲区读取数据作不同的处理(加和乘运算)。
/* File sem.c */
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#define MAXSTACK 100
int stack[MAXSTACK][2];
int size=0;
sem_t sem;
/* 从文件1.dat读取数据,每读一次,信号量加一*/
void ReadData1(void){
FILE *fp=fopen("1.dat","r");
while(!feof(fp)){
fscanf(fp,"%d %d",&stack[size][0],&stack[size][1]);
sem_post(&sem);
++size;
}
fclose(fp);
}
/*从文件2.dat读取数据*/
void ReadData2(void){
FILE *fp=fopen("2.dat","r");
while(!feof(fp)){
fscanf(fp,"%d %d",&stack[size][0],&stack[size][1]);
sem_post(&sem);
++size;
}
fclose(fp);
}
/*阻塞等待缓冲区有数据,读取数据后,释放空间,继续等待*/
void HandleData1(void){
while(1){
sem_wait(&sem);
printf("Plus:%d+%d=%d\n",stack[size][0],stack[size][1],
stack[size][0]+stack[size][1]);
–size;
}
}

void HandleData2(void){
while(1){
sem_wait(&sem);
printf("Multiply:%d*%d=%d\n",stack[size][0],stack[size][1],
stack[size][0]*stack[size][1]);
–size;
}
}
int main(void){
pthread_t t1,t2,t3,t4;
sem_init(&sem,0,0);
pthread_create(&t1,NULL,(void *)HandleData1,NULL);
pthread_create(&t2,NULL,(void *)HandleData2,NULL);
pthread_create(&t3,NULL,(void *)ReadData1,NULL);
pthread_create(&t4,NULL,(void *)ReadData2,NULL);
/* 防止程序过早退出,让它在此无限期等待*/
pthread_join(t1,NULL);
}

 
 在Linux下,我们用命令gcc -lpthread sem.c -o sem生成可执行文件sem。
我们事先编辑好数据文件1.dat和2.dat,假设它们的内容分别为1 2 3 4 5 6 7 8 9 10和 -1 -2 -3 -4 -5
-6 -7 -8 -9 -10 ,我们运行sem,得到如下的结果:
Multiply:-1*-2=2
Plus:-1+-2=-3
Multiply:9*10=90
Plus:-9+-10=-19
Multiply:-7*-8=56
Plus:-5+-6=-11
Multiply:-3*-4=12
Plus:9+10=19
Plus:7+8=15
Plus:5+6=11

  从中我们可以看出各个线程间的竞争关系。而数值并未按我们原先的顺序显示出来这是由于size这个数值被各个线程任意修改的缘故。这也往往是多线程编程要注意的问题。

5 小结
  多线程编程是一个很有意思也很有用的技术,使用多线程技术的网络蚂蚁是目前最常用的下载工具之一,使用多线程技术的grep比单线程的grep要快上几倍,类似的例子还有很多。希望大家能用多线程技术写出高效实用的好程序来。

2005年11月23日

 

Problem Statement

 

 

 

 

When editing a single line of text, there are four keys that can be used to move the cursor: end, home, left-arrow and right-arrow. As you would expect, left-arrow and right-arrow move the cursor one character left or one character right, unless the cursor is at the beginning of the line or the end of the line, respectively, in which case the keystrokes do nothing (the cursor does not wrap to the previous or next line). The home key moves the cursor to the beginning of the line, and the end key moves the cursor to the end of the line.

You will be given a int, N, representing the number of character in a line of text. The cursor is always between two adjacent characters, at the beginning of the line, or at the end of the line. It starts before the first character, at position 0. The position after the last character on the line is position N. You should simulate a series of keystrokes and return the final position of the cursor. You will be given a string where characters of the string represent the keystrokes made, in order. ‘L’ and ‘R’ represent left and right, while ‘H’ and ‘E’ represent home and end.

Definition

 

 

 

 

Class:

CursorPosition

Method:

getPosition

Parameters:

string, int

Returns:

int

Method signature:

int getPosition(string keystrokes, int N)

(be sure your method is public)

 

 

 

 

Constraints

-

keystrokes will be contain between 1 and 50 ‘L’, ‘R’, ‘H’, and ‘E’ characters, inclusive.

-

N will be between 1 and 100, inclusive.

Examples

0)

 

 

 

 

"ERLLL"

10

Returns: 7

First, we go to the end of the line at position 10. Then, the right-arrow does nothing because we are already at the end of the line. Finally, three left-arrows brings us to position 7.

1)

 

 

 

 

"EHHEEHLLLLRRRRRR"

2

Returns: 2

All the right-arrows at the end ensure that we end up at the end of the line.

2)

 

 

 

 

"ELLLELLRRRRLRLRLLLRLLLRLLLLRLLRRRL"

10

Returns: 3

3)

 

 

 

 

"RRLEERLLLLRLLRLRRRLRLRLRLRLLLLL"

19

Returns: 12

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.


我的答案:


#include <string>
#include <iostream>
using namespace std;
class CursorPosition
{
public:
    int getPosition(string keystrokes,int N);
};

int CursorPosition::getPosition(string keystrokes,int N)
{
    int pos = 0,i;
    int nCmd = keystrokes.size();
    int ELast = keystrokes.find_last_of(‘E’);
    ELast = ELast!=string::npos?ELast:0;
    int HLast = keystrokes.find_last_of(‘H’);
    HLast = ELast!=string::npos?HLast:0;
    pos = ELast>HLast?N:0;
   
    for(i= ELast>HLast?ELast:HLast;i<nCmd;i++)
    {
        switch(keystrokes[i])
        {
        case ‘L’:
            pos–;
            break;
        case ‘R’:
            pos++;
            break;
        }
        pos = pos>N?N:pos;
        pos = pos<0?0:pos;
       
    }
    return pos;
}

int main(int argc,char *argv[])
{
    CursorPosition cp;
    cout<<cp.getPosition("RRLEERLLLLRLLRLRRRLRLRLRLRLLLLL",19)<<endl;
    return 0;
}

 

Problem Statement

 

 

 

 

A simple line drawing program uses a blank 20 x 20 pixel canvas and a directional cursor that starts at the upper left corner pointing straight down. The upper left corner of the canvas is at (0, 0) and the lower right corner is at (19, 19). You are given a String[], commands, each element of which contains one of two possible commands. A command of the form "FORWARD x" means that the cursor should move forward by x pixels. Each pixel on its path, including the start and end points, is painted black. The only other command is "LEFT", which means that the cursor should change its direction by 90 degrees counterclockwise. So, if the cursor is initially pointing straight down and it receives a single "LEFT" command, it will end up pointing straight to the right. Execute all the commands in order and return the resulting 20 x 20 pixel canvas as a String[] where character j of element i represents the pixel at (i, j). Black pixels should be represented as uppercase ‘X’ characters and blank pixels should be represented as ‘.’ characters.

Definition

 

 

 

 

Class:

DrawLines

Method:

execute

Parameters:

String[]

Returns:

String[]

Method signature:

String[] execute(String[] commands)

(be sure your method is public)

 

 

 

 

Notes

-

The cursor only paints the canvas if it moves (see example 1).

Constraints

-

commands will contain between 1 and 50 elements, inclusive.

-

Each element of commands will be formatted as either "LEFT" or "FORWARD x" (quotes for clarity only), where x is an integer between 1 and 19, inclusive, with no extra leading zeros.

-

When executing the commands in order, the cursor will never leave the 20 x 20 pixel canvas.

Examples

0)

 

 

 

 

{"FORWARD 19", "LEFT", "FORWARD 19", "LEFT", "FORWARD 19", "LEFT", "FORWARD 19"}

Returns: {"XXXXXXXXXXXXXXXXXXXX",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"X………………X",
"XXXXXXXXXXXXXXXXXXXX" }

This sequence of commands draws a 20 x 20 outline of a square. The cursor is initially at (0, 0) pointing straight down. It then travels to (0, 19) after the first FORWARD command, painting each pixel along its path with a ‘*’. It then rotates 90 degrees left, travels to (19, 19), rotates 90 degrees left, travels to (19, 0), rotates 90 degrees left, and finally travels back to (0, 0).

1)

 

 

 

 

{"LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT", "LEFT"}

Returns: {"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"……………….." }

The cursor spins round and round, but never actually paints any pixels. The result is an empty canvas.

2)

 

 

 

 

{"FORWARD 1"}

Returns: {"X……………….",
"X……………….",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"………………..",
"……………….." }

Going forward by one pixel creates a line that is 2 pixels long because both the start and end points are painted.

3)

 

 

 

 

{"LEFT", "FORWARD 19", "LEFT", "LEFT", "LEFT",
"FORWARD 18", "LEFT", "LEFT", "LEFT", "FORWARD 17",
"LEFT", "LEFT", "LEFT", "FORWARD 16", "LEFT",
"LEFT", "LEFT", "FORWARD 15", "LEFT", "LEFT", "LEFT",
"FORWARD 14", "LEFT", "LEFT", "LEFT", "FORWARD 13",
"LEFT", "LEFT", "LEFT", "FORWARD 12", "LEFT", "LEFT",
"LEFT", "FORWARD 11", "LEFT", "LEFT", "LEFT", "FORWARD 10",
"LEFT", "LEFT", "LEFT", "FORWARD 9", "LEFT", "LEFT",
"LEFT", "FORWARD 8", "LEFT", "LEFT", "LEFT", "FORWARD 7"}

Returns: {"XXXXXXXXXXXXXXXXXXXX",
"……………….X",
"..XXXXXXXXXXXXXXXX.X",
"..X…………..X.X",
"..X.XXXXXXXXXXXX.X.X",
"..X.X……….X.X.X",
"..X.X.XXXXXXXX.X.X.X",
"..X.X.X……..X.X.X",
"..X.X.X……..X.X.X",
"..X.X.X……..X.X.X",
"..X.X.X……..X.X.X",
"..X.X.X……..X.X.X",
"..X.X.X……..X.X.X",
"..X.X.X……..X.X.X",
"..X.X.XXXXXXXXXX.X.X",
"..X.X…………X.X",
"..X.XXXXXXXXXXXXXX.X",
"..X…………….X",
"..XXXXXXXXXXXXXXXXXX",
"……………….." }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement

 

 

 

 

A square matrix is a grid of NxN numbers. For example, the following is a 3×3 matrix:

4 3 5
2 4 5
0 1 9

One way to represent a matrix of numbers, each of which is between 0 and 9 inclusive, is as a row-major string. To generate the string, simply concatenate all of the elements from the first row followed by the second row and so on, without any spaces. For example, the above matrix would be represented as "435245019".

You will be given a square matrix as a row-major string. Your task is to convert it into a vector <string>, where each element represents one row of the original matrix. Element i of the vector <string> represents row i of the matrix. You should not include any spaces in your return. Hence, for the above string, you would return {"435","245","019"}. If the input does not represent a square matrix because the number of characters is not a perfect square, return an empty vector <string>, {}.

Definition

 

 

 

 

Class:

MatrixTool

Method:

convert

Parameters:

string

Returns:

vector <string>

Method signature:

vector <string> convert(string s)

(be sure your method is public)

 

 

 

 

Constraints

-

s will contain between 1 and 50 digits, inclusive.

Examples

0)

 

 

 

 

"435245019"

Returns: {"435", "245", "019" }

The example above.

1)

 

 

 

 

"9"

Returns: {"9" }

2)

 

 

 

 

"0123456789"

Returns: { }

This input has 10 digits, and 10 is not a perfect square.

3)

 

 

 

 

"3357002966366183191503444273807479559869883303524"

Returns: {"3357002", "9663661", "8319150", "3444273", "8074795", "5986988", "3303524" }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.


我写的代码:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class MatrixTool
{
public:
    vector <string> convert(string s);
};

vector <string> MatrixTool::convert(string s)
{
    int n = s.size();
    int i=1,j=0,k=0;
    bool bMatrix = false;
    vector <string> vector_matrix;
    for(i;i<=n&&i<8;i++)
    {
        int temp = i*i;
        if( temp == n)
        {
            bMatrix = true;
            break;
        }
        else if( temp>n )
        {
            bMatrix = false;
            break;
        }
    }
    if(!bMatrix)
        return vector_matrix;
    vector_matrix.resize(i);
    for(j;j<i;j++)
        for(k = 0;k<i;k++)
            vector_matrix[j].push_back(s[i*j+k]);
   
    return vector_matrix;

2005年11月11日

    两年前,学校的退学通知像一盆冷水泼在了我的头上。贪玩的我,自负的我,认为这个垃圾学校的本科毕业证是一个垃圾,可有可无,老师上的课也像小儿科,根本就无心去听。后来又迷上了该死的盛大的传奇游戏,于是在大三二期一整个学期里的沉迷在里面,完全忘记了外面的世界,忘记了上课,到了期末考试的时候也没有去参加当时认为见鬼的考试。去吧,这个垃圾学校。于是,那个退学通知就来了,因为我一整个学期的学分为零。当时学校说要通知家里,我一听感觉整个世界都完了,让老爸知道的话非杀了不可。当时的我完全让给击垮了,甚至想到了自杀,呵呵,后来想想,明白了为什么这么多人在压力下选择了自杀,人没有到那种心情的时候是体会不到的。后来想到了,那我就出来混吧,于是我投了很多的简历。但是,谁会要一个大学还没毕业的学生呢。不过,虽然我不是个好学生,也花去了很多的时间去玩游戏,但是编程还算过得去,因为我高中的时候就开始自学编程了,大一的时候还帮学校做了一个勤工助学管理系统还挣了一千块钱,而且当时还玩了玩linux。当然,简历投了不少,当时有一个浙江海边小岛的网络公司的技术总监看了我的简历,也知道我的现况,在网上和我谈了些技术上的东西,就当是网络面试吧,对我感觉还满意,就叫我过去,当时挺感谢他的。那时候病急乱投医的我就准备过去了。没想到的是,几天后,北京一家做linux桌面操作系统的公司也给我回复了,让我做他们的测试题,当时是修改一小游戏程序达到他们的要求和做一个模拟的电话自动应答系统。这么多简历,只有这两年公司给我回复了,我花了两天把他们的测试做好了,当时也没想会通过。没想到的是这家公司让马上过北京去面试。面试想不到的顺利,只花了半个小时不到,并且待遇也还不错,对于一个辍的大学生来说,月薪4500很不错,就连当时陪我去面试的在北京上大学的同学都觉得实在是太顺利了。于是,我匆忙的回到长沙和校方达成了协议休学!于是,我就来到了北京,来到了我现在工作的公司。还在上高中的时候,就想过,以后工作了,第一站就是北京,没想到的是,我是在这样的情况下来到了北京。北京,我来了!!!!
    进入我工作的公司后,开始觉得压力很大,毕竟,不像在学校一样每天上几节课甚至不去上课。每天都对着电脑,感觉累极了。刚工作的我还是有很多不足的,毕竟我不是一个好学生,并且我进入公司分配到了公司的linux操作系统开发小组的控制面版小组,开始的一个星期都在熟悉操作系统的使用,其实我当时对linux还真只是fans级的用户而已,只是会一些安装美化,终端下的命令只会ls而已,想想,当时一个星期都在疯狂的学东西,要学的太多了!一个星期后我就进入了开发状态,现在想想来当时的效率怎么会这么高!!一两个星期下来,我熟悉了linux的基本命令,学习了autools,automake,aclocal,autconf等自动化生成工具,还要学习vi的使用,还要linux下的打包工具当时我们小组只有三个人,我们组长汪兴刚,李晋,还有我!我们负责的东西很杂,有用C的,有用python的,还有shell的,这些东西都要现学。这么多的东西一下堆到我的面前,头都要炸了!每天都累得一回到家倒头就能睡。当时就很害怕,害怕自己不能胜任这份工作!很感谢我当时的组长汪兴刚,他告诉我说,叫我一定要用信心,并且告诉我说,说我动手能力很强,很快就上手了,不错。就是他给了我信心,我告诉自己我一定能行!是的,我行,一个月之后公司就和我正式签约了!当时我记得非常清楚的是,和我一起进来的还有一个是北师大的研究生,当时我们组长告诉我说,他做题做得非常好,还是个研究生,公司当时是想让他做项目组长的,工资也开得比较高,但是两个月以后什么也做不了,工作一点进度也没有,于是就要降他工资,后来就走了。组长告诉我,他的工作做得还不如我好,这也给了我很大的信心,是的,我一定可以做得很好!后来也证明,我在公司呆下来了,工作也得到了认可。
    就这样,我在公司呆下来了。当时公司正在起步,很多的东西都要去争取,加班也就成了家常便饭,但是正是这些加班,让我和公司的同事们迅速的熟悉了起来!因为,一起工作一起奋斗到深夜甚至通宵那种工作热情很容易感染每个人的!也让我快的成长起来!学到了更多的东西!甚至在过年的时候,我们还在加班,因为过年后一个月我们就要参加linux桌面操作系统评测,也正是因为这样,公司为我们加班的同事报销往返的机票让我们能够回家过年。这也成了我的第一次,第一次坐飞机,呵呵,当时和我那些还在学校上学的同学说了,他们都羡慕得紧了。
    在公司经历了很多,也成长了很多。还有很多想说的,但看看夜都很深了,明天海军他们还约了要打球呢,要早点睡。
    今天,说了这么多,是因为最近有点烦,是工作上的,公司有点乱,也很让我失望。而且,今天小古(和我一样也辍学来北京了,只不过是比我晚出来了差不多一年)接到家里的电话,说学校发信回家了,家里知道了他辍学了,说是再不回学校就要除名了!真烦,如果是除名了就不用烦了,但是现在还有机会回去上学,我要回去么?其实也不是不想回去,这一段时间来,因为没证我失去了很多去一些好公司的机会,但是我没钱,家里也不知道我是辍学的。你不要问我,工作两年了怎么还没钱!我工作后,我要供我女朋友上学,还要供弟弟上大学,我一个人养三个人呢!看来,要来的事情还是要来了,爸爸迟早是要知道的!选择了这样难的路,也不是选择吧,是自己不争气吧,是不争气吗?那就坚决走下去吧!

2005年11月09日

0 前言: STL,为什么你必须掌握


对于程序员来说,数据结构是必修的一门课。从查找到排序,从链表到二叉树,几乎所有的算法和原理都需要理解,理解不了也要死记硬背下来。幸运的是这些理论
都已经比较成熟,算法也基本固定下来,不需要你再去花费心思去考虑其算法原理,也不用再去验证其准确性。不过,等你开始应用计算机语言来工作的时候,你会
发现,面对不同的需求你需要一次又一次去用代码重复实现这些已经成熟的算法,而且会一次又一次陷入一些由于自己疏忽而产生的bug中。这时,你想找一种工
具,已经帮你实现这些功能,你想怎么用就怎么用,同时不影响性能。你需要的就是STL, 标准模板库!

西方有句谚语:不要重复发明轮子!

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除……可以说,如果你理解了STL,你会发现你已不用拘泥于算法本身,从而站在巨人的肩膀上去考虑更高级的应用。

排序是最广泛的算法之一,本文详细介绍了STL中不同排序算法的用法和区别。

1 STL提供的Sort 算法


C++之所以得到这么多人的喜欢,是因为它既具有面向对象的概念,又保持了C语言高效的特点。STL 排序算法同样需要保持高效。因此,对于不同的需求,STL提供的不同的函数,不同的函数,实现的算法又不尽相同。

1.1 所有sort算法介绍


有的sort算法的参数都需要输入一个范围,[begin,
end)。这里使用的迭代器(iterator)都需是随机迭代器(RadomAccessIterator),
也就是说可以随机访问的迭代器,如:it+n什么的。(partition 和stable_partition 除外)

如果你需要自己定义比较函数,你可以把你定义好的仿函数(functor)作为参数传入。每种算法都支持传入比较函数。以下是所有STL sort算法函数的名字列表:

函数名 功能描述
sort 对给定区间所有元素进行排序
stable_sort 对给定区间所有元素进行稳定排序
partial_sort 对给定区间所有元素部分排序
partial_sort_copy 对给定区间复制并排序
nth_element 找出给定区间的某个位置对应的元素
is_sorted 判断一个区间是否已经排好序
partition 使得符合某个条件的元素放在前面
stable_partition 相对稳定的使得符合某个条件的元素放在前面

其中nth_element 是最不易理解的,实际上,这个函数是用来找出第几个。例如:找出包含7个元素的数组中排在中间那个数的值,此时,我可能不关心前面,也不关心后面,我只关心排在第四位的元素值是多少。

1.2 sort 中的比较函数

当你需要按照某种特定方式进行排序时,你需要给sort指定比较函数,否则程序会自动提供给你一个比较函数。

vector < int > vect;
//...
sort(vect.begin(), vect.end());
//此时相当于调用
sort(vect.begin(), vect.end(), less<int>() );

上述例子中系统自己为sort提供了less仿函数。在STL中还提供了其他仿函数,以下是仿函数列表:

名称 功能描述
equal_to 相等
not_equal_to 不相等
less 小于
greater 大于
less_equal 小于等于
greater_equal 大于等于

需要注意的是,这些函数不是都能适用于你的sort算法,如何选择,决定于你的应用。另外,不能直接写入仿函数的名字,而是要写其重载的()函数:

less<int>()
greater<int>()

当你的容器中元素时一些标准类型(int float char)或者string时,你可以直接使用这些函数模板。但如果你时自己定义的类型或者你需要按照其他方式排序,你可以有两种方法来达到效果:一种是自己写比较函数。另一种是重载类型的'<'操作赋。

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;

class myclass {
public:
myclass(int a, int b):first(a), second(b){}
int first;
int second;
bool operator < (const myclass &m)const {
return first < m.first;
}
};

bool less_second(const myclass & m1, const myclass & m2) {
return m1.second < m2.second;
}

int main() {

vector< myclass > vect;
for(int i = 0 ; i < 10 ; i ++){
myclass my(10-i, i*3);
vect.push_back(my);
}
for(int i = 0 ; i < vect.size(); i ++)
cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
sort(vect.begin(), vect.end());
cout<<"after sorted by first:"<<endl;
for(int i = 0 ; i < vect.size(); i ++)
cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";
cout<<"after sorted by second:"<<endl;
sort(vect.begin(), vect.end(), less_second);
for(int i = 0 ; i < vect.size(); i ++)
cout<<"("<<vect[i].first<<","<<vect[i].second<<")\n";

return 0 ;
}

知道其输出结果是什么了吧:

(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)
after sorted by first:
(1,27)
(2,24)
(3,21)
(4,18)
(5,15)
(6,12)
(7,9)
(8,6)
(9,3)
(10,0)
after sorted by second:
(10,0)
(9,3)
(8,6)
(7,9)
(6,12)
(5,15)
(4,18)
(3,21)
(2,24)
(1,27)

1.3 sort 的稳定性


发现有sort和stable_sort,还有 partition 和stable_partition,
感到奇怪吧。其中的区别是,带有stable的函数可保证相等元素的原本相对次序在排序后保持不变。或许你会问,既然相等,你还管他相对位置呢,也分不清
楚谁是谁了?这里需要弄清楚一个问题,这里的相等,是指你提供的函数表示两个元素相等,并不一定是一摸一样的元素。

例如,如果你写一个比较函数:

bool less_len(const string &str1, const string &str2)
{
return str1.length() < str2.length();
}


时,"apple" 和 "winter" 就是相等的,如果在"apple"
出现在"winter"前面,用带stable的函数排序后,他们的次序一定不变,如果你使用的是不带"stable"的函数排序,那么排序完后,
"Winter"有可能在"apple"的前面。

1.4 全排序

全排序即把所给定范围所有的元素按照大小关系顺序排列。用于全排序的函数有

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);

template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
StrictWeakOrdering comp);


第1,3种形式中,sort 和 stable_sort都没有指定比较函数,系统会默认使用operator<
对区间[first,last)内的所有元素进行排序,
因此,如果你使用的类型义军已经重载了operator<函数,那么你可以省心了。第2,
4种形式,你可以随意指定比较函数,应用更为灵活一些。来看看实际应用:

班上有10个学生,我想知道他们的成绩排名。

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
using namespace std;

class student{
public:
student(const string &a, int b):name(a), score(b){}
string name;
int score;
bool operator < (const student &m)const {
return score< m.score;
}
};

int main() {
vector< student> vect;
student st1("Tom", 74);
vect.push_back(st1);
st1.name="Jimy";
st1.score=56;
vect.push_back(st1);
st1.name="Mary";
st1.score=92;
vect.push_back(st1);
st1.name="Jessy";
st1.score=85;
vect.push_back(st1);
st1.name="Jone";
st1.score=56;
vect.push_back(st1);
st1.name="Bush";
st1.score=52;
vect.push_back(st1);
st1.name="Winter";
st1.score=77;
vect.push_back(st1);
st1.name="Andyer";
st1.score=63;
vect.push_back(st1);
st1.name="Lily";
st1.score=76;
vect.push_back(st1);
st1.name="Maryia";
st1.score=89;
vect.push_back(st1);
cout<<"------before sort..."<<endl;
for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
stable_sort(vect.begin(), vect.end(),less<student>());
cout <<"-----after sort ...."<<endl;
for(int i = 0 ; i < vect.size(); i ++) cout<<vect[i].name<<":\t"<<vect[i].score<<endl;
return 0 ;
}

其输出是:

------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Bush: 52
Jimy: 56
Jone: 56
Andyer: 63
Tom: 74
Lily: 76
Winter: 77
Jessy: 85
Maryia: 89
Mary: 92

sort采用的是成熟的"快速排序算法"(目前大部分STL版本已经不是采用简单的快速排序,而是结合内插排序算法)。注1
可以保证很好的平均性能、复杂度为n*log(n),由于单纯的快速排序在理论上有最差的情况,性能很低,其算法复杂度为n*n,但目前大部分的STL版
本都已经在这方面做了优化,因此你可以放心使用。stable_sort采用的是"归并排序",分派足够内存是,其算法复杂度为n*log(n),
否则其复杂度为n*log(n)*log(n),其优点是会保持相等元素之间的相对位置在排序前后保持一致。

1.5 局部排序

局部排序其实是为了减少不必要的操作而提供的排序方式。其函数原型为:

template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
StrictWeakOrdering comp);

template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);

template <class InputIterator, class RandomAccessIterator,
class StrictWeakOrdering>
RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last, Compare comp);

理解了sort 和stable_sort后,再来理解partial_sort 就比较容易了。先看看其用途:
班上有10个学生,我想知道分数最低的5名是哪些人。如果没有partial_sort,你就需要用sort把所有人排好序,然后再取前5个。现在你只需要对分数最低5名排序,把上面的程序做如下修改:

stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
partial_sort(vect.begin(), vect.begin()+5, vect.end(),less<student>());

输出结果为:

------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Bush: 52
Jimy: 56
Jone: 56
Andyer: 63
Tom: 74
Mary: 92
Jessy: 85
Winter: 77
Lily: 76
Maryia: 89

这样的好处知道了吗?当数据量小的时候可能看不出优势,如果是100万学生,我想找分数最少的5个人......

partial_sort采用的堆排序(heapsort),它在任何情况下的复杂度都是n*log(n). 如果你希望用partial_sort来实现全排序,你只要让middle=last就可以了。

partial_sort_copy其实是copy和partial_sort的组合。被排序(被复制)的数量是[first,
last)和[result_first, result_last)中区间较小的那个。如果[result_first,
result_last)区间大于[first, last)区间,那么partial_sort相当于copy和sort的组合。

1.6 nth_element 指定元素排序

nth_element一个容易看懂但解释比较麻烦的排序。用例子说会更方便:

班上有10个学生,我想知道分数排在倒数第4名的学生。

如果要满足上述需求,可以用sort排好序,然后取第4位(因为是由小到大排), 更聪明的朋友会用partial_sort, 只排前4位,然后得到第4位。其实这是你还是浪费,因为前两位你根本没有必要排序,此时,你就需要nth_element:

template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);

template <class RandomAccessIterator, class StrictWeakOrdering>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, StrictWeakOrdering comp);

对于上述实例需求,你只需要按下面要求修改1.4中的程序:

stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
nth_element(vect.begin(), vect.begin()+3, vect.end(),less<student>());

运行结果为:

------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Jone: 56
Bush: 52
Jimy: 56
Andyer: 63
Jessy: 85
Mary: 92
Winter: 77
Tom: 74
Lily: 76
Maryia: 89

第四个是谁?Andyer,这个倒霉的家伙。为什么是begin()+3而不是+4? 我开始写这篇文章的时候也没有在意,后来在ilovevc 的提醒下,发现了这个问题。begin()是第一个,begin()+1是第二个,... begin()+3当然就是第四个了。

1.7 partition 和stable_partition

好像这两个函数并不是用来排序的,'分类'算法,会更加贴切一些。partition就是把一个区间中的元素按照某个条件分成两类。其函数原型为:

template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first,
ForwardIterator last, Predicate pred)
template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last,
Predicate pred);

看看应用吧:
班上10个学生,计算所有没有及格(低于60分)的学生。
你只需要按照下面格式替换1.4中的程序:

stable_sort(vect.begin(), vect.end(),less<student>());
替换为:
student exam("pass", 60);
stable_partition(vect.begin(), vect.end(), bind2nd(less<student>(), exam));

其输出结果为:

------before sort...
Tom: 74
Jimy: 56
Mary: 92
Jessy: 85
Jone: 56
Bush: 52
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89
-----after sort ....
Jimy: 56
Jone: 56
Bush: 52
Tom: 74
Mary: 92
Jessy: 85
Winter: 77
Andyer: 63
Lily: 76
Maryia: 89

看见了吗,Jimy,Jone, Bush(难怪说美国总统比较笨 smile )都没有及格。而且使用的是stable_partition, 元素之间的相对次序是没有变.

2 Sort 和容器


STL中标准容器主要vector, list, deque, string, set, multiset, map, multimay, 其中set, multiset, map, multimap都是以树结构的方式存储其元素详细内容请参看:学习STL map, STL set之数据结构基础. 因此在这些容器中,元素一直是有序的。

这些容器的迭代器类型并不是随机型迭代器,因此,上述的那些排序函数,对于这些容器是不可用的。上述sort函数对于下列容器是可用的:

  • vector
  • string
  • deque

如果你自己定义的容器也支持随机型迭代器,那么使用排序算法是没有任何问题的。

对于list容器,list自带一个sort成员函数list::sort().
它和算法函数中的sort差不多,但是list::sort是基于指针的方式排序,也就是说,所有的数据移动和比较都是此用指针的方式实现,因此排序后的
迭代器一直保持有效(vector中sort后的迭代器会失效).

3 选择合适的排序函数


为什么要选择合适的排序函数?可能你并不关心效率(这里的效率指的是程序运行时间), 或者说你的数据量很小, 因此你觉得随便用哪个函数都无关紧要。

其实不然,即使你不关心效率,如果你选择合适的排序函数,你会让你的代码更容易让人明白,你会让你的代码更有扩充性,逐渐养成一个良好的习惯,很重要吧 smile

如果你以前有用过C语言中的qsort, 想知道qsort和他们的比较,那我告诉你,qsort和sort是一样的,因为他们采用的都是快速排序。从效率上看,以下几种sort算法的是一个排序,效率由高到低(耗时由小变大):

  1. partion
  2. stable_partition
  3. nth_element
  4. partial_sort
  5. sort
  6. stable_sort

记得,以前翻译过Effective STL的文章,其中对如何选择排序函数总结的很好:

  • 若需对vector, string, deque, 或 array容器进行全排序,你可选择sort或stable_sort;
  • 若只需对vector, string, deque, 或 array容器中取得top n的元素,部分排序partial_sort是首选.
  • 若对于vector, string, deque, 或array容器,你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部顺序,nth_element是最理想的;
  • 若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开,你最好使用partition或stable_partition;
  • 若使用的list容器,你可以直接使用partition和stable_partition算法,你可以使用list::sort代替sort和
    stable_sort排序。若你需要得到partial_sort或nth_element的排序效果,你必须间接使用。正如上面介绍的有几种方式可以
    选择。

总之记住一句话: 如果你想节约时间,不要走弯路, 也不要走多余的路!

4 小结


讨论技术就像个无底洞,经常容易由一点可以引申另外无数个技术点。因此需要从全局的角度来观察问题,就像观察STL中的sort算法一样。其实在
STL还有make_heap,
sort_heap等排序算法。本文章没有提到。本文以实例的方式,解释了STL中排序算法的特性,并总结了在实际情况下应如何选择合适的算法。

0 为什么需要hash_map

用过map吧?map提供一个很常用的功能,那就是提供key-value的存储和查找功能。例如,我要记录一个人名和相应的存储,而且随时增加,要快速查找和修改:

岳不群-华山派掌门人,人称君子剑
张三丰-武当掌门人,太极拳创始人
东方不败-第一高手,葵花宝典
...

这些信息如果保存下来并不复杂,但是找起来比较麻烦。例如我要找"张三丰"的信息,最傻的方法就是取得所有的记录,然后按照名字一个一个比较。如果要速度
快,就需要把这些记录按照字母顺序排列,然后按照二分法查找。但是增加记录的时候同时需要保持记录有序,因此需要插入排序。考虑到效率,这就需要用到二叉
树。讲下去会没完没了,如果你使用STL
的map容器,你可以非常方便的实现这个功能,而不用关心其细节。关于map的数据结构细节,感兴趣的朋友可以参看学习STL map, STL set之数据结构基础
看看map的实现:

#include <map>
#include <string>
using namespace std;
...
map<string, string> namemap;

//增加。。。
namemap["岳不群"]="华山派掌门人,人称君子剑";
namemap["张三丰"]="武当掌门人,太极拳创始人";
namemap["东方不败"]="第一高手,葵花宝典";
...

//查找。。
if(namemap.find("岳不群") != namemap.end()){
...
}

不觉得用起来很easy吗?而且效率很高,100万条记录,最多也只要20次的string.compare的比较,就能找到你要找的记录;200万条记录事,也只要用21次的比较。

速度永远都满足不了现实的需求。如果有100万条记录,我需要频繁进行搜索时,20次比较也会成为瓶颈,要是能降到一次或者两次比较是否有可能?而且当记录数到200万的时候也是一次或者两次的比较,是否有可能?而且还需要和map一样的方便使用。

答案是肯定的。这时你需要has_map. 虽然hash_map目前并没有纳入C++ 标准模板库中,但几乎每个版本的STL都提供了相应的实现。而且应用十分广泛。在正式使用hash_map之前,先看看hash_map的原理。

1 数据结构:hash_map原理

这是一节让你深入理解hash_map的介绍,如果你只是想囫囵吞枣,不想理解其原理,你倒是可以略过这一节,但我还是建议你看看,多了解一些没有坏处。

hash_map基于hash table(哈希表)。
哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的
情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。

其基本原理是:使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数,也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下
标,hash值)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素“分类”,然后将这个元素存储在相应“类”所对
应的地方,称为桶。

但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中。 总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。

hash_map,首先分配一大片内存,形成许多桶。是利用hash函数,对key进行映射到不同区域(桶)进行保存。其插入过程是:

  1. 得到key
  2. 通过hash函数得到hash值
  3. 得到桶号(一般都为hash值对桶数求模)
  4. 存放key和value在桶内。

其取值过程是:

  1. 得到key
  2. 通过hash函数得到hash值
  3. 得到桶号(一般都为hash值对桶数求模)
  4. 比较桶的内部元素是否与key相等,若都不相等,则没有找到。
  5. 取出相等的记录的value。

hash_map中直接地址用hash函数生成,解决冲突,用比较函数解决。这里可以看出,如果每个桶内部只有一个元素,那么查找的时候只有一次比较。当许多桶内没有值时,许多查询就会更快了(指查不到的时候).

由此可见,要实现哈希表, 和用户相关的是:hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。

2 hash_map 使用

2.1 一个简单实例

不要着急如何把"岳不群"用hash_map表示,我们先看一个简单的例子:随机给你一个ID号和ID号相应的信息,ID号的范围是1~2的31次方。如何快速保存查找。

#include <hash_map>
#include <string>
using namespace std;
int main(){
hash_map<int, string> mymap;
mymap[9527]="唐伯虎点秋香";
mymap[1000000]="百万富翁的生活";
mymap[10000]="白领的工资底线";
...
if(mymap.find(10000) != mymap.end()){
...
}

够简单,和map使用方法一样。这时你或许会问?hash函数和比较函数呢?不是要指定么?你说对了,但是在你没有指定hash函数和比较函数的时候,你会有一个缺省的函数,看看hash_map的声明,你会更加明白。下面是SGI STL的声明:

template <class _Key, class _Tp, class _HashFcn = hash<_Key>,
class _EqualKey = equal_to<_Key>,
class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class hash_map
{
...
}

也就是说,在上例中,有以下等同关系:

...
hash_map<int, string> mymap;
//等同于:
hash_map<int, string, hash<int>, equal_to<int> > mymap;

Alloc我们就不要取关注太多了(希望深入了解Allocator的朋友可以参看标准库 STL :Allocator能做什么)

2.2 hash_map 的hash函数

hash< int>到底是什么样子?看看源码:

struct hash<int> {
size_t operator()(int __x) const { return __x; }
};

原来是个函数对象。在SGI STL中,提供了以下hash函数:

struct hash<char*>
struct hash<const char*>
struct hash<char>
struct hash<unsigned char>
struct hash<signed char>
struct hash<short>
struct hash<unsigned short>
struct hash<int>
struct hash<unsigned int>
struct hash<long>
struct hash<unsigned long>

也就是说,如果你的key使用的是以上类型中的一种,你都可以使用缺省的hash函数。当然你自己也可以定义自己的hash函数。对于自定义变量,你只能如此,例如对于string,就必须自定义hash函数。例如:

struct str_hash{
size_t operator()(const string& str) const
{
unsigned long __h = 0;
for (size_t i = 0 ; i < str.size() ; i ++)
__h = 5*__h + str[i];
return size_t(__h);
}
};
//如果你希望利用系统定义的字符串hash函数,你可以这样写:
struct str_hash{
size_t operator()(const string& str) const
{
return return __stl_hash_string(str.c_str());
}
};

在声明自己的哈希函数时要注意以下几点:

  1. 使用struct,然后重载operator().
  2. 返回是size_t
  3. 参数是你要hash的key的类型。
  4. 函数是const类型的。

如果这些比较难记,最简单的方法就是照猫画虎,找一个函数改改就是了。

现在可以对开头的"岳不群"进行哈希化了 smile . 直接替换成下面的声明即可:

map<string, string> namemap; 
//改为:
hash_map<string, string, str_hash> namemap;

其他用法都不用边。当然不要忘了吧str_hash的声明以及头文件改为hash_map。

你或许会问:比较函数呢?别着急,这里就开始介绍hash_map中的比较函数。

2.3 hash_map 的比较函数

在map
中的比较函数,需要提供less函数。如果没有提供,缺省的也是less< Key>
。在hash_map中,要比较桶内的数据和key是否相等,因此需要的是是否等于的函数:equal_to< Key>
。先看看equal_to的源码:

//本代码可以从SGI STL
//先看看binary_function 函数声明,其实只是定义一些类型而已。
template <class _Arg1, class _Arg2, class _Result>
struct binary_function {
typedef _Arg1 first_argument_type;
typedef _Arg2 second_argument_type;
typedef _Result result_type;
};
//看看equal_to的定义:
template <class _Tp>
struct equal_to : public binary_function<_Tp,_Tp,bool>
{
bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; }
};

如果你使用一个自定义的数据类型,如struct mystruct, 或者const char* 的字符串,如何使用比较函数?使用比较函数,有两种方法. 第一种是:重载==操作符,利用equal_to;看看下面的例子:

struct mystruct{
int iID;
int len;
bool operator==(const mystruct & my) const{
return (iID==my.iID) && (len==my.len) ;
}
};

这样,就可以使用equal_to< mystruct>作为比较函数了。另一种方法就是使用函数对象。自定义一个比较函数体:

struct compare_str{
bool operator()(const char* p1, const char*p2) const{
return strcmp(p1,p2)==0;
}
};

有了compare_str,就可以使用hash_map了。

typedef hash_map<const char*, string, hash<const char*>, compare_str> StrIntMap;
StrIntMap namemap;
namemap["岳不群"]="华山派掌门人,人称君子剑";
namemap["张三丰"]="武当掌门人,太极拳创始人";
namemap["东方不败"]="第一高手,葵花宝典";

2.4 hash_map 函数

hash_map的函数和map的函数差不多。具体函数的参数和解释,请参看:STL 编程手册:Hash_map,这里主要介绍几个常用函数。

  1. hash_map(size_type n) 如果讲究效率,这个参数是必须要设置的。n 主要用来设置hash_map 容器中hash桶的个数。桶个数越多,hash函数发生冲突的概率就越小,重新申请内存的概率就越小。n越大,效率越高,但是内存消耗也越大。
  2. const_iterator find(const key_type& k) const. 用查找,输入为键值,返回为迭代器。
  3. data_type& operator[](const key_type& k) .
    这是我最常用的一个函数。因为其特别方便,可像使用数组一样使用。不过需要注意的是,当你使用[key
    ]操作符时,如果容器中没有key元素,这就相当于自动增加了一个key元素。因此当你只是想知道容器中是否有key元素时,你可以使用find。如果你
    希望插入该元素时,你可以直接使用[]操作符。
  4. insert
    函数。在容器中不包含key值时,insert函数和[]操作符的功能差不多。但是当容器中元素越来越多,每个桶中的元素会增加,为了保证效率,
    hash_map会自动申请更大的内存,以生成更多的桶。因此在insert以后,以前的iterator有可能是不可用的。
  5. erase 函数。在insert的过程中,当每个桶的元素太多时,hash_map可能会自动扩充容器的内存。但在sgi stl中是erase并不自动回收内存。因此你调用erase后,其他元素的iterator还是可用的。

3 相关hash容器

hash 容器除了hash_map之外,还有hash_set, hash_multimap, has_multiset, 这些容器使用起来和set, multimap, multiset的区别与hash_map和map的区别一样,我想不需要我一一细说了吧。

4 其他

这里列几个常见问题,应该对你理解和使用hash_map比较有帮助。

4.1 hash_map和map的区别在哪里?

  • 构造函数。hash_map需要hash函数,等于函数;map只需要比较函数(小于函数).
  • 存储结构。hash_map采用hash表存储,map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。

4.2 什么时候需要用hash_map,什么时候需要用map?


体来说,hash_map
查找速度会比map快,而且查找速度基本和数据数据量大小,属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小,
hash还有hash函数的耗时,明白了吧,如果你考虑效率,特别是在元素达到一定数量级时,考虑考虑hash_map。但若你对内存使用特别严格,希望
程序尽可能少消耗内存,那么一定要小心,hash_map可能会让你陷入尴尬,特别是当你的hash_map对象特别多时,你就更无法控制了,而且
hash_map的构造速度较慢。

现在知道如何选择了吗?权衡三个因素: 查找速度, 数据量, 内存使用。

这里还有个关于hash_map和map的小故事,看看:http://dev.csdn.net/Develop/article/14/14019.shtm

4.3 如何在hash_map中加入自己定义的类型?

你只要做两件事, 定义hash函数,定义等于比较函数。下面的代码是一个例子:

-bash-2.05b$ cat my.cpp
#include <hash_map>
#include <string>
#include <iostream>

using namespace std;
//define the class
class ClassA{
public:
ClassA(int a):c_a(a){}
int getvalue()const { return c_a;}
void setvalue(int a){c_a;}
private:
int c_a;
};

//1 define the hash function
struct hash_A{
size_t operator()(const class ClassA & A)const{
// return hash<int>(classA.getvalue());
return A.getvalue();
}
};

//2 define the equal function
struct equal_A{
bool operator()(const class ClassA & a1, const class ClassA & a2)const{
return a1.getvalue() == a2.getvalue();
}
};

int main()
{
hash_map<ClassA, string, hash_A, equal_A> hmap;
ClassA a1(12);
hmap[a1]="I am 12";
ClassA a2(198877);
hmap[a2]="I am 198877";

cout<<hmap[a1]<<endl;
cout<<hmap[a2]<<endl;
return 0;
}
-bash-2.05b$ make my
c++ -O -pipe -march=pentiumpro my.cpp -o my
-bash-2.05b$ ./my
I am 12
I am 198877

4.4如何用hash_map替换程序中已有的map容器?

这个很容易,但需要你有良好的编程风格。建议你尽量使用typedef来定义你的类型:

typedef map<Key, Value> KeyMap;

当你希望使用hash_map来替换的时候,只需要修改:

typedef hash_map<Key, Value> KeyMap;

其他的基本不变。当然,你需要注意是否有Key类型的hash函数和比较函数。

4.5为什么hash_map不是标准的?


体为什么不是标准的,我也不清楚,有个解释说在STL加入标准C++之时,hash_map系列当时还没有完全实现,以后应该会成为标准。如果谁知道更合
理的解释,也希望告诉我。但我想表达的是,正是因为hash_map不是标准的,所以许多平台上安装了g++编译器,不一定有hash_map的实现。我
就遇到了这样的例子。因此在使用这些非标准库的时候,一定要事先测试。另外,如果考虑到平台移植,还是少用为佳。

4.6 有学习使用hash_map的建议吗?

hash中文是哈希,也成为散列,听见别人说散列容器不要埋怨自己孤陋寡闻。了解hash系列,你还可以看看这篇文章:effective STL 25: 熟悉非标准散列容器, 另外建议查看源代码。如果还有问题,那么你可以在STL论坛上提问,会有高手回答你的。