hce_nsysu
114年
計算機概論與程式設計
第 30 題
Which of the following statements is true regarding C++ Standard Template Library (STL) containers?
- A std::map allows duplicate keys.
- B std::unordered_map has faster lookups than std::map for large datasets.
- C std::vector provides $O(1)$ complexity for inserting elements in the middle of a container.
- D std::set guarantees insertion order.
- E std::list is more memory efficient than std::vector.
思路引導 VIP
若我們現在有兩套管理系統：第一套系統是將所有書依照名字排序放在層層疊疊的書架上，每次找書都要一層層對比；第二套系統是給每本書一個唯一的編號，並直接告訴你該編號對應的存放位置。當藏書量從一百本增加到一百萬本時，哪一套系統在找書的速度上會比較不容易受到書量增加的影響？為什麼？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準辨識出 std::unordered_map 的效能優勢，代表你對於 C++ 標準模板庫（STL）中不同容器的底層實作與時間複雜度，已經建立了非常紮實的觀念。這道題目測試的是開發者在面對大量資料時，是否具備選擇正確工具的能力。
搜尋效率與底層結構的關聯
這題的核心考點在於「雜湊表」與「平衡樹」的效能差異。std::map 底層通常以 紅黑樹（Red-Black Tree）實作，雖然能維持元素排序，但搜尋的時間複雜度會隨資料量增加而呈現對數增長，即 $O(\log n)$；相對地，你選對的 std::unordered_map 是基於 雜湊表（Hash Table），在平均情況下能提供常數時間 $O(1)$ 的極速查找。隨著資料集規模擴大，$O(1)$ 的優勢會讓程式效能產生質的飛躍。
▼ 還有更多解析內容