临界区

　　临界区（Critical Section）是一段独占对某些共享资源访问的代码，在任意时刻只允许一个线程对共享资源进行访问。如果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操作共享资源的目的。

　　临界区在使用时以CRITICAL_SECTION结构对象保护共享资源，并分别用 EnterCriticalSection（）和LeaveCriticalSection（）函数去标识和释放一个临界区。所用到的 CRITICAL_SECTION结构对象必须经过InitializeCriticalSection（）的初始化后才能使用，而且必须确保所有线程中的任何试图访问此共享资源的代码都处在此临界区的保护之下。否则临界区将不会起到应有的作用，共享资源依然有被破坏的可能。


图1 使用临界区保持线程同步

　　下面通过一段代码展示了临界区在保护多线程访问的共享资源中的作用。通过两个线程来分别对全局变量g_cArray[10]进行写入操作，用临界区结构对象g_cs来保持线程的同步，并在开启线程前对其进行初始化。为了使实验效果更加明显，体现出临界区的作用，在线程函数对共享资源g_cArray [10]的写入时，以Sleep（）函数延迟1毫秒，使其他线程同其抢占CPU的可能性增大。如果不使用临界区对其进行保护，则共享资源数据将被破坏（参见图1（a）所示计算结果），而使用临界区对线程保持同步后则可以得到正确的结果（参见图1（b）所示计算结果）。代码实现清单附下：

// 临界区结构对象 CRITICAL_SECTION g_cs; // 共享资源 char g_cArray[10]; UINT ThreadProc10(LPVOID pParam) { 　// 进入临界区 　EnterCriticalSection(&g_cs); 　// 对共享资源进行写入操作 　for (int i = 0; i < 10; i++) 　{ 　　g_cArray[i] = ’a’; 　　Sleep(1); 　} 　// 离开临界区 　LeaveCriticalSection(&g_cs); 　return 0; } UINT ThreadProc11(LPVOID pParam) { 　// 进入临界区 　EnterCriticalSection(&g_cs); 　// 对共享资源进行写入操作 　for (int i = 0; i < 10; i++) 　{ 　　g_cArray[10 - i - 1] = ’b’; 　　Sleep(1); 　} 　// 离开临界区 　LeaveCriticalSection(&g_cs); 　return 0; } …… void CSample08View::OnCriticalSection() { 　// 初始化临界区 　InitializeCriticalSection(&g_cs); 　// 启动线程 　AfxBeginThread(ThreadProc10, NULL); 　AfxBeginThread(ThreadProc11, NULL); 　// 等待计算完毕 　Sleep(300); 　// 报告计算结果 　CString sResult = CString(g_cArray); 　AfxMessageBox(sResult); }

　　在使用临界区时，一般不允许其运行时间过长，只要进入临界区的线程还没有离开，其他所有试图进入此临界区的线程都会被挂起而进入到等待状态，并会在一定程度上影响。程序的运行性能。尤其需要注意的是不要将等待用户输入或是其他一些外界干预的操作包含到临界区。如果进入了临界区却一直没有释放，同样也会引起其他线程的长时间等待。换句话说，在执行了EnterCriticalSection（）语句进入临界区后无论发生什么，必须确保与之匹配的LeaveCriticalSection（）都能够被执行到。可以通过添加结构化异常处理代码来确保LeaveCriticalSection （）语句的执行。虽然临界区同步速度很快，但却只能用来同步本进程内的线程，而不可用来同步多个进程中的线程。

　　MFC为临界区提供有一个CCriticalSection类，使用该类进行线程同步处理是非常简单的，只需在线程函数中用CCriticalSection类成员函数 Lock（）和UnLock（）标定出被保护代码片段即可。对于上述代码，可通过CCriticalSection类将其改写如下：

// MFC临界区类对象 CCriticalSection g_clsCriticalSection; // 共享资源 char g_cArray[10]; UINT ThreadProc20(LPVOID pParam) { 　// 进入临界区 　g_clsCriticalSection.Lock(); 　// 对共享资源进行写入操作 　for (int i = 0; i < 10; i++) 　{ 　　g_cArray[i] = ’a’; 　　Sleep(1); 　} 　// 离开临界区 　g_clsCriticalSection.Unlock(); 　return 0; } UINT ThreadProc21(LPVOID pParam) { 　// 进入临界区 　g_clsCriticalSection.Lock(); 　// 对共享资源进行写入操作 　for (int i = 0; i < 10; i++) 　{ 　　g_cArray[10 - i - 1] = ’b’; 　　Sleep(1); 　} 　// 离开临界区 　g_clsCriticalSection.Unlock(); 　return 0; } …… void CSample08View::OnCriticalSectionMfc() { 　// 启动线程 　AfxBeginThread(ThreadProc20, NULL); 　AfxBeginThread(ThreadProc21, NULL); 　// 等待计算完毕 　Sleep(300); 　// 报告计算结果 　CString sResult = CString(g_cArray); 　AfxMessageBox(sResult); }

管理事件内核对象

　　在前面讲述线程通信时曾使用过事件内核对象来进行线程间的通信，除此之外，事件内核对象也可以通过通知操作的方式来保持线程的同步。对于前面那段使用临界区保持线程同步的代码可用事件对象的线程同步方法改写如下：

// 事件句柄 HANDLE hEvent = NULL; // 共享资源 char g_cArray[10]; …… UINT ThreadProc12(LPVOID pParam) { 　// 等待事件置位 　WaitForSingleObject(hEvent, INFINITE); 　// 对共享资源进行写入操作 　for (int i = 0; i < 10; i++) 　{ 　　g_cArray[i] = ’a’; 　　Sleep(1); 　} 　// 处理完成后即将事件对象置位 　SetEvent(hEvent); 　return 0; } UINT ThreadProc13(LPVOID pParam) { 　// 等待事件置位 　WaitForSingleObject(hEvent, INFINITE); 　// 对共享资源进行写入操作 　for (int i = 0; i < 10; i++) 　{ 　　g_cArray[10 - i - 1] = ’b’; 　　Sleep(1); 　} 　// 处理完成后即将事件对象置位 　SetEvent(hEvent); 　return 0; } …… void CSample08View::OnEvent() { 　// 创建事件 　hEvent = CreateEvent(NULL, FALSE, FALSE, NULL); 　// 事件置位 　SetEvent(hEvent); 　// 启动线程 　AfxBeginThread(ThreadProc12, NULL); 　AfxBeginThread(ThreadProc13, NULL); 　// 等待计算完毕 　Sleep(300); 　// 报告计算结果 　CString sResult = CString(g_cArray); 　AfxMessageBox(sResult); }

　　在创建线程前，首先创建一个可以自动复位的事件内核对象hEvent，而线程函数则通过WaitForSingleObject（）等待函数无限等待 hEvent的置位，只有在事件置位时WaitForSingleObject（）才会返回，被保护的代码将得以执行。对于以自动复位方式创建的事件对象，在其置位后一被WaitForSingleObject（）等待到就会立即复位，也就是说在执行ThreadProc12（）中的受保护代码时，事件对象已经是复位状态的，这时即使有ThreadProc13（）对CPU的抢占，也会由于WaitForSingleObject（）没有hEvent的置位而不能继续执行，也就没有可能破坏受保护的共享资源。在ThreadProc12（）中的处理完成后可以通过SetEvent（）对hEvent的置位而允许ThreadProc13（）对共享资源g_cArray的处理。这里SetEvent（）所起的作用可以看作是对某项特定任务完成的通知。

　　使用临界区只能同步同一进程中的线程，而使用事件内核对象则可以对进程外的线程进行同步，其前提是得到对此事件对象的访问权。可以通过OpenEvent（）函数获取得到，其函数原型为：

