1.1　編　程　技　巧

本節介紹一些在使用C＋＋語言進行代碼編寫以及調試時可能用到的技巧以及常見問題。

1.1.1　排序性能問題

相對于C語言內置的qsort函數，C＋＋中提供的sort函數使用起來更加方便，不需要做指針類型轉換。sort有兩種用法：第一種是傳入一個functor對象，另外一種是直接傳入一個排序函數，而筆者發現這兩種用法語義上都是正確的，但是筆者實際測試發現使用functor的版本比直接使用函數的版本快不少，測試代碼如下：

筆者的機器上測試發現，STL的sort使用functor的版本是最快的，比qsort都快一倍多。而使用sort傳入函數指針的版本速度是最慢的，相對于前兩者有大約6倍和3倍的差距，會在一些對排序性能要求很高的題目中形成比較明顯的瓶頸，提醒讀者注意。

1.1.2　整數輸入

最經常輸入的數據類型就是int，經常需要輸入之后直接插入到一個集合或者數組中，一般的做法是建立一個臨時變量，使用cin或者scanf輸入之后，再將這個臨時變量插入到集合中。這樣稍顯煩瑣。可以封裝讀取的函數并且這樣調用：

1.1.3　循環宏定義

算法比賽中，寫得最多的代碼就是像這樣的循環代碼：

這里N也可能是一個STL中集合的大小，如vector．size之類的。許多競賽選手習慣使用大量的宏定義來簡化代碼，筆者最常用的宏定義是簡化這個循環的：

這樣寫循環時，就會簡化成_for（i，0，N），這里的a、b兩個參數都可傳入表達式，例如：

宏使用得當，可以大量簡化代碼，最典型的例子是本書習題9-18中有一個五維的DP，里面有一個5層for循環，使用宏之后，可精簡的代碼非常可觀。

另外一個比較有用的是：

1.1.4　STL容器內容調試輸出

比賽中經常用到STL中的容器類，如vector和set，而且在調試過程中經常需要輸出這些容器的內容，每次都要寫循環來輸出，非常煩瑣。筆者封裝了兩個泛型函數使用C＋＋的IO流對集合進行輸出：

1.1.5　二維幾何運算類

在許多牽涉位置計算的題目（如本書習題3-5）中，需要模擬物體位置并且進行移動和轉向，如果每次都直接用x和y坐標分別計算，非常煩瑣，其實可以使用《算法競賽入門經典—訓練指南》一書第4章中的幾何操作類，復用向量的移動、旋轉等邏輯，詳細代碼請參考相關章節。

1.1.6　內存池

在一些題目中，需要動態分配對象。例如，表達式解析時需要動態分配語法樹的結點對象。一般的做法是直接用數組開辟空間，但是未必容易事先估計出需要開辟的空間大小，在邏輯控制中還要維護一個變量進行分配和釋放，如果是多種對象都要動態分配，則更加煩瑣。筆者基于vector容器和C＋＋的內存分配機制，編寫了一個內存池：

然后在每次需要釋放時直接調用dispose方法即可，不需要再維護各種中間變量。

1.1.7　泛型參數的使用

入門經典中很多算法的封裝都會在某個結構體內部開一個數組，并且使用一個類似于MAXSIZE的結構來全局定義這個數組的大小，典型的如圖論中的Dijkstra等算法：

如果同一個題目（如《算法競賽入門經典—訓練指南》中的習題UVa10269 Adventure of Super Mario）中需要在兩個不同的部分都用到Dijkstra算法怎么辦？這個時候一般的做法就是定義多個MAXSIZE變量，但是會比較煩瑣，也容易出錯。

其實可以引入C＋＋的泛型參數來解決這個問題：

使用時，就可以通過下面的方式來指定不同的MAXSIZE：

具體使用可以參考訓練指南中UVa10269的實現代碼。

1.1.8　位運算操作封裝

在使用位向量表示集合或進行狀態壓縮時，有個常用操作就是取得一個整數中某一位或者連續幾位對應的int值。這些代碼寫起來較為煩瑣，如果一個題目中多處調用，會增加出錯的可能，筆者針對這種情況封裝了一個位運算的操作類：

如果是32位整數位運算可以使用BitOp＜long＞來調用，64位可以使用BitOp＜long long＞來調用。

1.1.9　編譯腳本

一般都是使用g＋＋編譯然后在命令行運行，每次編譯都要輸入一堆命令，效率較低，所以筆者使用Windows命令行開發了兩個腳本。

（1）編譯腳本（ojc．bat）：這里假設ojc．bat以及g＋＋．exe所在的目錄已經加入到系統PATH環境變量中：

使用方法如下：

（2）編譯并且直接運行（ojr．bat）：這里同樣假設ojr．bat以及g＋＋．exe所在的目錄已經加入到系統PATH環境變量中。ojr．bat的內容如下：

以下命令會直接編譯源文件，然后直接從UVa100．in讀入數據運行：