亂八七糟的代碼

Basic Sample Senario :

Client 需要一種組件提供一種 FastString類(lèi)， 此類(lèi)具有 int length() 方法

解決方案：

靜態(tài)鏈接 ： 組件廠商將源代碼交給 client ，客戶將組件代碼與client 代碼編譯連接運(yùn)行。 如果組件代碼需要fix bug or update ，則client 端代碼需要重新編譯連接。 而且client軟件的不同實(shí)例使用各自的組件內(nèi)存對(duì)象。

動(dòng)態(tài)鏈接 ： 組件廠商使用DLL形式發(fā)放組件，此時(shí)不同的client實(shí)例可以共享組件在內(nèi)存中的代碼段。

DLL的問(wèn)題：1.導(dǎo)出名稱的問(wèn)題 ： 不同的compiler可以使用不同的mangle name 用來(lái)區(qū)分 c++的函數(shù)，那么使用不同的compiler的client和組件無(wú)法鏈接 （可以使用extern “C”解決全局函數(shù)名的問(wèn)題，使用 .DEF文件解決導(dǎo)出成員函數(shù)的問(wèn)題）

                   2.升級(jí)的問(wèn)題 ：如果組件最初定義為

class FastString
{
    char* m_psz;
public:
    FastString(const char* psz){strcpy(m_psz, psz);}
};

                                          而后廠商更改了組件的實(shí)現(xiàn)

class FastString
{
int newmember;
char* psz;
public:

FastString(const char* psz){strcpy(m_psz, psz);}

}

原來(lái)FastString對(duì)象大小為4字節(jié)，現(xiàn)在變?yōu)?字節(jié)，但是client端按照4字節(jié)分配對(duì)象， dll卻要向后面的4個(gè)字節(jié)存入一個(gè)指針，行為不可預(yù)料！

解決這一問(wèn)題的一種方法便是每次發(fā)布便更改dll的名字，即1.0, 2.0, x.0 等等。但這樣比較弱啊！！

這種問(wèn)題根本原因是啥呢？

class 的關(guān)鍵在于封裝了其中的實(shí)現(xiàn)細(xì)節(jié)，即用戶知道類(lèi)提供了哪些服務(wù)（ public方法）就行了，不需要管類(lèi)的內(nèi)部到底使用了哪些成員變量。這樣一來(lái)，只要接口沒(méi)變（類(lèi)提供功能），user就可以安心的使用任意版本的實(shí)現(xiàn)了。C++怎么不行呢？C++告訴用戶接口的同時(shí)，也告訴了用戶類(lèi)的實(shí)現(xiàn)(對(duì)象布局)。比如類(lèi)對(duì)象有多大啊，每個(gè)成員的偏移啊(具體可以看Inside c++ object model)。知道了這些，客戶端使用接口的代碼就和DLL中的具體實(shí)現(xiàn)緊密的耦合起來(lái)了，杯具 啊~

咋辦呢？ 只要不讓client直接創(chuàng)建FastString就行了，這樣client的代碼就不會(huì)受到FastString實(shí)現(xiàn)變化的影響了。給FastString加一個(gè)Wrapper類(lèi)，內(nèi)部嵌套一個(gè)FastString，所有對(duì)FastString的調(diào)用都foward給內(nèi)部的FastString member, 創(chuàng)建FastString 的任務(wù)在dll方面完成，client只知道Wrapper大小為4個(gè)字節(jié)--指向FastString的指針。這樣問(wèn)題解決了，但是太麻煩了，所有的接口都要包一層!! 而且多了一層調(diào)用!

還有啥辦法么？ 為了保證c++接口類(lèi)實(shí)現(xiàn)二進(jìn)制級(jí)別的兼容只能使用編譯器無(wú)關(guān)的特性：1.假設(shè)復(fù)合類(lèi)型表現(xiàn)形式相同(struct) 2. 傳參順序相同，可以使用指示符指定3.虛函數(shù)調(diào)用機(jī)制相同，即基于 vtbl 和 vptr. 基于這些假設(shè)，我們創(chuàng)建的c++接口類(lèi)所有函數(shù)設(shè)置為虛函數(shù)，那么不同compiler將為客戶端方法調(diào)用產(chǎn)生相同的機(jī)器代碼。定義了接口，便規(guī)定了所有繼承于他的類(lèi)的內(nèi)存結(jié)構(gòu)一定與它兼容。但此時(shí)不能告訴用戶類(lèi)的定義，否則重回上面的老路上了。怎么辦，只有接口客戶無(wú)法創(chuàng)建類(lèi)的定義，只有export一個(gè)創(chuàng)建類(lèi)對(duì)象的函數(shù)客戶了。  同上面的wrapper一樣，創(chuàng)建類(lèi)的操作僅僅在dll內(nèi)部調(diào)用，這意味著實(shí)際建造類(lèi)對(duì)象大小和布局的代碼與編譯實(shí)現(xiàn)類(lèi)的方法的代碼使用同樣的編譯器創(chuàng)建 （即ctor和call ctor的代碼由同一編譯器同時(shí)編譯）。由于虛析構(gòu)函數(shù)在vtbl的位置與compiler相關(guān)，所以不能把它設(shè)置為虛函數(shù)，只有顯示增加一個(gè)Delete函數(shù)完成析構(gòu)工作。

OK，當(dāng)前我們得到的DLL中只有創(chuàng)建類(lèi)對(duì)象的函數(shù)需要用extern “C”export 給客戶，其他的接口中的虛函數(shù)是通過(guò)虛表訪問(wèn)的，無(wú)需靠符號(hào)名字鏈接。

