容器 (抽象数据类型)

维基百科,自由的百科全书
(重定向自容器 (数据结构)
跳转至: 导航搜索

计算机科学中,容器是指实例为其他对象的集合的类、数据结构[1][2]或者抽象数据类型。换言之,它们以一种遵循特定访问规则的系统的方法来存储对象。容器的大小取决于其包含的对象(或元素)的数目。潜在的不同容器类型的实现可能在空间和时间复杂度上有所差别,这使得在给定应用场景中选择合适的某种实现具有灵活性。

概览[编辑]

容器可以三种方式看待:

  • 访问:即访问容器中对象的方式。在数组中,访问凭借数组索引完成。在堆栈中,访问遵循先入后出(或后入先出)的顺序[3]。在队列中,访问遵循先入先出(或后入后出)的顺序[4][5]
  • 存储:即存储容器中对象的方式。
  • 遍历:即遍历容器中对象的方式。

容器类应当实现如下的方法

  • 创建一个新的空容器(即构造函数);
  • 向容器中插入对象;
  • 从容器中删除对象;
  • 删除容器中的所有对象(即清空);
  • 访问容器中的对象;
  • 获取容器中对象的数目(即尺寸)。


容器有时结合迭代器实现。

分类:按存储类型[编辑]

  • 基于值的容器:存储对象的副本。
  • 基于引用英语: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)
  4. ^ FIFO(investopedia.com)
  5. ^ FIFO(businessdictionary.com)
  6. ^ PL/SQL Collections and Records. [2013-04-20]. 

外部链接[编辑]


面向对象编程