如何選出最適合的C++ STL容器?

2020-07-16 10:05:22
到此為止,本教學已經講解了 C++ STL 標準庫中所有容器的特性、功能以及用法,但考慮到一些讀者可能在糾結“什麼場景中選用哪個容器”這個問題,本節將帶領大家系統回顧一下所學的這些容器,並給出一個解決此問題的思路。

值得一提的是,雖然 STL 標準庫還有疊代器、演算法、函數物件等,但容器仍是大多數 C++ 程式設計師關注的焦點。首先,和普通陣列相比,容器支援動態擴容和收縮,還可以自行管理儲存的元素(例如排序),同時還提供有諸多成員方法,大大提高了開發效率等等。其次,每個容器的底層實現,都採用的是精心挑選的資料結構,這意味著在使用這些容器時,不用擔心它們的執行效率。

總的來說,C++ STL 標準庫(以 C++ 11 為準)提供了以下幾種容器供我們選擇:
  1. 序列式容器:array、vector、deque、list 和 forward_list;
  2. 關聯式容器:map、multimap、set 和 multiset;
  3. 無序關聯式容器:unordered_map、unordered_multimap、unordered_set 和 unordered_multiset;
  4. 容器介面卡:stack、queue 和 priority_queue。

注意,容器介面卡本質上也屬於容器,關於以上各個容器介面卡,後續章節會做詳細講解。

上面是依據容器型別進行分類的。實際上,每個容器所具有的特性都和其底層選用的儲存結構息息相關。根據容器底層採用的是連續的儲存空間,還是分散的儲存空間(以連結串列或者樹作為儲存結構),還可以將上面容器分為如下兩類:
  1. 採用連續的儲存空間:array、vector、deque;
  2. 採用分散的儲存空間:list、forward_list 以及所有的關聯式容器和雜湊容器。

注意,這裡將 deque 容器歸為使用連續儲存空間的這一類,是存在爭議的。因為 deque 容器底層採用一段一段的連續空間儲存元素,但是各段儲存空間之間並不一定是緊挨著的。關於 deque 容器的底層儲存結構(可閱讀《C++ STL deque底層實現原理》一節詳細了解),讀者理解即可,這裡不必深究。

既然 C++ STL 標準庫提供了這麼多種容器,在實際場景中我們應該如何選擇呢?

要想選擇出適用於該特定場景的最佳容器,需要綜合考慮多種實際因素,例如:
  • 是否需要在容器的指定位置插入新元素?如果需要,則只能選擇序列式容器,而關聯式容器和雜湊容器是不行的;
  • 是否對容器中各元素的儲存位置有要求?如果沒有,則可以考慮使用雜湊容器,反之就要避免使用雜湊容器;
  • 是否需要使用指定型別的疊代器?舉個例子,如果必須是隨機存取疊代器,則只能選擇 array、vector、deque;如果必須是雙向疊代器,則可以考慮 list 序列式容器以及所有的關聯式容器;如果必須是前向疊代器,則可以考慮 forward_list 序列式容器以及所有的雜湊容器;
  • 當發生新元素的插入或刪除操作時,是否要避免移動容器中的其它元素?如果是,則要避開 array、vector、deque,選擇其它容器;
  • 容器中查詢元素的效率是否為關鍵的考慮因素?如果是,則應優先考慮雜湊容器。

當然,以上問題並沒有涵蓋所有的情形,只是起到一個拋磚引玉的作用。在實際場景中,我們需要考慮更多的因素(例如對比各個容器解決當前問題所需的時間複雜度),經過層層篩選,最終找到適合該場景的那個容器。