基於順序存儲的多叉樹實現（五）：兄弟遍歷迭代器完整設計

系列背景

本系列實作基於連續記憶體（陣列/向量）的多叉樹容器 mtree。此篇聚焦兄弟遍歷迭代器：訪問給定節點的所有同胞節點（含自身）。

迭代器類型定義

template<bool is_const, bool is_reverse>
class sibling_iterator_impl : public iterator_base_impl<is_const> { ... };

using sibling_iterator           = sibling_iterator_impl<false, false>;
using reverse_sibling_iterator   = sibling_iterator_impl<false, true>;
using const_sibling_iterator     = sibling_iterator_impl<true, false>;
using const_reverse_sibling_iterator = sibling_iterator_impl<true, true>;

核心介面

• 構造/複製/轉換自 iterator_base
• 前置/後置 ++/--、+/-= 算術運算
• begin()/end() 範圍界定
• 受保護導航核心：first/last/increment/decrement（分正向/反向標籤分發）

關鍵導航邏輯（順序存儲索引運算）

節點結構含 first_child, last_child, next_sibling, prev_sibling, parent（均為相對偏移量）。

• forward_first：父節點 first_child 偏移 → 第一個孩子。
• forward_last：父節點 last_child 偏移 → 最後一個孩子。
• forward_next：當前節點 next_sibling 存在？偏移跳轉 : 返回 end() (size)。
• forward_prev：當前節點 prev_sibling 存在？偏移跳轉 : 返回 end()。

構造函數邏輯

從基底迭代器轉換時，若節點非空，計算並保存父節點偏移至 root_（作為遍歷根界）。根節點無父節點時 root_ = size()。

使用範例

// 正向遍歷兄弟
mtree<int,false>::iterator_base node = ...;
auto it = node.sibling_begin(); // 或 sibling_iterator it = node;
auto last = --it.end();
for (it = it.begin(); it != it.end(); ++it) {
    cout << *it;
    if (it != last) cout << ' ';
}

// 反向遍歷
auto rit = node.reverse_sibling_begin();
auto rlast = --rit.end();
for (rit = rit.begin(); rit != rit.end(); ++rit) { ... }

設計亮點

1. 標籤分發：no_reverse_tag/reverse_tag 靜態多型，編譯期消除分支，零開銷抽象。
2. 統一介面：四種迭代器共享介面，符合 STL 迭代器概念（雙向迭代器）。
3. 順序存儲優勢：索引運算替代指標追蹤，緩存友好，節點緊湊排布。

總結

兄弟遍歷迭代器展示了順序存儲樹結構高效導航的核心技術：以整數偏移量編碼樹拓撲，配合標籤分發實現多態導航。此設計模式可擴展至前序/後序/層序等各類遍歷器。