進(jìn)一步的，如果我們要給接口增加一個(gè)功能呢？ 如果直接在現(xiàn)有接口中方法聲明后加入新的方法，那么此方法會(huì)出現(xiàn)在vtbl的最后一欄，舊的client不會(huì)調(diào)用新方法，但是如果新的client訪問(wèn)老的對(duì)象呢? 不幸的事情發(fā)生了！ 這樣做的問(wèn)題在于，修改公開(kāi)的接口就打破了對(duì)象的封裝性。

那么增加接口功能只能通過(guò)設(shè)計(jì)一個(gè)接口繼承另一個(gè)接口，或者讓類(lèi)繼承多個(gè)接口來(lái)實(shí)現(xiàn)了。客戶可以在運(yùn)行時(shí)通過(guò)RTTI來(lái)詢問(wèn)對(duì)象，支持這個(gè)功能不，親？然而 ，RTTI也是一個(gè)compiler相關(guān)的東東，好吧，我們讓每個(gè)類(lèi)自己實(shí)現(xiàn)RTTI，也就是實(shí)現(xiàn)一個(gè)dynamic_cast 方法， 用來(lái)將自己cast成為自己實(shí)現(xiàn)的接口，如果不支持則返回 0 。

例如：

void* CFastString::Dynamic_Cast(const char* pszTypename)
{
void * pRev;
if(strcmp(pszTypename, "IFastString") == 0)
{
pRev = static_cast<IFastString*>(this);
}
else if(strcmp(pszTypename , "IOut") == 0)
{
pRev = static_cast<IOut*>(this);
}
else if(strcmp(pszTypename , "IExtent") == 0)
{
pRev = static_cast<IFastString*>(this);
}
else
{
return 0;
}

return pRev;
}

注意cast到IExtent的時(shí)候用了IFastString，因?yàn)镮FastString 和 IOut都是從IExtent繼承的，寫(xiě)IExtent的話不知道用哪個(gè)，用虛擬繼承可以使CFastString對(duì)象只有一份IExtent，為啥不用呢？ 你懂得。。。跟前面答案一樣，編譯器相關(guān)。

最后一個(gè)問(wèn)題是delete的問(wèn)題，用戶需要記得為每一個(gè)對(duì)象調(diào)用一次delete方法，而指針cast來(lái)cast去，想記得對(duì)象被delete沒(méi)有很難啊！ 怎么辦？ 用引用計(jì)數(shù)吧，把每個(gè)指針當(dāng)做具有生命周期的實(shí)體，創(chuàng)建時(shí)候計(jì)數(shù)++，銷(xiāo)毀時(shí)候--，等到0的時(shí)候就delete對(duì)象。

大功告成，通過(guò)vptr和vtbl的二進(jìn)制防火墻，我們做到了可重用的二進(jìn)制組件，組件變化客戶無(wú)需重新編譯 。

什么時(shí)候用memory-mapped files:

1.System use it to load and execute .exe and dll files.

2.Use memory-mapped files to access a data file on disk.

3.allow multiple processes running on the same machine to share data with each other.

------------------------------------------------------------------------------------------------------

用途一：使用mapping file executables and dlls

當(dāng)調(diào)用createProcess時(shí)候，系統(tǒng)做了以下的事情:

1.locates CreateProcess 中指定的the .exe file，失敗則return false

2.創(chuàng)建新的process kernel object

3.creates a private address space for new process

4.reserves a region of address space large enough to contain the .exe file.The desired location of this region is specified by the .exe file itself.by default ,base address is 0x00400000 .You can change it by create your app .exe fiel using linker’s /BASE option.

5.the systems notes that the physical storage baking the reserved region is in the .exe file on disk instread of the system’s paging file.(系統(tǒng)注意到，支持已保留區(qū)域的物理存儲(chǔ)區(qū)域是在磁盤(pán)上的.exe 文件而不是在系統(tǒng)頁(yè)面中)

當(dāng)。exe 被mapped into the process address space，系統(tǒng)訪問(wèn).exe的一個(gè)區(qū)域，那里列出了.exe含有的dll，然后系統(tǒng)利用 LoadLibrary for each dlls。系統(tǒng)map dll時(shí)候，如果dll的 preferred base address 被占據(jù)或者不夠大，dllwill try to find another region of address space to reserve for the dll。如果dll 被設(shè)定了/Fixed when it build,也就是不支持重定位，那么加載失敗。

如果加載dll或者exe 失敗，彈出對(duì)話框并且釋放申請(qǐng)的地址空間。

after all .exe  dll mapped into the process address space, system can begin exec the .exe file starup code. the sys takes care of all paging,buffering, and caching. 例如，如果一段代碼訪問(wèn)了一個(gè)并不在主存的地址，那么一個(gè)錯(cuò)誤產(chǎn)生，系統(tǒng)察覺(jué)到錯(cuò)誤并且自動(dòng)的調(diào)入page of code from the files image into a page of RAM。

the sys maps the page of ram to the proper location in the process address and allows the thread  to continue.

