10.1 C++ 標準函式庫、容器與 O 記號
其實你早就在用標準函式庫了。cin、cout（<iostream>）、abs 和 gcd（上冊 7.6）、isdigit（8.5）、sqrt（9.8）——這些都不是你寫的，也不是 C++ 語言本身的關鍵字，而是 C++ 標準函式庫（standard library） 提供的：一大箱寫程式常用的現成工具，跟著編譯器一起安裝，#include 對應的標頭檔（上冊 1.1 的名詞）就能拿來用。
除了「函式」，標準函式庫還提供另一類東西：容器（container）。函式庫上架的現成品其實有兩類——現成的函式，和現成的資料型態；容器屬於後者：每種容器用起來，就是一種新的型態。具體來說，一個容器就像一個型態專屬的整理櫃：
- 它負責裝很多個同型態的元素（一櫃整數、一櫃字串……）。
- 它附帶現成的操作：加入新元素、取得某個位置的元素、移除元素、詢問目前裝了幾個……
你可能也聽過 STL（Standard Template Library）這個詞——大家常拿它泛指標準函式庫裡的容器這類工具。
本單元先學兩個競程最常用的容器：vector（長度可變的陣列）和 string（字串），再學一個常跟容器搭配的工具型態 pair（成對資料；嚴格分類下它不是容器——見上方小提醒），外加延伸知識 array。標準函式庫裡還有更多容器（queue、stack、set、map……），屬於 Level 1 以上的內容，本書不介紹。順帶一提，這些名字的正式全名都有個 std:: 前綴（std::vector、std::string——std 是標準函式庫的「姓」）；因為本書範例都寫了 using namespace std;，平常省略不寫。
¶操作有快有慢：O 記號
上冊 4.9 教過估運算量：數程式大約執行幾次運算，再用「每秒約 10^9 次」換算成秒。容器把很多工作包裝成一行成員函式，但包起來不代表不花時間——同樣一行，背後可能只動一步，也可能整批搬家。競程用 O(\cdot) 記號標示「這一行背後是幾步」：它描述的是運算次數隨資料量 n 成長的「形狀」。Level 0 下最常遇到的是這五種：
| 記號 | 直覺 | n 變十倍會…… | 典型例子 |
|---|---|---|---|
| O(1) | 一步到位 | 一樣快 | 用索引取值 v[i]、詢問長度 size() |
| O(\sqrt{n}) | 只做根號次 | 慢三倍多 | 質數判斷（試到 \sqrt{n} 就停，見下） |
| O(n) | 把資料掃一遍 | 慢十倍 | 找最大值、把整個 vector 複製一份 |
| O(n \log n) | 比掃一遍慢一點點 | 慢十幾倍 | sort（第十一單元） |
| O(n^2) | 兩兩都比一次 | 慢一百倍 | 雙層迴圈 |
表裡的質數判斷比上冊 4.5 的例題聰明一截。那時我們拿 2 到 n-1 逐一試除，是 O(n)；但因數其實是成對出現的——36 = 2 \times 18 = 3 \times 12 = 4 \times 9 = 6 \times 6，每一對裡總有一個不超過 \sqrt{36} = 6。所以只要試到 \sqrt{n} 都沒找到因數，就能斷定 n 是質數，運算次數從 n 次縮成約 \sqrt{n} 次——n = 10^{12} 也只要試一百萬次。
兩個閱讀規則：
- 只看形狀，不看零頭。 一圈做 3 個運算的單層迴圈總共約 3n 次，我們照樣叫它 O(n)——決定生死的是「n 變大時它怎麼長」，不是前面的倍數。n = 10^6 時，3n 和 n 都是「百萬級」，n^2 卻是「兆級」——差距在形狀，係數只是零頭。（同理，O(1) 的準確意思是「操作量不隨 n 增加」，不代表電腦真的只執行一步。）
- \log 先不用懂。 O(n \log n) 裡的 \log 是什麼，第十七單元會用「一直除以 2」帶你直觀認識；現在只要記住它「比 O(n) 慢一點點、比 O(n^2) 快非常多」，10^6 筆資料通常也不成問題。
繼續往下之前，先去看資訊之芽算法班的〈複雜度分析〉影片，從例子建立對 O 記號的直觀，再回來讀後面的內容會順很多。
¶三步驟：估這個做法會不會 TLE
O 記號配上上冊 4.9 的 10^9 法則，就是競程拿到題目的標準決策流程：
- 認出 O：這個做法有幾層跟 n 有關的迴圈？用到的容器操作，查成員函式表看 O 標籤。
- 代入最大的 n：把題目給的上限代進去，得到總運算次數。
- 除以 10^9、跟時限比：本站題目時限多在 0.5 到 2 秒。
例：n \le 10^5 的題目想用雙層迴圈兩兩比較——O(n^2) 代入得 10^{10} 次、約 10 秒，穩穩 TLE，得換做法；改成掃一遍的 O(n) 做法只要 10^5 次，連 0.001 秒都不到。這正是上冊 4.9「看輸入大小猜做法」的升級版：以後看到 n \le 10^5，心裡想的不再是「兩層迴圈太慢」，而是「這題通常要 O(n \log n) 以內的做法」。
不過要注意：10^9 是極限，不是安全線。 上冊 4.9 的 10^9 說的是「機器一秒大約做得完幾次簡單運算」，那是貼著上限的數字——真的估到十億次，只要運算裡有除法、取餘這類慢一點的操作，或輸入輸出的量大，就會掉到時限外。而出題者在設計題目時，通常是讓正解的運算量落在 10^8 上下：留一段餘裕，正解才不會因為機器或寫法差一點就被卡掉。所以估完之後這樣讀：
| 估出來的運算次數 | 怎麼判斷 |
|---|---|
| \le 10^8 | 大致安全，多半就是出題者設想的做法 |
| 10^8 \sim 10^9 | 危險地帶：時限鬆一點可能過、緊一點就 TLE——先想想有沒有更快的做法 |
| > 10^9 | 幾乎確定 TLE，一定要換做法 |
三步驟上手之後，請接著讀 NTUCPC Guide 的〈複雜度〉：那裡有完整的計算方法（逐行分析、加乘法則）與「n 上限對應建議複雜度」的完整對照表（其中「遞迴複雜度」段落屬 Level 1 以上，可先跳過）。本單元教到「看懂標籤、三步驟估出會不會 TLE」為止——應付 Level 0 下的題目完全夠用；常見的優化手法（數學公式、標記陣列、\sqrt{n}、\log……）在第十七單元有一整個單元的經典實例；正式的複雜度分析（嚴格定義與證明）屬 Level 1 以上。
本單元接下來的每張成員函式表都標了 O(\cdot) 這一欄——查表時多看一眼，就是在練這套流程的第一步。