Namespaces
Variants

C++ named requirements: SequenceContainer

From cppreference.net
C++
C++ named requirements

A SequenceContainer 是一种 Container ，它以线性排列方式存储相同类型的对象。

目录

要求

给定以下类型和值：

类型 定义
C 序列容器类
T C 的元素类型
A C 的分配器类型：
R (C++23 起) 满足 container-compatible-range  <T> 概念的类型
Args (C++11 起) 模板参数包
Iter C::iterator
Ref C::reference
CRef C::const_reference
值 定义
v 类型为 C 的值
cv 类型为 const C 的值
i 、 j 满足 老式输入迭代器 要求，且 [ i , j ) 构成 有效范围 ，且迭代器所指元素可隐式转换为 C::value_type
rg (C++23 起) 类型为 R 的值
il (C++11 起) 类型为 std:: initializer_list < C :: value_type > 的值
n 类型为 C::size_type 的值
p 指向 v 的有效 常量迭代器
q 指向 v 的 可解引用 常量迭代器
q1 、 q2 指向 v 的常量迭代器，且 [ q1 , q2 ) 构成有效范围
t 类型为 (C++11 前) 类型为 C::value_type 的 左值 或常量右值 (C++11 起)
rv (C++11 起) 类型为 C::value_type 的非常量右值
args (C++11 起) 模式为 Arg&& 的函数参数包

C 满足 SequenceContainer 的要求，当且仅当满足以下所有条件：

  • C 满足 Container 的要求。
  • 下列语句和表达式是良构的，并具有指定语义：
基础操作
(标准库中所有序列容器必需 标准库 除 std::array (C++11 起) )
声明语句 语义 [1]
C c ( n, t ) ; 效果 构造包含 n 个 t 副本的序列容器。
前置条件

T 是 CopyInsertable 到 C 中的。

(C++11 起)
后置条件 std:: distance ( c. begin ( ) , c. end ( ) ) 为 n 。
C c ( i, j ) ; 效果 构造与范围 [ i , j ) 逐元素相等的序列容器。
  • 范围 [ i , j ) 中的每个迭代器均被精确解引用一次。
前置条件

T 可自 * i 通过 EmplaceConstructible 要求置入构造到 C 中

(C++11 起)
后置条件 std:: distance ( c. begin ( ) , c. end ( ) ) 等于 std:: distance ( i, j ) 。
表达式 类型 语义
C ( std:: from_range , rg )
(C++23 起) 		C 效果 构造与范围 rg 元素完全相同的序列容器。
  • 范围 rg 中的每个迭代器均被精确解引用一次。
前置条件 T 能够通过 EmplaceConstructible 从 * ranges:: begin ( rg ) 构造到 X 中。
后置条件 std:: distance ( begin ( ) , end ( ) ) 等于 ranges:: distance ( rg ) 。
C ( il )
(C++11 起) 		C 等价于 C ( il. begin ( ) , il. end ( ) ) 。
v = il
(C++11 起) 		C& 效果 将 il 所表示的区间赋值给 v 。 [2]
返回值 * this
前置条件 T 需满足可复制插入到 C 中，且满足 CopyInsertable 与 CopyAssignable 要求。
后置条件 v 的现有元素要么被销毁，要么被赋值。
v. emplace ( p, args )
(C++11 起) 		Iter 效果 在 p 前插入一个 T 类型的对象，该对象通过 std:: forward < Args > ( args ) ... 构造。
返回值 指向从 args 构造并插入到 v 中新元素的迭代器。
前置条件 T 能够通过 EmplaceConstructible 从 args 置入构造到 C 中。
v. insert ( p, t ) Iter 效果 在 p 之前插入 t 的副本。
返回值 指向插入到 v 中的 t 副本的迭代器。
前置条件

T 是 CopyInsertable 到 C 中的。

(C++11 起)
v. insert ( p, rv )
(C++11 起) 		Iter 效果 在 p 之前插入 rv 的副本，可能使用移动语义。
返回值 指向插入到 v 中的 rv 副本的迭代器。
前置条件 T 类型需满足可移动插入到 C 容器中的 MoveInsertable 要求。
v. insert ( p, n, t ) Iter 效果 在 p 之前插入 n 个 t 的副本。
返回值 指向插入到 v 的第一个元素副本的迭代器，若 n 为 ​ 0 ​ 则返回 p 。
前置条件

T 需满足可被复制插入到 C 中，且满足 CopyInsertable 与 CopyAssignable 要求。

(自 C++11 起)
v. insert ( p, i, j ) Iter 效果 在 p 之前插入范围 [ i , j ) 中元素的副本。
  • 范围 [ i , j ) 中的每个迭代器均被精确解引用一次。
返回值 指向插入到 v 的第一个元素副本的迭代器，若 i == j 为 true 则返回 p 。
前置条件
(C++11 起)
  • i 和 j 不在 v 中。
