4.10 循環（重復）結構

循環結構在本質上是一種包含選擇結構（循環條件的判斷）的重復執行的一組語句序列。標準C++/C語言提供了3種循環結構：do/while、while和for。循環結構基本上可以分為確定循環、不確定循環和無限循環，它們分別又可以叫做計數器控制的循環、標志控制的循環和死循環（busy-loop）。

這3種循環結構的基本語法如下：

它們都在條件表達式為true（非0值）時執行體內的語句序列。但是do/while結構在執行語句序列之后才測試條件表達式的真假，因此它至少要執行體內的語句序列一次，除非像下面這樣來用它：

                do {
                  if(條件表達式is false)break;
                  語句序列
                } while (條件表達式);

但是我們強烈建議不要這樣使用。

另外兩個結構在一開始就判斷條件表達式的值，如果為true則執行體內語句序列，否則退出循環。

for結構等價于下面的while結構：

                循環控制變量初始化語句;
                while (循環控制條件表達式) {
                  if (循環控制變量不等于其初始值)
                        修改循環控制變量;
                  語句序列
                }

如果循環體中出現了continue語句，則要防止它跳過循環控制變量的修改語句。for結構中把循環控制變量的修改放在前面而不是后面就是這個道理。

可以使用它們中的任何一種來編寫確定循環或不確定循環，但是我們建議：如果你的循環是確定的，最好使用for結構，否則使用while結構，do/while結構不常用。確定循環還有一個不常見的用法：起到延遲作用。

【提示4-19】： 標準C++/C語言允許在for語句中聲明（定義）變量，并且它的作用范圍為該for語句塊內。不過有些語言實現可能沒有遵循這個語義，例如，Visual C++就會把這樣聲明的變量挪到for語句塊外，從而它的作用域與for語句相同，在for語句塊結束后它仍然有效。這一點要重視。

4.10.1 for語句的循環控制變量

不要使用浮點數做計數器來控制循環，因為它可能是不精確的。

不要在循環體內修改循環變量——除了循環控制變量的遞增遞減，防止循環失去控制，尤其是for循環。在后面講到容器的時候也有一條類似的規則：不要在遍歷（迭代）容器的過程中對容器進行插入、刪除元素的操作。

【建議4-3】： 如果計數器從0開始計數，則建議for語句的循環控制變量的取值采用“前閉后開區間”寫法。要防止出現“差1”錯誤。

例如，示例4-11中的兩種風格：

示例4-11

其中x屬于前閉后開區間[0, N)，起點到終點的間隔為N，循環次數為N。y屬于閉區間[0, N-1]，起點到終點的間隔為N-1，循環次數為N。相比之下，前一種寫法更加直觀，盡管兩者的功能是相同的。

4.10.2 循環語句的效率

標準C++/C循環語句中，for語句使用頻率最高，while語句其次，do/while語句很少用。我們著重討論一下使用for語句遍歷多維數組的效率問題。

【建議4-4】： 對于多維數組來說，正確的遍歷方法要看語言以什么順序來安排數組元素的存儲空間。比如Fortran是以“先列后行”的順序在內存中連續存放數組元素，而C++/C則是以“先行后列”的順序來連續存儲數組元素。

因此，以“先列后行”存儲的數組，就應該以“先列后行”的順序遍歷，以“先行后列”存儲的數組就應該以“先行后列”的順序遍歷。

如示例4-12所示。

示例4-12

                double  array[1024][512];
                for (int r = 0; h < 1024; ++h)
                  for (int c = 0; c < 512; ++c) {
                        std::cout << array[r][c] << std::endl;
                        }

就C++/C多維數組來說，“先行后列”遍歷效率肯定好于“先列后行”遍歷，不管其行數遠大于列數還是情況相反甚至接近，即使在最壞的情況下也至少與“先列后行”遍歷的效率相當。影響效率的實際上主要是大型數組導致的內存頁面交換次數以及cache命中率的高低，而不是循環次數本身。

我們以二維int類型數組為例來說明這種情況，其他類型的二維數組或二維以上的數組也是同樣的道理。

