序列


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

描述

序列是一个大小可变的容器，其元素按严格的线性顺序排列。它支持元素的插入和删除。

细化自

前向容器，默认可构造

关联类型

无，除了前向容器的那些。

符号

`X`	序列模型的类型
`a`, `b`	类型为的对象`X`
`T`	的取值类型`X`
`t`	类型为的对象`T`
`p`, `q`	类型为的对象`X::iterator`
`n`	可转换为类型为的对象`X::size_type`

定义

如果a是序列，则p是a中的有效迭代器，如果它是一个有效的（非奇异的）迭代器，并且可以从a.begin().

如果a是序列，则[p, q)是a中的有效范围，如果p和q是a中的有效迭代器a并且如果q可以从p.

有效表达式

除了前向容器中定义的表达式外，以下表达式必须有效。

名称	表达式	类型要求	返回类型
填充构造函数	`X(n, t)`		`X`
填充构造函数	`X a(n, t);`
默认填充构造函数	`X(n)`	`T`是默认可构造。	`X`
默认填充构造函数	`X a(n);`	`T`是默认可构造。
范围构造函数	`X(i, j)`	`i`和`j`是输入迭代器，其值类型可转换为`T` [1]	`X`
范围构造函数	`X a(i, j);`	`i`和`j`是输入迭代器，其值类型可转换为`T` [1]
首元素	`a.front()`		`引用`如果`a`是可变的，`常量引用`否则。
插入	`a.insert(p, t)`		`X::iterator`
填充插入	`a.insert(p, n, t)`	`a`是可变的	`void`
范围插入	`a.insert(p, i, j)`	`i`和`j`是输入迭代器，其值类型可转换为`T` [1]. `a`是可变的	`void`
擦除	`a.erase(p)`	`a`是可变的	`迭代器`
范围擦除	`a.erase(p,q)`	`a`是可变的	`迭代器`
清空	`a.clear()`	`a`是可变的	`void`
调整大小	`a.resize(n, t)`	`a`是可变的	`void`
调整大小	`a.resize(n)`	`a`是可变的	`void`

表达式语义

表达式的语义仅在其未在前向容器中定义或有所不同时定义。

名称	表达式	前提条件	语义	后置条件
填充构造函数	`X(n, t)`	`n >= 0`	创建一个包含`n`的`t`	`size() == n`个副本的序列。每个元素都是`t`.
填充构造函数	`X a(n, t);`	`n >= 0`	创建一个包含`n`的`t`	`a.size() == n`的副本。序列的每个元素`a`都是`t`.
默认填充构造函数	`X(n)`	`n >= 0`	创建一个包含`n`个初始化为默认值的元素的序列。	`size() == n`个副本的序列。每个元素都是`T()`.
默认填充构造函数	`X a(n, t);`	`n >= 0`	创建一个包含`n`个初始化为默认值的元素的序列。	`a.size() == n`的副本。序列的每个元素`a`都是`T()`.
默认构造函数	`X a;`或`X()`		等价于`X(0)`.	`size() == 0`.
范围构造函数	`X(i, j)`	`[i,j)`是一个有效范围。	创建一个序列，它是范围`[i,j)`	`size()`等于从`i`到`j`的距离。每个元素都是范围中对应元素的副本`[i,j)`.
范围构造函数	`X a(i, j);`	`[i,j)`是一个有效范围。	创建一个序列，它是范围`[i,j)`	`a.size()`等于从`i`到`j`。中的每个元素`a`都是范围中对应元素的副本`[i,j)`.
首元素	`a.front()`	`!a.empty()`	等价于`*(a.first())`
插入	`a.insert(p, t)`	`p`是a中的有效迭代器`a`. `a.size() < a.max_size()`	的副本`t`被插入到`p`. [2] [3]	`a.size()`之前。被递增1。`*(a.insert(p,t))`都是`t`。序列中已存在的元素的相对顺序保持不变。
填充插入	`a.insert(p, n, t)`	`p`是a中的有效迭代器`a`. `n >= 0 && a.size() + n <= a.max_size()`.	`n`的`t`被插入到`p`. [2] [3] [4]	`a.size()`之前。被递增n。序列中已存在的元素的相对顺序保持不变。
范围插入	`a.insert(p, i, j)`	`[i,j)`是一个有效范围。`a.size()`加上从`i`到`j`的距离不超过`a.max_size()`.	将范围`[i,j)`的副本插入到`p`. [1] [2] [3]	`a.size()`之前。被递增从`i`到`j`。序列中已存在的元素的相对顺序保持不变。
擦除	`a.erase(p)`	`p`是a中可解引用的迭代器`a`.	销毁`p`指向的元素并将其从`a`. [3]	`a.size()`中移除。被递减1。序列中其他元素的相对顺序保持不变。返回值是指向被擦除元素后一个元素的迭代器。
范围擦除	`a.erase(p,q)`	`[p,q)`是a中的有效范围`a`.	销毁范围`[p,q)`中的元素并将其从`a`. [3]	`a.size()`中移除。被递减从`i`到`j`的距离。序列中其他元素的相对顺序保持不变。返回值是指向被擦除元素后一个元素的迭代器。
清空	`a.clear()`		等价于`a.erase(a.begin(), a.end())`
调整大小	`a.resize(n, t)`	`n <= a.max_size()`	修改容器，使其正好包含`n`个元素，根据需要在末尾插入元素或从末尾擦除元素。如果插入了任何元素，则它们是`t`的副本。如果`n > a.size()`，则此表达式等价于`a.insert(a.end(), n - size(), t)`的副本。如果`n < a.size()`，则它等价于`a.erase(a.begin() + n, a.end())`.	`a.size() == n`
调整大小	`a.resize(n)`	`n <= a.max_size()`	等价于`a.resize(n, T())`.	`a.size() == n`

复杂度保证

填充构造函数、默认填充构造函数和范围构造函数是线性的。

首元素是摊销常数时间。

填充插入、范围插入和范围擦除是线性的。

单个元素插入和擦除的复杂度取决于序列。

不变量

模型

注释

[1] 目前（1998年初），并非所有编译器都支持“成员模板”。如果您的编译器支持成员模板，则i和j可以是符合输入迭代器要求的任何类型。但是，如果您的编译器尚不支持成员模板，则i和j必须是类型为const T*或类型为X::const_iterator.

[2] 请注意，p等于a.begin()表示在a的开头（即在a中已存在的任何元素之前）插入某些内容，并且p等于a.end()表示将某些内容追加到a.

[3] 警告：无法保证在a上的有效迭代器在插入或擦除后仍然有效。在某些情况下，迭代器确实保持有效，而在其他情况下则无效。每个序列类的细节都不同。

[4] a.insert(p, n, t)保证不会比调用a.insert(p, t) n次慢。在某些情况下，它会快得多。

[5] Vector 通常优于 deque 和 list。 Deque 在序列开头和末尾频繁插入的情况下很有用，而 list 和 slist 在序列中间频繁插入的情况下很有用。在几乎所有其他情况下，vector 效率更高。

另请参阅

容器，前向容器，关联容器，前插入序列，后插入序列，vector, deque, list, slist