HANDLE OpenEvent( 　DWORD dwDesiredAccess, // 访问标志 　BOOL bInheritHandle, // 继承标志 　LPCTSTR lpName // 指向事件对象名的指针 );

　　如果事件对象已创建（在创建事件时需要指定事件名），函数将返回指定事件的句柄。对于那些在创建事件时没有指定事件名的事件内核对象，可以通过使用内核对象的继承性或是调用DuplicateHandle（）函数来调用CreateEvent（）以获得对指定事件对象的访问权。在获取到访问权后所进行的同步操作与在同一个进程中所进行的线程同步操作是一样的。

　　如果需要在一个线程中等待多个事件，则用 WaitForMultipleObjects（）来等待。WaitForMultipleObjects（）与WaitForSingleObject （）类似，同时监视位于句柄数组中的所有句柄。这些被监视对象的句柄享有平等的优先权，任何一个句柄都不可能比其他句柄具有更高的优先权。 WaitForMultipleObjects（）的函数原型为：

DWORD WaitForMultipleObjects( 　DWORD nCount, // 等待句柄数 　CONST HANDLE *lpHandles, // 句柄数组首地址 　BOOL fWaitAll, // 等待标志 　DWORD dwMilliseconds // 等待时间间隔 );

　　参数nCount指定了要等待的内核对象的数目，存放这些内核对象的数组由lpHandles来指向。fWaitAll对指定的这nCount个内核对象的两种等待方式进行了指定，为TRUE时当所有对象都被通知时函数才会返回，为FALSE则只要其中任何一个得到通知就可以返回。 dwMilliseconds在这里的作用与在WaitForSingleObject（）中的作用是完全一致的。如果等待超时，函数将返回 WAIT_TIMEOUT。如果返回WAIT_OBJECT_0到WAIT_OBJECT_0+nCount-1中的某个值，则说明所有指定对象的状态均为已通知状态（当fWaitAll为TRUE时）或是用以减去WAIT_OBJECT_0而得到发生通知的对象的索引（当fWaitAll为FALSE 时）。如果返回值在WAIT_ABANDONED_0与WAIT_ABANDONED_0+nCount-1之间，则表示所有指定对象的状态均为已通知，且其中至少有一个对象是被丢弃的互斥对象（当fWaitAll为TRUE时），或是用以减去WAIT_OBJECT_0表示一个等待正常结束的互斥对象的索引（当fWaitAll为FALSE时）。下面给出的代码主要展示了对WaitForMultipleObjects（）函数的使用。通过对两个事件内核对象的等待来控制线程任务的执行与中途退出：

// 存放事件句柄的数组 HANDLE hEvents[2]; UINT ThreadProc14(LPVOID pParam) { 　// 等待开启事件 　DWORD dwRet1 = WaitForMultipleObjects(2, hEvents, FALSE, INFINITE); 　// 如果开启事件到达则线程开始执行任务 　if (dwRet1 == WAIT_OBJECT_0) 　{ 　　AfxMessageBox("线程开始工作!"); 　　while (true) 　　{ 　　　for (int i = 0; i < 10000; i++); 　　　// 在任务处理过程中等待结束事件 　　　DWORD dwRet2 = WaitForMultipleObjects(2, hEvents, FALSE, 0); 　　　// 如果结束事件置位则立即终止任务的执行 　　　if (dwRet2 == WAIT_OBJECT_0 + 1) 　　　　break; 　　} 　} 　AfxMessageBox("线程退出!"); 　return 0; } …… void CSample08View::OnStartEvent() { 　// 创建线程 　for (int i = 0; i < 2; i++) 　　hEvents[i] = CreateEvent(NULL, FALSE, FALSE, NULL); 　　// 开启线程 　　AfxBeginThread(ThreadProc14, NULL); 　　// 设置事件0(开启事件) 　　SetEvent(hEvents[0]); } void CSample08View::OnEndevent() { 　// 设置事件1(结束事件) 　SetEvent(hEvents[1]); }

　　MFC为事件相关处理也提供了一个CEvent类，共包含有除构造函数外的4个成员函数PulseEvent（）、ResetEvent（）、 SetEvent（）和UnLock（）。在功能上分别相当与Win32 API的PulseEvent（）、ResetEvent（）、SetEvent（）和CloseHandle（）等函数。而构造函数则履行了原 CreateEvent（）函数创建事件对象的职责，其函数原型为：

CEvent(BOOL bInitiallyOwn = FALSE, BOOL bManualReset = FALSE, LPCTSTR lpszName = NULL, LPSECURITY_ATTRIBUTES lpsaAttribute = NULL );

　　按照此缺省设置将创建一个自动复位、初始状态为复位状态的没有名字的事件对象。封装后的CEvent类使用起来更加方便，图2即展示了CEvent类对A、B两线程的同步过程：


图2 CEvent类对线程的同步过程示意

　　B线程在执行到CEvent类成员函数Lock（）时将会发生阻塞，而A线程此时则可以在没有B线程干扰的情况下对共享资源进行处理，并在处理完成后通过成员函数SetEvent（）向B发出事件，使其被释放，得以对A先前已处理完毕的共享资源进行操作。可见，使用CEvent类对线程的同步方法与通过 API函数进行线程同步的处理方法是基本一致的。前面的API处理代码可用CEvent类将其改写为：

// MFC事件类对象 CEvent g_clsEvent; UINT ThreadProc22(LPVOID pParam) { 　// 对共享资源进行写入操作 　for (int i = 0; i < 10; i++) 　{ 　　g_cArray[i] = ’a’; 　　Sleep(1); 　} 　// 事件置位 　g_clsEvent.SetEvent(); 　return 0; } UINT ThreadProc23(LPVOID pParam) { 　// 等待事件 　g_clsEvent.Lock(); 　// 对共享资源进行写入操作 　for (int i = 0; i < 10; i++) 　{ 　　g_cArray[10 - i - 1] = ’b’; 　　Sleep(1); 　} 　return 0; } …… void CSample08View::OnEventMfc() { 　// 启动线程 　AfxBeginThread(ThreadProc22, NULL); 　AfxBeginThread(ThreadProc23, NULL); 　// 等待计算完毕 　Sleep(300); 　// 报告计算结果 　CString sResult = CString(g_cArray); 　AfxMessageBox(sResult); }

信号量内核对象

　　信号量（Semaphore）内核对象对线程的同步方式与前面几种方法不同，它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。在用 CreateSemaphore（）创建信号量时即要同时指出允许的最大资源计数和当前可用资源计数。一般是将当前可用资源计数设置为最大资源计数，每增加一个线程对共享资源的访问，当前可用资源计数就会减1，只要当前可用资源计数是大于0的，就可以发出信号量信号。但是当前可用计数减小到0时则说明当前占用资源的线程数已经达到了所允许的最大数目，不能在允许其他线程的进入，此时的信号量信号将无法发出。线程在处理完共享资源后，应在离开的同时通过 ReleaseSemaphore（）函数将当前可用资源计数加1。在任何时候当前可用资源计数决不可能大于最大资源计数。


图3 使用信号量对象控制资源

　　下面结合图例3来演示信号量对象对资源的控制。在图3中，以箭头和白色箭头表示共享资源所允许的最大资源计数和当前可用资源计数。初始如图（a）所示，最大资源计数和当前可用资源计数均为4，此后每增加一个对资源进行访问的线程（用黑色箭头表示）当前资源计数就会相应减1，图（b）即表示的在3个线程对共享资源进行访问时的状态。当进入线程数达到4个时，将如图（c）所示，此时已达到最大资源计数，而当前可用资源计数也已减到0，其他线程无法对共享资源进行访问。在当前占有资源的线程处理完毕而退出后，将会释放出空间，图（d）已有两个线程退出对资源的占有，当前可用计数为2，可以再允许2个线程进入到对资源的处理。可以看出，信号量是通过计数来对线程访问资源进行控制的，而实际上信号量确实也被称作Dijkstra计数器。

　　使用信号量内核对象进行线程同步主要会用到CreateSemaphore（）、OpenSemaphore（）、ReleaseSemaphore（）、 WaitForSingleObject（）和WaitForMultipleObjects（）等函数。其中，CreateSemaphore（）用来创建一个信号量内核对象，其函数原型为：

互斥内核对象

　　互斥（Mutex）是一种用途非常广泛的内核对象。能够保证多个线程对同一共享资源的互斥访问。同临界区有些类似，只有拥有互斥对象的线程才具有访问资源的权限，由于互斥对象只有一个，因此就决定了任何情况下此共享资源都不会同时被多个线程所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交出，以便其他线程在获得后得以访问资源。与其他几种内核对象不同，互斥对象在操作系统中拥有特殊代码，并由操作系统来管理，操作系统甚至还允许其进行一些其他内核对象所不能进行的非常规操作。为便于理解，可参照图6给出的互斥内核对象的工作模型：


图6 使用互斥内核对象对共享资源的保护

　　图（a）中的箭头为要访问资源（矩形框）的线程，但只有第二个线程拥有互斥对象（黑点）并得以进入到共享资源，而其他线程则会被排斥在外（如图（b）所示）。当此线程处理完共享资源并准备离开此区域时将把其所拥有的互斥对象交出（如图（c）所示），其他任何一个试图访问此资源的线程都有机会得到此互斥对象。

　　以互斥内核对象来保持线程同步可能用到的函数主要有CreateMutex（）、OpenMutex（）、 ReleaseMutex（）、WaitForSingleObject（）和WaitForMultipleObjects（）等。在使用互斥对象前，首先要通过CreateMutex（）或OpenMutex（）创建或打开一个互斥对象。CreateMutex（）函数原型为：

10、美国有多少辆加油站（汽车）？
　　11、有7克、2克砝码各一个，天平一只，如何只用这些物品三次将140克的盐 分成50、90克各一份？
　　12、有一辆火车以每小时15公里的速度离开洛杉矶直奔纽约，另一辆火车以第小时20公里的速度从纽约开往洛杉矶。如果有一只鸟，以外30公里每小时的速度和 两辆火车现时启动，从洛杉矶出发，碰到另辆车后返回，依次在两辆火车来回的飞行，直道两面辆火车相遇，请问，这只小鸟飞行了多长距离？
　　13、你有两个罐子，50个红色弹球，50个蓝色弹球，随机选出一个罐子，随机 选取出一个弹球放入罐子，怎么给红色弹球最大的选中机会？在你的计划中，得到 红球的准确几率是多少？
　　14、想象你在镜子前，请问，为什么镜子中的影像可以颠倒左右，却不能颠倒 上下？
　　15、你有四人装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被 污染的重量+1.只称量一次，如何判断哪个罐子的药被污染了？
　　16、如果你有无穷多的水，一个3夸脱的和一个5夸脱的提桶，你如何准确称出 4夸脱的水？
　　17、你有一桶果冻，其中有黄色，绿色，红色三种，，闭上眼睛选出同样颜色 的两个，抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻？
　　18、将汽车钥匙插入车门，向哪个方向旋转就可以打开车锁？
　　19、如果要你能去掉50个州的任何一个，那你去掉哪一个，为什么？
　　20、对一批编号为1~100 全部开关朝上开的灯进行以下操作
凡是1 的倍数反方向拨一次开关2 的倍数反方向又拨一次开关3 的倍数反方向 又拨一次开关。
　　问最后为关熄状态的灯的编号。
　　21、假设一张圆盘像唱机上的唱盘那样转动。这张盘一半是黑色，一半是白色 。假设你有数量不限的一些颜色传感器。要想确定圆盘转动的方向，你需要在它周围摆多少个颜色传感器？它们应该被摆放在什么位置？
　　22、假设时钟到了12点。注意时针和分针重叠在一起。在一天之中，时针和分针共重叠多少次？你知道它们重叠时的具体时间吗？
　　23、中间只隔一个数字的两个奇数被称为奇数对，比如17和19。证明奇数对之 间的数字总能被6整除（假设这两个奇数都大于6）。现在证明没有由三个奇数组成 的奇数对。
　　24、一个屋子有一个门（门是关闭的）和3盏电灯。屋外有3个开关，分别与这 3盏灯相连。你可以随意操纵这些开关，可一旦你将门打开，就不能变换开关了。确定每个开关具体管哪盏灯。
　　25、假设你有8个球，其中一个略微重一些，但是找出这个球的惟一方法是将两个球放在天平上对比。最少要称多少次才能找出这个较重的球？
　　26、下面玩一个拆字游戏，所有字母的顺序都被打乱。你要判断这个字是什么 。假设这个被拆开的字由5个字母组成：
　　　　1.共有多少种可能的组合方式？
　　　　2.如果我们知道是哪5个字母，那会怎么样？
　　　　3.找出一种解决这个问题的方法。
　　27、有4个女人要过一座桥。她们都站在桥的某一边，要让她们在17分钟内全 部通过这座桥。这时是晚上。她们只有一个手电筒。最多只能让两个人同时过桥。不管是谁过桥，不管是一个人还是两个人，必须要带着手电筒。手电筒必须要传来传去，不能扔过去。每个女人过桥的速度不同，两个人的速度必须以较慢的那个人 的速度过桥。
　　第一个女人：过桥需要1分钟；
　　第二个女人：过桥需要2分钟；
　　第三个女人：过桥需要5分钟；
　　第四个女人：过桥需要10分钟。
　　比如，如果第一个女人与第4个女人首先过桥，等她们过去时，已经过去了10 分钟。如果让第4个女人将手电筒送回去，那么等她到达桥的另一端时，总共用去了20分钟，行动也就失败了。怎样让这4个女人在17分钟内过桥？还有别的什么方 法？
　　28、如果你有两个桶，一个装的是红色的颜料，另一个装的是蓝色的颜料。你 从蓝色颜料桶里舀一杯，倒入红色颜料桶，再从红色颜料桶里舀一杯倒入蓝颜料桶。两个桶中红蓝颜料的比例哪个更高？通过算术的方式来证明这一点。
B：疯狂计算
　　29、已知两个1~30之间的数字，甲知道两数之和，乙知道两数之积。
　　甲问乙："你知道是哪两个数吗？"乙说："不知道"；
　　乙问甲："你知道是哪两个数吗？"甲说："也不知道"；
　　于是，乙说："那我知道了"；
　　随后甲也说："那我也知道了"；
　　这两个数是什么？
　　30、4，4，10，10，加减乘除，怎么出24点？
　　31、1000!有几位数，为什么？
　　32、F(n)=1 n>8 n<12
　　F(n)=2 n<2
　　F(n)=3 n=6
　　F(n)=4 n=other
　　使用+ - * /和sign(n)函数组合出F(n)函数
　　sign(n)=0 n=0
　　sign(n)=-1 n<0
　　sign(n)=1 n>0
　　33、编一个程序求质数的和例如F(7)=1+3+5+7+11+13+17=58
　　34、。。。
　　请仅用一支笔画四根直线将上图9 各点全部连接
　　35、三层四层二叉树有多少种
　　36、1--100000 数列按一定顺序排列，有一个数字排错，如何纠错？写出最好方法。两个数字呢？
　　参考答案
  1、day1 给1 段，
　　day2 让工人把1 段归还给2 段，
　　day3 给1 段，
　　day4 归还1 2 段，给4 段。
　　day5 依次类推……
　　2、面对这样的怪题，有些应聘者绞尽脑汁也无法分成；而有些应聘者却感到
此题实际很简单，把切成的8份蛋糕先拿出7份分给7人，剩下的1份连蛋糕盒一起分
给第8个人。
　　4、假如只有一个人戴黑帽子，那他看到所有人都戴白帽，在第一次关灯时就
应自打耳光，所以应该不止一个人戴黑帽子；如果有两顶黑帽子，第一次两人都只
看到对方头上的黑帽子，不敢确定自己的颜色，但到第二次关灯，这两人应该明白
，如果自己戴着白帽，那对方早在上一次就应打耳光了，因此自己戴的也是黑帽子
，于是也会有耳光声响起；可事实是第三次才响起了耳光声，说明全场不止两顶黑
帽，依此类推，应该是关了几次灯，有几顶黑帽。
　　5、比如你怎样快速估算支架和柱子的高度、球的半径，算出各部分的体积等
等。招聘官的说法："就CNTOWER这道题来说，它和一般的谜语或智力题还是有区别
的。我们称这类题为’快速估算题’，主要考的是快速估算的能力，这是开发软件
必备的能力之一。当然，题目只是手段，不是目的，最终得到一个结果固然是需要
的，但更重要的是对考生得出这个结果的过程也就是方法的考察。"Mr Miller为记
者举例说明了一种比较合理的答法，他首先在纸上画出了CN TOWER的草图，然后快
速估算支架和各柱的高度，以及球的半径，算出各部分体积，然后和各部分密度运
算，最后相加得出一个结果。
　　这一类的题目其实很多，如："估算一下密西西比河里的水的质量。""如果你
是田纳西州州长，请估算一下治理好康柏兰河的污染需要多长时间。"
　　"估算一下一个行进在小雨中的人5分钟内身上淋到的雨的质量。"
　　Mr Miller接着解释道："像这样的题目，包括一些推理题，考的都是人的
ProblemSolving(解决问题的能力)，不是哪道题你记住了答案就可以了的。"
　　对于公司招聘的宗旨，Mr Miller强调了四点，这些是有创造性的公司普遍注
重的员工素质，是想要到知名企业实现自己的事业梦想的人都要具备的素质和能力 。
　　要求一：RawSmart（纯粹智慧），与知识无关。
　　要求二：Long-termPotential(长远学习能力)。
　　要求三：TechnicSkills(技能)。
　　要求四：Professionalism(职业态度)。
　　6、她的回答是：选择前五层楼都不拿，观察各层钻石的大小，做到心中有数
。后五层楼再选择，选择大小接近前五层楼出现过最大钻石大小的钻石。她至今也
不知道这道题的准确答案，"也许就没有准确答案，就是考一下你的思路，"她如是
说。
　　7、分析：有个康奈尔的学生写文章说他当时在微软面试时就是碰到了这道题
，最短只能做出在19分钟内过桥。
　　8、两边一起烧。
　　9、答案之一：从麻省理工大学一位计算机系教授那里听来的答案，首先在同
等用材的情况下他的面积最大。第二因为如果是方的、长方的或椭圆的，那无聊之
徒拎起来它就可以直接扔进地下道啦！但圆形的盖子嘛，就可以避免这种情况了
　　10、这个乍看让人有些摸不着头脑的问题时，你可能要从问这个国家有多少小
汽车入手。面试者也许会告诉你这个数字，但也有可能说："我不知道，你来告诉
我。"那么，你对自己说，美国的人口是2.75亿。你可以猜测，如果平均每个家庭
（包括单身）的规模是2.5人，你的计算机会告诉你，共有1.1亿个家庭。你回忆起
在什么地方听说过，平均每个家庭拥有1.8辆小汽车，那么美国大约会有1.98亿辆
小汽车。接着，只要你算出替1.98亿辆小汽车服务需要多少加油站，你就把问题解
决了。重要的不是加油站的数字，而是你得出这个数字的方法。
　　12、答案很容易计算的：
　　假设洛杉矶到纽约的距离为s
　　那小鸟飞行的距离就是(s/(15+20))*30。
　　13、无答案，看你有没有魄力坚持自己的意见。
　　14、因为人的两眼在水平方向上对称。
　　15、从第一盒中取出一颗，第二盒中取出2 颗，第三盒中取出三颗。
　　依次类推，称其总量。
　　16、比较复杂：
　　Ａ、先用3 夸脱的桶装满，倒入5 夸脱。以下简称3->5)
　　在5 夸脱桶中做好标记b1，简称b1)。
　　B、用3 继续装水倒满5 空3 将5 中水倒入3 直到b1 在3 中做标记b2
　　Ｃ、用5 继续装水倒满3 空5 将3 中水倒入5 直到b2
　　Ｄ、空3 将5 中水倒入3 标记为b3
　　Ｅ、装满5 空3 将5 中水倒入3 直到3 中水到b3
　　结束了，现在5 中水为标准的4 夸脱水。
　　20、素数是关，其余是开。
　　29、允许两数重复的情况下
　　答案为x=1，y=4；甲知道和A=x+y=5，乙知道积B=x*y=4
　　不允许两数重复的情况下有两种答案
　　答案1：为x=1，y=6；甲知道和A=x+y=7，乙知道积B=x*y=6
　　答案2：为x=1，y=8；甲知道和A=x+y=9，乙知道积B=x*y=8
　　解：
　　设这两个数为x，y.
　　甲知道两数之和 A=x+y；
　　乙知道两数之积 B=x*y；
　　该题分两种情况 ：
　　允许重复， 有(1 <= x <= y <= 30)；
　　不允许重复，有(1 <= x < y <= 30)；
　　当不允许重复，即(1 <= x < y <= 30)；
　　1)由题设条件：乙不知道答案
　　<=> B=x*y 解不唯一
　　=> B=x*y 为非质数
　　又∵ x ≠ y
　　∴ B ≠ k*k (其中k∈N)
　　结论(推论1)：
　　B=x*y 非质数且 B ≠ k*k (其中k∈N)
　　即：B ∈(6，8，10，12，14，15，18，20...)
　　证明过程略。
　　2)由题设条件：甲不知道答案
　　<=> A=x+y 解不唯一
　　=> A >= 5；
　　分两种情况：
　　A=5，A=6时x，y有双解
　　A>=7 时x，y有三重及三重以上解
　　假设 A=x+y=5
　　则有双解
　　x1=1，y1=4；
　　x2=2，y2=3
　　代入公式B=x*y：
　　B1=x1*y1=1*4=4；(不满足推论1，舍去)
　　B2=x2*y2=2*3=6；
　　得到唯一解x=2，y=3即甲知道答案。
　　与题设条件："甲不知道答案"相矛盾，
　　故假设不成立，A=x+y≠5
　　假设 A=x+y=6
　　则有双解。
　　x1=1，y1=5；
　　x2=2，y2=4
　　代入公式B=x*y：
　　B1=x1*y1=1*5=5；(不满足推论1，舍去)
　　B2=x2*y2=2*4=8；
　　得到唯一解x=2，y=4
　　即甲知道答案
　　与题设条件："甲不知道答案"相矛盾
　　故假设不成立，A=x+y≠6
　　当A>=7时
　　∵ x，y的解至少存在两种满足推论1的解
　　B1=x1*y1=2*(A-2)
　　B2=x2*y2=3*(A-3)
　　∴ 符合条件
　　结论(推论2)：A >= 7
　　3)由题设条件：乙说"那我知道了"
　　=>乙通过已知条件B=x*y及推论(1)(2)可以得出唯一解
　　即：
　　A=x+y， A >= 7
　　B=x*y， B ∈(6，8，10，12，14，15，16，18，20...)
　　1 <= x < y <= 30
　　x，y存在唯一解
　　当 B=6 时：有两组解
　　x1=1，y1=6
　　x2=2，y2=3 (∵ x2+y2=2+3=5 < 7∴不合题意，舍去)
　　得到唯一解 x=1，y=6
　　当 B=8 时：有两组解
　　x1=1，y1=8
　　x2=2，y2=4 (∵ x2+y2=2+4=6 < 7∴不合题意，舍去)
　　得到唯一解 x=1，y=8
　　当 B>8 时：容易证明均为多重解
　　结论：
　　当B=6时有唯一解 x=1，y=6当B=8时有唯一解 x=1，y=8
　　4)由题设条件：甲说"那我也知道了"
　　=>　甲通过已知条件A=x+y及推论(3)可以得出唯一解
　　综上所述，原题所求有两组解：
　　x1=1，y1=6
　　x2=1，y2=8
　　当x<=y时，有(1 <= x <= y <= 30)；
　　同理可得唯一解 x=1，y=4
　　31、 　　解：1000
　　Lg(1000!)=sum(Lg(n))
　　n=1
　　用3 段折线代替曲线可以得到
　　10(0+1)/2+90(1+2)/2+900(2+3)/2=2390
　　作为近似结果，好象1500~3000 都算对
　　32、F(n)=1 n>8 n<12
　　F(n)=2 n<2
　　F(n)=3 n=6
　　F(n)=4 n=other
　　使用+ - * /和sign(n)函数组合出F(n)函数
　　sign(n)=0 n=0
　　sign(n)=-1 n<0
　　：sign(n)=1 n>0
　　解:只要注意[sign(n-m)*sign(m-n)+1]在n=m 处取1 其他点取0 就可以了
　　34、米字形的画就行了

1 前言

了解你所使用的编程语言究竟是如何实现的，对于C++程序员可能特别有意义。首先，它可以去除我们对于所使用语言的神秘感，使我们不至于对于编译器干的活感到完全不可思议；尤其重要的是，它使我们在Debug和使用语言高级特性的时候，有更多的把握。当需要提高代码效率的时候，这些知识也能够很好地帮助我们。

本文着重回答这样一些问题：
 * 类如何布局？
 * 成员变量如何访问？
 * 成员函数如何访问？
 * 所谓的“调整块”（adjuster thunk）是怎么回事？
 * 使用如下机制时，开销如何：
 * 单继承、多重继承、虚继承
 * 虚函数调用
 * 强制转换到基类，或者强制转换到虚基类
 * 异常处理
首先，我们顺次考察C兼容的结构（struct）的布局，单继承，多重继承，以及虚继承；
接着，我们讲成员变量和成员函数的访问，当然，这里面包含虚函数的情况；
再接下来，我们考察构造函数，析构函数，以及特殊的赋值操作符成员函数是如何工作的，数组是如何动态构造和销毁的；
最后，简单地介绍对异常处理的支持。

对每个语言特性，我们将简要介绍该特性背后的动机，该特性自身的语意（当然，本文决不是“C++入门”，大家对此要有充分认识），以及该特性在微软的VC++中是如何实现的。这里要注意区分抽象的C++语言语意与其特定实现。微软之外的其他C++厂商可能提供一个完全不同的实现，我们偶尔也会将VC++的实现与其他实现进行比较。

2 类布局

本节讨论不同的继承方式造成的不同内存布局。

2.1 C结构（struct）

