容器 (資料類型)

在電腦科學中，容器是指一種類、數據結構、^[1][2]或者抽象資料類型，其實例為其他類的對象。換言之，它們以一種遵循特定訪問規則的方法來儲存對象。容器的大小取決於其包含的對象（或元素）的數目。潛在的不同容器類型的實現可能在空間和時間複雜度上有所差別，這使得在給定應用場景中選擇合適的某種實現具有靈活性。

概覽

容器可以三種方式看待：

• 訪問：即訪問容器中對象的方式。
  • 在陣列中，訪問憑藉陣列索引完成。
  • 在棧中，訪問遵循先入後出（或後入先出）的順序^[3]。
  • 在佇列中，訪問遵循先入先出（或後入後出）的順序^[4][5]。
  • 並非所有設計中，這些不同的數據結構都是嚴格意義上的容器。特別地，按ISO C++的定義，C++標準庫中的容器是符合容器要求（container requirement）的類型；C++標準庫中作為陣列的std::array的特化是這樣的容器，但作為棧std::stack和作為佇列的std::queue並不是容器，而是基於其它容器的容器配接器（container adaptor）。後者和容器有很多實際差異，例如自身不提供迭代器。
• 儲存：即儲存容器中對象的方式。
• 遍歷：即遍歷容器中對象的方式。

典型的容器實現如下的方法：

• 建立一個新的空容器（即建構函式）。
• 向容器中插入對象。
• 從容器中刪除對象。
• 刪除容器中的所有對象（即清空）。
• 訪問容器中的對象。
• 取得容器中對象的數目（即尺寸）。

並非所有設計遵循以上要求，例如C++標準庫的std::array不提供清空，而std::forward_list不提供對象計數。

容器有時結合迭代器實現。

分類

按儲存類型

• 基於值的容器：儲存對象的副本。
• 基於參照 （英語：reference）的容器：儲存指標或對象的參照。

單值或關聯容器

• 單值容器：每個對象在容器中被獨立儲存，並且其被直接或憑藉迭代器訪問。
• 關聯容器：關聯陣列、對映或者字典是由鍵值對組成的容器，因此每一個鍵在給定容器中最多出現一次。如果一個值（對象）被儲存在給定容器中，那麼鍵可以用於尋找它。

圖形容器

部件工具箱使用特殊控制項（也稱作容器）去將其他控制項分組（窗口、面板等）。除它們的圖形特性之外，它們有和容器類一致的表現：它們存有它們子控制項的列表，並且允許對子控制項進行增加、刪除或取得等操作。

不同實現

• .NET: System.Collections (MSDN)（頁面存檔備份，存於互聯網檔案館）
• ActionScript3: AS3Commons Collections Framework
• C++: C++標準庫 (SC++L) or the obsolete 標準模板庫 (STL)
  • 容器在標準模板庫中被分為關聯容器和標準的序列容器。除了這兩種類型之外，也存在容器配接器。由容器實現的數據結構包含陣列、列表、對映、佇列、集合、堆疊、表、樹以及向量。
• Java: Java集合框架(JCF)
• Objective-C: Foundation Kit的部分。
• PL/SQL: 集合^[6]
• Python: 內建容器 list、dict、tuple和set，可使用collections（頁面存檔備份，存於互聯網檔案館）模組進一步拓展。
• Scala: 在scala.collection.mutable and scala.collection.immutable包中的可變及不可變容器。

參見

• 數據結構列表
• 標準模板庫#容器
• 集合
• 堆疊
• Java ConcurrentMap

參考資料

1. Paul E. Black (ed.), entry for data structure in Dictionary of Algorithms and Data Structures. US National Institute of Standards and Technology.15 December 2004. Accessed on Oct 04, 2011.
2. Entry data structure in the Encyclopædia Britannica (2009) Online entry （頁面存檔備份，存於互聯網檔案館） Accessed on Oct 04, 2011.
3. LIFO(investopedia.com). [2016-08-19]. （原始內容存檔於2016-08-24）.
4. FIFO(investopedia.com). [2016-08-19]. （原始內容存檔於2016-08-09）.
5. FIFO(businessdictionary.com). [2016-08-19]. （原始內容存檔於2016-08-27）.
6. PL/SQL Collections and Records. [2013-04-20]. （原始內容存檔於2013-05-09）.

外部連結

• Container Data Structure Declaration and Initialization（頁面存檔備份，存於互聯網檔案館）
• Container data structures（頁面存檔備份，存於互聯網檔案館）
• Python SortedContainers module（頁面存檔備份，存於互聯網檔案館） A fast implementation of sorted list, sorted dict, and sorted set data types in Python.