跳至內容

容器 (數據類型)

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

計算機科學中,容器是指一種類、數據結構[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)的容器:存儲指針或對象的引用。

單值或關聯容器

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

圖形容器

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

不同實現

參見

參考資料

  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). 

外部連結