由于C++基于C，所以C++也“基本上”兼容C。特别地，C++规范在“结构”上使用了和C相同的，简单的内存布局原则：成员变量按其被声明的顺序排列，按具体实现所规定的对齐原则在内存地址上对齐。所有的C/C++厂商都保证他们的C/C++编译器对于有效的C结构采用完全相同的布局。这里，A是一个简单的C结构，其成员布局和对齐方式都一目了然。

struct A {
   char c;
   int i;
};

译者注：从上图可见，A在内存中占有8个字节，按照声明成员的顺序，前4个字节包含一个字符（实际占用1个字节，3个字节空着，补对齐），后4个字节包含一个整数。A的指针就指向字符开始字节处。

2.2 有C++特征的C结构

当然了，C++不是复杂的C，C++本质上是面向对象的语言：包含继承、封装，以及多态。原始的C结构经过改造，成了面向对象世界的基石——类。除了成员变量外，C++类还可以封装成员函数和其他东西。然而，有趣的是，除非为了实现虚函数和虚继承引入的隐藏成员变量外，C++类实例的大小完全取决于一个类及其基类的成员变量！成员函数基本上不影响类实例的大小。

这里提供的B是一个C结构，然而，该结构有一些C++特征：控制成员可见性的“public/protected/private”关键字、成员函数、静态成员，以及嵌套的类型声明。虽然看着琳琅满目，实际上只有成员变量才占用类实例的空间。要注意的是，C++标准委员会不限制由“public/protected/private”关键字分开的各段在实现时的先后顺序，因此，不同的编译器实现的内存布局可能并不相同。（在VC++中，成员变量总是按照声明时的顺序排列）。

struct B {
public:
   int bm1;
protected:
   int bm2;
private:
   int bm3;
   static int bsm;
   void bf();
   static void bsf();
   typedef void* bpv;
   struct N { };
};

译者注：B中，为何static int bsm不占用内存空间？因为它是静态成员，该数据存放在程序的数据段中，不在类实例中。

2.3 单继承

C++提供继承的目的是在不同的类型之间提取共性。比如，科学家对物种进行分类，从而有种、属、纲等说法。有了这种层次结构，我们才可能将某些具备特定性质的东西归入到最合适的分类层次上，如“怀孩子的是哺乳动物”。由于这些属性可以被子类继承，所以，我们只要知道“鲸鱼、人”是哺乳动物，就可以方便地指出“鲸鱼、人都可以怀孩子”。那些特例，如鸭嘴兽（生蛋的哺乳动物），则要求我们对缺省的属性或行为进行覆盖。
C++中的继承语法很简单，在子类后加上“:base”就可以了。下面的D继承自基类C。

struct C {
   int c1;
   void cf();
};

struct D : C {
   int d1;
   void df();
};

既然派生类要保留基类的所有属性和行为，自然地，每个派生类的实例都包含了一份完整的基类实例数据。在D中，并不是说基类C的数据一定要放在D的数据之前，只不过这样放的话，能够保证D中的C对象地址，恰好是D对象地址的第一个字节。这种安排之下，有了派生类D的指针，要获得基类C的指针，就不必要计算偏移量了。几乎所有知名的C++厂商都采用这种内存安排。在单继承类层次下，每一个新的派生类都简单地把自己的成员变量添加到基类的成员变量之后。看看上图，C对象指针和D对象指针指向同一地址。

2.4 多重继承

大多数情况下，其实单继承就足够了。但是，C++为了我们的方便，还提供了多重继承。

比如，我们有一个组织模型，其中有经理类（分任务），工人类（干活）。那么，对于一线经理类，即既要从上级经理那里领取任务干活，又要向下级工人分任务的角色来说，如何在类层次中表达呢？单继承在此就有点力不胜任。我们可以安排经理类先继承工人类，一线经理类再继承经理类，但这种层次结构错误地让经理类继承了工人类的属性和行为。反之亦然。当然，一线经理类也可以仅仅从一个类（经理类或工人类）继承，或者一个都不继承，重新声明一个或两个接口，但这样的实现弊处太多：多态不可能了；未能重用现有的接口；最严重的是，当接口变化时，必须多处维护。最合理的情况似乎是一线经理从两个地方继承属性和行为——经理类、工人类。

C++就允许用多重继承来解决这样的问题：

struct Manager ... { ... };
struct Worker ... { ... };
struct MiddleManager : Manager, Worker { ... };

这样的继承将造成怎样的类布局呢？下面我们还是用“字母类”来举例：

struct E {
   int e1;
   void ef();
};

struct F : C, E {
   int f1;
   void ff();
 
 
};
 
结构F从C和E多重继承得来。与单继承相同的是，F实例拷贝了每个基类的所有数据。与单继承不同的是，在多重继承下，内嵌的两个基类的对象指针不可能全都与派生类对象指针相同：
 
F f;
// (void*)&f == (void*)(C*)&f;
// (void*)&f <  (void*)(E*)&f;
译者注：上面那行说明C对象指针与F对象指针相同，下面那行说明E对象指针与F对象指针不同。

观察类布局，可以看到F中内嵌的E对象，其指针与F指针并不相同。正如后文讨论强制转化和成员函数时指出的，这个偏移量会造成少量的调用开销。

具体的编译器实现可以自由地选择内嵌基类和派生类的布局。VC++按照基类的声明顺序先排列基类实例数据，最后才排列派生类数据。当然，派生类数据本身也是按照声明顺序布局的（本规则并非一成不变，我们会看到，当一些基类有虚函数而另一些基类没有时，内存布局并非如此）。

2.5 虚继承

回到我们讨论的一线经理类例子。让我们考虑这种情况：如果经理类和工人类都继承自“雇员类”，将会发生什么？
 
struct Employee { ... };
struct Manager : Employee { ... };
struct Worker : Employee { ... };
struct MiddleManager : Manager, Worker { ... };
 
如果经理类和工人类都继承自雇员类，很自然地，它们每个类都会从雇员类获得一份数据拷贝。如果不作特殊处理，一线经理类的实例将含有两个雇员类实例，它们分别来自两个雇员基类。如果雇员类成员变量不多，问题不严重；如果成员变量众多，则那份多余的拷贝将造成实例生成时的严重开销。更糟的是，这两份不同的雇员实例可能分别被修改，造成数据的不一致。因此，我们需要让经理类和工人类进行特殊的声明，说明它们愿意共享一份雇员基类实例数据。

很不幸，在C++中，这种“共享继承”被称为“虚继承”，把问题搞得似乎很抽象。虚继承的语法很简单，在指定基类时加上virtual关键字即可。
 
struct Employee { ... };
struct Manager : virtual Employee { ... };
struct Worker : virtual Employee { ... };
struct MiddleManager : Manager, Worker { ... };
 
使用虚继承，比起单继承和多重继承有更大的实现开销、调用开销。回忆一下，在单继承和多重继承的情况下，内嵌的基类实例地址比起派生类实例地址来，要么地址相同（单继承，以及多重继承的最靠左基类），要么地址相差一个固定偏移量（多重继承的非最靠左基类）。然而，当虚继承时，一般说来，派生类地址和其虚基类地址之间的偏移量是不固定的，因为如果这个派生类又被进一步继承的话，最终派生类会把共享的虚基类实例数据放到一个与上一层派生类不同的偏移量处。请看下例：
 
struct G : virtual C {
   int g1;
   void gf();
};
 
译者注：GdGvbptrG（In G, the displacement of G’s virtual base pointer to G）意思是：在G中，G对象的指针与G的虚基类表指针之间的偏移量，在此可见为0，因为G对象内存布局第一项就是虚基类表指针； GdGvbptrC（In G, the displacement of G’s virtual base pointer to C）意思是：在G中，C对象的指针与G的虚基类表指针之间的偏移量，在此可见为4。

struct H : virtual C {
   int h1;
   void hf();
};
 
struct I : G, H {
   int i1;
   void _if();
};
 
暂时不追究vbptr成员变量从何而来。从上面这些图可以直观地看到，在G对象中，内嵌的C基类对象的数据紧跟在G的数据之后，在H对象中，内嵌的C基类对象的数据也紧跟在H的数据之后。但是，在I对象中，内存布局就并非如此了。VC++实现的内存布局中，G对象实例中G对象和C对象之间的偏移，不同于I对象实例中G对象和C对象之间的偏移。当使用指针访问虚基类成员变量时，由于指针可以是指向派生类实例的基类指针，所以，编译器不能根据声明的指针类型计算偏移，而必须找到另一种间接的方法，从派生类指针计算虚基类的位置。

在VC++中，对每个继承自虚基类的类实例，将增加一个隐藏的“虚基类表指针”（vbptr）成员变量，从而达到间接计算虚基类位置的目的。该变量指向一个全类共享的偏移量表，表中项目记录了对于该类而言，“虚基类表指针”与虚基类之间的偏移量。

其它的实现方式中，有一种是在派生类中使用指针成员变量。这些指针成员变量指向派生类的虚基类，每个虚基类一个指针。这种方式的优点是：获取虚基类地址时，所用代码比较少。然而，编译器优化代码时通常都可以采取措施避免重复计算虚基类地址。况且，这种实现方式还有一个大弊端：从多个虚基类派生时，类实例将占用更多的内存空间；获取虚基类的虚基类的地址时，需要多次使用指针，从而效率较低等等。

在VC++中，G拥有一个隐藏的“虚基类表指针”成员，指向一个虚基类表，该表的第二项是GdGvbptrC。（在G中，虚基类对象C的地址与G的“虚基类表指针”之间的偏移量（当对于所有的派生类来说偏移量不变时，省略“d”前的前缀））。比如，在32位平台上，GdGvptrC是8个字节。同样，在I实例中的G对象实例也有“虚基类表指针”，不过该指针指向一个适用于“G处于I之中”的虚基类表，表中一项为IdGvbptrC，值为20。

观察前面的G、H和I，我们可以得到如下关于VC++虚继承下内存布局的结论：
 首先排列非虚继承的基类实例；
 有虚基类时，为每个基类增加一个隐藏的vbptr，除非已经从非虚继承的类那里继承了一个vbptr；
 排列派生类的新数据成员；
 在实例最后，排列每个虚基类的一个实例。

该布局安排使得虚基类的位置随着派生类的不同而“浮动不定”，但是，非虚基类因此也就凑在一起，彼此的偏移量固定不变。

3 成员变量

介绍了类布局之后，我们接着考虑对不同的继承方式，访问成员变量的开销究竟如何。

没有继承。没有任何继承关系时，访问成员变量和C语言的情况完全一样：从指向对象的指针，考虑一定的偏移量即可。
 
C* pc;
pc->c1; // *(pc + dCc1);
译者注：pc是指向C的指针。
 访问C的成员变量c1，只需要在pc上加上固定的偏移量dCc1（在C中，C指针地址与其c1成员变量之间的偏移量值），再获取该指针的内容即可。

单继承。由于派生类实例与其基类实例之间的偏移量是常数0，所以，可以直接利用基类指针和基类成员之间的偏移量关系，如此计算得以简化。
 
D* pd;
pd->c1; // *(pd + dDC + dCc1); // *(pd + dDc1);
pd->d1; // *(pd + dDd1);
译者注：D从C单继承，pd为指向D的指针。
 当访问基类成员c1时，计算步骤本来应该为“pd+dDC+dCc1”，即为先计算D对象和C对象之间的偏移，再在此基础上加上C对象指针与成员变量c1之间的偏移量。然而，由于dDC恒定为0，所以直接计算C对象地址与c1之间的偏移就可以了。
 当访问派生类成员d1时，直接计算偏移量。

多重继承。虽然派生类与某个基类之间的偏移量可能不为0，然而，该偏移量总是一个常数。只要是个常数，访问成员变量，计算成员变量偏移时的计算就可以被简化。可见即使对于多重继承来说，访问成员变量开销仍然不大。
 
F* pf;
pf->c1; // *(pf + dFC + dCc1); // *(pf + dFc1);
pf->e1; // *(pf + dFE + dEe1); // *(pf + dFe1);
pf->f1; // *(pf + dFf1);
译者注：F继承自C和E，pf是指向F对象的指针。
 访问C类成员c1时，F对象与内嵌C对象的相对偏移为0，可以直接计算F和c1的偏移；
 访问E类成员e1时，F对象与内嵌E对象的相对偏移是一个常数，F和e1之间的偏移计算也可以被简化；
 访问F自己的成员f1时，直接计算偏移量。

虚继承。当类有虚基类时，访问非虚基类的成员仍然是计算固定偏移量的问题。然而，访问虚基类的成员变量，开销就增大了，因为必须经过如下步骤才能获得成员变量的地址：获取“虚基类表指针”；获取虚基类表中某一表项的内容；把内容中指出的偏移量加到“虚基类表指针”的地址上。然而，事情并非永远如此。正如下面访问I对象的c1成员那样，如果不是通过指针访问，而是直接通过对象实例，则派生类的布局可以在编译期间静态获得，偏移量也可以在编译时计算，因此也就不必要根据虚基类表的表项来间接计算了。

I* pi;
pi->c1; // *(pi + dIGvbptr + (*(pi+dIGvbptr))[1] + dCc1);
pi->g1; // *(pi + dIG + dGg1); // *(pi + dIg1);
pi->h1; // *(pi + dIH + dHh1); // *(pi + dIh1);
pi->i1; // *(pi + dIi1);
I i;
i.c1; // *(&i + IdIC + dCc1); // *(&i + IdIc1);
译者注：I继承自G和H，G和H的虚基类是C，pi是指向I对象的指针。
 访问虚基类C的成员c1时，dIGvbptr是“在I中，I对象指针与G的“虚基类表指针”之间的偏移”，*(pi + dIGvbptr)是虚基类表的开始地址，*(pi + dIGvbptr)[1]是虚基类表的第二项的内容（在I对象中，G对象的“虚基类表指针”与虚基类之间的偏移），dCc1是C对象指针与成员变量c1之间的偏移；
 访问非虚基类G的成员g1时，直接计算偏移量；
 访问非虚基类H的成员h1时，直接计算偏移量；
 访问自身成员i1时，直接使用偏移量；
 当声明了一个对象实例，用点“.”操作符访问虚基类成员c1时，由于编译时就完全知道对象的布局情况，所以可以直接计算偏移量。

当访问类继承层次中，多层虚基类的成员变量时，情况又如何呢？比如，访问虚基类的虚基类的成员变量时？一些实现方式为：保存一个指向直接虚基类的指针，然后就可以从直接虚基类找到它的虚基类，逐级上推。VC++优化了这个过程。VC++在虚基类表中增加了一些额外的项，这些项保存了从派生类到其各层虚基类的偏移量。

4 强制转化

如果没有虚基类的问题，将一个指针强制转化为另一个类型的指针代价并不高昂。如果在要求转化的两个指针之间有“基类-派生类”关系，编译器只需要简单地在两者之间加上或者减去一个偏移量即可（并且该量还往往为0）。

F* pf;
(C*)pf; // (C*)(pf ? pf + dFC : 0); // (C*)pf;
(E*)pf; // (E*)(pf ? pf + dFE : 0);

C和E是F的基类，将F的指针pf转化为C*或E*，只需要将pf加上一个相应的偏移量。转化为C类型指针C*时，不需要计算，因为F和C之间的偏移量为0。转化为E类型指针E*时，必须在指针上加一个非0的偏移常量dFE。C++规范要求NULL指针在强制转化后依然为NULL，因此在做强制转化需要的运算之前，VC++会检查指针是否为NULL。当然，这个检查只有当指针被显示或者隐式转化为相关类型指针时才进行；当在派生类对象中调用基类的方法，从而派生类指针被在后台转化为一个基类的Const “this” 指针时，这个检查就不需要进行了，因为在此时，该指针一定不为NULL。

正如你猜想的，当继承关系中存在虚基类时，强制转化的开销会比较大。具体说来，和访问虚基类成员变量的开销相当。

I* pi;
(G*)pi; // (G*)pi;
(H*)pi; // (H*)(pi ? pi + dIH : 0);
(C*)pi; // (C*)(pi ? (pi+dIGvbptr + (*(pi+dIGvbptr))[1]) : 0);
译者注：pi是指向I对象的指针，G,H是I的基类，C是G,H的虚基类。
 强制转化pi为G*时，由于G*和I*的地址相同，不需要计算；
 强制转化pi为H*时，只需要考虑一个常量偏移；
 强制转化pi为C*时，所作的计算和访问虚基类成员变量的开销相同，首先得到G的虚基类表指针，再从虚基类表的第二项中取出G到虚基类C的偏移量，最后根据pi、虚基类表偏移和虚基类C与虚基类表指针之间的偏移计算出C*。

一般说来，当从派生类中访问虚基类成员时，应该先强制转化派生类指针为虚基类指针，然后一直使用虚基类指针来访问虚基类成员变量。这样做，可以避免每次都要计算虚基类地址的开销。见下例。