在C++中，二維數組以“先行后列”的順序存儲在連續的內存中。例如，int a[10][3]在內存中的映像如圖4-6所示（假設一個int大小為4字節，這是在MSVC下某次執行時打印出來的邏輯地址）。

我們來比較一下“先行后列”遍歷和“先列后行”遍歷的過程。

“先行后列”：

                  for (int i = 0; i < 10; ++i)
                      for (int j = 0; j < 3; ++j)
                          {
                          a[i][j] = 0;
                          }

即外層循環走過每一個行，在走到特定的某一行時，內層循環走過該行包含的每一列的所有元素。顯然內層循環執行時地址跳躍的幅度很小，都是連續地依次訪問每

一個內存位置相鄰的元素，沒有跨行存取。

圖4-6 C++/C數組的內存映像

“先列后行”：

                  for (int j = 0; j < 3; ++j)
                      for (int i = 0; i < 10; ++i)
                          {
                          a[i][j] = 0;
                          }

外層循環依次走訪每一列，對于其中的某一列，內層循環依次訪問該列包含的每一個元素，但是這些元素的內存位置不再是相鄰的，而是跨行的。很顯然，地址跳躍的幅度較大。

數組元素的訪問是真正的隨機訪問（直接地址計算）。如果整個數組能夠在一個內存頁中容納下，那么在對整個數組進行操作的過程中至少不會為了訪問數組元素而出現缺頁中斷、頁面調度和頁面交換等情況，只需要一次外存讀取操作就可以將數組所在的整個頁面調入內存，然后直接訪問內存就可以了。此時“先行后列”和“先列后行”的遍歷效率差不多（僅有的差別是cache命中率不同，但是差別不大）。

但是如果整個數組內容需要多個內存頁來容納的話，情況就大不一樣了，尤其是列數較大的情況下。我們就考慮一種特殊的情況：假設一個內存頁的大小為4096字節，并且定義一個int數組，其列數為1024（即每一行的元素恰好占用一頁），行數遠小于列數，假設為128行。雖然這個假設比較特殊，但是足以說明問題。我們來計算一下“先行后列”遍歷和“先列后行”遍歷分別需要進行多少次頁面交換。

數組定義：

                int  b[128][1024];

這就是說，該數組每行包含1024個int類型數，正好占據一個內存頁的空間，因此整個數組將占據128個內存頁。

“先行后列”：

                  for (int i = 0; i < 128; ++i)
                      for (int j = 0; j < 1024; ++j)
                          {
                          b[i][j] = 0;
                          }

外層循環走過每一個行，在走到特定的某一行時，內層循環走過該行的1024個元素，正好走完一頁，沒有發生頁面調度，且cache命中率高；當循環進入下一行時操作系統從外存調入下一頁。因此可以得知，遍歷完整個數組發生頁面調度的次數最多為128次（假設一次調度一頁）。

“先列后行”：

                  for (int j = 0; j < 1024; ++j)
                      for (int i = 0; i < 128; ++i)
                          {
                          b[i][j] = 0;
                          }

在遍歷某一列的時候，由于它包含的每一個元素都恰好分別位于每一個行內，因此內層循環每執行一次就會發生一次頁面調度，遍歷一列下來就會發生128次頁面調度，顯然總共發生的頁面調度次數將可能達到1024×128次（假設一次調度一頁），也就是“先行后列”遍歷的1024倍。不過實際情況并沒有這么壞，因為如果物理內存足夠，頁面調度和頁面交換的次數往往會減少很多。但是可以肯定的是：“先列后行”遍歷發生的頁面交換次數要比“先行后列”多，且cache命中率相對也低。這恰恰就是導致“先列后行”遍歷效率降低的真正原因。

結論（針對大型數組，大規模矩陣）：

（1）當行數遠大于列數的時候(m?n)，“先行后列”遍歷的效率高于“先列后行”遍歷的效率，這是顯然的，但可能不明顯。

（2）反之當列數遠大于行數的時候(n?m)，“先行后列”遍歷的效率必然高于“先列后行”遍歷的效率，這是從上面分析可以得出的結論。

（3）即使行數和列數接近的時候（m≈n），“先行后列”的效率還是高于“先列后行”遍歷的效率。

