Chapter II. 新手上路
實作技巧
基本常識
作者baluteshih
協作者dj4zo6u.6
先備知識線上評測系統

萬用標頭檔


在比賽時我們常常需要使用各式各樣的 C++ 內建函式,而呼叫這些函式必須引用相對應的標頭檔。例如需要 #include <iostream> 才能使用 cin 、需要 #include <algorithm> 才能使用 sort……每次都要記哪些函式屬於哪個標頭檔,還需要全部在比賽中打出來,又累又慢,就不能簡單的一次到位嗎?

在大多數情況下,我們都可以仰賴 <bits/stdc++.h> (俗稱萬用標頭檔)。怎麼使用呢?我們可以把幾乎所有 #include 開頭的程式碼都刪掉,直接寫下一行

#include <bits/stdc++.h>

就搞定了!我們已經可以呼叫幾乎所有 C++ 內建的標準函式。

這簡單的一行到底做了什麼呢?在 C++ 裡面 #include XXX 的做的事情差不多是將一份預先寫好的 XXX 文件直接貼在程式碼裡面,而若讀者去了解一下 <bits/stdc++.h> 的內容的話,可以看到類似這種東西,也就是 <bits/stdc++.h> 幾乎把所有標準函式庫的標頭檔都在裡面引用了一遍!

注意到我們強調了「大多數情況下」適用,這是因為 <bits/stdc++.h> 並不在 C++ 的官方規範中,儘管目前多數的 Online Judge、包含比賽使用的評測系統都支援 <bits/stdc++.h> 的引用,但還是難免會在少數地方無法使用,特此提醒。

不過既然有這種懶人作法,為什麼 C++ 不一口氣幫大家內建好所有函式就好,還要讓使用者一個一個引用呢?別忘記程式碼寫完之後,是需要先經過「編譯器」進行編譯才能成為一個程式的,而既然引用的意義是展開一份預先寫好的文件,一旦引用了 <bits/stdc++.h>,就等價展開了無數標準函式的程式碼,使得 C++ 編譯器的編譯速度變慢。有興趣的讀者可以嘗試寫兩份輸出 Hello World 的程式碼,一份引用 <bits/stdc++.h>、另一份只引用 <iostream>,並分別編譯兩份程式碼來感受一下他們的編譯速度,相信在大多數電腦上都有著肉眼可辨識的差異。

命名空間


如果讀者有嘗試參考過各種 C++ 的程式範例、或者是一些程式競賽選手寫的 C++ 程式碼,可能時常看見以下這一行

using namespace std;

這一行是在做什麼呢?讓我們看看以下這份程式碼

#include <iostream>
using namespace std;

int main() {
    cout << "Hello World!\n";
}

如果把 using namespace std; 這行拿掉並編譯的話,應該會顯示如下的錯誤訊息

error: 'cout' was not declared in this scope; did you mean 'std::cout'?

這是因為 C++ 其實把大多數的標準函式都包在了一個名為 std 的「命名空間 (namespace) 」裡面。用簡單的比喻來說,當我們提到「資工系」時,一旁的人通常不會知道我們是在講「臺灣大學資工系」、「陽明交通大學資工系」、又或是其他學校的資工系,這是因為不只有一間大學有資工系。所以如果寫出「臺灣大學資工系」這個完整的詞,大家就會知道我們在指臺灣大學底下的資工系。若是拿掉 using namespace std ,範例程式中的 cout 就得寫成完整的函式名稱「 std::cout 」,代表使用 std 這個 namespace 底下的 cout 函式。

一個命名空間就好像一間大學,裡面有各式各樣的科系,每次提到一個科系都得講一次哪個大學不會太麻煩嗎?如果我們在臺灣大學裡提到「資工系」,旁人都會默認我們是指「臺灣大學資工系」,而這就是 using namespace 的含義。讀者可以想像 using namespace std 就好像進入了 std 這間大學,也因此一提到 cout 時,C++ 就會知道我們在使用 std::cout

using namespace std 雖然方便,但一個明顯的缺點就是「變數撞名」,讀者可以想像如果我們同時進入了臺灣大學和陽明交通大學兩個空間裡,兩所學校都有的資工系就會變得分不清楚了!這也是為什麼大型 C++ 專案通常會迴避直接使用 using namespace ,如果一口氣引用了太多函式,很容易引起不容易察覺的變數撞名,導致編譯錯誤。不過在比程式競賽的場合,通常都不用擔心這個問題,直接大膽寫下 using namespace std 吧!