/* before: */             ... pi->c1 ... pi->c1 ...
/* faster: */ C* pc = pi; ... pc->c1 ... pc->c1 ...
译者注：前者一直使用派生类指针pi，故每次访问c1都有计算虚基类地址的较大开销；后者先将pi转化为虚基类指针pc，故后续调用可以省去计算虚基类地址的开销。

5 成员函数

一个C++成员函数只是类范围内的又一个成员。X类每一个非静态的成员函数都会接受一个特殊的隐藏参数——this指针，类型为X* const。该指针在后台初始化为指向成员函数工作于其上的对象。同样，在成员函数体内，成员变量的访问是通过在后台计算与this指针的偏移来进行。
 
struct P {
   int p1;
   void pf(); // new
   virtual void pvf(); // new
 
 
};

P有一个非虚成员函数pf()，以及一个虚成员函数pvf()。很明显，虚成员函数造成对象实例占用更多内存空间，因为虚成员函数需要虚函数表指针。这一点以后还会谈到。这里要特别指出的是，声明非虚成员函数不会造成任何对象实例的内存开销。现在，考虑P::pf()的定义。
 
void P::pf() { // void P::pf([P *const this])
   ++p1;   // ++(this->p1);
}

这里P:pf()接受了一个隐藏的this指针参数，对于每个成员函数调用，编译器都会自动加上这个参数。同时，注意成员变量访问也许比看起来要代价高昂一些，因为成员变量访问通过this指针进行，在有的继承层次下，this指针需要调整，所以访问的开销可能会比较大。然而，从另一方面来说，编译器通常会把this指针缓存到寄存器中，所以，成员变量访问的代价不会比访问局部变量的效率更差。
译者注：访问局部变量，需要到SP寄存器中得到栈指针，再加上局部变量与栈顶的偏移。在没有虚基类的情况下，如果编译器把this指针缓存到了寄存器中，访问成员变量的过程将与访问局部变量的开销相似。

5.1 覆盖成员函数

和成员变量一样，成员函数也会被继承。与成员变量不同的是，通过在派生类中重新定义基类函数，一个派生类可以覆盖，或者说替换掉基类的函数定义。覆盖是静态（根据成员函数的静态类型在编译时决定）还是动态（通过对象指针在运行时动态决定），依赖于成员函数是否被声明为“虚函数”。

Q从P继承了成员变量和成员函数。Q声明了pf()，覆盖了P::pf()。Q还声明了pvf()，覆盖了P::pvf()虚函数。Q还声明了新的非虚成员函数qf()，以及新的虚成员函数qvf()。

struct Q : P {
   int q1;
   void pf();  // overrides P::pf
   void qf();  // new
   void pvf(); // overrides P::pvf
   virtual void qvf(); // new
};
 
对于非虚的成员函数来说，调用哪个成员函数是在编译时，根据“->”操作符左边指针表达式的类型静态决定的。特别地，即使ppq指向Q的实例，ppq->pf()仍然调用的是P::pf()，因为ppq被声明为“P*”。（注意，“->”操作符左边的指针类型决定隐藏的this参数的类型。）
 
P p; P* pp = &p; Q q; P* ppq = &q; Q* pq = &q;
pp->pf();  // pp->P::pf();  // P::pf(pp);
ppq->pf(); // ppq->P::pf(); // P::pf(ppq);
pq->pf();  // pq->Q::pf();  // Q::pf((P*)pq); （错误!）
pq->qf();  // pq->Q::qf();  // Q::qf(pq);
译者注：标记“错误”处，P*似应为Q*。因为pf非虚函数，而pq的类型为Q*，故应该调用到Q的pf函数上，从而该函数应该要求一个Q* const类型的this指针。

对于虚函数调用来说，调用哪个成员函数在运行时决定。不管“->”操作符左边的指针表达式的类型如何，调用的虚函数都是由指针实际指向的实例类型所决定。比如，尽管ppq的类型是P*，当ppq指向Q的实例时，调用的仍然是Q::pvf()。
 
pp->pvf();  // pp->P::pvf();  // P::pvf(pp);
ppq->pvf(); // ppq->Q::pvf(); // Q::pvf((Q*)ppq);
pq->pvf();  // pq->Q::pvf();  // Q::pvf((P*)pq); （错误！）
译者注：标记“错误”处，P*似应为Q*。因为pvf是虚函数，pq本来就是Q*，又指向Q的实例，从哪个方面来看都不应该是P*。

为了实现这种机制，引入了隐藏的vfptr成员变量。一个vfptr被加入到类中（如果类中没有的话），该vfptr指向类的虚函数表（vftable）。类中每个虚函数在该类的虚函数表中都占据一项。每项保存一个对于该类适用的虚函数的地址。因此，调用虚函数的过程如下：取得实例的vfptr；通过vfptr得到虚函数表的一项；通过虚函数表该项的函数地址间接调用虚函数。也就是说，在普通函数调用的参数传递、调用、返回指令开销外，虚函数调用还需要额外的开销。

回头再看看P和Q的内存布局，可以发现，VC++编译器把隐藏的vfptr成员变量放在P和Q实例的开始处。这就使虚函数的调用能够尽量快一些。实际上，VC++的实现方式是，保证任何有虚函数的类的第一项永远是vfptr。这就可能要求在实例布局时，在基类前插入新的vfptr，或者要求在多重继承时，虽然在右边，然而有vfptr的基类放到左边没有vfptr的基类的前面。

许多C++的实现会共享或者重用从基类继承来的vfptr。比如，Q并不会有一个额外的vfptr，指向一个专门存放新的虚函数qvf()的虚函数表。Qvf项只是简单地追加到P的虚函数表的末尾。如此一来，单继承的代价就不算高昂。一旦一个实例有vfptr了，它就不需要更多的vfptr。新的派生类可以引入更多的虚函数，这些新的虚函数只是简单地在已存在的，“每类一个”的虚函数表的末尾追加新项。

5.2 多重继承下的虚函数

如果从多个有虚函数的基类继承，一个实例就有可能包含多个vfptr。考虑如下的R和S类：
 
struct R {
   int r1;
   virtual void pvf(); // new
   virtual void rvf(); // new
};
 

struct S : P, R {
   int s1;
   void pvf(); // overrides P::pvf and R::pvf
   void rvf(); // overrides R::rvf
   void svf(); // new
};

这里R是另一个包含虚函数的类。因为S从P和R多重继承，S的实例内嵌P和R的实例，以及S自身的数据成员S::s1。注意，在多重继承下，靠右的基类R，其实例的地址和P与S不同。S::pvf覆盖了P::pvf()和R::pvf()，S::rvf()覆盖了R::rvf()。
 
S s; S* ps = &s;
((P*)ps)->pvf(); // (*(P*)ps)->P::vfptr[0])((S*)(P*)ps)
((R*)ps)->pvf(); // (*(R*)ps)->R::vfptr[0])((S*)(R*)ps)
ps->pvf();       // one of the above; calls S::pvf()
译者注：
 调用((P*)ps)->pvf()时，先到P的虚函数表中取出第一项，然后把ps转化为S*作为this指针传递进去；
 调用((R*)ps)->pvf()时，先到R的虚函数表中取出第一项，然后把ps转化为S*作为this指针传递进去；

因为S::pvf()覆盖了P::pvf()和R::pvf()，在S的虚函数表中，相应的项也应该被覆盖。然而，我们很快注意到，不光可以用P*，还可以用R*来调用pvf()。问题出现了：R的地址与P和S的地址不同。表达式(R*)ps与表达式(P*)ps指向类布局中不同的位置。因为函数S::pvf希望获得一个S*作为隐藏的this指针参数，虚函数必须把R*转化为S*。因此，在S对R虚函数表的拷贝中，pvf函数对应的项，指向的是一个“调整块”的地址，该调整块使用必要的计算，把R*转换为需要的S*。
译者注：这就是“thunk1: this-= sdPR; goto S::pvf”干的事。先根据P和R在S中的偏移，调整this为P*，也就是S*，然后跳转到相应的虚函数处执行。

在微软VC++实现中，对于有虚函数的多重继承，只有当派生类虚函数覆盖了多个基类的虚函数时，才使用调整块。

5.3 地址点与“逻辑this调整”

考虑下一个虚函数S::rvf()，该函数覆盖了R::rvf()。我们都知道S::rvf()必须有一个隐藏的S*类型的this参数。但是，因为也可以用R*来调用rvf()，也就是说，R的rvf虚函数槽可能以如下方式被用到：
 
((R*)ps)->rvf(); // (*((R*)ps)->R::vfptr[1])((R*)ps)
 
所以，大多数实现用另一个调整块将传递给rvf的R*转换为S*。还有一些实现在S的虚函数表末尾添加一个特别的虚函数项，该虚函数项提供方法，从而可以直接调用ps->rvf()，而不用先转换R*。MSC++的实现不是这样，MSC++有意将S::rvf编译为接受一个指向S中嵌套的R实例，而非指向S实例的指针（我们称这种行为是“给派生类的指针类型与该虚函数第一次被引入时接受的指针类型相同”）。所有这些在后台透明发生，对成员变量的存取，成员函数的this指针，都进行“逻辑this调整”。

当然，在debugger中，必须对这种this调整进行补偿。
 
ps->rvf(); // ((R*)ps)->rvf(); // S::rvf((R*)ps)
译者注：调用rvf虚函数时，直接给入R*作为this指针。

所以，当覆盖非最左边的基类的虚函数时，MSC++一般不创建调整块，也不增加额外的虚函数项。

5.4 调整块

正如已经描述的，有时需要调整块来调整this指针的值（this指针通常位于栈上返回地址之下，或者在寄存器中），在this指针上加或减去一个常量偏移，再调用虚函数。某些实现（尤其是基于cfront的）并不使用调整块机制。它们在每个虚函数表项中增加额外的偏移数据。每当虚函数被调用时，该偏移数据（通常为0）,被加到对象的地址上，然后对象的地址再作为this指针传入。

ps->rvf();
// struct { void (*pfn)(void*); size_t disp; };
// (*ps->vfptr[i].pfn)(ps + ps->vfptr[i].disp);
译者注：当调用rvf虚函数时，前一句表示虚函数表每一项是一个结构，结构中包含偏移量；后一句表示调用第i个虚函数时，this指针使用保存在虚函数表中第i项的偏移量来进行调整。

这种方法的缺点是虚函数表增大了，虚函数的调用也更加复杂。

现代基于PC的实现一般采用“调整—跳转”技术：
 
S::pvf-adjust: // MSC++
this -= SdPR;
goto S::pvf()
 
当然，下面的代码序列更好（然而，当前没有任何实现采用该方法）：
 
S::pvf-adjust:
this -= SdPR; // fall into S::pvf()
S::pvf() { ... }
译者注：IBM的C++编译器使用该方法。

5.5 虚继承下的虚函数

T虚继承P，覆盖P的虚成员函数，声明了新的虚函数。如果采用在基类虚函数表末尾添加新项的方式，则访问虚函数总要求访问虚基类。在VC++中，为了避免获取虚函数表时，转换到虚基类P的高昂代价，T中的新虚函数通过一个新的虚函数表获取，从而带来了一个新的虚函数表指针。该指针放在T实例的顶端。
 
struct T : virtual P {
   int t1;
   void pvf();         // overrides P::pvf
   virtual void tvf(); // new
};
 
void T::pvf() {
   ++p1; // ((P*)this)->p1++; // vbtable lookup!
   ++t1; // this->t1++;
}
 
如上所示，即使是在虚函数中，访问虚基类的成员变量也要通过获取虚基类表的偏移，实行计算来进行。这样做之所以必要，是因为虚函数可能被进一步继承的类所覆盖，而进一步继承的类的布局中，虚基类的位置变化了。下面就是这样的一个类：
 
struct U : T {
   int u1;
};

在此U增加了一个成员变量，从而改变了P的偏移。因为VC++实现中，T::pvf()接受的是嵌套在T中的P的指针，所以，需要提供一个调整块，把this指针调整到T::t1之后（该处即是P在T中的位置）。

5.6 特殊成员函数

本节讨论编译器合成到特殊成员函数中的隐藏代码。

5.6.1 构造函数和析构函数

正如我们所见，在构造和析构过程中，有时需要初始化一些隐藏的成员变量。最坏的情况下，一个构造函数要执行如下操作：

  * 如果是“最终派生类”，初始化vbptr成员变量，调用虚基类的构造函数；
  * 调用非虚基类的构造函数
  * 调用成员变量的构造函数
  * 初始化虚函数表成员变量
  * 执行构造函数体中，程序所定义的其他初始化代码

（注意：一个“最终派生类”的实例，一定不是嵌套在其他派生类实例中的基类实例）

所以，如果你有一个包含虚函数的很深的继承层次，即使该继承层次由单继承构成，对象的构造可能也需要很多针对虚函数表的初始化。
反之，析构函数必须按照与构造时严格相反的顺序来“肢解”一个对象。

 * 合成并初始化虚函数表成员变量
 * 执行析构函数体中，程序定义的其他析构代码
 * 调用成员变量的析构函数（按照相反的顺序）
 * 调用直接非虚基类的析构函数（按照相反的顺序）
 * 如果是“最终派生类”，调用虚基类的析构函数（按照相反顺序）

在VC++中，有虚基类的类的构造函数接受一个隐藏的“最终派生类标志”，标示虚基类是否需要初始化。对于析构函数，VC++采用“分层析构模型”，代码中加入一个隐藏的析构函数，该函数被用于析构包含虚基类的类（对于“最终派生类”实例而言）；代码中再加入另一个析构函数，析构不包含虚基类的类。前一个析构函数调用后一个。

5.6.2 虚析构函数与delete操作符

考虑结构V和W。
 
struct V {
   virtual ~V();
};
 
  struct W : V {
   operator delete();
};
 
析构函数可以为虚。一个类如果有虚析构函数的话，将会象有其他虚函数一样，拥有一个虚函数表指针，虚函数表中包含一项，其内容为指向对该类适用的虚析构函数的地址。这些机制和普通虚函数相同。虚析构函数的特别之处在于：当类实例被销毁时，虚析构函数被隐含地调用。调用地（delete发生的地方）虽然不知道销毁的动态类型，然而，要保证调用对该类型合适的delete操作符。例如，当pv指向W的实例时，当W::~W被调用之后，W实例将由W类的delete操作符来销毁。
 
V* pv = new V;
delete pv;   // pv->~V::V(); // use ::operator delete()
pv = new W;
delete pv;   // pv->~W::W(); // use W::operator delete()
pv = new W;
::delete pv; // pv->~W::W(); // use ::operator delete()
译者注：
 V没有定义delete操作符，delete时使用函数库的delete操作符；
 W定义了delete操作符，delete时使用自己的delete操作符；
 可以用全局范围标示符显示地调用函数库的delete操作符。

为了实现上述语意，VC++扩展了其“分层析构模型”，从而自动创建另一个隐藏的析构帮助函数——“deleting析构函数”，然后，用该函数的地址来替换虚函数表中“实际”虚析构函数的地址。析构帮助函数调用对该类合适的析构函数，然后为该类有选择性地调用合适的delete操作符。

6 数组

堆上分配空间的数组使虚析构函数进一步复杂化。问题变复杂的原因有两个：
1、 堆上分配空间的数组，由于数组可大可小，所以，数组大小值应该和数组一起保存。因此，堆上分配空间的数组会分配额外的空间来存储数组元素的个数；
2、 当数组被删除时，数组中每个元素都要被正确地释放，即使当数组大小不确定时也必须成功完成该操作。然而，派生类可能比基类占用更多的内存空间，从而使正确释放比较困难。
 
struct WW : W { int w1; };
pv = new W[m];
delete [] pv; // delete m W's  (sizeof(W)  == sizeof(V))
pv = new WW[n];
delete [] pv; // delete n WW's (sizeof(WW) >  sizeof(V))
译者注：WW从W继承，增加了一个成员变量，因此，WW占用的内存空间比W大。然而，不管指针pv指向W的数组还是WW的数组，delete[]都必须正确地释放WW或W对象占用的内存空间。

虽然从严格意义上来说，数组delete的多态行为C++标准并未定义，然而，微软有一些客户要求实现该行为。因此，在MSC++中，该行为是用另一个编译器生成的虚析构帮助函数来完成。该函数被称为“向量delete析构函数”（因其针对特定的类定制，比如WW，所以，它能够遍历数组的每个元素，调用对每个元素适用的析构函数）。

7 异常处理

简单说来，异常处理是C++标准委员会工作文件提供的一种机制，通过该机制，一个函数可以通知其调用者“异常”情况的发生，调用者则能据此选择合适的代码来处理异常。该机制在传统的“函数调用返回，检查错误状态代码”方法之外，给程序提供了另一种处理错误的手段。