當(dāng)為一個(gè)app創(chuàng)建第二個(gè)實(shí)例時(shí)，系統(tǒng)只是簡(jiǎn)單的打開(kāi)另外一個(gè)memory-mapped view  of file-mapping object that identifies the exec files image and create a new process object and a new thread object.利用內(nèi)存映射文件，多個(gè)實(shí)例可以共享代碼和數(shù)據(jù)。實(shí)際上，file 是分為多個(gè)section ，多個(gè)節(jié)均對(duì)齊于頁(yè)邊界。如果一個(gè)instance of the app 修改了全局變量，系統(tǒng)應(yīng)用了copy-on-write 機(jī)制，復(fù)制修改的頁(yè)面，并更新實(shí)例的file-mapping view。當(dāng)我們調(diào)試程序時(shí)同樣的事情會(huì)發(fā)生，debuger modify code，sys use cow again。

當(dāng)一個(gè)進(jìn)程被加載，系統(tǒng)檢查其所有映射文件頁(yè),系統(tǒng)將所有通常用cow保護(hù)的頁(yè)面提交給存儲(chǔ)系統(tǒng)，這些頁(yè)面僅僅是被提交，當(dāng)文件被訪問(wèn)的時(shí)候，系統(tǒng)讀入相應(yīng)的頁(yè)面，如果頁(yè)面沒(méi)有被修改，那么他們可以被換出，如果已經(jīng)修改，系統(tǒng)將修改過(guò)的頁(yè)面轉(zhuǎn)入已經(jīng)提交的頁(yè)面之一(這點(diǎn)很晦澀啊 system swaps the modified page to one of the perviously committed pages in the paging file ,怎么翻譯呢~~~~ ：（   )

------------------------------------------------------------------------------------------------------

在可執(zhí)行文件或者dll中共享靜態(tài)變量

------------------------------------------------------------------------------------------------------

內(nèi)存映射數(shù)據(jù)文件

例子：要把一個(gè)文件所有字節(jié)倒置

如果利用file mapping 我們告訴系統(tǒng)使用一個(gè)虛擬空間的區(qū)域來(lái)倒置文件，然后告訴把文件的第一個(gè)字節(jié)映射到保留空間的第一個(gè)字節(jié)，然后就像處理內(nèi)存中的字符串一樣處理文件即可，引文系統(tǒng)會(huì)幫助你完成文件緩存以及調(diào)頁(yè)等工作。

使用流程：

1.創(chuàng)建一個(gè)file kernel object that identifies the file on disk that you want to use as a memory –mapped file

2.創(chuàng)建一個(gè)file mapping kernel object 告訴系統(tǒng)文件的大小，以及你準(zhǔn)備如何訪問(wèn)文件

3.告訴系統(tǒng)map all或者部分文件到你的進(jìn)程地址空間

當(dāng)使用結(jié)束后要：

1告訴系統(tǒng) unmap file-mapping kernel object form your process add

2cloes filemapping kernel object

3close file kernel object

---------

具體步驟

--1. 創(chuàng)建文件內(nèi)核對(duì)象

CreateFile

失敗返回 INVALID_HANDLE_VALUE = –1 一般來(lái)說(shuō)windows func 失敗return null這個(gè)比較特殊

createfile dwdesiredAccess 需要設(shè)置為 GENERIC_READ 或者 GENERIC_WRITE 

--2. 創(chuàng)建file-mapping 內(nèi)核對(duì)象

CreatefileMapping(HANDLE,PSECURITY_ATTRIBUTES,DWORD fdwProtect,DWORD dwMaximumsizeHigh,DWORD dwMaximumSizeLow,PCTSTR pszName);

第一個(gè)參數(shù)使用createfile 返回的handle。psa一般使用默認(rèn)null。當(dāng)創(chuàng)建一個(gè)file mapping object 時(shí)候，系統(tǒng)并不會(huì) 馬上保留一個(gè)地址空間，然后將file映射到這個(gè)區(qū)域。但很i，當(dāng)系統(tǒng)map時(shí)候，系統(tǒng)必須知道為physical storage分配什么樣的保護(hù)屬性，第三個(gè)參數(shù)指明了這些。

后面兩個(gè)參數(shù)指明file的大小，ensure  enouth physical storage is available for the file-mapping object.

high指明高32位，low指明低32位。如果想創(chuàng)建一個(gè)反應(yīng)現(xiàn)在文件大小的map，均傳0.

pszName 用于與其它進(jìn)程共享內(nèi)存映射文件

--3.將文件數(shù)據(jù)map to process address space

使用這個(gè)函數(shù)

PVOID MapViewOfFile(HANDLE hfileMappingObject,dwDesireaccess,dwFileOffsetHigh,dwFileOffsetLow,dwNumberOfbytestomap)

文件沒(méi)必要一次全映射，一次映射一部分，這一部分成為一個(gè)view

首先通過(guò)high和low 指定開(kāi)始映射的字節(jié)

其次是指定映射多大，0則映射到文件尾部。

--4.unmapping the file data from the process address space

UnmapviewOfFile(PVOID pvBaseAdddress);

參數(shù)使用mapview的返回值

如果強(qiáng)制write back to disk 則使用 FlushViewOfFile(PVOID pvAddress,SIZE_T dwNumberOfBytesToFlush)

第一個(gè)地址是想要開(kāi)始flush的地址

--5.關(guān)閉filemapping object 以及file object

-----------------------------------------------------------------------------------

使用filemap 在進(jìn)程之間共享數(shù)據(jù)

例子：

app開(kāi)始時(shí)候，系統(tǒng)調(diào)用createfile to open .exe file onthe disk。sys call creatFileMapping to create filemapping object.然后系統(tǒng)調(diào)用  mapviewofffileEX (with sec_image flag to point out it is a pe file),So that the file’s image is mapped to the address of the first byte of exectuable code of this mapped view. System creates the primary thread , puts the address of the first byte of exec code of this mapped view in the thread instruction pointer,and then lets the cpu start exec the code.

