C++ STL map::find 與迭代器遍歷順序說明

代碼片段

map<int, int> m1;
m1.insert({1,20}); m1.insert({4,40}); m1.insert({3,60});
m1.insert({2,50}); m1.insert({6,40}); m1.insert({7,30});

auto p = m1.find(2); // 找到 key=2
auto prev = p; --prev; // 上一個元素
auto next = p; ++next; // 下一個元素
cout << prev->first << " " << prev->second << endl; // 輸出 1 20
cout << next->first << " " << next->second << endl; // 輸出 3 60

為什麼輸出 1 和 3？

`std::map` 內部按 Key 升序排列 (紅黑樹)，與插入順序無關。插入後實際順序為：

Key: 1 2 3 4 6 7
Val: 20 50 60 40 40 30

因此 `find(2)` 定位到 key=2，`--prev` 得到 key=1，`++next` 得到 key=3。

關鍵特性

• 有序性：`begin()` 到 `end()` 遍歷即為 Key 升序。
• 迭代器雙向：支援 `++`、`--`。
• 查找複雜度：O(log N)。

常見誤區

以為 `map` 保持插入順序 → 錯。需保持插入順序請用 `std::vector>` 或 C++17 `std::map` 無此特性，可考慮 `boost::multi_index` 或自定義結構。