事實勝于雄辯！下面我們就來做一個實際測試，測試代碼如示例4-13所示。

示例4-13

                  const int MAX_ROW = 500;
                  const int MAX_COLUMN = 10000;
                  int (*a)[MAX_COLUMN] = new int[MAX_ROW][MAX_COLUMN];
                  std::cerr << "int array(MAX_ROW = " << MAX_ROW \
                          << ", MAX_COLUMN = " << MAX_COLUMN << ")\n";
                      // 先行后列
                  DWORD start = GetTickCount();
                  for (int i = 0; i < MAX_ROW; ++i)
                      for (int j = 0; j < MAX_COLUMN; ++j)
                          a[ i ][ j ] = 1;
                  DWORD end = GetTickCount();
                  std::cerr << "Stepthrough by row-first-column-last takes " \
                          << (end - start) << "毫秒\n";
                  delete []a;
--------------------------------------------------------------------------------------------------------------------------------
                  const int MAX_ROW = 500;
                  const int MAX_COLUMN = 10000;
                  int (*a)[MAX_COLUMN] = new int[MAX_ROW][MAX_COLUMN];
                  std::cerr << "int array(MAX_ROW = " << MAX_ROW \
                          << ", MAX_COLUMN = " << MAX_COLUMN << ")\n";
                      // 先列后行
                  DWORD start = GetTickCount();
                  for (int j = 0; j < MAX_COLUMN; ++j)
                      for (int i = 0; i < MAX_ROW; ++i)
                          a[ i ][ j ] = 1;
                  DWORD end = GetTickCount();
                  std::cerr << "Stepthrough by column-first-row-last takes " \
                          <<(end-start)<<" 毫秒\n";
                  delete []a;

表4-3是某次不同行列配對下的一組測試結果（單位：ms），測試平臺：Intel CPU 1.7GHz + Windows 2000 + MSVC++6.0。

表4-3 多維數組遍歷測試結果

比較一下測試結果，看看每種情況下所花費時間的相對大小，一切就都明白了。

【建議4-5】： 如果循環體內存在邏輯判斷，并且循環次數很大，宜將邏輯判斷移到循環體的外面。

在示例4-14中，左側的寫法比右側的寫法多執行了N-1次邏輯判斷，并且前者的邏輯判斷打斷了循環的“流水線”作業，使得編譯器不能對循環進行優化處理，降低了效率。如果N非常大，最好采用右側的寫法，可以提高效率。如果N非常小，兩者效率差別并不明顯，采用左側的寫法比較好，因為程序更加簡潔。

示例4-14

我們舉一個循環結構的例子來結束本節：求兩個整數的最大公約數和最小公倍數。

求最大公約數可采用輾轉相除法，其流程如圖4-7所示。最小公倍數就是兩個整數的乘積除以其最大公約數，程序見示例4-15。

圖4-7 求最大公約數和最小公倍數的流程

示例4-15

                int main()
                {
                  unsigned long a,b,c=0;      /* 兩個整數和臨時變量 */
                  unsigned long lcm=0,gcd=0;  /* 最小公倍數和最大公約數 */
                  while (1) {
                        printf ( "Please input two positive integers(spacebar as separator): " );
                        scanf ( "%lu %lu", &a, &b );
                        if (a <= 0 || b <= 0) {
                            printf ( "Input error!\n" );
                            continue;
                        }
                        else
                            break;
                  }
                  unsigned long ra=a,rb=b;    /* 保存原始數據 */
                  while (a % b != 0){
                      c = a % b;
                      a = b;
                      b = c;
                  }
                  gcd = b;
                  lcm=(ra*rb)/gcd;         /* 使用原始數據計算lcm*/
                  printf("Their Greatest Common Divisor is %lu.\n", gcd);
                  printf("Their Least Common Multiple is %lu.\n", lcm);
                  return 0;
                }
                // testing
                Input two positive integers:1240  85
                Their Greatest Common Divisor is 5.
                Their Least Common Multiple is 21080.
                Input two positive integers:85  1240
                Their Greatest Common Divisor is 5.
                Their Least Common Multiple is 21080.