If user 再啟動(dòng)同一個(gè)app，sys 看到file-mapping已經(jīng)存在了，系統(tǒng)maps a view of file a second time，this time in the context of the newly created process address space.

像所有內(nèi)核對(duì)象一樣，有三種方法共享他，繼承，命名對(duì)象以及賦值handle。

···頁(yè)文件支持的內(nèi)存映射文件

許多應(yīng)用程序運(yùn)行是產(chǎn)生數(shù)據(jù)需要和其他進(jìn)程共享如果必須在硬盤(pán)建立文件才可以共享，那么效率很低。因此微軟提供了由system paging file 支持的 file mapping。不需要createfile ，只需要在調(diào)用createFilemapping 的時(shí)候傳進(jìn)一個(gè) INVALID_HANDLE_VALUE 作為hFile 參數(shù)即可。 映射文件大小同樣是由high 和low 參數(shù)決定的。

`````稀疏提交的內(nèi)存映射文件

--看來(lái)需要把虛擬內(nèi)存那章一起看看了~~~~

A 簡(jiǎn)單的模擬 ,不過(guò)我寫(xiě)的很麻煩

Problem

On Unix computers, data is stored in directories. There is one root directory, and this might have several directories contained inside of it, each with different names. These directories might have even more directories contained inside of them, and so on.

A directory is uniquely identified by its name and its parent directory (the directory it is directly contained in). This is usually encoded in a path, which consists of several parts each preceded by a forward slash ('/'). The final part is the name of the directory, and everything else gives the path of its parent directory. For example, consider the path:

/home/gcj/finals

To create a directory, you can use the mkdir command. You specify a path, and thenmkdir will create the directory described by that path, but only if the parent directory already exists. For example, if you wanted to create the "/home/gcj/finals" and "/home/gcj/quals" directories from scratch, you would need four commands:

mkdir /home
mkdir /home/gcj
mkdir /home/gcj/finals
mkdir /home/gcj/quals

Given the full set of directories already existing on your computer, and a set of new directories you want to create if they do not already exist, how many mkdir commands do you need to use?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with a line containing two integers N and M, separated by a space.

The next N lines each give the path of one directory that already exists on your computer. This list will include every directory already on your computer other than the root directory. (The root directory is on every computer, so there is no need to list it explicitly.)

The next M lines each give the path of one directory that you want to create.

Each of the paths in the input is formatted as in the problem statement above. Specifically, a path consists of one or more lower-case alpha-numeric strings (i.e., strings containing only the symbols 'a'-'z' and '0'-'9'), each preceded by a single forward slash. These alpha-numeric strings are never empty.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of mkdir you need.

Limits

1 ≤ T ≤ 100.
No path will have more than 100 characters in it.
No path will appear twice in the list of directories already on your computer, or in the list of directories you wish to create. A path may appear once in both lists however. (See example case #2 below).
If a directory is listed as being on your computer, then its parent directory will also be listed, unless the parent is the root directory.
The input file will be no longer than 100,000 bytes in total.

Small dataset

0 ≤ N ≤ 10.
1 ≤ M ≤ 10.

Large dataset

0 ≤ N ≤ 100.
1 ≤ M ≤ 100.

Sample

Input
Output

3
0 2
/home/gcj/finals
/home/gcj/quals
2 1
/chicken
/chicken/egg
/chicken
1 3
/a
/a/b
/a/c
/b/b

Gluk的解法:

 set <string> S;
        REP (i, n)
        {
            string s;
            cin >> s;
            S.insert(s);//已有的路徑用set表示
        }

        int res =0 ;

        REP (i, m)
        {
            string s;
            cin >> s;
            vector <string> ss;
            REP (j, s.size())
                if(s[j] == '/')
                    s[j] = ' ';//用空格替換’/’，然后使用istringstream分隔各級(jí)目錄
            istringstream iss (s);
            while (iss >> s) {
                ss.pb (s);
            }

            s = "";
            REP (i, ss.size ())
            {
                s = s+"/"+ss[i];
                if (S.find(s) == S.end())//依次加入各級(jí)目錄，/a  /a/b  /a/b/c 增加遞增的所有目錄
                {
                    res ++;
                    S.insert(s);
                }
            }
        }

題目中的這一句

If a directory is listed as being on your computer, then its parent directory will also be listed, unless the parent is the root directory.

告訴我們?nèi)绻?a/b被list存在，那么/a也一定被list出來(lái)了 ，所以上面代碼可以不去分隔處理已經(jīng)給出的目錄

yuhch123的解法

struct node {
   map <string, node *> sons;//每個(gè)節(jié)點(diǎn)，用map實(shí)現(xiàn)兒子節(jié)點(diǎn)
};
node *root;//一個(gè)根節(jié)點(diǎn)
int T;
int N, M;
char tmp[100005];
int ans = 0;
void insert(node *cnt, char *tmp) {//在節(jié)點(diǎn)cnt處，插入tmp子樹(shù)
   int i;
   if (tmp[0] == 0)//為空則返回
      return;
   assert(tmp[0] == '/');
   string str;
   for (i = 1; tmp[i] != '/' && tmp[i] != 0; i ++)//第一層
      str += tmp[i];
   if (cnt -> sons.find(str) == cnt -> sons.end()) {//如果沒(méi)有這子樹(shù)，則創(chuàng)建子樹(shù)
      ans ++;//需要一次mkdir 
      struct node *tmp2 = new node();
      cnt -> sons[str] = tmp2;
   }
   insert(cnt -> sons[str], tmp + i);// 遞歸創(chuàng)建子樹(shù)
}
int main() {
   int i;
   int Case = 1;
   scanf("%d", &T);
   while (T --) {
      scanf("%d%d", &N, &M);
      root = new node();
      for (i = 0; i < N; i ++) {
     scanf("%s", tmp);
     insert(root, tmp);
      }
      ans = 0;
      for (i = 0; i < M; i ++) {
     scanf("%s", tmp);
     insert(root, tmp);
      }
      printf("Case #%d: %d\n", Case ++, ans);
   }
   return 0;
}

neal.wu的解法

vector <string> parse (string s)
{
    vector <string> v;
    string next = "";
    
    for (int i = 0; i < (int) s.length (); i++)
    {
        next += s [i];
        
        if (i + 1 == (int) s.length () || s [i + 1] == '/')
        {
            v.push_back (next);
            next = "";
        }
    }
    
    return v;
}

set <string> direc;

int insert (vector <string> v)
{
    int count = 0;
    string s = "";
    
    for (int i = 0; i < (int) v.size (); i++)
    {
        s += v [i];
        count += direc.insert (s).second ? 1 : 0; //set返回一個(gè)pair<iterator,bool> bool指示插入是否成功   

 }
    
    return count;
}

int main ()
{
             freopen("d:\\input.txt","r",stdin);
  
    for (scanf ("%d", &T); TC <= T; TC++)
    {
        scanf ("%d %d", &N, &M);
        direc.clear ();
        int make = 0;
        char str [1000];
        
        for (int i = 0; i < N; i++)
        {
            do gets (str); while (strlen (str) == 0);//do gets 過(guò)濾回車(chē)空字符串
            insert (parse (str));
        }
        
        for (int i = 0; i < M; i++)
        {
            do gets (str); while (strlen (str) == 0);
            make += insert (parse (str));
        }
        
        printf ("Case #%d: %d\n", TC, make);
    }
    
    //system ("pause");
    return 0;
}

ploh的解法:

int main(void)
{freopen("d:\\input.txt","r",stdin);
  int T; cin >> T;
  for (int t = 1; t <= T; t++) {
    int ans = 0;
    set <string> have, want;
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
      string path; cin >> path;
      have.insert(path);
    }
    for (int i = 0; i < M; i++) {//用一個(gè)set保存所有需要加入的
      string path; cin >> path;
      want.insert(path);
      for (int j = 1; j < path.length(); j++)
    if (path[j] == '/')
      want.insert(path.substr(0, j));
    }
    for (set <string>::iterator it = want.begin(); it != want.end(); it++)//遍歷所有需要加入的，然后看是否存在
      if (!have.count(*it))
    ans++;
    printf("Case #%d: %d\n", t, ans);
  }
}

這學(xué)期也開(kāi)始了好久，總結(jié)下。

項(xiàng)目上：基本弄完了碼頭，算是結(jié)束了吧，剩下的工作是好好總結(jié)下學(xué)到的東西，把架構(gòu)，用到的技術(shù)都理順了，方便之后面試回答。

生活上：這半個(gè)月gf生病了，嘉定閔行兩頭跑果然很累，不過(guò)還好一直抽空看書(shū)。健康很重要~~ 要抓緊鍛煉身體了。本錢(qián)一定要掌握好。

找實(shí)習(xí)：先后筆試了摩根it和微軟。上周摩根給了電面，全英文的。完全沒(méi)有思想準(zhǔn)備的我正在在閔行g(shù)f那里照顧她，手邊什么書(shū)也沒(méi)有，項(xiàng)目資料也沒(méi)有，我的處女面就這樣“裸著”度過(guò)了，到現(xiàn)在還沒(méi)有消息，也不知道是不是默劇了。 微軟是上周六筆試的，也沒(méi)有消息，sigh~不知道是沒(méi)改完卷子還是杯具了~~

關(guān)于實(shí)習(xí)的筆試和面試要專(zhuān)門(mén)寫(xiě)東西總結(jié)一下，方便以后查閱。

1-4號(hào)放假，應(yīng)該不會(huì)有新的安排進(jìn)來(lái)（面試之類(lèi)的），得安排下事情

上周把大話設(shè)計(jì)模式翻了一遍，利用這幾天要仔細(xì)的重新過(guò)一遍，每一個(gè)模式都寫(xiě)代碼實(shí)踐一下。

然后想看看c++標(biāo)準(zhǔn)文檔，這個(gè)會(huì)很慢，可以選擇性的跳過(guò)一些東西，總共700多頁(yè)，看前300頁(yè)就可以了，后面是介紹庫(kù)的。一天看75頁(yè)，恩 ···比較困難·· 盡力吧

其他的就不安排了，也做不完的。

另外，之后學(xué)的東西，一定要及時(shí)用日志記下來(lái)，否則時(shí)間長(zhǎng)了還要從頭學(xué)起`````

