容器 (資料類型)

类,数据结构在计算机科学

電腦科學中,容器是指一種類、資料結構[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). 

外部連結

編輯