淺談C++ 容器查找效率

更新時間：2025年06月27日 10:02:44 作者：pumpkin84514

本文主要介紹了淺談C++ STL容器的查找效率差異,對比vector、list、set/map、unordered_set和deque等,幫助選擇合適容器以優(yōu)化性能,感興趣的可以了解一下

0. 先把“查找復(fù)雜度”聊明白
1. std::vector —— “排排坐”的長桌子
2. std::list —— “珍珠項鏈”
3. std::set —— 自動排序的“有序字典”
4. std::unordered_set —— “散列表”小黑屋
5. std::map vs std::unordered_map —— 鍵值對“雙子星”
6. std::deque —— 可以從兩頭裝菜的“長盤子”
7. “多索引”技巧 —— 一份數(shù)據(jù)，多把鑰匙
8. 記憶卡片（純中文朗朗上口）
最后一句話

只要選對容器，多寫幾行代碼就能讓程序“飛”起來。下面用生活化的比喻 + 足夠多的帶注釋示例，幫你弄懂常用 STL 容器的查找特性。
讀完你應(yīng)該能快速判斷：“我的場景該用哪一個？”

0. 先把“查找復(fù)雜度”聊明白

記號	含義	舉個??
O(1)	常數(shù)時間	像從冰箱門口拿飲料——一下就到手
O(log n)	對數(shù)時間	折半查電話簿——越找越快
O(n)	線性時間	排隊買奶茶——要挨個等

只要記?。簲?shù)字越小越快，O(1) 最爽，O(n) 最慢。

1. std::vector —— “排排坐”的長桌子

特點：元素一字排開，內(nèi)存連續(xù)，跟操場跑道一樣直。

查找

沒排序：只能一個個比——O(n)
排好序：可折半查——O(log n)

#include <vector>
#include <algorithm>   // std::sort, std::binary_search
#include <iostream>

int main() {
    std::vector<int> nums{5, 1, 4, 3, 2};   // 連續(xù)擺放的「長桌子」
    
    std::sort(nums.begin(), nums.end());    // ① 排序一次，之后查找快
                                            //    nums 變成 {1,2,3,4,5}
    bool has3 = std::binary_search(         // ② 折半查找 3
        nums.begin(), nums.end(), 3);       //    O(log n)
    
    std::cout << (has3 ? "找到了" : "沒找到") << '\n';
}

什么時候用

數(shù)據(jù)量可控、想要下標(biāo)隨機訪問。
插入刪除不多（尤其不是在中間插）。

2. std::list —— “珍珠項鏈”

特點：每顆珠子（節(jié)點）用線（指針）串起來，插拔容易。
查找：得一顆顆摸——O(n)，而且分散指針不利于 CPU 緩存。

#include <list>
#include <algorithm>
#include <iostream>

int main() {
    std::list<int> lst{1, 2, 3, 4, 5};          // 一串節(jié)點
    
    auto it = std::find(lst.begin(), lst.end(), 3); // ① 線性查找
    std::cout << (it != lst.end() ? "找到了" : "沒找到") << '\n';
}

什么時候用插入 / 刪除動作特別頻繁、但不太在意查找速度，比如任務(wù)隊列需要隨時插入或移走元素。

3. std::set —— 自動排序的“有序字典”

底層：紅黑樹，像一個能自動平衡的家譜圖。
查找 / 增刪：都 O(log n)。

#include <set>
#include <iostream>

int main() {
    std::set<int> s{4, 1, 3, 2};      // 元素自動有序：{1,2,3,4}

    bool has2 = s.contains(2);        // C++20 起可直接 contains
    std::cout << (has2 ? "有 2" : "沒 2") << '\n';
}

什么時候用既想要“去重”又想要“元素排好序”，而且單個元素查找要快。

4. std::unordered_set —— “散列表”小黑屋

底層：哈希表，把元素按哈希值分到不同“桶”里。
平均查找：O(1)，最壞沖突多時 O(n)。
元素?zé)o序：放進(jìn)去啥順序不管。

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<std::string> words; // 小黑屋摞桶
    words.insert("hello");
    words.insert("world");

    if (words.contains("hello")) {         // 平均 O(1)
        std::cout << "嘿~ 找到了 hello\n";
    }
}

什么時候用不需要順序，只想“秒查秒存”，典型如去重、統(tǒng)計次數(shù)。

5. std::map vs std::unordered_map —— 鍵值對“雙子星”

容器	底層	查找	是否有序
map	紅黑樹	O(log n)	?
unordered_map	哈希表	O(1) 平均	?

#include <map>
#include <unordered_map>
#include <iostream>

int main() {
    std::map<int, std::string> ordered;          // 有序
    ordered[2] = "B"; ordered[1] = "A";

    std::unordered_map<int, std::string> hash;   // 無序
    hash[2] = "B"; hash[1] = "A";

    std::cout << ordered[1] << ' ' << hash[1] << '\n';
}

什么時候用

需要按鍵遍歷且保持有序：map。
只關(guān)心查、增、刪速度：unordered_map。

6. std::deque —— 可以從兩頭裝菜的“長盤子”

特點：首尾插入 / 刪除都是 O(1)；中間操作比 vector 慢點。
查找：線性 O(n)；隨機訪問語法與 vector 一樣。

#include <deque>
#include <algorithm>
#include <iostream>

int main() {
    std::deque<int> q{1, 2, 3};
    q.push_front(0);        // 頭部 O(1)
    q.push_back(4);         // 尾部 O(1)

    bool has3 = std::find(q.begin(), q.end(), 3) != q.end();
    std::cout << (has3 ? "有 3" : "沒 3") << '\n';
}

什么時候用既想要隨機訪問，又要在首尾頻繁加減元素，比如滑動窗口算法。

7. “多索引”技巧 —— 一份數(shù)據(jù)，多把鑰匙

如果你既想按 ID 查，又想按名字查，可以：

#include <vector>
#include <unordered_map>

struct User { int id; std::string name; };

std::vector<User> users;                      // 主數(shù)組
std::unordered_map<int, User*> id_index;      // id → 指針
std::unordered_map<std::string, User*> name_index; // name → 指針