良好的編程風(fēng)格是：new和delete 配套使用，即如果使用new [] 則使用delete []

事實(shí)上，如果我們使用的是自定義類(lèi)型int char等，或者我們使用的是沒(méi)有內(nèi)存申請(qǐng)的類(lèi)，我們使用 delete A;并不會(huì)發(fā)生什么不好的事情。

這是由delete 的語(yǔ)義決定的。當(dāng)我們是申請(qǐng)一組對(duì)象時(shí)候，編譯器會(huì)加入內(nèi)存大小信息和此段內(nèi)存相關(guān)聯(lián)。因此當(dāng)我們delte A 時(shí)，編譯器會(huì)按照內(nèi)存大小收回分給我們的內(nèi)存。顯然，如果是基本類(lèi)型或者沒(méi)有申請(qǐng)內(nèi)存的情況這樣的行為是良好的。但是如果我們?cè)谧越?lèi)型中申請(qǐng)了內(nèi)存~對(duì)不起，編譯器是不知道的，這些申請(qǐng)的內(nèi)存就是內(nèi)存泄露，隨著程序不斷進(jìn)行，堆不斷地被侵蝕·····

這就是delete的第二個(gè)作用，他會(huì)施加析構(gòu)函數(shù)在我們申請(qǐng)的內(nèi)存上，如果我們delete A，只會(huì)在第一個(gè)上施加，而如果delete [] A;他會(huì)對(duì)數(shù)組中每一個(gè)元素進(jìn)行析構(gòu)~~