因为C++是面向对象的语言，很自然地，C++中用对象来表达异常状态。并且，使用何种异常处理也是基于“抛出的”异常对象的静态或动态类型来决定的。不光如此，既然C++总是保证超出范围的对象能够被正确地销毁，异常实现也必须保证当控制从异常抛出点转换到异常“捕获”点时（栈展开），超出范围的对象能够被自动、正确地销毁。
考虑如下例子：
 
struct X { X(); }; // exception object class
struct Z { Z(); ~Z(); }; // class with a destructor
extern void recover(const X&);
void f(int), g(int);

int main() {
   try {
      f(0);
   } catch (const X& rx) {
      recover(rx);
   }
   return 0;
}

void f(int i) {
   Z z1;
   g(i);
   Z z2;
   g(i-1);
}

void g(int j) {
   if (j < 0)
      throw X();
}
译者注：X是异常类，Z是带析构函数的工作类，recover是错误处理函数，f和g一起产生异常条件，g实际抛出异常。

这段程序会抛出异常。在main中，加入了处理异常的try & catch框架，当调用f(0)时，f构造z1，调用g(0)后，再构造z2，再调用g(-1)，此时g发现参数为负，抛出X异常对象。我们希望在某个调用层次上，该异常能够得到处理。既然g和f都没有建立处理异常的框架，我们就只能希望main函数建立的异常处理框架能够处理X异常对象。实际上，确实如此。当控制被转移到main中异常捕获点时，从g中的异常抛出点到main中的异常捕获点之间，该范围内的对象都必须被销毁。在本例中，z2和z1应该被销毁。

谈到异常处理的具体实现方式，一般情况下，在抛出点和捕获点都使用“表”来表述能够捕获异常对象的类型；并且，实现要保证能够在特定的捕获点真正捕获特定的异常对象；一般地，还要运用抛出的对象来初始化捕获语句的“实参”。通过合理地选择编码方案，可以保证这些表格不会占用过多的内存空间。

异常处理的开销到底如何？让我们再考虑一下函数f。看起来f没有做异常处理。f确实没有包含try，catch，或者是throw关键字，因此，我们会猜异常处理应该对f没有什么影响。错！编译器必须保证一旦z1被构造，而后续调用的任何函数向f抛回了异常，异常又出了f的范围时，z1对象能被正确地销毁。同样，一旦z2被构造，编译器也必须保证后续抛出异常时，能够正确地销毁z2和z1。

要实现这些“展开”语意，编译器必须在后台提供一种机制，该机制在调用者函数中，针对调用的函数抛出的异常动态决定异常环境（处理点）。这可能包括在每个函数的准备工作和善后工作中增加额外的代码，在最糟糕的情况下，要针对每一套对象初始化的情况更新状态变量。例如，上述例子中，z1应被销毁的异常环境当然与z2和z1都应该被销毁的异常环境不同，因此，不管是在构造z1后，还是继而在构造z2后，VC++都要分别在状态变量中更新（存储）新的值。

所有这些表，函数调用的准备和善后工作，状态变量的更新，都会使异常处理功能造成可观的内存空间和运行速度开销。正如我们所见，即使在没有使用异常处理的函数中，该开销也会发生。

幸运的是，一些编译器可以提供编译选项，关闭异常处理机制。那些不需要异常处理机制的代码，就可以避免这些额外的开销了。

8 小结

好了，现在你可以写C++编译器了（开个玩笑）。
在本文中，我们讨论了许多重要的C++运行实现问题。我们发现，很多美妙的C++语言特性的开销很低，同时，其他一些美妙的特性（译者注：主要是和“虚”字相关的东西）将造成较大的开销。C++很多实现机制都是在后台默默地为你工作。一般说来，单独看一段代码时，很难衡量这段代码造成的运行时开销，必须把这段代码放到一个更大的环境中来考察，运行时开销问题才能得到比较明确的答案。

  

用MAP的特点是代码短，思路简单，很容易实现，但耗时大。下面给出trie版本的。

my code2:

上述代码中插入和查找可当模板来用了。。。

