C++ STL 深度解析：map/multimap 查找函數效能與原理

為何選擇 map？

• 鍵值非數值型或稀疏分佈時，map (紅黑樹) 提供 O(log n) 查找/插入/刪除。
• 鍵值自動有序，支援範圍查詢與有序遍歷。
• 需一鍵多值時用 multimap。

核心查找函數對比

原始碼層面解析 (MSVC STL 片段)

// count 實際透過 equal_range 實現
size_type count(const key_type& _Keyval) const {
    _Paircc _Ans = equal_range(_Keyval);
    size_type _Num = 0;
    _Distance(_Ans.first, _Ans.second, _Num);
    return _Num;
}

// find 實際透過 lower_bound 實現
iterator find(const key_type& _Keyval) {
    iterator _Where = lower_bound(_Keyval);
    return (_Where == end() || _DEBUG_LT_PRED(comp, _Keyval, _Key(_Where._Mynode())))
        ? end() : _Where;
}

結論：對 map (唯一鍵)，find 與 count 效能相同；若需使用 value，find 直接回傳 iterator 更優；multimap 無 operator[]，必須用 equal_range 遍歷區間。

完整實戰範例

#include <map>
#include <string>
#include <iostream>
using namespace std;

void DemoMapFind() {
    map m = {{1, "A"}, {2, "B"}, {5, "C"}};
    multimap mm = {{1, "A"}, {1, "A2"}, {2, "B"}};

    // 1. map::find - 最常用
    auto it = m.find(2);
    if (it != m.end()) cout << "map find: " << it->second << '\n';

    // 2. map::count - 僅判斷存在
    if (m.count(1)) cout << "key 1 exists\n";

    // 3. equal_range - 取得完整區間
    auto range = m.equal_range(1); // map 只有 0 或 1 個
    for (auto p = range.first; p != range.second; ++p)
        cout << "map equal_range: " << p->second << '\n';

    // 4. multimap 遍歷同鍵所有值
    auto mrange = mm.equal_range(1);
    for (auto p = mrange.first; p != mrange.second; ++p)
        cout << "mm equal_range: " << p->second << '\n'; // 輸出 A, A2

    // 5. lower/upper_bound - 區間查詢
    auto lb = m.lower_bound(3); // 第一個 ≥ 3 的鍵 (5)
    auto ub = m.upper_bound(3); // 第一個 > 3 的鍵 (5)
    if (lb != m.end()) cout << "lower_bound key: " << lb->first << " val: " << lb->second << '\n';

    // 6. multimap 同理
    auto mlb = mm.lower_bound(1); // 第一個 1
    auto mub = mm.upper_bound(1); // 第一個 > 1 (即 2)
    for (auto p = mlb; p != mub; ++p) cout << "mm range [1]: " << p->second << '\n';
}

int main() {
    DemoMapFind();
    return 0;
}

效能建議

1. 優先用 find：需存取 value 時，避免二次查找。
2. 避免 count + operator[]：兩次 log n，且 operator[] 會插入預設值。
3. 大量插入：C++17 可用 try_emplace / insert_or_assign 避免重複查找。
4. 自定義比較：構造函數傳入 comparator，如 map<K,V,greater<K>> 降序。

總結

理解 lower_bound 為核心、find/count/equal_range 為上層封裝的關係，能根據場景選擇最高效的查找方式。multimap 處理一對多關係時，equal_range 是唯一正確的遍歷手段。