so····

試驗(yàn)很容易做，寫(xiě)兩個(gè)類(lèi)，一個(gè)申請(qǐng)內(nèi)存，一個(gè)普通的類(lèi)，然后循環(huán)申請(qǐng)大量數(shù)組，但是用 delete A 形式，然后看看內(nèi)存占用就行了

數(shù)據(jù)對(duì)齊：是指數(shù)據(jù)所在的內(nèi)存地址必須是該數(shù)據(jù)長(zhǎng)度的整數(shù)倍。處理器可以直接訪問(wèn)對(duì)齊的數(shù)據(jù)，而訪問(wèn)未對(duì)齊的數(shù)據(jù)會(huì)在內(nèi)部進(jìn)行一系列的調(diào)整，雖然可以正常處理，但是會(huì)降低運(yùn)行速度。例如一個(gè)處理器總線寬度為64位，那么地址必須為8的倍數(shù)，也就是一次取出8個(gè)字節(jié)。如果我們可以保證所有double地址都為8的倍數(shù)，那么可以用一個(gè)存儲(chǔ)器操作來(lái)讀或者寫(xiě)double了，否則我們可能需要執(zhí)行兩次存儲(chǔ)器訪問(wèn)，因?yàn)閷?duì)象可能位于兩個(gè)8字節(jié)存儲(chǔ)器塊中

對(duì)于結(jié)構(gòu)體也是一樣的例如 struct s2{int i;int j;char c;}; 如果我們把這個(gè)結(jié)構(gòu)打包成9個(gè)字節(jié)，只要保證起始地址滿足4的對(duì)齊要求我們就可以保證i j的對(duì)齊，不過(guò)如果我們聲明了一個(gè)數(shù)組，那么元素地址成為 xd,xd+9,xd+18,xd+27 不滿足對(duì)齊了。因此我們呢要分配12個(gè)字節(jié)給這個(gè)結(jié)構(gòu)體

更進(jìn)一步 ：

未對(duì)齊的數(shù)據(jù)會(huì)以不同方式給cpu帶來(lái)麻煩~

1.如果一個(gè)變量被劃分到兩個(gè)緩存行，那么我們需要訪問(wèn)兩個(gè)緩存行才可以。

2.一些simd指令總是要求對(duì)齊的指令，對(duì)于未對(duì)齊的指令，數(shù)據(jù)對(duì)齊也會(huì)影響這些指令的使用。

Drainage Ditches
Hal Burch

Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.

Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network. Note however, that there can be more than one ditch between two intersections.

Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

PROGRAM NAME: ditch

INPUT FORMAT

Line 1:
Two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream.

