10.3 vector 的陣列與巢狀 vector

vector 本身也是一種型態，所以它能當陣列的元素，甚至能當另一個 vector 的元素。這一節就用這兩種「裝 vector 的櫃子」，回頭解決開場售票口的難題。

¶vector 的陣列

「vector 的陣列」是競程的常用場景：題目給很多條數列、總長度有上限，但單條長度沒有上限。二維陣列得替每條數列都按上限開好開滿，記憶體直接爆炸；vector 的陣列讓每條數列各自長大，總共大約只花實際元素的空間：

const int MAX_N = 100005;
vector<int> line[MAX_N];   // 10^5 + 5 條各自獨立、長度可各異的數列，每條一開始都是空的

宣告方式跟普通陣列一樣（全域＋const 常數大小，上冊 6.1 的慣例）——寫死的是條數的上限，每條的長度則交給 vector 自己伸縮。每條 vector 自帶少量管理資訊、也常多預留一點空間備用，但跟「按最壞上限開滿」相比是天壤之別——開 10^5 條空 vector 只花一點固定成本，記憶體主要隨實際加入的元素成長。

先用互動圖解建立畫面感再往下讀（本節兩種寫法都在裡面，讀到巢狀 vector 時記得回來切分頁玩）：

開場的售票口場景，正是本站題目〈排隊模擬 1〉：n 個售票口（n \le 10^5），依序發生 Q 筆事件——1 x d 是「國家編號 d 的民眾加入 x 號窗口的隊尾」、2 x y 是「x 號窗口隊尾的人移動到 y 號窗口的隊尾」；所有事件結束後，由隊首到隊尾輸出每個窗口的名單。10.2 的工具已經到齊，我們把它完整解掉：

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 100005;
vector<int> line[MAX_N];               // line[i]：i 號售票口的隊伍，隊首在前、隊尾在後

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < q; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            int x, d;
            cin >> x >> d;
            line[x].push_back(d);              // 國家 d 的民眾加入 x 號窗口的隊尾
        } else {
            int x, y;
            cin >> x >> y;
            line[y].push_back(line[x].back()); // x 號隊尾的人排到 y 號窗口的隊尾……
            line[x].pop_back();                // ……並離開原本的隊伍
        }
    }
    for (int i = 1; i <= n; i++) {
        int len = line[i].size();              // size() 先存進 int（10.4 會解釋原因）
        cout << len;
        for (int j = 0; j < len; j++) {
            cout << ' ' << line[i][j];
        }
        cout << '\n';
    }
    return 0;
}

執行結果（用題目的範例輸入）：

2 5 7
2 24 233

兩種事件各只花一到三行：「加入隊尾」就是 push_back；「跳隊」拆成三步——back() 看看 x 號隊尾是誰、push_back 把他排進 y 號隊尾、pop_back 讓他離開原隊伍。題目保證事件 2 發生時 x 號窗口一定有人，所以這裡的 back() 與 pop_back() 不會踩到「空 vector 是 UB」的地雷；沒有這種保證的題目，動手前記得先 empty() 檢查。

¶巢狀 vector

容器裡也能裝容器：vector<vector<int>>——連「有幾條數列」都可以動態增減（注意角括號是一層包一層）。剛剛的解法只要把 line 的宣告搬進 main、改成巢狀版，其餘一行都不用動：

int n, q;
cin >> n >> q;
vector<vector<int>> line(n + 1);   // n + 1 條空數列：用編號 1 到 n，0 號放著不用

「（長度，初始值）」的長度可以是變數（10.2），所以巢狀版連 MAX_N 都不需要——題目給幾個窗口就開幾條。巢狀 vector 也能用 push_back 一次加入一整條數列：

vector<vector<int>> g;                           // 一開始 0 條數列
g.push_back({1, 2, 3});                          // 加入一整條數列
g.push_back({4});
cout << g[0][2] << ' ' << g[1].size() << '\n';   // 輸出 3 1

g[0][2] 的讀法跟二維陣列（上冊 6.9）一樣：第 0 條數列的索引 2 元素。但心裡的圖像要換掉：這不是一個方方正正的表格，而是兩步取值——g[0] 先從外層挑出第 0 條（它本身就是一個 vector），後面的 [2] 再取那條自己的索引 2。也因為每條各自伸縮，g[0] 長度 5、g[1] 長度 0 完全合法，每一條的索引都從自己的 0 開始算。（回到上面的圖 10-2 切到「巢狀 vector」分頁，點任一個格子——訊息會把這兩步逐字拆給你看。）

兩種寫法在 Level 0 幾乎等價，選哪個都行：條數上限已知、想省事就用全域的 vector 陣列；條數執行時才知道，或之後想整個複製（10.6 會看到）就用巢狀 vector。

動手試試看：先解掉好多數列（簡單版）（vector 的陣列），再把〈排隊模擬 1〉自己從零重打一遍提交——能不看課本寫出來才算真的會。行有餘力，挑戰進階版〈排隊模擬 2〉：一次移動 k 個人、順序還可能反轉，工具完全一樣，考驗你對 push_back、back、pop_back 的熟練度。