v. insert_range ( p, rg )
(C++23 起) 		Iter 效果 在 p 之前插入 rg 中元素的副本。
  • 范围 rg 中的每个迭代器恰好被解引用一次。
返回值 指向插入到 v 的第一个元素副本的迭代器，若 rg 为空则返回 p 。
前置条件
v. insert ( p, il )
(C++11 起) 		Iter 等价于 v. insert ( p, il. begin ( ) , il. end ( ) ) 。
v. erase ( q ) Iter 效果 删除由 q 指向的元素。
返回值 指向被擦除元素之前紧邻 q 之后元素的迭代器，若不存在此类元素则返回 v. end ( ) 。
v. erase ( q1, q2 ) Iter 效果 删除 [ q1 , q2 ) 范围内的元素。
返回值 返回指向被擦除元素前 q2 所指向元素的迭代器，若该元素不存在则返回 v. end ( ) 。
v. clear ( ) void 效果 销毁 v 中的所有元素。
  • 使所有指向 v 元素的引用、指针和迭代器失效，并可能使尾后迭代器失效。
后置条件 v. empty ( ) 为 true 。
复杂度 线性。
v. assign ( i, j ) void 效果 将 v 中的元素替换为 [ i , j ) 范围的副本。
  • 使所有指向 v 元素的引用、指针和迭代器失效。
  • [ i , j ) 范围内的每个迭代器仅被解引用一次。
前置条件
(C++11 起)
  • i 和 j 不在 v 中
v. assign_range ( rg )
(C++23 起) 		void 效果 将 v 中的元素替换为 rg 中每个元素的副本。
前置条件
v. assign ( il )
(C++11 起) 		void 等价于 v. assign ( il. begin ( ) , il. end ( ) ) 。
v. assign ( n, t ) void 作用 将 v 中的元素替换为 n 个 t 的副本。
前置条件

T 需满足可被复制插入到 C 中，且满足 CopyInsertable 与 CopyAssignable 要求。

(C++11 起)
额外操作 [3]
（仅对特定序列容器要求，省略 std:: ）
表达式 类型 语义
v. front ( ) Ref 容器 basic_string , array , vector , inplace_vector , deque , list , forward_list
返回值 * v. begin ( )
cv. front ( ) CRef 容器 basic_string , array , vector , inplace_vector , deque , list , forward_list
返回值 * cv. begin ( )
v. back ( ) Ref 容器 basic_string , array , vector , inplace_vector , deque , list
等价于 auto tmp = v. end ( ) ; -- tmp ; return * tmp ; [4] 。
cv. back ( ) CRef 容器 basic_string , array , vector , inplace_vector , deque , list
等效于 auto tmp = cv. end ( ) ; -- tmp ; return * tmp ; [5] 。
v. emplace_front ( args )
(C++11 起) 		void 容器 deque , list , forward_list
效果 前置插入一个类型为 T 的对象，该对象通过 std:: forward < Args > ( args ) ... 构造。
返回值 v. front ( )
前置条件 T 能够通过 EmplaceConstructible 方式从 args 构造到 C 中。
v. emplace_back ( args )
(自 C++11 起) 		void 容器 vector , inplace_vector , deque , list
效果 追加一个类型为 T 的对象，该对象通过 std:: forward < Args > ( args ) ... 构造。
返回值 v. back ( )
前置条件 T 可 EmplaceConstructible 到 C 从 args 构造。
v. push_front ( t ) void 容器 deque , list , forward_list
效果 在首部添加 t 的副本。
前置条件

T 是 CopyInsertable 到 C 中的。

(C++11 起)
v. push_front ( rv )
(C++11 起) 		void 容器 deque , list , forward_list
效果 前置插入 rv 的副本，可能使用移动语义。
前置条件 T 类型满足 MoveInsertable 要求，可被插入 C 容器。
v. prepend_range ( rg )
(自 C++23 起) 		void 容器 deque , list , forward_list
效果 在 v. begin ( ) 之前插入 rg 中元素的 [6] 副本。
  • 范围 rg 中的每个迭代器都会被解引用恰好一次。
前置条件 T 能够通过 EmplaceConstructible 从 * ranges:: begin ( rg ) 构造到 C 中。
v. push_back ( t ) void 容器 basic_string , vector , inplace_vector , deque , list
效果 追加 t 的副本。
前置条件

T 是 CopyInsertable 到 C 中的。

(C++11 起)
v. push_back ( rv )
(C++11 起) 		void 容器 basic_string , vector , inplace_vector , deque , list
效果 追加 rv 的副本，可能使用移动语义。
前置条件 T 类型满足 MoveInsertable 要求，可被插入到 C 容器中。
v. append_range ( rg )
(自 C++23 起) 		void 容器 vector , inplace_vector , deque , list
效果 在 v. end ( ) 之前插入 [6] rg 中元素的副本。
  • 范围 rg 中的每个迭代器均被精确解引用一次。