Line 2..N+1:
Each of N lines contains three integers, S<sub>i</sub>, E<sub>i</sub>, and C<sub>i</sub>. S<sub>i</sub> and E<sub>i</sub> (1 <= S<sub>i</sub>, E<sub>i</sub> <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from S<sub>i</sub> to E<sub>i</sub>. C<sub>i</sub> (0 <= C<sub>i</sub> <= 10,000,000) is the maximum rate at which water will flow through the ditch.

SAMPLE INPUT (file ditch.in)

5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

OUTPUT FORMAT

One line with a single integer, the maximum rate at which water may emptied from the pond.

SAMPLE OUTPUT (file ditch.out)

50

最基本的網(wǎng)絡(luò)流

   1:  #include<iostream>

   2:  #include<fstream>

   3:  #include<string>

   4:  #include<vector>

   5:  #include<map>

   6:  #include<algorithm>

   7:  #include<sstream>

   8:  #include <cstring>

   9:  #include <queue>

  10:  using namespace std;

  11:  const int MAXN = 220;

  12:  const int infi = 0x7FFFFFFF;

  13:   int capacity[MAXN][MAXN], prenode[MAXN], flow[MAXN];

  14:   queue<int> mq; 

  15:   

  16:  int start, end, N;

  17:  void init(){

  18:      freopen("ditch.in","r",stdin);

  19:      //freopen("e:\\usaco\\ditch.in","r",stdin);

  20:      start = 1;  

  21:      scanf("%d %d",&N,&end); int c, s, t;

  22:      memset(capacity,0,sizeof(capacity));

  23:      for(int i=0;i<N;i++)

  24:      {

  25:          scanf("%d %d %d",&c,&s,&t);

  26:          capacity[c][s] += t; //兩個(gè)節(jié)點(diǎn)間不只有一條路

  27:      } 

  28:  }

  29:  int bfs(){//尋找增廣路徑

  30:      while(!mq.empty()) mq.pop(); 

  31:      mq.push(start);  //源節(jié)點(diǎn)入隊(duì)

  32:      //memset(flow,0,sizeof(flow));

  33:      memset(prenode,-1,sizeof(prenode)); //重置前向節(jié)點(diǎn)

  34:      prenode[start] = 0; flow[start]=infi; //源節(jié)點(diǎn)流量無(wú)限大

  35:      while(!mq.empty()){

  36:          int cur = mq.front(); 

  37:          mq.pop();

  38:          if(cur == end) break; //到達(dá)匯點(diǎn)結(jié)束路徑 

  39:          for(int i=1;i<=end;i++){ 

  40:              if(prenode[i]==-1 && capacity[cur][i]) //訪問(wèn)當(dāng)前節(jié)點(diǎn)所有未訪問(wèn)的相鄰節(jié)點(diǎn)，更新flow

  41:              {

  42:                  prenode[i] = cur;

  43:                  flow[i] = (flow[cur]<capacity[cur][i]?flow[cur]:capacity[cur][i]);

  44:                  mq.push(i);

  45:              }

  46:          }

  47:      }

  48:      if(prenode[end]==-1)  //如果未找到增廣路徑返回-1

  49:          return -1;

  50:      return flow[end];

  51:  }

  52:  int Edmonds_Karp(){

  53:      int total = 0, pathcapacity;//pathcapacity 路徑增加量

  54:      while((pathcapacity = bfs()) != -1){//可以找到增廣路徑時(shí)候進(jìn)行循環(huán)

  55:          int cur = end;    //從匯點(diǎn)開(kāi)始增加逆向節(jié)點(diǎn)

  56:          while( cur != start ){

  57:              int t = prenode[cur] ;

  58:              capacity[t][cur] -= pathcapacity;

  59:              capacity[cur][t] += pathcapacity;

  60:              cur = t;

  61:          }

  62:          total += pathcapacity;//max_flow

  63:      }

  64:      return total;

  65:  }

  66:  void output(){

  67:      freopen("ditch.out","w",stdout);

  68:      //freopen("c:\\usaco\\ditch.out","w",stdout);

  69:      cout<<Edmonds_Karp()<<endl;

  70:  } 

  71:     int main()

  72:  {

  73:      init();  

  74:      output();

  75:      return 0;

  76:  }

標(biāo)程：使用貪心法，尋找一條增廣路徑的時(shí)候不斷尋找cap最大的，未被訪問(wèn)的節(jié)點(diǎn)mloc；然后更新跟mloc相鄰的節(jié)點(diǎn)flow以

及prenode信息.最后當(dāng)運(yùn)行到end時(shí)候，更新路徑節(jié)點(diǎn)capacity，同時(shí)增加max_flow.重復(fù)上述過(guò)程直到找不到增廣路徑

   1:  #include <stdio.h>

   2:  #include <string.h>

   3:   

   4:  #define MAXI 200

   5:   

   6:  /* total drain amount between intersection points */

   7:  int drain[MAXI][MAXI];

   8:  int nint; /* number of intersection points */

   9:   

  10:  int cap[MAXI]; /* amount of flow that can get to each node */

  11:  int vis[MAXI]; /* has this node been visited by Dijkstra's yet? */

  12:  int src[MAXI]; /* the previous node on the path from the source to here */

  13:   

  14:  int augment(void)

  15:   { /* run a Dijkstra's varient to find maximum augmenting path */

  16:    int lv;

  17:    int mloc, max;

  18:    int t;

  19:   

  20:    memset(cap, 0, sizeof(cap));

  21:    memset(vis, 0, sizeof(vis));

  22:   

  23:    cap[0] = 2000000000;

  24:    while (1)

  25:     {

  26:      /* find maximum unvisited node */

  27:      max = 0;

  28:      mloc = -1;

  29:      for (lv = 0; lv < nint; lv++)

  30:        if (!vis[lv] && cap[lv] > max)

  31:         {

  32:          max = cap[lv];

  33:      mloc = lv;

  34:         }

  35:      if (mloc == -1) return 0;

  36:      if (mloc == nint-1) break; /* max is the goal, we're done */

  37:   

  38:      vis[mloc] = -1; /* mark as visited */

  39:   

  40:      /* update neighbors, if going through this node improves the

  41:         capacity */

  42:      for (lv = 0; lv < nint; lv++)

  43:        if (drain[mloc][lv] > cap[lv] && max > cap[lv])

  44:         {

  45:          cap[lv] = drain[mloc][lv];

  46:      if (cap[lv] > max) cap[lv] = max;

  47:      src[lv] = mloc;

  48:         }

  49:     }

  50:    max = cap[nint-1];

  51:   

  52:    /* augment path, starting at end */

  53:    for (lv = nint-1; lv > 0; lv = src[lv])

  54:     {

  55:      t = src[lv];

  56:      drain[t][lv] -= max;

  57:      drain[lv][t] += max;

  58:     }

  59:    return max;

  60:   }

  61:   

  62:  int main(int argc, char **argv)

  63:   {

  64:    FILE *fout, *fin;

  65:    int lv;

  66:    int num;

  67:    int p1, p2, c;

  68:   

  69:    if ((fin = fopen("ditch.in", "r")) == NULL)

  70:     {

  71:      perror ("fopen fin");

  72:      exit(1);

  73:     }

  74:    if ((fout = fopen("ditch.out", "w")) == NULL)

  75:     {

  76:      perror ("fopen fout");

  77:      exit(1);

  78:     }

  79:   

  80:    fscanf (fin, "%d %d", &num, &nint);

  81:    while (num--)

  82:     {

  83:      fscanf (fin, "%d %d %d", &p1, &p2, &c);

  84:      p1--;

  85:      p2--;

  86:      drain[p1][p2] += c; /* note += handles two ditches between same points */

  87:     }

  88:   

  89:    /* max flow algorithm: augment while you can */

  90:    c = 0;

  91:    while ((p1 = augment()))

  92:      c += p1;

  93:    fprintf (fout, "%d\n", c);

  94:    return 0;

  95:   }

最后一章~~拖了幾天，得趕緊記下了~~

名字： On the cusp of the object model

7.1 Template

Template用的很少，這節(jié)中的有些東西比較晦澀，挑一些能理解的記下吧。剩下的等用的多了再回頭來(lái)看。

Template的具現(xiàn)行為 template instantiation

Template <calss T>class Point{

  public: enum Status{unallocated,normalized};Point(T x=0.0,T y=0.0);

~Point() ; void * operator new(size_t);private:static Point<T> *freelist

static int chunksize; T _x,_y;

};

編譯器看到這樣的聲明，會(huì)有什么動(dòng)作？？

沒(méi)有。static data 不可用 enum 不可用 ，enum雖然類(lèi)型固定，但他只能和template point class 的某個(gè)實(shí)體來(lái)存取或操作。我們可以 point<float>::Status s;

但是不能 point::status s; 因此我們可能想把enum抽離到一個(gè)非模板類(lèi)以避免多重拷貝。同樣道理，freelist 和chunksize對(duì)于程序而言也不可用。必須明確指定point<float>::freelist.也就是說(shuō)靜態(tài)數(shù)據(jù)成員是和特定類(lèi)型的類(lèi)綁定的而不是泛型的模板類(lèi)。但是如果定義一個(gè)指針不一定會(huì)具現(xiàn)出相應(yīng)的類(lèi)，因?yàn)橐粋€(gè)指針，并不一定指向一個(gè)class object。編譯器不需要知道該class 相應(yīng)的任何member 或者數(shù)據(jù)或者

