容器

类目：容器

描述

容器是一个可以存储对象（它的元素），并具有访问其元素的方法的一个对象。特别是，每一个容器模式类型都有一个关联的迭代器类型来遍历容器中的元素。

不能保证容器中的元素按特定的方式来存储；事实上，不同的是每次迭代器是如何通过容器的。也不能保证容器的多个迭代器是一直有效的。（特定的容器类型，像前向容器是提供这样的保证的。）

容器“拥有”它的元素：存储在一个容器中的元素的寿命不能超过容器本身。[1]

完善

Assignable

相关类型

(Value type)值类型  X::value_type  存储在容器中的对象类型。值类型必须是Assignable，但不必是DefaultConstructible.[2]
(Iterator type)迭代器类型 X::iterator  迭代器类型用来遍历容器的元素。迭代器的值类型就是容器的值类型。必须可以从iterator type转换成const iterator type。迭代器的类型必须是一个输入迭代器。[3]
(Const iterator type)常量迭代器类型 X::const_iterator 是一个可以查看但不能修改容器中元素的迭代器类型。[3][4]
(Reference type)引用类型 X::reference 是一个行为像容器值类型引用的类型。[5]
(Const reference type)常量引用类型 X::const_reference 是一个行为像容器值类型常量引用的类型。[5]
(Pointer type)指针类型 X::pointer 是一个行为像容器值类型指针的类型。[6]
(Distance type)距离类型 X::distance_type  一个有符号整数类型来表示两个容器迭代器之间的距离。此类型必须跟迭代器之间的距离类型是一样的。[2]
(Size type)大小类型 X::size_type 一个无符号整数类型来表示任何非负值的容器距离类型。[2]

标记法

X    容器模式对象
a,b  X类型对象
T    X类型的值

定义

容器的(size)大小就是它所包含的元素个数，它是一个非负数。

容器的(area)面积就是它占用的字节数。更确切地说，它是元素的面积的总和加上与容器本身相关的任何开销。如果容器的值类型T是一个简单的类型（而不是一个容器类型），那么这个容器的面积就是sizeof(T)的常数倍。也就是说，一个简单值类型的容器a的面积是O(a.size())。

一个(variable sized)可变大小的容器提供插入和/或移除元素的方法；容器大小可能会变化。一个(fixed size)固定大小的容器，它的大小在它的生命周期内是一只不变的。一些固定大小的容器类型，大小在编译时确定。

有效表达式

除了Assignable,EqualityComparable,和LessThanComparable这些已经定义的表达式，下面的表达式也必须是有效的。

名称      表达式         类型要求    返回类型
范围起始  a.begin()                  如果是可变的，返回值为iterator(迭代器)，否则为const_iterator[4][7]
范围结束  a.end()                    如果是可变的，返回值为iterator(迭代器)，否则为const_iterator[4]
大小      a.size()                   size_type
最大容量  a.max_size()               size_type
空容器    a.empty()                  可转换成bool类型
交换      a.swap(b)                  void

表达式语义

名称          表达式       前提    语义                                                         后置
拷贝构造函数  X(a)                                                                              X().size() == a.size()。X()包含了a中所有元素的副本。
拷贝构造函数  X b(a)                                                                            b().size() == a.size()。b包含了a中所有元素的副本。
赋值运算符    b = a                                                                             b().size() == a.size()。b包含了a中所有元素的副本。
析构函数      a.~X()               销毁a中所有的元素，并释放为它们分配的内存（如果有的话）。
范围起始      a.begin()            返回一个指向容器第一个元素的迭代器(iterator)。[7]            a.begin()要么是提领要么是past-the-end。仅仅当a.size == 0的时候它才是past-the-end。
范围结束      a.end()              返回一个指向容器的最后一个元素的后面的迭代器(iterator)。     a.end 是 past-the-end。
大小          a.size()             返回容器的大小，也就是元素的个数。[8]                        a.size() >= 0 && a.size <= a.max_size()
最大容量      a.max_size()         返回容器的最大容量。[8]                                      a.max_size() >= 0 && a.max_size >= a.size()
空容器        a.empty()            相当于 a.size() == 0 （但是可能更快）                        
交换          a.swap(b)            相当于swap(a,b)[9]

复杂性担保

拷贝构造函数，复制操作符，析构函数跟容器大小呈线性关系。

begin()和end()的摊销时间为常数。

size()跟容器大小呈线性关系。[10] max_size()和empty()的摊销时间为常数。如果你要测试一个容器是否为空，你应该总是写c.empty而不是c.size() == 0。这两个表达式是等价的，但前者可能要快得多。

swap()的摊销时间为常数。[9]

不变量

有效范围     任何容器a， [a.begin(), a.end())是一个有效范围。[11]
范围大小     a.size()等于从a.begin()到a.end()的距离。
完整性       一个迭代算法[a.begin(), a.end())，将会遍历a中的每个元素。[11]

模型

vector

注释

[1]元素的寿命不能超过其容器可能看起来像一个严重的限制，事实上，它并不是限制。请注意指针和迭代器都是对象；就像任何其他对象一样，他们可以被存储在一个容器内。在这种情况下，容器拥有指针本身，而不是它们指向的对象。

[2]这种表达式必须是一个typedef，这是一个类型的代名词。

[3]这可能是一个typedef或者其他类型，或者一个定义嵌套类作为一个内部类的X的特定的类型。

[4]容器的iterator类型和const iterator类型可能是一样的：不能保证每个容器必须有一个相关的可变迭代器类型。例如，set和hash_set定义iterator和const iterator为同一类型。

[5]引用类型需要与普通C++引用类型有相同的语义，但它实际上并不是普通的C++引用。例如，在某些实现中，可能会提供额外的引用类型来支持非标准的内存模型。但是请注意，“智能引用”（用户定义的引用类型提供额外的功能）不是一个可行的选择。用户定义的类型不可能与C++引用类型具有相同语义，因为C++语言不支持重新定义的成员访问运算符(operator.)。

[6]跟[5]中的引用类型一样，指针类型需要与C++指针有相同的语义，但实际并不是C++指针。“智能指针”不同于“智能引用”是有可能的。因为可以为用户定义类型来定义的引用操作符和指针成员访问运算符可以访问运算符*和->。

[7]迭代器类型(iterator type)必须是一个输入迭代器(input iterator)，它只提供了一个非常薄弱的担保；特别是，输入迭代算法必须都是“单通道”。容器只有一个简单的迭代器(iterator)可以随时激活。Forward Container(前向容器)没有这个限制。

[8]一个固定大小的容器，size() == max_size()。

[9]对于任何Assignable类型，swap可以定义分配条款。这需要三个任务，每一个容器类型，容器的大小呈线性关系。然而，在某种意义上，a.swap(b)是多余的。它的存在仅仅为了提高效率：许多容器，如vector和list，它实现swap的时间复杂度是不变的，而不是线性的。一些容器类型X，那么它们的模板化swap(X&,X&)可以简单地写在X::swap(X&)。也就是说X::swap(X&)只能定义在执行时间是常量的情况下。不是所有的容器类X都需要这样的一个成员函数，但是如果这样的函数存在，那么必须保证摊销时间为常量。

[10]对于许多容器，如vector和deque，size是O(1).这满足了O(N)的要求。

[11]虽然[a.begin(), a.end())必须是一个有效的范围，而且每个元素必须都包含在容器内，但是在这个范围内出现的顺序是不确定的。如果你两次遍历一个容器，它不能保证这两次的遍历顺序是相同的。Forward Container前向容器没有这个限制。

参见

迭代器概述，输入迭代器，序列