Metaprogramming

設計一支程式來製造程式碼，令該程式碼充分運用程式語言自身擁有的能力，輕鬆地、更有效率地完成更多事情。

舉個例子。例如現在有一個四則運算式需要計算：

5 + 8 * (2 - 3) + 7 * -6 / (2 - 1) + 1

這是一個經典的問題，大家應該不陌生。身經百戰的演算法設計高手，必然不假思索說出：stack，把所有符號依序放入stack，依照運算符號的優先次序push和pop，一下子就算完了。聽來簡單，但實做起來還是頗麻煩。

這裡要介紹的是更輕鬆、更強悍的方法：寫程式製造一支會進行四則運算的程式。大家都知道C/C++的語法當中，就有四則運算的語法了。現在來設計一支程式，製作出四則運算的程式碼吧！

void arithmetic() { // 輸入四則運算式 string s; cin >> s; // 製作程式碼 ofstream fout("temp.cpp"); fout << "#include <iostream>\n"; fout << "int main()\n"; fout << "{\n" fout << " std::cout << (" << s << ") << endl;\n"; fout << " return 0;\n"; fout << "}\n"; fout.close(); }

如果輸入方才的四則運算式，就會產生如下程式碼，檔名為temp.cpp。

#include <iostream> int main() { std::cout << (5 + 8 * (2 - 3) + 7 * -6 / (2 - 1) + 1) << endl; return 0; }

然後編譯temp.cpp、執行一下，就有答案了。您甚至可以把編譯、執行的指令，統統寫進程式碼當中：

void arithmetic() { // 輸入四則運算式 ...... // 製作程式碼 ...... // 編譯和執行（在Linux底下） system("g++ temp.cpp -o temp.out"); system("./temp.out"); // 刪除暫存檔案 system("rm temp.out"); system("rm temp.cpp"); }

程式設計師藉由Metaprogramming能做更多事情！現在的資訊領域當中，應用到Metaprogramming的也相當多，各位可以再去蒐集相關資料來閱讀。:)

Quine

寫一支程式，其功能是輸出本身程式碼。

給一題尚未有測試資料的題目，目前還不能送。

UVa 724

Array Indexing

「索引」可說是電腦的奇技！一個元素存放到陣列之後，不論是在陣列的哪個地方，只要利用索引值（index），就能在一瞬間找到元素。

大多數的演算法都運用了「索引」的技巧，讓程式執行速度更快。

以下介紹索引的幾種運用方式。是我自己歸類整理的，並不是標準。

一、定位

概念為：將物件放入陣列中，array[位置] = 物件。

當元素很多時，我們可以放到陣列裡。我們只要記錄索引值，依舊可以常數時間得到元素。

範例：求最大值。將元素連續地放入陣列，若想紀錄一元素，僅需一索引值。

void find_maximum() // 用變數直接記最大值 { int array[5] = {3, 6, 9, 8, 1}; int max = -10000; for (int i=0; i<5; i++) if (array[i] > max) max = array[i]; cout << "最大值為" << max; } void find_maximum() // 用索引值紀錄最大值位置 { int array[5] = {3, 6, 9, 8, 1}; int p = 0; // 最大值的索引值 for (int i=1; i<5; i++) if (array[i] > array[p]) p = i; cout << "最大值為" << array[p]; }

範例：求子字串。將元素連續地放入陣列，若想紀錄一區間，僅需頭尾的索引值。

void substring() { char s[10] = "Hello, world!"; char t[10]; int i, j; for (i=2, j=0; i<6; i++, j++) t[j] = s[i]; t[j] = '\0'; cout << "s的子字串[2,6)是" << t; }

範例：連續數字和。將元素連續地放入陣列，利用問題本身的數學性質以及索引值，快速得到答案。

void consecutive_sum() { int array[5] = {3, 6, 9, 8, 1}; int sum[5] = {0}; sum[0] = array[0]; for (int i=1; i<5; i++) sum[i] = sum[i-1] + array[i]; cout << "區間[2,4]的連續數字和是" << sum[4] - sum[2-1]; }

範例：求中位數。將元素依照大小順序並連續地放入陣列，利用索引值得到位於中間的元素。

void median() { int array[5] = {1, 3, 6, 8, 9}; // 由小到大排序 cout << "中位數是" << array[5/2]; }

範例：二分搜尋法（Binary Search）。將元素依照大小順序並連續地放入陣列，然後夾擠索引值。如果使用的是鏈接串列，因為元素們都沒有索引值，就無法使用二分搜尋法。

void binary_search() { int array[5] = {1, 3, 6, 8, 9}; // 由小到大排序 int key = 3; // 搜尋陣列裡有沒有3 int left = 0, right = 5; // 索引值範圍 while (left < right) { int mid = (left + right) / 2; if (array[mid] < pivot) left = mid + 1; else if (array[mid] > pivot) right = mid - 1; else if (array[mid] == pivot) return mid; } return left; }

範例：二元樹（Binary Tree）。元素的索引值對應到樹的結構，是一種特殊的定位。

// 得到array[index]的左邊小孩的索引值 int left_child_index(int index) {return index * 2;} // 得到array[index]的右邊小孩的索引值 int right_child_index(int index) {return index * 2 + 1;} void binary_tree() { int array[5 + 1] = {0, 3, 6, 9, 8, 1}; // array[0]不使用 cout << "根為" << array[1]; cout << "根的左邊小孩是" << array[ left_child_index(1) ]; cout << "根的右邊小孩是" << array[ right_child_index(1) ]; }

範例：堆疊（stack）、佇列（queue）。元素連續地放入陣列，然後以改變索引值的方式，來動態增減堆疊及佇列的元素。

void stack() { int stack[10]; // 一個堆疊 int top = 0; // 索引值 stack[top++] = 3; // push stack[top++] = 6; // push if (top > 0) // is empty? int n = stack[--top]; // pop } void queue() { int stack[10]; // 一個佇列 int front = 0, rear = 0; // 索引值 queue[rear++] = 3; // push queue[rear++] = 6; // push if (front < rear) // is empty? int n = queue[front++]; // pop }

二、歸類並標記

概念為：物件直接作為陣列的索引值，array[物件] = 物件的屬性。

範例：正整數集合。物件是：正整數，物件的屬性是：是否在集合裡頭出現。

void add_element() { // 一個有限集合 bool set[100]; // 初始化為空集合 for (int i=0; i<100; i++) set[i] = false; // 設定集合元素 set[5] = true; // 集合裡有5 set[3] = true; // 集合裡有3 set[3] = false; // 集合裡沒有3 }

範例：統計英文字母出現次數。物件是英文字母，物件的屬性是英文字母的出現次數。

void count_letter() { char s[20] = "hi, I am a boy"; // 歸類並標記 // 26個字母，字母的ASCII值剛好連續。 int count[26 + 26] = {0}; for (int i=0; s[i] != '\0'; i++) if (s[i] >= 'a' && s[i] <= 'z') count[ s[i] - 'a' ]++; else if (s[i] >= 'A' && s[i] <= 'Z') count[ s[i] - 'A' ]++; // 印出英文字母的出現次數，不分大小寫。 for (int i=0; i<26; i++) if (count[i] > 0) cout << char('A' + i) << "的個數為" << count[i]; }

範例：計數排序法（Counting Sort）。索引值的大小順序，剛好也是元素的大小順序，故可用於排序。

void counting_sort() { // 假設陣列裡數值不重複 int array[5] = {3, 6, 9, 8, 1}; // 歸類並標記 bool count[100] = {false}; for (int i=0; i<5; i++) count[ array[i] ] = true; // 索引值的大小順序，剛好也是元素的大小順序。 for (int i=0, j=0; i<100 && j<5; i++) if (count[i]) // 數值不重複 array[j++] = i; }

範例：雜湊表（hash table）。元素的索引值由特殊方法決定，是一種特殊的歸類。

int hash(int n) // 根據元素的數值來製造一個index { return n * 97 % 100; } void hash_table() { int array[5] = {3, 6, 9, 8, 1}; int table[100]; for (int i=0; i<5; i++) { // 替array[i]製造一個index int index = hash(array[i]); // 將array[i]放入hash table table[index] = array[i]; } }

三、轉換

概念為：array[物件] = 另一個物件。類似函數的概念。

範例：取代（Substitution）、移位（Transposition）。取代和移位是密碼學的基礎概念。取代是文字的轉換，移位則是位置的轉換。

void substitution() { char s[10] = "Hello!", t[10] = ""; // 建立轉換表格 char crypt[128]; for (int i=0; i<128; i++) crypt[i] = i; crypt['!'] = 'w'; crypt['H'] = 'Y'; // 開始轉換 int n; for (n=0; s[n] != '\0'; n++) t[n] = crypt[ s[n] ]; t[n] = '\0'; } void transposition() { char s[10] = "Hello!", t[10] = ""; // 建立轉換表格 int crypt[50]; for (int i=0; i<50; ++i) crypt[i] = i; crypt[2] = 3; crypt[3] = 5; crypt[5] = 2; // 開始轉換 int n; for (n=0; s[n] != '\0'; n++) t[n] = crypt[ s[n] ]; t[n] = '\0'; }

範例：page table。作業系統的機制，可將虛擬位址轉換成實體位址，是位址的轉換。

程式碼略。

附錄：定址的時間複雜度

當索引值大小為N時，有人認為定址的時間複雜度是O(log₂N)，也有人認為是O(1)。這兩種說法都是有其依據的。

以數學的觀點來看：N共有log₂N個位元，用二元樹的概念，依照各個位元的數值是0或是1進行分支，分支到底後就完成定址了。所以定址的時間複雜度是O(log₂N)。

以電路的觀點來看：一顆中央處理器可以平行處理32位元（現在已有64位元），只要是介於0到2^32-1的索引值，都可以在1單位時間完成定址，而不必用32單位時間來完成定址。所以定址的時間複雜度是O(1)。

討論演算法的時間複雜度時，我們傾向假設定址的時間複雜度是O(1)。

附錄：定址的範圍

方才提到一顆中央處理器可以平行處理32位元，理論上可以定址到2^32以內的位址。一個位址一般擁有1byte的記憶體大小，所以我們利用定址方式，可以運用的記憶體就有2^32 * 1byte = 4GB 這麼多。

但是作業系統會保留一些位址、預留一些記憶體空間以維持系統運作，所以使用者實際可以運用的記憶體其實不到4GB。

當記憶體沒有插到4GB的時候，作業系統利用一種叫做virtual memory的技術，以硬碟空間補足記憶體不足4GB的部份。

位址是連續不斷的，我們寫程式也都直接假設位址對應到的記憶體空間是連續不斷的，然而實際上並不是連續的。作業系統運用一種叫做paging的技術，藉由page table，讓記憶體看起來是連續的。

Bitwise Operator

歡迎來到二進位的世界。電腦資料都是以二進位儲存，想當然程式語言的變數也都是以二進位儲存。在C/C++當中有幾個位元運算子：<< SHIFT LEFT、>> SHIFT RIGHT、& AND、| OR、^ XOR、~ NOT，可以對變數進行位元運算。接下來要介紹位元運算的一些用途。

UVa 10469 10264

<< SHIFT LEFT
>> SHIFT RIGHT

這兩個運算子的功能主要是移動一個變數中的所有位元，位元向左/向右移動之後，最高位/最低位的位元會消失，最低位/最高位的位元補0：

5 << 1 = 10	// 00101 的全部位元向左移動一位數變成 01010。
5 << 2 = 20	// 00101 的全部位元向左移動兩位數變成 10100。
5 >> 1 = 2	// 00101 的全部位元向右移動一位數變成 00010。
5 >> 2 = 1	// 00101 的全部位元向右移動一位數變成 00001。

在十進位當中，當全部位數向左移動一位時，數值大小會變成原來的十倍，向左移動兩位時，會變成原來的百倍。這種情形在二進位也是成立的，當全部位元向左移動一位時，會變成原來的兩倍，向左移動兩位時，會變成原來的四倍。至於往右移動也是類似道理，變成了除法而已。

由於電腦進行位元運算比乘法、除法運算快上許多，所以有很多專業的程式設計師，會利用位元運算來取代乘法、除法運算。優點是程式執行效率增加，缺點是程式碼可讀性變低：

int n = 5; n = n >> 1; // 即是 n = n / 2 之意。 /* 該式子也可寫成 n >>= 1 或 n /= 2。 */

& AND

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

&的功能是將兩個變數對應的位元進行AND邏輯運算，然後產生新變數。

   00000000000000000000000001110100 -> 116
 & 00000000000000000000000000101001 -> 41
 ----------------------------------
   00000000000000000000000000100000 -> 32

&的特色，就是可以判斷出位元是不是1。例如我們想要數一個變數有幾個位元是1：

int count_bit_1(int n) { // 由右往左看n的每一個位元。 int c = 0; for (int i=0; i<32; ++i) // int變數有32個位元 if (n & (1 << i)) c++; return c; } int count_bit_1(int n) { // 一樣是由右往左，但是每次都刪掉n的最左邊位元。 int c = 0; for (; n; n>>=1) if (n & 1) c++; return c; }

| OR

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

|的功能是將兩個變數對應的位元進行OR邏輯運算，然後產生新變數。

   00000000000000000000000001110100 -> 116
 | 00000000000000000000000000101001 -> 41
 ----------------------------------
   00000000000000000000000001111101 -> 125

|的特色，就是把位元強制標記成1。例如我們想要把五位數標成1：

int mark_5th_bit(int n) { return n | (1 << 4); }

^ XOR

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

^的功能是將兩個變數對應的位元進行XOR邏輯運算，然後產生新變數。

   00000000000000000000000001110100 -> 116
 ^ 00000000000000000000000000101001 -> 41
 ----------------------------------
   00000000000000000000000001011101 -> 93

^的特色，就是把位元的0和1顛倒。例如我們想要顛倒第五位數：

int reverse_5th_bit(int n) { return n ^ (1 << 4); }

~ NOT

~ 0 = 1
~ 1 = 0

~的功能是顛倒一個變數每一個位元的0和1。

 ~ 00000000000000000000000000000011 -> 3
 ----------------------------------
   11111111111111111111111111111100 -> -4

延伸閱讀：>>的陷阱

當變數是正值或零時，>>會在左端最高位補零；當變數是負值時，>>會在左端最高位補一，讓變數保持負數。

int n = 1; // 00000000000000000000000000000001 -> +1 cout << (n << 31); // 10000000000000000000000000000000 -> -2147483648 // 二進位補數法，最高位是一則為負數。 // n由正數變成負數。 cout << ((n << 31) >> 31); // 11111111111111111111111111111111 -> -1 // n保持負數，結果竟然不是+1。 cout << ((1 << 31) >> 31); // 11111111111111111111111111111111 -> -1 // 注意到一開始的1是int型態。

當用到最高位元、也用到>>的時候，必須改用unsigned int、unsigned long long int等變數型態，才會得到正確結果。

延伸閱讀：unsigned的陷阱

一般來說，實施位元運算時，程式設計師喜歡採用unsigned變數型態，避免>>的陷阱。

此時要特別小心，勿將unsigned與signed型態的變數一起進行計算，很容易出現意想不到的事情。例如拿unsigned與signed變數進行加減法、比大小；例如把unsigned變數傳入函數，但是函數參數是signed變數。

Bitwise Trick

http://kuoe0.ch/1436/

http://kuoe0.ch/1503/

http://www.aggregate.org/MAGIC/

http://graphics.stanford.edu/~seander/bithacks.html

實作時要特別小心運算子優先次序。沒有特地括括號的情況下，次序高的先結合。

交換兩個int變數

// 注意：比直接交換還要慢。 void swap(int& x, int& y) { x = x ^ y; y = x ^ y; x = x ^ y; } // 下面的寫法有暫存變數存取順序問題。 // 是未定義行為，不同的編譯器可能產生不同結果。 // 千萬不要如此取巧。 void swap(int& x, int& y) { x ^= y ^= x ^= y; }

計算有幾個位元是1（32位元整數）

// http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html // __builtin_popcount int count_bits(int x) { x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1); x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2); x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4); x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8); x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16); return x; }

顛倒位元順序（32位元整數）

int reverse_bits(int x) { x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa); x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc); x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0); x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00); x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000); return x; }

窮舉所有子集合

一個變數代表一個集合（即是bitset），每個位元分別代表每個集合元素。

// 枚舉 s 的所有非空子集合 for (int i = s; i; i = i-1 & s) cout << s;

檢查缺少的正整數

陣列裡放入1到10的正整數，最後發現少了一個，請找出少了哪一個。

使用Counting Sort雖然時間複雜度低，但是空間複雜度高。

int array[9] = {2, 3, 5, 9, 4, 6, 10, 8, 1}; int find_lack_number() { int n = 0; // 1到10全部xor起來 for (int i=0; i<10; ++i) n ^= i; // 陣列裡的數字全部xor起來，與先前結果做xor。 for (int i=0; i<9; ++i) n ^= array[i]; return n; }

8 Queen Problem（八皇后問題）

http://www.matrix67.com/blog/archives/266

使用回溯法。變數代替陣列，位元代替陣列元素。

const int N = 8; // 皇后數目 const int mask = (1 << N) - 1; // 弄出8個1 int ans = 0; // 合理的排列數目 void eight_queen() { backtrack(0, 0, 0); // 以橫線為單位遞迴 } // 皇后已占據的直線們、左斜線們、右斜線們。占據為1。 void backtrack(int col, int ld, int rd) { if (col == mask) {ans++; return;} // 找到一組解 int pos = mask & ~(col | ld | rd); // 可以放皇后的空位。空位為1。 while (pos /*!= 0*/) // 依序嘗試各個空位。 { int p = pos & -pos; // 最低位的1。一個可以放皇后的空位。 pos = pos - p; // 該空位消失，待會放皇后。 // 放上皇后，算好皇后占據的位置，然後遞迴至下一條橫線。 backtrack(col+p, (ld+p)<<1, (rd+p)>>1); } }

UVa 11195

Nim（捻）

這是兩個人玩的小遊戲。桌面上有N堆石子，兩個人輪流從桌上取走石子，每人每次只能取其中一堆石子，至少取一顆，至多搬走整堆。最後淨空桌面的人勝利，請判斷誰會勝利。

這個問題的解答，跟每堆石子的數量多寡有關。神奇的是，竟然跟二進位表示法有很大關連： http://oddest.nc.hcc.edu.tw/math152.htm。

int stone[10] = {2, 3, 4, 6, 6, 2, 3, 4, 8, 9}; void nim() { int x = 0; for (int i=0; i<10; ++i) x ^= stone[i]; if (x) cout << "先手贏"; else cout << "後手贏"; }

UVa 10165

Gray Code

void gray_code(int n) { for (int i=0; i<(1<<n); ++i) cout << i^(i>>1); }

Josephus Problem

模數為二的時候，答案為：去除n的最高位元，然後整體左移一位，最後加上一。

Fast Inverse Square Root（平方根倒數）

原理是牛頓法，避開了開根號和除法運算，節省了很多計算時間。除此之外還使用了很多神奇的技巧，包括電腦結構和程式語言的冷知識。

3D繪圖經常要計算平方根倒數。相傳是原作者在開發電腦遊戲「雷神之鎚」時，所發明的方法。

http://en.wikipedia.org/wiki/Fast_inverse_square_root

http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf

// 1.0 / sqrt(x) float InvSqrt(float x) { float xhalf = 0.5f * x; int i = *(int*)&x; i = 0x5f3759df - (i >> 1); x = *(float*)&i; x = x * (1.5f - xhalf * x * x); return x; }

前言

我自己有一套簡單的解讀方式，儘管這不一定是C/C++設計者的原意，但是應該能讓大家確實的掌握指標的概念。

記憶體與位址

談指標之前，必須簡述一下記憶體與位址的概念。我們可以把記憶體簡單地想成一條很長很長的0與1字串，總長度是固定的。

接著我們要替這條長長的字串訂立位址，就像是替一條公路設立里程碑。一開始是位址是零，然後每八個字，就讓位址增加一單位。

註：早期的CPU一次可讀八個字，所以設定八個字為一單位。而現在的CPU一次可讀三十二字，更新穎的CPU一次可讀六十四字，但是都仍然維持八個字為一單位。

位址通常都會用16進位表示，數值開頭再加個0x，表示是16進位數字。

變數

程式當中所有宣告的變數均會存放到記憶體當中的某一段，變數的數值會轉換成二進位，以0與1字串形式儲存。

編譯器和作業系統會幫我們安排適當的地點，讓這些變數不會重疊在一起。另外，如果是宣告陣列，在記憶體當中一定是連續的一段，中間不會被隔開。

int a = 10; // 4 bytes = 32 bits int b[3] = {5, 6, 7}; // 12 bytes，陣列會連續 char c = 'a'; // 1 byte char d; // 1 byte

沒有變數的地方，我們不能隨意取值和設值，否則會讓程式立刻中止。

至於有變數但是沒有設定初始值的地方，無法預測是0或1，我們不能隨意取值，否則會產生不可預期的結果，甚至讓程式當掉。

想要取得變數儲存的數值，只要直接用變數名稱就行了。

int a = 5; cout << a; // 印出5

想要獲得變數所在的位址，只要在變數名稱前面加&，就能算出變數的位址。

int a; cout << &a; // 印出變數的位址，是看不懂的亂碼。 cout << (int)&a; // 轉型成int，這樣才會印成整數數字。 cout << hex << int(&a); // 印成十六進位數字。 cout << (void*)&a; // 正式的寫法是轉換成void*型態， // 並且自動印成十六進位數字。 printf("%p", &a); // C語言則是使用%p。

儲存位址的變數型態

我們假設C/C++有一種變數型態叫做address，此變數型態儲存的數值，是一個位址。

// 假設位址是32位元 address a = 0x00000010; address b = 0x00000014; address c; address d[2] = {0x00000010, 0x00000014}; // 也可以改用十進位 address a = 16; address b = 20; address c; address d[2] = {16, 20};

C/C++的指標，概念上等同於address變數型態。無論是哪一種型態的指標，儲存的數值，都是一個位址，沒有差別。

// 直接把int*連帶星號看作是一種變數型態 // 設值時要先轉型，不然會變成complie error int* a = (int*) 0x00000010; char* b = (char*) 0x00000014; char* c; float* d[2] = {(float*) 0x00000010, (float*) 0x00000014}; double* e[2][2]; // 也可以改用十進位 int* a = (int*) 16; char* b = (char*) 20; char* c; float* d[2] = {(float*) 16, (float*) 20}; double* e[2][2];

現在我們可以把任何一個變數的位址，儲存在指標之中了。這時候指標的型態發揮用處了：編譯器會判斷「指標型態」與「變數型態多一個*」兩者一不一致，當不一致時會告知我們錯誤訊息。

int x; int* a; a = &x; // 一個位址變數a，設定其值是一個位址。 // x的型態是int，用&得到位址之後，就多一個*，成為int*。 // a的型態是int*。兩者一致。 cout << (int)a; // 印出a裡面的數值，該數值是x之位址 char y; int* a; // a = &y; // compile error ! 型態不一致 a = (int*)&y; // 轉型過後就可以了 cout << (int)a;

儲存位址的變數，本身也是一個變數呀，當然它也有位址了。我們也可以把這個位址，用另一個位址變數存起來。

// 虛擬碼 address a; address b = &a; // C/C++實際上卻得這樣做，因為要滿足型態檢查的規則。 int* a; int** b = &a; // 為了滿足型態檢查的規則，所以只好把int*多加一個* // 發展出一個int**的變數型態。 char*** c; char**** d = &c; // 同樣道理

位址進行比大小運算

我們可以讓兩個位址比大小，比較原則就跟一般的整數比大小一樣。

int* a = (int*) 0x00000010; int* b = (int*) 0x00000014; if (a < b) cout << "a < b"; if (a == b) cout << "a == b"; if (a >= b) cout << "a >= b";

位址進行減法運算

我們可以讓兩個位址相減，相減的結果是一個int變數。

char* a = (char*) 0x000000A0; char* b = (char*) 0x00000001; int c = a - b; cout << c;

註：我們無法直接讓兩個位址相加，除非自行將位址轉型成整數。

位址進行加整數、減整數運算

我們可以讓位址跟整數相加，讓位址減掉整數（但是不能讓整數減掉位址），以及使用加加與減減運算。

這時候指標的型態總算是有用處了，C/C++很聰明，會根據「指標型態少一個*」的型態所占的記憶體大小，來決定加與減的基本倍率。

int* a = (int*) 0x00000000; a = a + 1; // int是4 byte，C/C++會幫你把倍率弄成四。 cout << a; // 0x00000004 char* b = (char*) 0x00000000; b = b + 1; // char是1 byte，C/C++會幫你把倍率弄成一。 cout << b; // 0x00000001 int*** c = (int***) 0x00000000; c = c + 1; // int**是位址變數是4 byte，C/C++會幫你把倍率弄成四。 cout << c; // 0x00000004 int* d = (int*) 0x00000000; d++; --d; ++d; cout << d; // 0x00000004

位址進行反運算

我們可讓位址進行NOT運算，規則與一般整數進行NOT運算一樣，結果是一個int變數。

int* a = (int*) 0x00000010; int* b = (int*) 0x00000000; int x; x = !a; cout << x; // 印出整數0 x = !b; cout << x; // 印出整數1

位址進行解參考運算

我們可以從一個位址開始，抓一段連續的記憶體，當作一個變數。只要在一個位址前面加上*就行了。（這個*與宣告變數時用到的*意義不同，也與乘法運算的*意義不同。）

這個時候指標型態再度發揮功用，C/C++會根據「指標型態少一個*」的型態，從該位址開始，截取該型態大小的記憶體當作一個變數，並自動設定好變數型態。

cout << *((char)0x00000010); // compile error，char沒辦法在少掉一個*了。 cout << *((char*)0x00000010); // 從0x00000010開始抓1 byte當作變數，且型態是char*少一個*，也就是char。 cout << *((char***)0x00000010); // 與上一行得到的變數數值完全相同，只是該變數的型態會被當作是char**。 // 註：沒有變數在0x00000010那裡的話，會產生不可預期結果。程式可能會當掉。 int* a = (int*) 0x00000010; cout << *a; // int是4 byte，C/C++會從0x00000010抓4 byte。 // 沒有變數在那裡的話，會產生不可預期結果。程式可能會當掉。 char* b = (char*) 0x00000010; cout << *a; // char是1 byte，C/C++會從0x00000010抓1 byte。 // 沒有變數在那裡的話，會產生不可預期結果。程式可能會當掉。 int x = 7; int* c = &x; cout << c; // 印出x的位址 cout << *c; // 印出數字7，實際上有變數在那裡，一定抓得到數值。 int* d = &x; *d = 3; // 把那塊記憶體設值為3 cout << d; // 印出x的位址 cout << *d; // 印出數字3

重點回顧

1. 在變數前面加&，就能得到變數所在位址。變數型態多一個*。
2. 不管是哪種指標，其實都是儲存位址的變數型態。
3. 位址的運算（指標的運算）
	1. 設值運算（assign）：=
	2. 比較運算（compare）：< > == >= <= !=
	3. 減法運算（subtract）：-
	4. 加整數、減整數：+ - 前++ 後++ 前-- 後--。不能整數減位址。
	5. 反運算（not）：前面加!
	6. 解參考（dereference）：前面加*
	7. 參考（reference）：前面加&。存位址的變數也是個變數，既是變數就有位址。
	8. 索引（index）: []，請見下面介紹。
	其他運算，必須自行轉型成整數後，才有辦法算。
4. 編譯器會做型態檢查，參考與解參考時，會拿「指標型態少一個*」的型態做判斷。

附錄：Endianness

下面的程式碼的執行結果，跟0與1在記憶體內排放的順序很有關係，看你使用的電腦系統是使用Big-Endian還是Little-Endian，印出來的結果會不一樣。

int x = 7; char* a = (char*)&x; cout << *a; // 用Little-Endian的電腦系統，結果是7 // 用Big-Endian的電腦系統，結果是0

Endianness的詳細介紹：http://libai.math.ncu.edu.tw/bcc16/pool/1.33.shtml。

註：一般家用電腦都是採用Little-Endian。這裡所畫的圖都是Big-Endian，是為了讓各位比較容易理解。

附錄：memset

我們都知道C的標準函式庫有一個函式叫做memset，不管要被設值的資料是什麼型態，都是以1 byte為單位來設值。寫成程式碼大概是這樣：

void memset(void* array, char value, int size) { char* a = array; for (int i = 0; i < size; i++) *(a + i) = value; }

附錄：void*

C語言有一種特殊的指標是void*。其實他也是儲存一個位址，唯一的差別是它不能進行解參考。C++則已經捨棄亦沒有必要使用void*。

void* a = (void*) 0x00000010; *a; // compiler error，型態檢查不會過！

附錄：同一行宣告許多指標

如果想在同一行宣告許多指標，則從第二個變數名稱開始，都要額外加上星號才行。這是一個不太直覺的規定。既然古人發明C時就這樣規定，我們只得依從。

int* a, b; // 以我們的解讀，這樣可以宣告兩個指標， // 不過這是錯誤的方式。 // 這被規定成:宣告一個指標和一個int變數。 int* a, *b; // 於是我們變成要這樣寫... typedef int* int_star; // 或是利用typedef關鍵字，自訂一個型態名稱... int_star a, b;

附錄：指標的指標的指標，解參考再解參考再解參考，取位址。

各位讀過上面文章之後，應該可以輕易弄清楚這些事情背後的原理，而不是去背記*和&可以相互抵銷這種東西。

註：有些面試主考官最喜歡問這樣的問題，好似懂了這些東西就是會寫程式。這個問題不是在考驗你會不會寫程式，這是在考驗你眼睛好不好。

int x = 1; int* a = &x; int** b = &a; cout << &x; cout << &a; cout << &b; cout << **b; cout << *a; cout << *b; cout << *&x; cout << *&&x; // &只能加在變數名稱前面，左邊的&顯然不是這樣。 cout << **&&x; // &只能加在變數名稱前面，左邊的&顯然不是這樣。 cout << **&a; cout << ***&b;

附錄：動態記憶體

宣告動態記憶體，由於實用性與技術上的考量，編譯器沒辦法直接給個變數名字，所以只好給變數的位址，湊合著用。

int* a = new int; int* b = new int[5]; int** c = new int*; *a = 0; // 挺麻煩的 *b = 1; *(b + 1) = 2; // 超麻煩的

位址加整數、減整數後，進行解參考運算

a[x]這個語法，表面上看起來是得到a陣列第x格。事實上[]的意思是「指標加減整數後，進行解參考運算」，a[x]其實是*(a+x)的意義，a和x其中之一為整數、另外之一為位址變數。會有這種語法是因為易讀、方便。

int* a = new int[5]; // a是一個儲存位址的變數 *a = 8; // 取陣列第0格，本來必須這樣寫。 a[0] = 8; // 其實就是 *(a + 0) = 8;，與上一行結果相同。 0[a] = 8; // 其實就是 *(0 + a) = 8;，與上一行結果相同。 *(a+1) = 7; // 取陣列第1格，本來必須這樣寫。 a[1] = 7; // 其實就是 *(a + 1) = 7;，與上一行結果相同。 1[a] = 7; // 其實就是 *(1 + a) = 7;，與上一行結果相同。 int* b; b = &(a[1]); // 得到陣列第1格的位址 b = &(*(a+1)); // 與上一行結果相同 *(b-1) = 9; // 取陣列第0格。 b[-1] = 9; // 其實就是 *(b + -1) = 9;，與上一行結果相同。 (-1)[b] = 9; // 其實就是 *(-1 + b) = 9;，與上一行結果相同。 -1[b]; // 會變成 -*(1 + b);，最後才取負值， // 而不是 *(-1 + b);，要小心。 -b[1]; // 與上一行結果相同。

陣列變數型態

陣列是一種變數型態，要宣告一個陣列變數並不困難。

int a[5]; // a是一個陣列變數，型態是int[5]。 // a是常數，不能更動其值。 int b[3][2]; // b是一個陣列變數，型態是int[3][2]。 // b是常數，不能更動其值。 int[5] a; // 不能這樣寫。 int[3][2] b; // 不能這樣寫。

C/C++宣告陣列變數的語法非常不直覺，造就許多亂象。既然事實已經無法改變，也只能接受它了。

比較特別的是，一般的變數我們都能知道變數裡所存放的值，只要使用變數的名稱就能得到變數值。然而我們無法得知陣列變數裡所存放的值，事實上我們也不需要用到此值。

陣列變數的指標

陣列變數既然是一個變數，當然也擁有記憶體位址了。同樣地，使用&就可以取得記憶體位址。

int a[5]; int (*pa)[5] = &a; // 宣告一個位址變數pa，儲存a所在的位址。 // 變數型態是int[5]加一個*，寫成int(*)[5]。 int b[3][2]; int (*pb)[3][2] = &b; // 宣告一個位址變數pb，儲存b所在的位址。 // 變數型態是int[3][2]加一個*，寫成int(*)[3][2]。

陣列變數會自動改變變數型態

http://c-faq.com/aryptr/aryptrequiv.html

使用陣列變數時，編譯器會自動幫忙把陣列變數改變成另一種型態的變數，並且設定其數值為陣列第零格所在的記憶體位址。

int a[5]; // 宣告一個陣列變數a，型態是int[5]。 cout << a; // 編譯器將a改變成型態為int*的變數，其值為&(a[0])。 int b[3][2]; // 宣告一個陣列變數b，型態是int[3][2]。 cout << b; // 編譯器將b改變成型態為int(*)[2]的變數，其值為&(b[0])。

只有三種情況，編譯器會保留陣列變數的原本模樣。

int a[5]; sizeof(a); // 得到a陣列的記憶體使用量。 cout << sizeof(a); // 印出 4 x 5 = 20。 &a; // 得到陣列變數所在的記憶體位址。 cout << (void*)&a; // 印出a所在的記憶體位址。 char s[5] = "abcd"; // 用string literal初始化陣列變數。 // "abcd"的型態是陣列，不會被轉換成指標。

搞得這麼複雜，是因為編譯器想盡辦法讓我們不能更動陣列變數儲存的數值。畢竟陣列是用來規劃大量變數的儲存位置，要是隨便更動陣列變數的話，牽一髮動全身，記憶體就大亂了。

另一方面，改變成指標形態之後，要存取陣列元素就方便多了。請參考前面Pointer章節提到的各種運算。

存取陣列元素

int a[5]; // 宣告一個陣列變數a，型態是int[5]。 // 注意到以下的a通通被編譯器改變成型態為int*的變數，其值為&(a[0])。 *a = 8; // 取陣列第0格，本來必須這樣寫。 a[0] = 8; // 其實就是 *(a + 0) = 8;，與上一行結果相同。 0[a] = 8; // 其實就是 *(0 + a) = 8;，與上一行結果相同。 *(a+1) = 7; // 取陣列第1格，本來必須這樣寫。 a[1] = 7; // 其實就是 *(a + 1) = 7;，與上一行結果相同。 1[a] = 7; // 其實就是 *(1 + a) = 7;，與上一行結果相同。

初始化陣列變數、初始化陣列元素

我們不能更動、也看不到陣列變數儲存的數值！只有編譯器和作業系統有權力初始化陣列變數，而我們只能初始化陣列元素。

int x; // 宣告一個變數。 int x = 5; // 宣告並且初始化一個變數。 int x(5); // 宣告並且用小括號初始化一個變數。 int a[5]; // 宣告一個陣列變數， int a[5] = 0x00000014; // 無法初始化陣列變數！compile error int a[5](0x00000014); // 無法初始化陣列變數！compile error // 況且陣列變數儲存的根本就不是記憶體位址！ int a[5] = {3, 4, 5, 1, 2}; // 宣告一個陣列變數a，型態是int[5]。 // 並且用大括號初始化陣列元素。 int a[] = {3, 4, 5, 1, 2}; // 讓編譯器幫忙數有多少個元素， // 讓編譯器幫忙決定變數型態。 // 型態是int[5]。 int a[5] = {3, 4}; // 宣告一個陣列變數a，型態是int[5]。 // 並且用大括號初始化前面兩個陣列元素。 // 編譯器會幫忙初始化後面三個陣列元素為零。

附帶一提，在新版本的C/C++當中，struct、vector也都可以使用大括號初始化元素，相當方便。這就留給讀者自行研究吧。

陣列元素是字元（也就是字串）

字串是一個char陣列。

// 宣告一個陣列變數s，型態是char[5]。 char s[5] = {'a', 'b', 'c', 'd', '\0'}; char s[] = {'a', 'b', 'c', 'd', '\0'};

前面提到，陣列變數會自動改變變數型態。凡是使用char[]型態的變數時，編譯器一樣會把變數型態改變為char*。

另外一定要提的是，C++ I/O遇到char*變數時，會雞婆地處理後續字元；而不是當作一個普通的記憶體位址。

char s[5] = {'a', 'b', 'c', 'd', '\0'}; char* t = s; // 宣告一個變數，型態是char*。 // 注意到s會被編譯器改變成型態為char*的變數， // 其值為&(s[0])，所以t的值也是&(s[0])。 cout << t; // 從第0個字元開始印！ // 自動印出後面的字元，直到遇到'\0'。 // 而不是印出&(s[0])這個記憶體位址。 cout << t+1; // 從第1個字元開始印！ cin >> t; // 從陣列第0格開始存。 // 自動讀入後面的字元，直到遇到space/tab/enter， // 並且自動補'\0'。 // 而不是讀入一個記憶體位址。 cin >> t+1; // 從陣列第1格開始存。 // 注意到以下的s通通被編譯器改變成型態為char*的變數，其值為&(s[0])。 cout << s; // 同前 cout << s+1; cin >> s; cin >> s+1; printf("%s", t); // C語言則是要明確規定印字串，才會印出後面字元。 printf("%p", t); // 印出&(s[0])這個記憶體位址。 printf("%s", s); printf("%p", s);

附錄：string literal

說到了字串，就不得不提一下string literal。雙引號括起的字串，稱做string literal，是一個陣列變數，而且編譯器會把陣列元素設定成常數，我們不能更動其值。

http://c-faq.com/aryptr/aryptr2.html

char* s = "abcd"; s[0] = 'e'; // runtime error! // "abcd"是string literal，變數型態是char[5]。 // 編譯器會自動幫忙把char[5]型態改變成為char*型態， // 其值為陣列第0格的記憶體位址，可以想做是字元'a'的記憶體位址。 // 不能更動陣列變數，也不能更動陣列元素。 char t[5] = "abcd"; t[0] = 'e'; // OK! // "abcd"是string literal，變數型態是char[5]。 // 特例：編譯器保留原本的char[5]型態，不會改變為char*型態！ // 於是就變成一種特殊的初始化語法。 // 不能更動陣列變數，但是可以更動陣列元素。 // 用string literal初始化陣列變數。 char s[5] = "abcd"; // 讓編譯器自己數有幾個字元。 char s[] = "abcd"; // 編譯器會幫忙連接雙印號字串，成為一個string literal。 char s[5] = "ab" "c" "d"; // "abcd"的變數型態是char[5]。 // 注意到編譯器會把"abcd"改變成型態為char*的變數， // 其值為陣列第0格的記憶體位址，可以想做是字元'a'的記憶體位址。 cout << "abcd"; // 從第0個字元開始印：abcd cout << "abcd" + 1; // 從第1個字元開始印：bcd cout << *"abcd"; // 印出第0個字元：a cout << *("abcd" + 1); // 印出第1個字元：b cout << "abcd"[2]; // 印出第2個字元：c cout << 3["abcd"]; // 印出第3個字元：d printf("%s", "abcd"); // 從第0個字元開始印：abcd printf("%s", "abcd" + 1); // 從第1個字元開始印：bcd printf("%p", "abcd"); // 印出第0個字元的位址：0x00440000 printf("%p", "abcd" + 1); // 印出第1個字元的位址：0x00440001 printf("%c", *"abcd"); // 印出第0個字元：a printf("%c", *("abcd" + 1));// 印出第1個字元：b

陣列元素是指標

我們也可以宣告一個存位址的陣列。

int*** a[5]; // a的每一個元素的變數型態都是int***。 // 至於a本身的變數形態寫成int***[5]。 a[0] = (int***) 0x00000010; *a = (int***) 0x0000010; // 與上一行意義相同

這樣的陣列變數，也可以用&得到記憶體位址。然而變數型態相當複雜，不實用，又難背，這裡就略過不提了。

陣列元素是陣列

這個太瘋狂了。我一點也不想介紹。反正就是多維陣列。

得到陣列大小

使用sizeof關鍵字就可以得到陣列大小。注意到，回傳的變數型態是size_t，一般來說是一個無號整數；回傳的變數型態絕對不是int。

int a[5]; sizeof(a); // 得到a陣列的記憶體使用量。 cout << sizeof(a); // 印出 4 x 5 = 20。

有一種情況要特別小心：函數的參數寫成陣列變數的模樣，但是編譯器事實上會幫忙改成指標變數。此時用sizeof得到的不是陣列大小而是指標大小。

void function(int a[5]) // 小心！a的變數型態其實是int*！ { cout << sizeof(a); // 印出 4 而不是 20！ }

附錄：動態記憶體

上個章節提到，宣告動態記憶體，編譯器給不出變數名稱，只能給個指標將就著用。不過在新版本的C/C++當中，已經可以給出變數名稱了。

int n; cin >> n; int* a = new[n]; // 給個int*將就著用。 // 注意到這完全跟陣列變數無關。 int b[n]; // 動態記憶體！ // 至於b的變數型態是什麼，我也不知道！

附錄：heap與stack

編譯器進行記憶體管理，有兩個概念稱做heap和stack，分別是指整個記憶體的前端、後端這兩塊區域。heap通常用來存放程式當中一開始就建立好的變數，以及存放動態記憶體；stack用來存放執行過程中新建立的變數。

然而heap和stack的實際運作情形，在不同的編譯器和作業系統可能有一些差異，似乎沒有一個絕對的說法。

當記憶體用量過大，造成heap與stack兩塊區域相撞，此時稱做stack overflow，程式會當機。

http://www.newty.de/fpt/index.html

sstream - 讀取一行不知道有多少個的數字

sstream當中的istringstream物件，可以以近似於cin的方式來讀取一個string變數內含的資料。

sstream的意義為string stream，也就是說，把string變數看待成stream。至於istringstream的i，應該就是指input之意吧。

下面的程式可以讀入一行不知道個數為多少個的數字，並輸出這些數字的總和。

#include <sstream> void demo() { string line; while ( getline( cin, line ) ) // 利用 getline() 讀入一行輸入 { // 針對此行建立一個 istringstream 物件 istringstream in( line ); int sum = 0, x; while ( in >> x ) sum += x; cout << sum << endl; } }

sstream - 讀取不知道有多少行的輸入、並且做tokenize

#include <sstream> int main() { int a, b, c; char line[100]; while (cin.getline(line, 100) && *line) { istringstream sin(line); sin >> a >> b >> c; cout << "read abc: " << a << " " << b << " " << c << endl; } return 0; }

UVa 483

cstdio - 數字轉字串，字串轉數字

C的標準函式庫提供了兩個非常好用的函式，可以快速的轉換字串成為數值。

char s[10]; int n; int count = sscanf(s, "%d", &n); // 字串s轉數字n int length = sprintf(s, "%d", n); // 數字n轉字串s

UVa 10427

iostream iomaip - 八、十、十六進位數的輸出入

int num; cin >> hex >> num; cout << hex << num; // 讀入/輸出八進位數字 cin >> dec >> num; cout << dec << num; // 讀入/輸出十進位數字 cin >> oct >> num; cout << oct << num; // 讀入/輸出十六進位數字 // 讀入/輸出 n 進位數字，但是 n 只能是 8、10、16 #include <iomanip> cout << setbase(n) << num; cin >> setbase(n) >> num;

就算使用者輸入ABC或abc（十六進位表示法），compiler還是可以將之轉換成十進位數字，存到num裡面。

十六進位時，輸入的數字有0x或0X開頭也可以（不要把0打成英文字母o或O了）。

附帶一提，因為iomanip已經建好了hex oct dec等關鍵字，所以用setiosflags(ios::hex)是沒有任何效果的。【有待商榷】

double num; cin >> num;

就算使用者輸入2e3（科學記號表示法），compiler還是可以將之轉換成十進位數字，存到num裡面。

UVa 537

string cstring - 字串運算

一、讀字串，直到遇見空白、換行、檔案結束為止。

string s1, s2; cin >> s1 >> s2; char s1[100], s2[100]; cin >> s1 >> s2;

二、讀字串，直到一定數量，或者遇見空白、換行、檔案結束為止。

string s; cin >> setw(50) >> s; char s[100]; cin >> setw(50) >> s; // 讀入49個字元和補一個'\0'

三、讀一行。

string s; getline(cin, s); // C++ char s[100]; cin.getline(s, 100); // C++ char s[100]; gets(s); // C

四、讀全部。

string s; getline(cin, s, EOF); // C++ char s[10000]; cin.getline(s, 10000, EOF); // C++ char s[10000]; fgets(s, 10000, stdin); // C

五、讀到特定字元為止。

string s1; getline(cin, s1, '$'); char s1[100]; cin.getline(s1, 100, '$');

六、交換。

string s1, s2; s1.swap(s2); // O(1) char s1[100], s2[100], temp[100]; strcpy(temp, s1); strcpy(s1, s2); strcpy(s2, temp); // O(N)

七、長度。

string s1; int length = s1.length(); // O(1) char s1[100]; int length = strlen(s1); // O(N)

八、比大小。

string s1, s2; if (s1 > s2) parapara... if (s1 < s2) parapara... if (s1 == s2) parapara... char s1[100], s2[100]; if (strcmp(s1, s2) == 1) parapara... if (strcmp(s1, s2) == -1) parapara... if (strcmp(s1, s2) == 0) parapara... 等於 -1 時是 a < b : abc 和 edf 、 abc 和 abcde 、 abc 和 acb。 等於 0 時是 a = b : abcde 和 abcde。 等於 1 時是 a > b : b 和 a。 a > b 的意思，就是 a 的字典順序在 b 之後，順序比較後面。

九、字串後面接字串。

string s1, s2; s1 += s2; char s1[100], s2[100]; strcat(s1, s2); // 小心s1空間不足

set - 儲存字串

char s[10][100]; char t[100]; struct cmp { bool operator()(const char* a, const char* b) { return strcmp(a, b) < 0; } }; void string_matching() { set<char*, cmp> dictionary; for (int i=0; i<10; ++i) dictionary.insert(s[i]); set<char*, cmp>::iterator it = dictionary.find(t); if (it == dictionary.end()) cout << "字典裡沒有t字串"; else cout << "字典裡有t字串"; }

algorithm - 排序

sort()為Quick Sort，stable_sort()為Merge Sort。

排序基本資料型態的方法。

int A[] = {1, 4, 2, 8, 5, 7}; int N = sizeof(A) / sizeof(int); sort(A, A + N); vector<int> B(A, A + N); sort(B.begin(), B.end());

排序自訂資料型態的方法有兩種寫法。

struct Point {int x, y;} A[10]; bool compare(const Point& i, const Point& j) { return i.x < j.x || i.x == j.x && i.y < j.y; } void demo() { sort(A, A + 10, compare); vector<Point> B(A, A + 10); sort(B.begin(), B.end(), compare); } struct Point { int x, y; bool operator<(const Edge& j) const { return x < j.x || x == j.x && y < j.y; } } A[10]; void demo() { sort(A, A + 10); vector<Point> B(A, A + 10); sort(B.begin(), B.end()); }

ctime - 計時

clock_t start, end; start = clock(); function(); // 估計function的執行時間 end = clock(); cout << end - start << endl; // 單位是千分之一秒

ctime - 亂數

// 要先設定一個 random seed，用系統時間來設定 srand( static_cast< unsigned int >( time(0) ) ); // 取 0~99 之間的亂數 for (int i=0; i<10; i++) { int k = rand() % 100; cout << k << "\n"; }

climits - 變數型態的極值

CHAR_BIT	char變數的記憶體大小(bits)    8
MB_LEN_MAX	一個字元的記憶體大小(byte)    1(英文系統) 2(中文系統)
SCHAR_MIN	有號char變數的下限值          -128
SCHAR_MAX	有號char變數的上限值          127
UCHAR_MAX	無號char變數的上限值          255
CHAR_MIN	char變數的下限值              -128 或 0
CHAR_MAX	char變數的上限值              127 或 255
SHRT_MIN	short int變數的下限值         -32768
SHRT_MAX	short int變數的上限值         32767
USHRT_MAX	無號short int變數的上限值     65535
INT_MIN		int變數的下限                 -2147483648
INT_MAX		int變數的上限值               2147483647
UINT_MAX	無號int變數的上限值           4294967295
LONG_MIN	long int變數的上限值          -2147483648
LONG_MAX	long int變數的下限值          2147483647
ULONG_MAX	無號long int變數的下限值      4294967295

附帶一提< limits.h >和< climits >是屬於C的函式庫，C++另有推出< limits >。

UVa 465

cassert - 檢查程式有沒有問題

assert()可以用來檢查程式中的變數數值正不正確。

在程式執行的期間，一旦執行至assert()的地方，若是assert()括號之中的敘述句不成立，就會跳出程式有問題的視窗。若沒有跳出任何程式有問題的視窗，就意味著程式成功的通過了所有assert()的檢查。

下面的這段程式碼利用了assert()，藉以檢查queue的運算是否如預期所料。

queue<int> Q; Q.push(8); Q.push(7); Q.push(6); Q.push(2); assert(Q.size() == 4); assert(Q.back() == 2); assert(Q.front() == 8); Q.pop(); assert(Q.front() == 7); Q.pop(); assert(Q.front() == 6); Q.pop(); assert(Q.front() == 2); Q.pop(); assert(Q.empty());

typeinfo - 印出變數型態的名稱

利用typeid(變數).name()這個語法，可以得到該變數的變數型態。如果該變數是一個物件，則會得到該物件所屬的class名稱。範例程式碼如下所示：

class haha { ...... } obj; int value = 0; int array[2][3]; void demo() { cout << typeid(obj).name(); // 得到class haha cout << typeid(value).name(); // 得到int cout << typeid(array).name(); // 得到A2_A3_i }

VC++和gcc同時能使用long long的方法

/* Declares 64-bit unsigned integer type 'uint64' */ #ifdef _MSC_VER typedef unsigned __int64 uint64; #else typedef unsigned long long uint64; #endif