容器 (数据类型)

在计算机科学中，容器是指一种类、数据结构、^[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.