內(nèi)存布局，所以沒(méi)有必要具現(xiàn)。但是如果是定義并初始化一個(gè)引用就真的會(huì)具現(xiàn)出一個(gè)實(shí)體，因?yàn)椴淮嬖诳找谩?/font>

成員函數(shù)并不應(yīng)該被實(shí)體化，只有當(dāng)他被調(diào)用的時(shí)候才需要被具現(xiàn)出來(lái)。

template<class T>

class mumble{

public: Muble(T t=1024):tt(t){ if(tt!=t)throw ex; }

private: T tt;

};

上面的模板中出現(xiàn)錯(cuò)誤有，t=1024 不一定成功，!= 不一定定義

這兩個(gè)錯(cuò)誤只有到具現(xiàn)操作結(jié)合具體類(lèi)型才能確定出來(lái)

編譯器面對(duì)一個(gè)template聲明，在他被一組實(shí)際參數(shù)具現(xiàn)之前，只能實(shí)行以有限地錯(cuò)誤檢查，只有特定實(shí)體定義之后，才會(huì)發(fā)現(xiàn)一些與語(yǔ)法無(wú)關(guān)的但是十分明顯的錯(cuò)誤，這是技術(shù)上的一大問(wèn)題。

Template 的名稱決議方式

.h文件定義

void out(int x){
    cout<<"out_by_class_define_scrope"<<endl;
}
template <class type>
class A{
public:
    void test1(){
        out(m1);
    }
    void test2(){
        out(m2);
    }
private:
    int m1;
    type m2;
};

.cpp文件定義

void out(double x){
    cout<<"out_by_class_instantiation_scrope"<<endl;
}

int main(）
{    
    A<double> a;
    a.test1();
    a.test2();

}

按照書(shū)中的說(shuō)法，如果一個(gè)函數(shù)，參數(shù)類(lèi)型和type無(wú)關(guān)的話，應(yīng)該取他的scope of template declaration中定義的函數(shù)，而反之取在他的instantiation中的那個(gè)。事實(shí)上在測(cè)試中發(fā)現(xiàn)

MSVC 中 ，函數(shù)定義的決議是依照類(lèi)型的，如果有合適的函數(shù)比如type是double，此時(shí)如果定義處或者具現(xiàn)處有double型的函數(shù)定義，那么函數(shù)就會(huì)決議為那一個(gè)定義的~~~

MEMber function的具現(xiàn)行為：

編譯器如何確保只有一個(gè)vtable產(chǎn)生？ 一種方法是 每一個(gè)virtual func地址都放在vtable中，如果取得函數(shù)地址，則表示virtual func 的定義必然出現(xiàn)在程序的某個(gè)地點(diǎn)，否則程序無(wú)法連接成功。此外該函數(shù)只能有一個(gè)實(shí)體，否則也是連接不成功。那么，就把vtable放在定義了該class的第一個(gè)non-inline，nonpure virtual function的文件中吧。。（not so clear）

在實(shí)現(xiàn)層面上，template 似乎拒絕全面自動(dòng)化，以手動(dòng)方式在個(gè)別的object module中完成預(yù)先的具現(xiàn)工作是一種有效率的方法。