容器


类别：容器	组件类型：概念

描述

容器是一个存储其他对象（其元素）的对象，并具有访问其元素的方法。特别是，每个作为容器模型的类型都有一个关联的迭代器类型，可用于遍历容器的元素。

不能保证容器的元素以任何确定的顺序存储；实际上，在每次遍历容器时，顺序可能不同。也不能保证在任何时间都可能有多个容器迭代器处于活动状态。（某些特定类型的容器，例如前向容器，确实提供了此类保证。）

容器“拥有”其元素：存储在容器中的元素的生命周期不能超过容器本身的生命周期。[1]

细化自

可赋值

关联类型

值类型	`X::value_type`	存储在容器中的对象类型。值类型必须是可赋值的，但不必是可默认构造的。[2]
迭代器类型	`X::iterator`	用于遍历容器元素的迭代器类型。迭代器的值类型应为容器的值类型。必须存在从迭代器类型到常量迭代器类型的转换。迭代器类型必须是输入迭代器。[3]
常量迭代器类型	`X::const_iterator`	可用于检查但不能修改容器元素的迭代器类型。[3] [4]
引用类型	`X::reference`	充当对容器值类型的引用的类型。[5]
常量引用类型	`X::const_reference`	充当对容器值类型的常量引用的类型。[5]
指针类型	`X::pointer`	充当对容器值类型的指针的类型。[6]
距离类型	`X::difference_type`	用于表示容器的两个迭代器之间距离的有符号整型类型。此类型必须与迭代器的距离类型相同。[2]
大小类型	`X::size_type`	可以表示容器距离类型任何非负值的无符号整型类型。[2]

表示法

`X`	作为容器模型的类型
`a`, `b`	类型为的对象`X`
`T`	的 value_type`X`

定义

容器的大小是它包含的元素数量。大小为非负数。

容器的面积是它占用的总字节数。更具体地说，它是元素面积的总和加上与容器本身相关的任何开销。如果容器的值类型T是简单类型（与容器类型相反），则容器的面积以上限为常数乘以容器的大小乘以sizeof(T)。也就是说，如果a是具有简单值类型的容器，则a的面积为O(a.size()).

可变大小容器是指提供插入和/或删除元素方法的容器；其大小在容器的生命周期内可能发生变化。固定大小容器是指大小在容器的生命周期内保持不变的容器。在某些固定大小的容器类型中，大小在编译时确定。

有效表达式

除了可赋值、相等可比较和小于可比较中定义的表达式外，以下表达式必须有效。

名称	表达式	返回类型
范围的开始	`a.begin()`	`迭代器`如果`a`是可变的，`const_iterator`否则 [4] [7]
范围的结束	`a.end()`	`迭代器`如果`a`是可变的，`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()`	返回一个指向容器中第一个元素的迭代器。[7]	`a.begin()`要么可解引用，要么是超出末尾的。当且仅当`a.size() == 0`.
范围的结束	`a.end()`	时，它超出末尾。	`a.end()`返回一个指向容器中最后一个元素之后的迭代器。
大小	`a.size()`	超出末尾。	`返回容器的大小，即其元素数量。[8]`
最大大小	`a.max_size()`	a.size() >= 0 && a.size() <= max_size()	`返回此容器可能具有的最大大小。[8]`
空容器	`a.empty()`	a.max_size() >= 0 && a.max_size() >= a.size()`a.size() == 0`等效于
交换	`a.swap(b)`	a.max_size() >= 0 && a.max_size() >= a.size()`。(但可能更快)。` [9]

swap(a,b)

复杂度保证

复制构造函数、赋值运算符和析构函数在容器的大小上是线性的。begin()和end()

是均摊常数时间。size()在容器的大小上是线性的。[10]begin()max_size()empty()是均摊常数时间。如果您正在测试容器是否为空，则应始终编写c.empty()而不是c.size() == 0

。这两个表达式是等效的，但前者可能快得多。swap()

是均摊常数时间。[9]

不变量	有效范围`a`, `对于任何容器`[a.begin(), a.end())
是有效范围。[11]	`a.size()`范围大小`a.begin()`等于从`a.end()`.
到	的距离。`对于任何容器`完整性`a`. [11]

遍历范围的算法

将遍历

中的每个元素。

模型

vector注释[1] 元素的生命周期不能超过其容器的生命周期这一事实似乎是一个严重的限制。实际上，情况并非如此。请注意，指针和迭代器是对象；像任何其他对象一样，它们可以存储在容器中。在这种情况下，容器“拥有”指针本身，但不拥有它们指向的对象。

[2] 此表达式必须是注释typedefX.

，即已具有其他名称的类型的同义词。[3] 这可以是begin()某些其他类型的同义词，或者是在类中定义的嵌套类。迭代器begin()const_iterator[4] 容器的迭代器类型和常量迭代器类型可以相同：不能保证每个容器都必须具有关联的可变迭代器类型。例如，

sethash_set).

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

operator。）。

[6] 与引用[5] 的情况一样，指针类型必须具有与 C++ 指针相同的语义，但不必实际上是 C++ 指针。“智能指针”与“智能引用”不同，是可能的。这是因为用户定义类型可以定义解引用运算符和指针成员访问运算符，operator*.

operator->a.swap(b)[7] 迭代器类型只需要是输入迭代器，它提供了一组非常弱的保证；特别是，输入迭代器上的所有算法都必须是“单遍”的。因此，在任何时间只能有一个容器迭代器处于活动状态。此限制在前向容器中已移除。[8] 在固定大小容器的情况下，size() == max_size()X[9] 对于任何可赋值类型，swap 可以根据赋值来定义。这需要三个赋值，每个赋值对于容器类型来说，在容器的大小上是线性的。从某种意义上说，是多余的。它仅出于效率的目的而存在：对于许多容器（例如vector 和list），可以实现swap使其运行时复杂度为常数而不是线性。如果对于某些容器类型可以实现这一点，则模板特化使其运行时复杂度为常数而不是线性。如果对于某些容器类型swap(X&, X&)X可以简单地用

X::swap(X&)将遍历begin()来编写。这意味着, 仅应在存在此类常数时间实现时才定义。并非每个容器类都需要具有此类成员函数，但如果成员函数存在，则保证其为均摊常数时间。

[10] 对于许多容器（例如对于任何容器deque

size

为O(1)。这满足了它必须为O(N)的要求。

[11] 虽然必须是有效范围，并且必须包含容器中的每个元素，但元素在该范围中出现的顺序未指定。如果您两次遍历容器，则不能保证顺序在这两次遍历中都相同。此限制在前向容器中已移除。