问题求解模式
    动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

   初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
     图1 动态规划决策过程示意图

    (1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
    (2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
    (3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。
    (4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

算法实现
    动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。使用动态规划求解问题，最重要的就是确定动态规划三要素：问题的阶段,每个阶段的状态以及从前一个阶段转化到后一个阶段之间的递推关系。递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。下面分别以求解最大化投资回报问题和最长公共子序列问题为例阐述用动态规划算法求解问题的一般思路。

1. 最大化投资回报问题：某人有一定的资金用来购买不同面额的债卷，不同面额债卷的年收益是不同的，求给定资金，年限以及债卷面额、收益的情况下怎样购买才能使此人获得最大投资回报。
    程序输入约定：第一行第一列表示资金（1000的倍数）总量，第二列表示投资年限；第二行表示债卷面额总数；从第三行开始每行表示一种债卷，占用两列，前一列表示债卷面额，后一列表示其年收益，如下输入实例，
10000 1
2
4000 400
3000 250
程序实现如下，注释几乎说明了一切，所以不再另外分析。
/// 此数组是算法的关键存储结构，用来存储不同阶段各种债卷
/// 组合下对应可获取的最大利息。
int saifa[80005];

/// 此函数用于计算当前债卷在不同购买额下的最优利息情况，
/// 注意此时的利息情况是基于上一次债卷的情况下计算得到的，
/// 也就是说当前利息最优是基于上一次利息最优的基础上计算出来的，
/// 这也正好体现了动态规划中“最优化原则”：不管前面的策略如何，
/// 此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。
/*
    动态规划的求解过程一般都可以用一个最优决策表来描述，
    对于本程序，以示例输入为例，对于第一年，其最优决策表如下：
    0 1 2 3   4   5   6   7   8   9   10(*1000)  -- (1)
    0 0 0 0   400 400 400 400 800 800 800        -- (2)
    0 0 0 250 400 400 500 650 800 900 900        -- (3)
    (1) -- 表示首先选利息为400的债卷在对应资金下的最优利息。
    (2) -- 表示可用来购买债卷的资金。
    (3) -- 表示在已有状态下再选择利息为300的债卷在对应资金下的最优利息。
    注意上面表格，在求购买利息为300的债卷获得的最优收益的时候，
    参考了以前的最优状态，以3行8列的650为例，7(*1000)可以
    在以前购买了0张4000的债卷的基础上再2张3000的，也可以在以前购
    买了1张4000的基础上再买1张3000，经比较取其收益大的，这就是典
    型的动态规划中的当前最优状态计算。
    本程序中把上面的最优决策二维表用一个一维数组表示，值得借鉴。
*/
void add(int a,int b)
{ cout << a << " " << b << endl; // for debug
 for(int i=0;i<=80000;i++)
 {
  if(i+a > 80000)
  {
   break;
  }

  if(saifa[i]+b > saifa[i+a]) // 累计同时购买多种债卷时的利息
  {
   saifa[i+a] = saifa[i] + b;
  }

  if(i<200) // for debug
   cout << i << "-" << saifa[i] << " ";
 }
 cout << endl; // for debug
}

int main(void)
{
 int n,d,money,year,pay,bond;
 int ii,i;

 scanf("%d",&n);
 for(ii=0;ii<n;ii++)
 {
  memset(saifa,0,sizeof(saifa));
  scanf("%d%d",&money,&year);
  scanf("%d",&d);

  for(i=0;i<d;i++)
  {
   scanf("%d%d",&pay,&bond);
   add(pay/1000,bond);
  }

  // 计算指定年限内最优组合的本金利息总额
  for(i=0;i<year;i++)
  { cout << saifa[money/1000] << " "; // for debug
   money += saifa[money/1000];
  }
  cout << endl; // for debug

  printf("%d\n",money);
 }

 return 0;
}
上述程序实现方法同样适合于背包问题，最优库存问题等，只是针对具体情况，最优决策表的表示和生成会有所不同。

2. 最长公共子串问题：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子串就是求给定两个序列的一个最长公共子序列。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。
问题分析：
    给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。如采用列举A的所有子序列，并一一检查其是否又是B的子序列，并随时记录所发现的子序列，最终求出最长公共子序列。这种方法因耗时太多而不可取。
    考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：
（1） 如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；
（2） 如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；
（3） 如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。
这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个 最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列 和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。
    为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法，具体说明如下。
定义c[i][j]为序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最长公共子序列的长度，计算c[i][j]可递归地表述如下：
（1）c[i][j] = 0                         如果i=0或j=0；
（2）c[i][j] = c[i-1][j-1]+1             如果i,j>0，且a[i-1] = b[j-1]；
（3）c[i][j] = max{c[i][j-1], c[i-1][j]} 如果i,j>0，且a[i-1] != b[j-1]。
按此算式可写出计算两个序列的最长公共子序列的长度函数。由于c[i][j]的产生仅依赖于c[i-1][j-1]、c[i-1][j]和c[i][j-1]，故可以从c[m][n]开始，跟踪c[i][j]的产生过程，逆向构造出最长公共子序列。细节见程序。

#include <stdio.h>
#include <string.h>

#define N 100

char a[N], b[N], str[N];
int c[N][N];

int lcs_len(char* a, char* b, int c[][N])
{
    int m = strlen(a), n = strlen(b), i, j;

    for( i=0; i<=m; i++ )    
        c[i][0]=0;
    for( i=0; i<=n; i++ )    
        c[0][i]=0;

    for( i=1; i<=m; i++ ) 
    {
        for( j=1; j<=n; j++ )
        {
            if (a[i-1]==b[j-1])
                c[i][j]=c[i-1][j-1]+1;
            else if (c[i-1][j]>=c[i][j-1])
                c[i][j]=c[i-1][j];
            else
                c[i][j]=c[i][j-1];
        }
    }

    return c[m][n];
}

char* build_lcs(char s[], char* a, char* b)
{
    int i = strlen(a), j = strlen(b);
    int k = lcs_len(a,b,c);
    s[k] = '\0';
    while( k>0 )
    {
        if (c[i][j]==c[i-1][j]) 
            i--;
        else if (c[i][j]==c[i][j-1]) 
            j--;
        else
        {
            s[--k]=a[i-1];
            i--; j--;
        }
    }

    return s;
}

void main()
{ 
    printf("Enter two string (length < %d) :\n",N);
    scanf("%s%s",a,b);
    printf("LCS=%s\n",build_lcs(str,a,b));
}

假如int a[3][4];

则 a[i][j] == *(a[i]+j) == *(*(a+i)+j)

数组名就是数组内存的首地址

1、 函数的指针

一个函数被编译和连接后，要占用一定的内存区，它的首地址就是该函数的指针，函数的指针也是该函数的入口地址。

假设p=max()函数。p是函数指针，且max有返回值，则下列

c=max(a,b);

c=(*p)(a,b)

c=p(a,b)

都是等价的，对p不能做增减运算

2、 内联函数

*不能有多分支语句和循环语句，否则作普通函数

*不能是递归子函数

*所含语句行数应该为1~5行

4、带缺省参数的函数

从友到左被定义，右边不能含有缺省参数

5、 void Sort(int *&val)   val是个int*型的引用型变量

6、Q: 带符号数赋予不带符号数的变量

   A: short x=-35;

      unsigned short y;

      y=x;

   x原=-35=1000 0000 0010 0011

   x补=    1111 1111 1101 1101

   将它看作不带符号的二进制数

所以 y=x补=1111 1111 1101 1101=65501

 Q:无符号数赋予有符号数

     unsigned short x=65530;

     short y;

     y=x;

 A: x=65530=1111 1111 1111 1010

      y补=x;

所以y原=1000 0000 0000 0110

所以y= -000 0000 0000 0110=-6

7、int a=b=6;是不允许的，但是int a,b=a=6;却是可以的。

8、++与+等的优先级

优先级     高——> 低

+,-,++,--     *,/,%        +,-        <<,>>

__同级_     __同级_   __同级_    __同级_

Q： -a++ 由于++,-同级，所欲按结合性从右向左，故等价于 –(a++)

-++a EQU -(++a)

但是 ++(-a)是个错误的表达式，因为-a不是变量，而是表达式，不能对表达式进行自增。(-a)++同理也是错误的。

a+++b 未定义。不该使用。

a+--b EQU a+(--b)

9、Q:指向不同类型指针

int *p;

float f;

p=&f; //ERROR,p指向的类型是int，类型不匹配

10、假设p=&a则

*p EQU *(&a)   EQU     *&a   EQU   a

&a EQU &(*a) EQU   &*p EQU p

11、       y=*p++ 等价于 y=*(p++) 注： y的值等于*p的值，p的新值等于(p原值+1) X 相应数据类型长度。

y=*++p 等价于 y=*(++p) 注： y的值为(p+1)X数据类型长度。

y=(*p)++   y值等于*p，*p的值为*p + 1

y=++(*p)   y的值等于(*p)+1 *p新值等于 (*p)+1
12、%取余运算。
(-3)%2   EQU  -(3%2)=-1
5%-1      EQU   5%3=2
19%10%5 EQU (19%10)%5=4

1、 如何使用无参构造函数初始化？

aClass obj();   //error，不能加括号

aClass obj;

2、声明为引用的数据成员和const数据成员必须采用成员初始化列表进行初始化。

3、类与const

①const成员函数定义：在该函数中不改变调用他的对象的值。

eg: void Func() const;

②const成员函数可重载，根据对象是否是const来决定调用。

③构造函数和析构函数不能声明为const

④const数据成员 必须在构造函数初始化列表中被初始化。

eg: class test

{

test(int i):data(i) {}

……

private:

    const int data;

}

注：const对象的“常量性质”在从构造函数完成对象初始化 到 对象析构函数被调用结束这个过程之间一直保持。

⑤static成员函数不能声明为const。const指示函数不能修改它操作的对象的内容，但static成员函数独立于类的任何对象。

⑥不一致使用const

void Func2(int a[])

{

……

}

void Func1(const int a[])

{

     Func2(a); //Error，不能将const修改为非const。Func2参数也该声明为const

……

} void Func2()vo

4、友元friend，原型在类定义内出现，但友元不是成员函数，private、protected等与友元无关，因此可以放在类的任何地方。

5、在派生类的构造函数的初始化列表中初始化成员、调用基类的构造函数，可以防止重复初始化。

6、若一个类中含virtual函数，则该类的析构函数应该为virtual

7、重载复数类的+运算符。

Complex operator + (const Complex& x,const Complex& y)

{

       return (a,b);   //此语句调用下面的构造函数

}

Complex::Complex(const Complex& x,const Comolex& y)

         :real(x.real+y.real),imag(x.img+y.img)

{

}

7、临时对象

class X

{……};

X x1(100);   //只有它不会产生临时对象，只有1个构造函数被调用

X x2=X(100);

X x3=100;

8、多重继承

继承关系如下图

Employee

Employer

Worker

Manager

Engineer

产生二义性：如

 Engineer   eng;

 eng.Worker::Sex=0;

 eng.Manager::Sex=1;

解决方法：使用虚基类

   class Worker:public virtual Employee

{

};

class Manager:public virtual Employer

{

};

类之间的关系如下图所示：

Employer

Worker

Manager

Engineer

不过这样还是存在问题的，这是c++自身所决定的。

      8位CPU 当然不会产生数据对齐问题，当CPU发展到16，32位时，因为CPU的一次内存访问就能取回4个byte（且用32位举例，这个数据理所当然的缓存在相应的32位寄存器中）——里面可能存储了4个1byte的数据，也可能存储了2个2byte的数据……，所以CPU在逻辑上将内存单元寻址地址边界设置为4的倍数（如：0，4，8，12……），这是数据对齐产生的必要条件之一；另一个原因是程序中使用的数据类型并非都是4的倍数，如：char（1byte），short（2byte），int（4byte）等等。让我们考虑一下一个2byte的的变量在内存单元中排布吧：如果这个变量地址为0或1或2，那么CPU一次内存访问就能够取得你的变量；但如果是3的话，很不幸，CPU还得访问一次内存以取得全部数据。

       2、举例说明

struct A {
    char m_ch;     //1 Byte
    char *m_pStr;  //4 Byte
};                 //sizeof(A)=8,按4对齐

struct B {
    char m_ch;     //1 Byte
    int m_count;   //4 Byte  
};                 //sizeof(A)=8,按4对齐

struct C {
    bool m_ok;     //1 Byte
    char m_name[6];//char 也是 1 Byte,6个char罢了
};

________________________________________结构体成员________________________________ 

struct X
{
    double m_width;      //8 Byte
    char   m_name[6];    //1 Byte per
};                       //sizeof(X)=16

struct Y {
    int m_no;            //4 Byte
    X   m_x;             //X按8对齐,故按8对齐,
};                       //sizeof(Y)=8x3=24，提示可将X m_x扩展成struct X

struct X2
{
    double m_width;      //8 Byte
    char   m_name[9];    //1 Byte per,前8字节+8字节中的一个字节
};                       //sizeof(X2)=8+8+8=24

struct X2
{
    double m_width;      //8 Byte      8x1
    char   m_name[9];    //占用8+8     8x2 和 8x3
};                      

struct Y2 {
    int m_no;             //4 Byte,占用另一个8字节 8x4
    X2   m_x;             
};                        //sizeof(Y2)=8+8+8+8=32

enum DataType {IntData,CharData,VcharData};
struct Item    
{
     char ItemNAme[30];  //按4对齐，故是32
     DataType ItemType;  //enum站4个字节
     char ItemDecr[50];  //按4对齐，所以是52
     int ItemLength;     //4字节
};

sizeof(Item) = 32+4+52+4=92

#pragma pack(2) //指定对齐方式是2
enum DataType {IntData,CharData,VcharData};

struct Item    
{
    char ItemNAme[30];  //30
    DataType ItemType;  //4
    char ItemDecr[50];  //50
    int ItemLength;     //4
};

sizeof(Item) = 30+4+50+4=88

评价一个算法的优劣,可通过在一个特定的存储访问序列（页面走向）上运行它，并计算缺页数量来实现。

1 先入先出法（FIFO）

最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。
这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。
FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。

2 最优置换算法（OPT）

最优置换（Optimal Replacement）是在理论上提出的一种算法。其实质是：当调入新的一页而必须预先置换某个老页时，所选择的老页应是将来不再被使用，或者是在最远的将来才被访问。采用这种页面置换算法，保证有最少的缺页率。
但是最优页面置换算法的实现是困难的，因为它需要人们预先就知道一个进程整个运行过程中页面走向的全部情况。不过，这个算法可用来衡量（如通过模拟实验分析或理论分析）其他算法的优劣。

用最佳页面置换法计算缺页次数

6 5 4 3 5 4 3 6 5 4 5 

－－－－－－－－－－－

6 6 6 3 3 3 3 6 6 6 6 

5 5 5 5 5 5 5 5 5 5 

4 4 4 4 4 4 4 4 4 


仅仅第四列3和第八列6处,缺页.

第四列处:

opt算法中，页面发生冲突时，被替换的页面是未来访问最靠后的页面。

例子中，第4列处，6的再次访问最靠后，因而6被替换。

之后，第8列处，3被替换是因为3，4，5中未来被访问的页是4，5。

所以，3被替换。

3 最久未使用算法（LRU）

FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU）。
LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。
LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：
（1）计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。这样做，不仅要查页表，而且当页表改变时（因CPU调度）要维护这个页表中的时间，还要考虑到时钟值溢出的问题。
（2）栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。
因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。
一种LRU近似算法是最近未使用算法（Not Recently Used，NUR）。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在最近一段时间里它未被访问过。

4 第二次机会算法（SCR）

第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，检查它的访问位。如果是0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。
第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。

页面置换算法还有很多变种，如考虑到被置换页是否修改过、按FIFO算法选中的页正在使用等情况，都需要硬件、软件协同实现。

  （1）加减法。

     a = a + b;

     b = a - b;

     a = a - b;

  该方法可以交换整型和浮点型数值的变量，但在处理浮点型的时候有可能出现精度的损失，例如对数据：

     a = 3.123456

     b = 1234567.000000

  交换后各变量值变为：

     a = 1234567.000000

     b = 3.125000

  很明显，原来a的值在交换给b的过程中发生了精度损失。

  （2）乘除法。

     a = a * b;

     b = a / b;

     a = a / b;

  乘除法更像是加减法向乘除运算的映射，它与加减法类似：可以处理整型和浮点型变量，但在处理浮点型变量时也存在精度损失问题。而且乘除法比加减法要多一条约束：b必不为0。

  可能经验上的某种直觉告诉我们：加减法和乘除法可能会溢出，而且乘除的溢出会特别严重。其实不然，采用这两种方法都不会溢出。以加减法为例，第一步的加运算可能会造成溢出，但它所造成的溢出会在后边的减运算中被溢出回来。

  （3）异或法。

     a ^= b;

     b ^= a;

     a ^= b;

  异或法可以完成对整型变量的交换，对于浮点型变量它无法完成交换。

  第二类方法更像是玩了一个文字游戏，此种方法采用了在代码中嵌入汇编代码的方法避免了临时变量的引入，但究其本质还是会使用额外的存储空间。此种方法可以有很多种，下边列出几种：

  （1）使用xchg指令，这也是比较直观、容易想到的方法，因为xchg指令的功能就是交换源操作数和目的操作数的值，这里要使用额外寄存器来暂存变量。内嵌汇编代码如下：

     _asm

     {

         mov eax,a

         xchg b,eax

         mov a,eax

     }

  （2）使用额外的栈。这里使用反向的出栈顺序来完成交换。内嵌代码有如下两种形式：

     _asm

     {

         push a

         push b

         pop a

         pop b

     }

  另一种形式：

     _asm push a

     a = b;

     _asm pop a

  （3）使用mov指令。这种方法使用额外寄存器来暂存一个变量的值。

     _asm mov eax,a

     a = b;

     _asm mov b,eax

  其实第二类方法并不合格，它虽然没有显式的使用临时变量，但还是会用到额外的存贮空间。不过也不能说没有必要掌握，从实用的角度看还是很“有用”的。不是有公司出过这样的面试题吗？“不使用加减法和异或法完成不使用中间变量交换两个数值型变量的值”。此时或许只好使用这种方法了。

8 sum+=i;
9 }
10 return sum;
11 }
12
13
14 main()
15 {
16 int i;
17 long result = 0;
18 for(i=1; i<=100; i++)
19 {
20 result += i;
21 }
22
23 printf("result[1-100] = %d \n", result );
24 printf("result[1-250] = %d \n", func(250) );
25 }
编译生成执行文件：（Linux下）
hchen/test> cc -g tst.c -o tst
使用GDB调试：
hchen/test> gdb tst <---------- 启动GDB
GNU gdb 5.1.1
Copyright 2002 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB. Type "show warranty" for details.
This GDB was configured as "i386-suse-linux"...
(gdb) l <-------------------- l命令相当于list，从第一行开始例出原码。
1 #include
2
3 int func(int n)
4 {
5 int sum=0,i;
6 for(i=0; i 7 {
8 sum+=i;
9 }
10 return sum;
(gdb) <-------------------- 直接回车表示，重复上一次命令
11 }

12
13
14 main()
15 {
16 int i;
17 long result = 0;
18 for(i=1; i<=100; i++)
19 {
20 result += i;
(gdb) break 16 <-------------------- 设置断点，在源程序第16行处。
Breakpoint 1 at 0x8048496: file tst.c, line 16.
(gdb) break func <-------------------- 设置断点，在函数func()入口处。
Breakpoint 2 at 0x8048456: file tst.c, line 5.
(gdb) info break <-------------------- 查看断点信息。
Num Type Disp Enb Address What
1 breakpoint keep y 0x08048496 in main at tst.c:16
2 breakpoint keep y 0x08048456 in func at tst.c:5
(gdb) r <--------------------- 运行程序，run命令简写
Starting program: /home/hchen/test/tst
Breakpoint 1, main () at tst.c:17 <---------- 在断点处停住。
17 long result = 0;
(gdb) n <--------------------- 单条语句执行，next命令简写。
18 for(i=1; i<=100; i++)
(gdb) n
20 result += i;
(gdb) n
18 for(i=1; i<=100; i++)
(gdb) n
20 result += i;
(gdb) c <--------------------- 继续运行程序，continue命令简写。
Continuing.
result[1-100] = 5050 <----------程序输出。
Breakpoint 2, func (n=250) at tst.c:5
5 int sum=0,i;
(gdb) n
6 for(i=1; i<=n; i++)
(gdb) p i <--------------------- 打印变量i的值，print命令简写。
$1 = 134513808
(gdb) n
8 sum+=i;
(gdb) n
6 for(i=1; i<=n; i++)

(gdb) p sum
$2 = 1
(gdb) n
8 sum+=i;
(gdb) p i
$3 = 2
(gdb) n
6 for(i=1; i<=n; i++)
(gdb) p sum
$4 = 3
(gdb) bt <--------------------- 查看函数堆栈。
#0 func (n=250) at tst.c:5
#1 0x080484e4 in main () at tst.c:24
#2 0x400409ed in __libc_start_main () from /lib/libc.so.6
(gdb) finish <--------------------- 退出函数。
Run till exit from #0 func (n=250) at tst.c:5
0x080484e4 in main () at tst.c:24
24 printf("result[1-250] = %d \n", func(250) );
Value returned is $6 = 31375
(gdb) c <--------------------- 继续运行。
Continuing.
result[1-250] = 31375 <----------程序输出。
Program exited with code 027. <--------程序退出，调试结束。
(gdb) q <--------------------- 退出gdb。
hchen/test>
好了，有了以上的感性认识，还是让我们来系统地认识一下gdb吧。
使用GDB
————
一般来说GDB主要调试的是C/C++的程序。要调试C/C++的程序，首先在编译时，我们必
须要把调试信息加到可执行文件中。使用编译器（cc/gcc/g++）的 -g 参数可以做到这一点。
如：
> cc -g hello.c -o hello
> g++ -g hello.cpp -o hello
如果没有-g，你将看不见程序的函数名、变量名，所代替的全是运行时的内存地址。当你用
-g把调试信息加入之后，并成功编译目标代码以后，让我们来看看如何用gdb来调试他。
启动GDB的方法有以下几种：

1、gdb
program也就是你的执行文件，一般在当然目录下。
2、gdb core
用gdb同时调试一个运行程序和core文件，core是程序非法执行后core dump后产生的文件。
3、gdb
如果你的程序是一个服务程序，那么你可以指定这个服务程序运行时的进程ID。gdb会自
动attach上去，并调试他。program应该在PATH环境变量中搜索得到。
GDB启动时，可以加上一些GDB的启动开关，详细的开关可以用gdb -help查看。我在下
面只例举一些比较常用的参数：
-symbols
-s
从指定文件中读取符号表。
-se file
从指定文件中读取符号表信息，并把他用在可执行文件中。
-core
-c
调试时core dump的core文件。
-directory
-d
加入一个源文件的搜索路径。默认搜索路径是环境变量中PATH所定义的路径。
GDB的命令概貌
———————
启动gdb后，就你被带入gdb的调试环境中，就可以使用gdb的命令开始调试程序了，gdb
的命令可以使用help命令来查看，如下所示：
/home/hchen> gdb
GNU gdb 5.1.1
Copyright 2002 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB. Type "show warranty" for details.
This GDB was configured as "i386-suse-linux".
(gdb) help

List of classes of commands:
aliases -- Aliases of other commands
breakpoints -- Making program stop at certain points
data -- Examining data
files -- Specifying and examining files
internals -- Maintenance commands
obscure -- Obscure features
running -- Running the program
stack -- Examining the stack
status -- Status inquiries
support -- Support facilities
tracepoints -- Tracing of program execution without stopping the program
user-defined -- User-defined commands
Type "help" followed by a class name for a list of commands in that class.
Type "help" followed by command name for full documentation.
Command name abbreviations are allowed if unambiguous.
(gdb)
gdb的命令很多，gdb把之分成许多个种类。help命令只是例出gdb的命令种类，如果要看
种类中的命令，可以使用help 命令，如：help breakpoints，查看设置断点的所有命令。也
可以直接help 来查看命令的帮助。
gdb中，输入命令时，可以不用打全命令，只用打命令的前几个字符就可以了，当然，命令
的前几个字符应该要标志着一个唯一的命令，在Linux下，你可以敲击两次TAB键来补齐
命令的全称，如果有重复的，那么gdb会把其例出来。
示例一：在进入函数func时，设置一个断点。可以敲入break func，或是直接就是b func
(gdb) b func
Breakpoint 1 at 0x8048458: file hello.c, line 10.
示例二：敲入b按两次TAB键，你会看到所有b打头的命令：
(gdb) b
backtrace break bt
(gdb)
示例三：只记得函数的前缀，可以这样：
(gdb) b make_ <按TAB键>
（再按下一次TAB键，你会看到:）
make_a_section_from_file make_environ
make_abs_section make_function_type
make_blockvector make_pointer_type

make_cleanup make_reference_type
make_command make_symbol_completion_list
(gdb) b make_
GDB把所有make开头的函数全部例出来给你查看。
示例四：调试C++的程序时，有可以函数名一样。如：
(gdb) b 'bubble( M-?
bubble(double,double) bubble(int,int)
(gdb) b 'bubble(
你可以查看到C++中的所有的重载函数及参数。（注：M-?和“按两次TAB键”是一个意思）
要退出gdb时，只用发quit或命令简称q就行了。
GDB中运行UNIX的shell程序
————————————
在gdb环境中，你可以执行UNIX的shell的命令，使用gdb的shell命令来完成：
shell
调用UNIX的shell来执行，环境变量SHELL中定义的UNIX的shell将会被用来执行，如
果SHELL没有定义，那就使用UNIX的标准shell：/bin/sh。（在Windows中使用Command.com
或cmd.exe）
还有一个gdb命令是make：
make
可以在gdb中执行make命令来重新build自己的程序。这个命令等价于“shell make ”。
在GDB中运行程序
————————
当以gdb 方式启动gdb后，gdb会在PATH路径和当前目录中搜索的源文件。如要确认gdb
是否读到源文件，可使用l或list命令，看看gdb是否能列出源代码。
在gdb中，运行程序使用r或是run命令。程序的运行，你有可能需要设置下面四方面的事。
1、程序运行参数。
set args 可指定运行时参数。（如：set args 10 20 30 40 50）
show args 命令可以查看设置好的运行参数。
2、运行环境。
path
可设定程序的运行路径。
show paths 查看程序的运行路径。

set environment varname [=value] 设置环境变量。如：set env USER=hchen
show environment [varname] 查看环境变量。
3、工作目录。
cd
相当于shell的cd命令。
pwd 显示当前的所在目录。
4、程序的输入输出。
info terminal 显示你程序用到的终端的模式。
使用重定向控制程序输出。如：run > outfile
tty命令可以指写输入输出的终端设备。如：tty /dev/ttyb
调试已运行的程序
————————
两种方法：
1、在UNIX下用ps查看正在运行的程序的PID（进程ID），然后用gdb PID格式挂接正在
运行的程序。
2、先用gdb 关联上源代码，并进行gdb，在gdb中用attach命令来挂接进程的PID。并用
detach来取消挂接的进程。
暂停 / 恢复程序运行
—————————
调试程序中，暂停程序运行是必须的，GDB可以方便地暂停程序的运行。你可以设置程序
的在哪行停住，在什么条件下停住，在收到什么信号时停往等等。以便于你查看运行时的变
量，以及运行时的流程。
当进程被gdb停住时，你可以使用info program 来查看程序的是否在运行，进程号，被暂停
的原因。
在gdb中，我们可以有以下几种暂停方式：断点（BreakPoint）、观察点（WatchPoint）、捕
捉点（CatchPoint）、信号（Signals）、线程停止（Thread Stops）。如果要恢复程序运行，可
以使用c或是continue命令。
一、设置断点（BreakPoint）
我们用break命令来设置断点。正面有几点设置断点的方法：
break
在进入指定函数时停住。C++中可以使用class::function或function(type,type)格式来指定函

数名。
break
在指定行号停住。
break +offset
break -offset
在当前行号的前面或后面的offset行停住。offiset为自然数。
break filename:linenum
在源文件filename的linenum行处停住。
break filename:function
在源文件filename的function函数的入口处停住。
break *address
在程序运行的内存地址处停住。
break
break命令没有参数时，表示在下一条指令处停住。
break ... if
...可以是上述的参数，condition表示条件，在条件成立时停住。比如在循环境体中，可以设
置break if i=100，表示当i为100时停住程序。
查看断点时，可使用info命令，如下所示：（注：n表示断点号）
info breakpoints [n]
info break [n]
二、设置观察点（WatchPoint）
观察点一般来观察某个表达式（变量也是一种表达式）的值是否有变化了，如果有变化，马
上停住程序。我们有下面的几种方法来设置观察点：
watch
为表达式（变量）expr设置一个观察点。一量表达式值有变化时，马上停住程序。
rwatch
当表达式（变量）expr被读时，停住程序。
awatch
当表达式（变量）的值被读或被写时，停住程序。

info watchpoints
列出当前所设置了的所有观察点。
三、设置捕捉点（CatchPoint）
你可设置捕捉点来补捉程序运行时的一些事件。如：载入共享库（动态链接库）或是C++
的异常。设置捕捉点的格式为：
catch
当event发生时，停住程序。event可以是下面的内容：
1、throw 一个C++抛出的异常。（throw为关键字）
2、catch 一个C++捕捉到的异常。（catch为关键字）
3、exec 调用系统调用exec时。（exec为关键字，目前此功能只在HP-UX下有用）
4、fork 调用系统调用fork时。（fork为关键字，目前此功能只在HP-UX下有用）
5、vfork 调用系统调用vfork时。（vfork为关键字，目前此功能只在HP-UX下有用）
6、load 或 load 载入共享库（动态链接库）时。（load为关键字，目前此功能只在HP-UX
下有用）
7、unload 或 unload 卸载共享库（动态链接库）时。（unload为关键字，目前此功能只在
HP-UX下有用）
tcatch
只设置一次捕捉点，当程序停住以后，应点被自动删除。
四、维护停止点
上面说了如何设置程序的停止点，GDB中的停止点也就是上述的三类。在GDB中，如果你
觉得已定义好的停止点没有用了，你可以使用delete、clear、disable、enable这几个命令来
进行维护。
clear
清除所有的已定义的停止点。
clear
clear
清除所有设置在函数上的停止点。
clear
clear
清除所有设置在指定行上的停止点。
delete [breakpoints] [range...]
删除指定的断点，breakpoints为断点号。如果不指定断点号，则表示删除所有的断点。range
表示断点号的范围（如：3-7）。其简写命令为d。

比删除更好的一种方法是disable停止点，disable了的停止点，GDB不会删除，当你还需要
时，enable即可，就好像回收站一样。
disable [breakpoints] [range...]
disable所指定的停止点，breakpoints为停止点号。如果什么都不指定，表示disable所有的
停止点。简写命令是dis.
enable [breakpoints] [range...]
enable所指定的停止点，breakpoints为停止点号。
enable [breakpoints] once range...
enable所指定的停止点一次，当程序停止后，该停止点马上被GDB自动disable。
enable [breakpoints] delete range...
enable所指定的停止点一次，当程序停止后，该停止点马上被GDB自动删除。
五、停止条件维护
前面在说到设置断点时，我们提到过可以设置一个条件，当条件成立时，程序自动停止，这
是一个非常强大的功能，这里，我想专门说说这个条件的相关维护命令。一般来说，为断点
设置一个条件，我们使用if关键词，后面跟其断点条件。并且，条件设置好后，我们可以
用condition命令来修改断点的条件。（只有break和watch命令支持if，catch目前暂不支持
if）
condition
修改断点号为bnum的停止条件为expression。
condition
清除断点号为bnum的停止条件。
还有一个比较特殊的维护命令ignore，你可以指定程序运行时，忽略停止条件几次。
ignore
表示忽略断点号为bnum的停止条件count次。
六、为停止点设定运行命令
我们可以使用GDB提供的command命令来设置停止点的运行命令。也就是说，当运行的
程序在被停止住时，我们可以让其自动运行一些别的命令，这很有利行自动化调试。对基于
GDB的自动化调试是一个强大的支持。
commands [bnum]

... command-list ...
end
为断点号bnum指写一个命令列表。当程序被该断点停住时，gdb会依次运行命令列表中的
命令。
例如：
break foo if x>0
commands
printf "x is %d\n",x
continue
end
断点设置在函数foo中，断点条件是x>0，如果程序被断住后，也就是，一旦x的值在foo
函数中大于0，GDB会自动打印出x的值，并继续运行程序。
如果你要清除断点上的命令序列，那么只要简单的执行一下commands命令，并直接在打个
end就行了。
七、断点菜单
在C++中，可能会重复出现同一个名字的函数若干次（函数重载），在这种情况下，break 不
能告诉GDB要停在哪个函数的入口。当然，你可以使用break 也就是把函数的参数类型告
诉GDB，以指定一个函数。否则的话，GDB会给你列出一个断点菜单供你选择你所需要的
断点。你只要输入你菜单列表中的编号就可以了。如：
(gdb) b String::after
[0] cancel
[1] all
[2] file:String.cc; line number:867
[3] file:String.cc; line number:860
[4] file:String.cc; line number:875
[5] file:String.cc; line number:853
[6] file:String.cc; line number:846
[7] file:String.cc; line number:735
> 2 4 6
Breakpoint 1 at 0xb26c: file String.cc, line 867.
Breakpoint 2 at 0xb344: file String.cc, line 875.
Breakpoint 3 at 0xafcc: file String.cc, line 846.
Multiple breakpoints were set.
Use the "delete" command to delete unwanted
breakpoints.
(gdb)

可见，GDB列出了所有after的重载函数，你可以选一下列表编号就行了。0表示放弃设置
断点，1表示所有函数都设置断点。
八、恢复程序运行和单步调试
当程序被停住了，你可以用continue命令恢复程序的运行直到程序结束，或下一个断点到来。
也可以使用step或next命令单步跟踪程序。
continue [ignore-count]
c [ignore-count]
fg [ignore-count]
恢复程序运行，直到程序结束，或是下一个断点到来。ignore-count表示忽略其后的断点次
数。continue，c，fg三个命令都是一样的意思。
step
单步跟踪，如果有函数调用，他会进入该函数。进入函数的前提是，此函数被编译有debug
信息。很像VC等工具中的step in。后面可以加count也可以不加，不加表示一条条地执行，
加表示执行后面的count条指令，然后再停住。
next
同样单步跟踪，如果有函数调用，他不会进入该函数。很像VC等工具中的step over。后面
可以加count也可以不加，不加表示一条条地执行，加表示执行后面的count条指令，然后
再停住。
set step-mode
set step-mode on
打开step-mode模式，于是，在进行单步跟踪时，程序不会因为没有debug信息而不停住。
这个参数有很利于查看机器码。
set step-mod off
关闭step-mode模式。
finish
运行程序，直到当前函数完成返回。并打印函数返回时的堆栈地址和返回值及参数值等信息。
until 或 u
当你厌倦了在一个循环体内单步跟踪时，这个命令可以运行程序直到退出循环体。
stepi 或 si
nexti 或 ni
单步跟踪一条机器指令！一条程序代码有可能由数条机器指令完成，stepi和nexti可以单步
执行机器指令。与之一样有相同功能的命令是“display/i $pc” ，当运行完这个命令后，单
步跟踪会在打出程序代码的同时打出机器指令（也就是汇编代码）

九、信号（Signals）
信号是一种软中断，是一种处理异步事件的方法。一般来说，操作系统都支持许多信号。尤
其是UNIX，比较重要应用程序一般都会处理信号。UNIX定义了许多信号，比如SIGINT
表示中断字符信号，也就是Ctrl+C的信号，SIGBUS表示硬件故障的信号；SIGCHLD表示
子进程状态改变信号；SIGKILL表示终止程序运行的信号，等等。信号量编程是UNIX下
非常重要的一种技术。
GDB有能力在你调试程序的时候处理任何一种信号，你可以告诉GDB需要处理哪一种信
号。你可以要求GDB收到你所指定的信号时，马上停住正在运行的程序，以供你进行调试。
你可以用GDB的handle命令来完成这一功能。
handle
在GDB中定义一个信号处理。信号可以以SIG开头或不以SIG开头，可以用定义一个要处
理信号的范围（如：SIGIO-SIGKILL，表示处理从SIGIO信号到SIGKILL的信号，其中包
括SIGIO，SIGIOT，SIGKILL三个信号），也可以使用关键字all来标明要处理所有的信号。
一旦被调试的程序接收到信号，运行程序马上会被GDB停住，以供调试。其可以是以下几
种关键字的一个或多个。
nostop
当被调试的程序收到信号时，GDB不会停住程序的运行，但会打出消息告诉你收到这种信
号。
stop
当被调试的程序收到信号时，GDB会停住你的程序。
print
当被调试的程序收到信号时，GDB会显示出一条信息。
noprint
当被调试的程序收到信号时，GDB不会告诉你收到信号的信息。
pass
noignore
当被调试的程序收到信号时，GDB不处理信号。这表示，GDB会把这个信号交给被调试程
序会处理。
nopass
ignore
当被调试的程序收到信号时，GDB不会让被调试程序来处理这个信号。
info signals
info handle
查看有哪些信号在被GDB检测中。
十、线程（Thread Stops）

如果你程序是多线程的话，你可以定义你的断点是否在所有的线程上，或是在某个特定的线
程。GDB很容易帮你完成这一工作。
break thread
break thread if ...
linespec指定了断点设置在的源程序的行号。threadno指定了线程的ID，注意，这个ID是
GDB分配的，你可以通过“info threads”命令来查看正在运行程序中的线程信息。如果你
不指定thread 则表示你的断点设在所有线程上面。你还可以为某线程指定断点条件。如：
(gdb) break frik.c:13 thread 28 if bartab > lim
当你的程序被GDB停住时，所有的运行线程都会被停住。这方便你你查看运行程序的总体
情况。而在你恢复程序运行时，所有的线程也会被恢复运行。那怕是主进程在被单步调试时。
查看栈信息
—————
当程序被停住了，你需要做的第一件事就是查看程序是在哪里停住的。当你的程序调用了一
个函数，函数的地址，函数参数，函数内的局部变量都会被压入“栈”（Stack）中。你可以
用GDB命令来查看当前的栈中的信息。
下面是一些查看函数调用栈信息的GDB命令：
backtrace
bt
打印当前的函数调用栈的所有信息。如：
(gdb) bt
#0 func (n=250) at tst.c:6
#1 0x08048524 in main (argc=1, argv=0xbffff674) at tst.c:30
#2 0x400409ed in __libc_start_main () from /lib/libc.so.6
从上可以看出函数的调用栈信息：__libc_start_main --> main() --> func()
backtrace
bt
n是一个正整数，表示只打印栈顶上n层的栈信息。
backtrace <-n>
bt <-n>
-n表一个负整数，表示只打印栈底下n层的栈信息。
如果你要查看某一层的信息，你需要在切换当前的栈，一般来说，程序停止时，最顶层的栈

就是当前栈，如果你要查看栈下面层的详细信息，首先要做的是切换当前栈。
frame
f
n是一个从0开始的整数，是栈中的层编号。比如：frame 0，表示栈顶，frame 1，表示栈的
第二层。
up
表示向栈的上面移动n层，可以不打n，表示向上移动一层。
down
表示向栈的下面移动n层，可以不打n，表示向下移动一层。
上面的命令，都会打印出移动到的栈层的信息。如果你不想让其打出信息。你可以使用这三
个命令：
select-frame 对应于 frame 命令。
up-silently 对应于 up 命令。
down-silently 对应于 down 命令。
查看当前栈层的信息，你可以用以下GDB命令：
frame 或 f
会打印出这些信息：栈的层编号，当前的函数名，函数参数值，函数所在文件及行号，函数
执行到的语句。
info frame
info f
这个命令会打印出更为详细的当前栈层的信息，只不过，大多数都是运行时的内内地址。比
如：函数地址，调用函数的地址，被调用函数的地址，目前的函数是由什么样的程序语言写
成的、函数参数地址及值、局部变量的地址等等。如：
(gdb) info f
Stack level 0, frame at 0xbffff5d4:
eip = 0x804845d in func (tst.c:6); saved eip 0x8048524
called by frame at 0xbffff60c
source language c.
Arglist at 0xbffff5d4, args: n=250
Locals at 0xbffff5d4, Previous frame's sp is 0x0
Saved registers:
ebp at 0xbffff5d4, eip at 0xbffff5d8
info args

打印出当前函数的参数名及其值。
info locals
打印出当前函数中所有局部变量及其值。
info catch
打印出当前的函数中的异常处理信息。
查看源程序
—————
一、显示源代码
GDB 可以打印出所调试程序的源代码，当然，在程序编译时一定要加上-g的参数，把源程
序信息编译到执行文件中。不然就看不到源程序了。当程序停下来以后，GDB会报告程序
停在了那个文件的第几行上。你可以用list命令来打印程序的源代码。还是来看一看查看源
代码的GDB命令吧。
list
显示程序第linenum行的周围的源程序。
list
显示函数名为function的函数的源程序。
list
显示当前行后面的源程序。
list -
显示当前行前面的源程序。
一般是打印当前行的上5行和下5行，如果显示函数是是上2行下8行，默认是10行，当
然，你也可以定制显示的范围，使用下面命令可以设置一次显示源程序的行数。
set listsize
设置一次显示源代码的行数。
show listsize
查看当前listsize的设置。
list命令还有下面的用法：
list ,

显示从first行到last行之间的源代码。
list ,
显示从当前行到last行之间的源代码。
list +
往后显示源代码。
一般来说在list后面可以跟以下这们的参数：
行号。
<+offset> 当前行号的正偏移量。
<-offset> 当前行号的负偏移量。
哪个文件的哪一行。
函数名。
哪个文件中的哪个函数。
<*address> 程序运行时的语句在内存中的地址。
二、搜索源代码
不仅如此，GDB还提供了源代码搜索的命令：
forward-search
search
向前面搜索。
reverse-search
全部搜索。
其中，就是正则表达式，也主一个字符串的匹配模式，关于正则表达式，我就不在这里讲了，
还请各位查看相关资料。
三、指定源文件的路径
某些时候，用-g编译过后的执行程序中只是包括了源文件的名字，没有路径名。GDB提供
了可以让你指定源文件的路径的命令，以便GDB进行搜索。
directory
dir
加一个源文件路径到当前路径的前面。如果你要指定多个路径，UNIX下你可以使用“:”，
Windows下你可以使用“;”。

directory
清除所有的自定义的源文件搜索路径信息。
show directories
显示定义了的源文件搜索路径。
四、源代码的内存
你可以使用info line命令来查看源代码在内存中的地址。info line后面可以跟“行号”，“函
数名”，“文件名:行号”，“文件名:函数名”，这个命令会打印出所指定的源码在运行时的内
存地址，如：
(gdb) info line tst.c:func
Line 5 of "tst.c" starts at address 0x8048456 and ends at 0x804845d .
还有一个命令（disassemble）你可以查看源程序的当前执行时的机器码，这个命令会把目前
内存中的指令dump出来。如下面的示例表示查看函数func的汇编代码。
(gdb) disassemble func
Dump of assembler code for function func:
0x8048450 : push %ebp
0x8048451 : mov %esp,%ebp
0x8048453 : sub $0x18,%esp
0x8048456 : movl $0x0,0xfffffffc(%ebp)
0x804845d : movl $0x1,0xfffffff8(%ebp)
0x8048464 : mov 0xfffffff8(%ebp),%eax
0x8048467 : cmp 0x8(%ebp),%eax
0x804846a : jle 0x8048470
0x804846c : jmp 0x8048480
0x804846e : mov %esi,%esi
0x8048470 : mov 0xfffffff8(%ebp),%eax
0x8048473 : add %eax,0xfffffffc(%ebp)
0x8048476 : incl 0xfffffff8(%ebp)
0x8048479 : jmp 0x8048464
0x804847b : nop
0x804847c : lea 0x0(%esi,1),%esi
0x8048480 : mov 0xfffffffc(%ebp),%edx
0x8048483 : mov %edx,%eax
0x8048485 : jmp 0x8048487
0x8048487 : mov %ebp,%esp
0x8048489 : pop %ebp
0x804848a : ret
End of assembler dump.

查看运行时数据
———————
在你调试程序时，当程序被停住时，你可以使用print命令（简写命令为p），或是同义命令
inspect来查看当前程序的运行数据。print命令的格式是：
print
print /
是表达式，是你所调试的程序的语言的表达式（GDB可以调试多种编程语言），是输出的格
式，比如，如果要把表达式按16进制的格式输出，那么就是/x。
一、表达式
print和许多GDB的命令一样，可以接受一个表达式，GDB会根据当前的程序运行的数据
来计算这个表达式，既然是表达式，那么就可以是当前程序运行中的const常量、变量、函
数等内容。可惜的是GDB不能使用你在程序中所定义的宏。
表达式的语法应该是当前所调试的语言的语法，由于C/C++是一种大众型的语言，所以，本
文中的例子都是关于C/C++的。（而关于用GDB调试其它语言的章节，我将在后面介绍）
在表达式中，有几种GDB所支持的操作符，它们可以用在任何一种语言中。
@
是一个和数组有关的操作符，在后面会有更详细的说明。
::
指定一个在文件或是一个函数中的变量。
{}
表示一个指向内存地址的类型为type的一个对象。
二、程序变量
在GDB中，你可以随时查看以下三种变量的值：
1、全局变量（所有文件可见的）
2、静态全局变量（当前文件可见的）
3、局部变量（当前Scope可见的）
如果你的局部变量和全局变量发生冲突（也就是重名），一般情况下是局部变量会隐藏全局
变量，也就是说，如果一个全局变量和一个函数中的局部变量同名时，如果当前停止点在函

数中，用print显示出的变量的值会是函数中的局部变量的值。如果此时你想查看全局变量
的值时，你可以使用“::”操作符：
file::variable
function::variable
可以通过这种形式指定你所想查看的变量，是哪个文件中的或是哪个函数中的。例如，查看
文件f2.c中的全局变量x的值：
gdb) p 'f2.c'::x
当然，“::”操作符会和C++中的发生冲突，GDB能自动识别“::” 是否C++的操作符，所
以你不必担心在调试C++程序时会出现异常。
另外，需要注意的是，如果你的程序编译时开启了优化选项，那么在用GDB调试被优化过
的程序时，可能会发生某些变量不能访问，或是取值错误码的情况。这个是很正常的，因为
优化程序会删改你的程序，整理你程序的语句顺序，剔除一些无意义的变量等，所以在GDB
调试这种程序时，运行时的指令和你所编写指令就有不一样，也就会出现你所想象不到的结
果。对付这种情况时，需要在编译程序时关闭编译优化。一般来说，几乎所有的编译器都支
持编译优化的开关，例如，GNU的C/C++编译器GCC，你可以使用“-gstabs”选项来解决
这个问题。关于编译器的参数，还请查看编译器的使用说明文档。
三、数组
有时候，你需要查看一段连续的内存空间的值。比如数组的一段，或是动态分配的数据的大
小。你可以使用GDB的“@”操作符，“@”的左边是第一个内存的地址的值，“@”的右
边则你你想查看内存的长度。例如，你的程序中有这样的语句：
int *array = (int *) malloc (len * sizeof (int));
于是，在GDB调试过程中，你可以以如下命令显示出这个动态数组的取值：
p *array@len
@的左边是数组的首地址的值，也就是变量array所指向的内容，右边则是数据的长度，其
保存在变量len中，其输出结果，大约是下面这个样子的：
(gdb) p *array@len
$1 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40}
如果是静态数组的话，可以直接用print数组名，就可以显示数组中所有数据的内容了。
四、输出格式

一般来说，GDB会根据变量的类型输出变量的值。但你也可以自定义GDB的输出的格式。
例如，你想输出一个整数的十六进制，或是二进制来查看这个整型变量的中的位的情况。要
做到这样，你可以使用GDB的数据显示格式：
x 按十六进制格式显示变量。
d 按十进制格式显示变量。
u 按十六进制格式显示无符号整型。
o 按八进制格式显示变量。
t 按二进制格式显示变量。
a 按十六进制格式显示变量。
c 按字符格式显示变量。
f 按浮点数格式显示变量。
(gdb) p i
$21 = 101
(gdb) p/a i
$22 = 0x65
(gdb) p/c i
$23 = 101 'e'
(gdb) p/f i
$24 = 1.41531145e-43
(gdb) p/x i
$25 = 0x65
(gdb) p/t i
$26 = 1100101
五、查看内存
你可以使用examine命令（简写是x）来查看内存地址中的值。x命令的语法如下所示：
x/
n、f、u是可选的参数。
n 是一个正整数，表示显示内存的长度，也就是说从当前地址向后显示几个地址的内容。
f 表示显示的格式，参见上面。如果地址所指的是字符串，那么格式可以是s，如果地十是
指令地址，那么格式可以是i。

u 表示从当前地址往后请求的字节数，如果不指定的话，GDB默认是4个bytes。u参数可
以用下面的字符来代替，b表示单字节，h表示双字节，w表示四字节，g表示八字节。当
我们指定了字节长度后，GDB会从指内存定的内存地址开始，读写指定字节，并把其当作
一个值取出来。
表示一个内存地址。
n/f/u三个参数可以一起使用。例如：
命令：x/3uh 0x54320 表示，从内存地址0x54320读取内容，h表示以双字节为一个单位，3
表示三个单位，u表示按十六进制显示。
六、自动显示
你可以设置一些自动显示的变量，当程序停住时，或是在你单步跟踪时，这些变量会自动显
示。相关的GDB命令是display。
display
display/
display/
expr是一个表达式，fmt表示显示的格式，addr表示内存地址，当你用display设定好了一
个或多个表达式后，只要你的程序被停下来，GDB会自动显示你所设置的这些表达式的值。
格式i和s同样被display支持，一个非常有用的命令是：
display/i $pc
$pc是GDB的环境变量，表示着指令的地址，/i则表示输出格式为机器指令码，也就是汇
编。于是当程序停下后，就会出现源代码和机器指令码相对应的情形，这是一个很有意思的
功能。
下面是一些和display相关的GDB命令：
undisplay
delete display
删除自动显示，dnums意为所设置好了的自动显式的编号。如果要同时删除几个，编号可以
用空格分隔，如果要删除一个范围内的编号，可以用减号表示（如：2-5）
disable display
enable display
disable和enalbe不删除自动显示的设置，而只是让其失效和恢复。

info display
查看display设置的自动显示的信息。GDB会打出一张表格，向你报告当然调试中设置了多
少个自动显示设置，其中包括，设置的编号，表达式，是否enable。
七、设置显示选项
GDB中关于显示的选项比较多，这里我只例举大多数常用的选项。
set print address
set print address on
打开地址输出，当程序显示函数信息时，GDB会显出函数的参数地址。系统默认为打开的，
如：
(gdb) f
#0 set_quotes (lq=0x34c78 "<<", rq=0x34c88 ">>")
at input.c:530
530 if (lquote != def_lquote)
set print address off
关闭函数的参数地址显示，如：
(gdb) set print addr off
(gdb) f
#0 set_quotes (lq="<<", rq=">>") at input.c:530
530 if (lquote != def_lquote)
show print address
查看当前地址显示选项是否打开。
set print array
set print array on
打开数组显示，打开后当数组显示时，每个元素占一行，如果不打开的话，每个元素则以逗
号分隔。这个选项默认是关闭的。与之相关的两个命令如下，我就不再多说了。
set print array off
show print array
set print elements
这个选项主要是设置数组的，如果你的数组太大了，那么就可以指定一个来指定数据显示的
最大长度，当到达这个长度时，GDB就不再往下显示了。如果设置为0，则表示不限制。
show print elements

查看print elements的选项信息。
set print null-stop
如果打开了这个选项，那么当显示字符串时，遇到结束符则停止显示。这个选项默认为off。
set print pretty on
如果打开printf pretty这个选项，那么当GDB显示结构体时会比较漂亮。如：
$1 = {
next = 0x0,
flags = {
sweet = 1,
sour = 1
},
meat = 0x54 "Pork"
}
set print pretty off
关闭printf pretty这个选项，GDB显示结构体时会如下显示：
$1 = {next = 0x0, flags = {sweet = 1, sour = 1}, meat = 0x54 "Pork"}
show print pretty
查看GDB是如何显示结构体的。
set print sevenbit-strings
设置字符显示，是否按“\nnn”的格式显示，如果打开，则字符串或字符数据按\nnn显示，
如“\065”。
show print sevenbit-strings
查看字符显示开关是否打开。
set print union
设置显示结构体时，是否显式其内的联合体数据。例如有以下数据结构：
typedef enum {Tree, Bug} Species;
typedef enum {Big_tree, Acorn, Seedling} Tree_forms;
typedef enum {Caterpillar, Cocoon, Butterfly}
Bug_forms;
struct thing {
Species it;
union {

Tree_forms tree;
Bug_forms bug;
} form;
};
struct thing foo = {Tree, {Acorn}};
当打开这个开关时，执行 p foo 命令后，会如下显示：
$1 = {it = Tree, form = {tree = Acorn, bug = Cocoon}}
当关闭这个开关时，执行 p foo 命令后，会如下显示：
$1 = {it = Tree, form = {...}}
show print union
查看联合体数据的显示方式
set print object
在C++中，如果一个对象指针指向其派生类，如果打开这个选项，GDB会自动按照虚方法
调用的规则显示输出，如果关闭这个选项的话，GDB就不管虚函数表了。这个选项默认是
off。
show print object
查看对象选项的设置。
set print static-members
这个选项表示，当显示一个C++对象中的内容是，是否显示其中的静态数据成员。默认是
on。
show print static-members
查看静态数据成员选项设置。
set print vtbl
当此选项打开时，GDB将用比较规整的格式来显示虚函数表时。其默认是关闭的。
show print vtbl
查看虚函数显示格式的选项。
八、历史记录
当你用GDB的print查看程序运行时的数据时，你每一个print都会被GDB记录下来。GDB
会以$1, $2, $3 .....这样的方式为你每一个print命令编上号。于是，你可以使用这个编号访问
以前的表达式，如$1。这个功能所带来的好处是，如果你先前输入了一个比较长的表达式，
如果你还想查看这个表达式的值，你可以使用历史记录来访问，省去了重复输入。

九、GDB环境变量
你可以在GDB的调试环境中定义自己的变量，用来保存一些调试程序中的运行数据。要定
义一个GDB的变量很简单只需。使用GDB的set命令。GDB的环境变量和UNIX一样，
也是以$起头。如：
set $foo = *object_ptr
使用环境变量时，GDB会在你第一次使用时创建这个变量，而在以后的使用中，则直接对
其賦值。环境变量没有类型，你可以给环境变量定义任一的类型。包括结构体和数组。
show convenience
该命令查看当前所设置的所有的环境变量。
这是一个比较强大的功能，环境变量和程序变量的交互使用，将使得程序调试更为灵活便捷。
例如：
set $i = 0
print bar[$i++]->contents
于是，当你就不必，print bar[0]->contents, print bar[1]->contents地输入命令了。输入这样的
命令后，只用敲回车，重复执行上一条语句，环境变量会自动累加，从而完成逐个输出的功
能。
十、查看寄存器
要查看寄存器的值，很简单，可以使用如下命令：
info registers
查看寄存器的情况。（除了浮点寄存器）
info all-registers
查看所有寄存器的情况。（包括浮点寄存器）
info registers
查看所指定的寄存器的情况。
寄存器中放置了程序运行时的数据，比如程序当前运行的指令地址（ip），程序的当前堆栈
地址（sp）等等。你同样可以使用print命令来访问寄存器的情况，只需要在寄存器名字前
加一个$符号就可以了。如：p $eip。

改变程序的执行
———————
一旦使用GDB挂上被调试程序，当程序运行起来后，你可以根据自己的调试思路来动态地
在GDB中更改当前被调试程序的运行线路或是其变量的值，这个强大的功能能够让你更好
的调试你的程序，比如，你可以在程序的一次运行中走遍程序的所有分支。
一、修改变量值
修改被调试程序运行时的变量值，在GDB中很容易实现，使用GDB的print命令即可完成。
如：
(gdb) print x=4
x=4这个表达式是C/C++的语法，意为把变量x的值修改为4，如果你当前调试的语言是
Pascal，那么你可以使用Pascal的语法：x:=4。
在某些时候，很有可能你的变量和GDB中的参数冲突，如：
(gdb) whatis width
type = double
(gdb) p width
$4 = 13
(gdb) set width=47
Invalid syntax in expression.
因为，set width是GDB的命令，所以，出现了“Invalid syntax in expression”的设置错误，
此时，你可以使用set var命令来告诉GDB，width不是你GDB的参数，而是程序的变量名，
如：
(gdb) set var width=47
另外，还可能有些情况，GDB并不报告这种错误，所以保险起见，在你改变程序变量取值
时，最好都使用set var格式的GDB命令。
二、跳转执行
一般来说，被调试程序会按照程序代码的运行顺序依次执行。GDB提供了乱序执行的功能，
也就是说，GDB可以修改程序的执行顺序，可以让程序执行随意跳跃。这个功能可以由GDB
的jump命令来完：
jump

指定下一条语句的运行点。可以是文件的行号，可以是file:line格式，可以是+num这种偏
移量格式。表式着下一条运行语句从哪里开始。
jump
这里的
是代码行的内存地址。
注意，jump命令不会改变当前的程序栈中的内容，所以，当你从一个函数跳到另一个函数
时，当函数运行完返回时进行弹栈操作时必然会发生错误，可能结果还是非常奇怪的，甚至
于产生程序Core Dump。所以最好是同一个函数中进行跳转。
熟悉汇编的人都知道，程序运行时，有一个寄存器用于保存当前代码所在的内存地址。所以，
jump命令也就是改变了这个寄存器中的值。于是，你可以使用“set $pc”来更改跳转执行
的地址。如：
set $pc = 0x485
三、产生信号量
使用singal命令，可以产生一个信号量给被调试的程序。如：中断信号Ctrl+C。这非常方便
于程序的调试，可以在程序运行的任意位置设置断点，并在该断点用GDB产生一个信号量，
这种精确地在某处产生信号非常有利程序的调试。
语法是：signal ，UNIX的系统信号量通常从1到15。所以取值也在这个范围。
single命令和shell的kill命令不同，系统的kill命令发信号给被调试程序时，是由GDB截
获的，而single命令所发出一信号则是直接发给被调试程序的。
四、强制函数返回
如果你的调试断点在某个函数中，并还有语句没有执行完。你可以使用return命令强制函数
忽略还没有执行的语句并返回。
return
return
使用return命令取消当前函数的执行，并立即返回，如果指定了，那么该表达式的值会被认
作函数的返回值。
五、强制调用函数

call
表达式中可以一是函数，以此达到强制调用函数的目的。并显示函数的返回值，如果函数返
回值是void，那么就不显示。
另一个相似的命令也可以完成这一功能——print，print后面可以跟表达式，所以也可以用他
来调用函数，print和call的不同是，如果函数返回void，call则不显示，print则显示函数返
回值，并把该值存入历史数据中。
在不同语言中使用GDB
——————————
GDB支持下列语言：C, C++, Fortran, PASCAL, Java, Chill, assembly, 和 Modula-2。一般说
来，GDB会根据你所调试的程序来确定当然的调试语言，比如：发现文件名后缀为“.c”
的，GDB会认为是C程序。文件名后缀为“.C, .cc, .cp, .cpp, .cxx, .c++”的，GDB会认为是
C++程序。而后缀是“.f, .F”的，GDB会认为是Fortran程序，还有，后缀为如果是“.s, .S”
的会认为是汇编语言。
也就是说，GDB会根据你所调试的程序的语言，来设置自己的语言环境，并让GDB的命令
跟着语言环境的改变而改变。比如一些GDB命令需要用到表达式或变量时，这些表达式或
变量的语法，完全是根据当前的语言环境而改变的。例如C/C++中对指针的语法是*p，而在
Modula-2中则是p^。并且，如果你当前的程序是由几种不同语言一同编译成的，那到在调
试过程中，GDB也能根据不同的语言自动地切换语言环境。这种跟着语言环境而改变的功
能，真是体贴开发人员的一种设计。
下面是几个相关于GDB语言环境的命令：
show language
查看当前的语言环境。如果GDB不能识为你所调试的编程语言，那么，C语言被认为是默
认的环境。
info frame
查看当前函数的程序语言。
info source
查看当前文件的程序语言。
如果GDB没有检测出当前的程序语言，那么你也可以手动设置当前的程序语言。使用set
language命令即可做到。
当set language命令后什么也不跟的话，你可以查看GDB所支持的语言种类：

(gdb) set language
The currently understood settings are:
local or auto Automatic setting based on source file
c Use the C language
c++ Use the C++ language
asm Use the Asm language
chill Use the Chill language
fortran Use the Fortran language
java Use the Java language
modula-2 Use the Modula-2 language
pascal Use the Pascal language
scheme Use the Scheme language
于是你可以在set language后跟上被列出来的程序语言名，来设置当前的语言环境。
后记
——
GDB是一个强大的命令行调试工具。大家知道命令行的强大就是在于，其可以形成执行序
列，形成脚本。UNIX下的软件全是命令行的，这给程序开发提代供了极大的便利，命令行
软件的优势在于，它们可以非常容易的集成在一起，使用几个简单的已有工具的命令，就可
以做出一个非常强大的功能。
于是UNIX下的软件比Windows下的软件更能有机地结合，各自发挥各自的长处，组合成
更为强劲的功能。而Windows下的图形软件基本上是各自为营，互相不能调用，很不利于
各种软件的相互集成。在这里并不是要和Windows做个什么比较，所谓“寸有所长，尺有
所短”，图形化工具还是有不如命令行的地方。（看到这句话时，希望各位千万再也不要认为
我就是“鄙视图形界面”，和我抬杠了 ）
我是根据版本为5.1.1的GDB所写的这篇文章，所以可能有些功能已被修改，或是又有更
为强劲的功能。而且，我写得非常仓促，写得比较简略，并且，其中我已经看到有许多错别
字了（我用五笔，所以错字让你看不懂），所以，我在这里对我文中的差错表示万分的歉意。
文中所罗列的GDB的功能时，我只是罗列了一些带用的GDB的命令和使用方法，其实，
我这里只讲述的功能大约只占GDB所有功能的60%吧，详细的文档，还是请查看GDB的
帮助和使用手册吧，或许，过段时间，如果我有空，我再写一篇GDB的高级使用。
我个人非常喜欢GDB的自动调试的功能，这个功能真的很强大，试想，我在UNIX下写个
脚本，让脚本自动编译我的程序，被自动调试，并把结果报告出来，调试成功，自动checkin
源码库。一个命令，编译带着调试带着checkin，多爽啊。只是GDB对自动化调试目前支持
还不是很成熟，只能实现半自动化，真心期望着GDB的自动化调试功能的成熟。