快捷導(dǎo)航

淺談C++ 容器查找效率

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

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

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

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

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

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

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

1. std::vector —— “排排坐”的長(zhǎng)桌子

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

查找

沒排序：只能一個(gè)個(gè)比——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ù)擺放的「長(zhǎng)桌子」
    
    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í)候用

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

2. std::list —— “珍珠項(xiàng)鏈”

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

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

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

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

3. std::set —— 自動(dòng)排序的“有序字典”

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

#include <set>
#include <iostream>

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

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

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

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

底層：哈希表，把元素按哈希值分到不同“桶”里。
平均查找：O(1)，最壞沖突多時(shí) 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";
    }
}

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

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

容器	底層	查找	是否有序
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';
}

什么時(shí)候用

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

6. std::deque —— 可以從兩頭裝菜的“長(zhǎng)盤子”

特點(diǎn)：首尾插入 / 刪除都是 O(1)；中間操作比 vector 慢點(diǎn)。
查找：線性 O(n)；隨機(jī)訪問語(yǔ)法與 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';
}

什么時(shí)候用既想要隨機(jī)訪問，又要在首尾頻繁加減元素，比如滑動(dòng)窗口算法。

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 → 指針