偽指標

偽指標是一種指標的替代寫法，舉個例子，假設我們想要寫一個普通的單向 Linked List，好好使用指標寫的話，可能會寫出一個像這樣的 struct：

struct Node {
    int val = -1;
    Node *next = nullptr;
};

// b 放在 a 後面，假設 b->next == nullptr
void insert(Node *a, Node *b) {
    b->next = a->next;
    a->next = b;
}

void traverse(Node *cur) {
    while (cur != nullptr) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << "\n";
}

void delete_list(Node *cur) {
    while (cur != nullptr) {
        Node *tmp = cur;
        cur = cur->next;
        delete tmp;
    }
}

void test() {
    int n = 10;
    Node *start = nullptr, *last = nullptr;
    for (int i = 0; i < n; i++) {
        Node *node = new Node();
        node->val = i;
        if (last) insert(last, node);
        if (!start) start = node;
        last = node;
    }
    // 遍歷 linked list，輸出 0 1 2 ... 9
    traverse(start);
    delete_list(start);
}

在這個程式碼裡面，每個節點存了指向下一個節點的指標，要是不喜歡用指標的話，就可以使用偽指標。偽指標的精神非常簡單：真正的指標存的是東西在記憶體裡的位置，我們也可以仿照指標的精神，把東西都放在一個陣列裡面，然後直接用它在陣列裡的 index 來作為指向它的指標。

這樣寫的話，就會變成：

struct Node {
    int val = 0;
    int next = -1; // 用 -1 代表 nullptr
};
Node arr[100];
int cnt = 0;

int newnode() {
    return cnt++;
}

void insert(int a, int b) {
    arr[b].next = arr[a].next;
    arr[a].next = b;
}

void traverse(int cur) {
    while (cur != -1) {
        cout << arr[cur].val << " ";
        cur = arr[cur].next;
    }
    cout << "\n";
}

// 不用寫 delete 了

void test() {
    int n = 10;
    int start = -1, last = -1;
    for (int i = 0; i < n; i++) {
        int node = newnode();
        arr[node].val = i;
        if (last != -1) insert(last, node);
        if (start == -1) start = node;
        last = node;
    }
    // 遍歷 linked list，輸出 0 1 2 ... 9
    traverse(start);
}

基本上是在做一模一樣的事情，只是 new Node() 改成呼叫 newnode() 這個 function，它會回傳用來存節點的陣列 arr 裡一個還沒用過的位置，然後本來使用指標的地方，都改成存在那個節點 arr 裡的 index，這個 index 就是所謂的偽指標。

這看起來只是換個寫法而已，除了不喜歡指標的人，在需要用指標時可以改用偽指標以外，有時候這麼寫還會有額外的好處。

看起來就是一件標準的雙向 linked list 可以做到的事情，不過題目指定要刪的節點的方式是「指定某個節點編號、刪掉它的下一個節點」，所以我們必須要能夠很快的找到編號 $k$ 的節點在哪裡。雖然 linked list 本身不支援隨機存取，但當然總是可以很無腦的開一個陣列，存下指向每一個節點的指標，不過既然都開陣列了，要是用的是偽指標，只要直接好好把第 $i$ 個節點放在陣列的第 $i$ 格，那就不需要做額外的事了！

要是懶得寫成 struct、每個節點裡的資訊夠少，像是這題中，每個節點需要存的資訊只有左邊的人和右邊的人而已（第 $i$ 個人放在陣列第 $i$ 格，就也不需要額外再存節點編號），更可以直接開兩個陣列 l、r，l[i] 和 r[i] 就是第 $i$ 個人左、右的兩人，然後用 linked list 的方式處理刪點即可。這樣也可以用完全跟指標無關的語言解讀：l[i] 就是站在 $i$ 左邊的人的編號、r[i] 就是站在 $i$ 右邊的人的編號。

當然的，只要沒有省記憶體之類的需求，用指標實作或是使用 std::list 並儲存 iterator 也是完全可以的，偽指標只是一種替代方案。

偽指標除了是實作上的替代品之外，其實在記憶體管理方面是可以帶來真正的好處的。

在剛才實作 linked list 的例子中，注意到我們寫的指標版本裡，有一個 function delete_list()，這個 function 是用來把一個 linked list 中所有節點都 delete，這是因為我們的 Node 都是用 new 開出來的，或是不手動刪除的話，他們在程式執行結束前都會佔用一塊記憶體空間，沒用了就刪掉可以節省不必要的浪費。不過，這樣要多實作一段找出所有節點的指標並一一 delete 的程式碼，有一點麻煩，如果用的是陣列的話，不需要用到了之後，有更輕鬆的作法能避免浪費空間，像是：

• 在下次需要使用時直接把上面程式碼裡那個 cnt 重設成 0、別忘了 newnode() 要重新初始化（直接寫 arr[cnt] = Node() 就可以了），這樣就可以直接重複利用空間。
• 如果真的不需要用了，而且這個陣列也是用 new 出來的，那只要 call 一次 delete [] arr 就好。

不管怎樣都比遍歷一次 linked list 再一一刪除節點輕鬆很多，在遇到更複雜的資料結構的時候，這麼做的方便性就會相當顯著了。這種「開一個陣列來儲存物件」的方法叫作 memory pool，就是開一個陣列當成記憶體使用，其實不一定要跟偽指標搭配，若比較喜歡指標的話，用指標來當作儲存位置的方式也是可以的，這個方法主要的目的是避免使用 new。

如果一開始沒辦法確定 memory pool 會需要存多少東西，也可以用像是 std::vector 的動態陣列來當作儲存物件的陣列，只不過有一件事情需要注意：當 std::vector 的大小成長時，有時會為了找到一塊更大的記憶體空間，而自動搬家到記憶體裡比較空曠的地方，此時如果你本來有存指向 vector 中位置的指標或 iterator，它是不會自動指到搬家後的位置的，得用偽指標的方法，直接儲存在陣列裡的 index 才不會出事。

最後，使用 memory pool 還有一個好處是，電腦在讀取一塊連續記憶體上的資料時，會比讀取一堆散在各處的資料來的快，而使用 memory pool 就能讓資料都放在一個陣列裡，確保它們都在一塊連續記憶體內，而且使用 memory pool 也能避免頻繁使用 new、delete 等等記憶體操作，能夠提升一點程式的執行速度。