輸入優化?


讓我們來看看以下例題:

例題
[Tutorial] 輸入輸出練習
Source:NCOJ 16

來做點輸入輸出的練習吧!

現在輸入 $N$ 行 $N$ 個整數,請你原封不動的把他們輸出出來。

條件限制
  • $1\leq N \leq 5\times 10^6$

輸入 $N$ 個數字,原封不動的把他們輸出出來?還不簡單,馬上就來寫:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        cout << x << "\n";
    }
}

...結果上傳時吃了一個 TLE!?這該怎麼辦?

左想右想這題也沒有什麼演算法可言,剛入門的新手可能會不知所措。這其實是因為 C++ 的預設輸入非常的慢!

但為什麼這麼慢呢?我們先來看看要怎麼解決這個問題,只要把程式碼改成這樣:

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        cout << x << "\n";
    }
}

上傳後就奇蹟似的 AC 了!

為什麼只加入一行 ios::sync_with_stdio(false), cin.tie(nullptr); 就可以快這麼多呢?首先要先知道,C++ 其實是跟他的前身,C,有兼容的,也就是說大多數的 C 語法在 C++ 都是可以使用的。

而講到 C 的輸入和輸出,就是 <stdio.h> 裡面 scanfprintf,可別以為輸入跟輸出是件很簡單的事情,這些輸入和輸出的函式們背後還得維護各式各樣的資訊,如果 C++ 完全不管 C 原本的輸入輸出方式自己寫了一套 cincout,只要使用者共用 scanfcin 兩種輸入方式,整個程式就會大亂!

因此,cincout 預設是會顧及 scanfprintf 的輸入輸出系統的,讀者可以想像成是他們要額外花心力去配合 C,這樣一來速度變慢自然是合理的,而 ios::sync_with_stdio(false) 就是關掉與 C 同步的關鍵函式!也就是說,加了這行,C++ 就不用再特別顧及 C 的輸入輸出了——相對的,加了這行之後,千萬不要再混用 C++ 跟 C 的輸入輸出。

cin.tie(nullptr) 的作用是什麼?這其中的原因更為複雜一些,若簡略一點說明就是 C++ 顧慮到了 cincout 同時使用可能產生的潛在問題,因此 cin 會「flush」cout。什麼是 flush 呢?想像輸出就像是 C++ 要發薪水給終端機,C++ 通常都認為終端機是一個需要每天用錢的人,所以他每天都走到終端機面前發給他薪水;但現實生活中,薪水通常都是一個月一個月在發的,如果 C++ 每天都要特別花時間走到終端機面前給他薪水的話,與蒐集起來一口氣發一個月的薪水相比足足就多花了三十倍的時間在走路!這裡,「走過去發薪水」的動作正是我們正在比喻的「flush」。

這也是為什麼 flush 對速度的影響這麼大,因為 C++ 每次都得花心思讓終端機收到輸出,而透過 cin.tie(nullptr) 解開 cincout 的綁定,就可以將每次動作都 flush 的這件事取消,也就是讓 C++ 先把輸出蒐集起來到一定的量後、再一口氣輸出給終端機,進而大大增加速度!

拿這題作為例子,如果輸入是

3
1
2
3

在下面這張圖中,左圖顯示了加上 cin.tie(nullptr) 後在終端機輸入的結果、右圖則是沒有加上的結果,讀者可以想一下「每次輸入就輸出」和「全部輸入完才一次輸出」的差別來理解這兩張圖。

endl

加了 ios::sync_with_stdio(false), cin.tie(nullptr); 還是 TLE 嗎?你的程式是不是這樣的呢?

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        cout << x << endl;
    }
}

與前面的差別在於,第 11 行的換行不是使用 "\n",還是 endl——沒錯,這兩者是有差別的!

endl 到底是什麼呢?他其實是「換行」加上「flush」的意思,這裡的 flush 就是我們上面才提到的東西,也就是說,使用 endl 就跟沒有加 cin.tie(nullptr) 是一樣的,在比賽時千萬別誤用了。