前置条件 T 能够通过 EmplaceConstructible 方式从 * ranges:: begin ( rg ) 构造到 C 中。
v. pop_front ( ) void 容器 deque , list , forward_list
效果 销毁首个元素。
前置条件 a. empty ( ) 为 false 。
v. pop_back ( ) void 容器 basic_string , vector , inplace_vector , deque , list
效果 销毁最后一个元素。
前置条件 a. empty ( ) 为 false 。
v [ n ] Ref 容器 basic_string , array , vector , inplace_vector , deque
等价于 return * ( v. begin ( ) + n ) ; 。
cv [ n ] CRef 容器 basic_string , array , vector , inplace_vector , deque
等价于 return * ( cv. begin ( ) + n ) ; 。
v. at ( n ) Ref 容器 basic_string , array , vector , inplace_vector , deque
返回值 * ( v. begin ( ) + n )
异常 当 n >= v. size ( ) 为 true 时抛出 std::out_of_range 。
cv. at ( n ) CRef 容器 basic_string , array , vector , inplace_vector , deque
返回值 * ( cv. begin ( ) + n )
异常 当 n >= cv. size ( ) 为 true 时抛出 std::out_of_range 。
注释
  1. ↑ 对于效果等同于其他操作的表达式，这些操作内部表达式的条件将继承表格中列出的条件。
  2. ↑ std::array 支持从 花括号包围的初始化列表 进行赋值，但不支持从 std::initializer_list 赋值。
  3. ↑ 以下所有操作 除 prepend_range 和 append_range 外 (自 C++23 起) 均具有均摊常数时间复杂度。
  4. ↑ 在 C++98 中， tmp 被声明为 C::iterator 类型。
  5. ↑ 在 C++98 中， tmp 被声明为 C::const_iterator 类型。
  6. ↑ 6.0 6.1 插入顺序相对于 rg 中元素的顺序保持非反转。

此外，对于每个序列容器：

  • 接受两个输入迭代器的构造函数模板，以及成员函数模板重载的 insert 、 append 、 assign 、 replace 函数，若对应的模板实参不满足 LegacyInputIterator 要求，则不会参与重载决议。
  • 若推导出的类型不符合 LegacyInputIterator 或 Allocator 要求，则含有对应模板参数的推导指引不参与重载决议。
(C++17 起)

标准库

以下标准库字符串类型和容器满足 SequenceContainer 要求：

存储和操作字符序列
(类模板)
(C++11)
固定大小就地连续数组
(类模板)
可调整大小的连续数组
(类模板)
(C++26)
可调整大小、固定容量、就地连续数组
(类模板)
双端队列
(类模板)
(C++11)
单向链表
(类模板)
双向链表
(类模板)

用法说明

容器 优点 缺点
std::vector 快速访问，连续存储 插入/删除操作大多效率低下
std:: inplace_vector 快速访问，原地连续存储 固定容量且插入/删除操作大多效率低下
std::array 快速访问，原地连续存储 元素数量固定且不支持插入/删除操作
std::deque 快速访问，首尾插入/删除高效 序列中间位置的插入/删除效率低下
std::list
std::forward_list 		序列中间位置插入/删除高效 访问操作多为线性时间复杂度

缺陷报告

以下行为变更缺陷报告被追溯应用于先前发布的 C++ 标准。

DR 适用版本 发布行为 正确行为
LWG 139 C++98 未要求对指定容器实现可选操作 要求实现并具有分摊时间复杂度
LWG 149 C++98 v. insert ( p, t ) 返回 Iter 而
v. insert ( p, n, t ) 和 v. insert ( p, n, t )
返回 void 		全部返回 Iter
LWG 151 C++98 q1 被要求必须可解引用 [1] 允许不可解引用
LWG 355 C++98 调用 v. back ( ) 或 v. pop_back ( ) 会
执行 -- v. end ( ) ，存在风险 [2] 		改为递减
v. end ( ) 的副本
LWG 589 C++98 i 和 j 所引用的元素
可能无法转换为 C::value_type 		要求隐式
可转换为 C::value_type
LWG 2194 C++11 std::queue 、 std::priority_queue 和
std::stack 也被视为 SequenceContainer [3] 		它们不属于 SequenceContainer
LWG 2231 C++11 v. clear ( ) 的复杂度要求
在C++11中被错误遗漏 		重新确认复杂度为线性
LWG 3927 C++98 operator [ ] 没有隐式要求 添加了隐式要求
  1. ↑ 这是一个缺陷，因为它使得当 v. erase ( v. begin ( ) , v. end ( ) ) 的行为在 v 为空容器时变为未定义。
  2. ↑ 如果 v. end ( ) 的类型是基本类型， -- v. end ( ) 的写法是不合法的。当 v 的类型被模板化时尤其危险，这种情况下该缺陷可能难以被发现。
  3. ↑ 在C++98中它们未被记录为 SequenceContainer 类型。