C++ 具名要求：序列容器 (SequenceContainer)

来自cppreference.com
See More


 
C++
 
C++ 具名要求
 

序列容器 (SequenceContainer) 是在线性排列中存储相同类型对象的容器 (Container) 。

要求

给定以下类型和值：

类型 定义
C 序列容器类
T C 的元素类型
A C 的分配器类型：
  • 在 C::allocator_type 存在时是该类型，
  • 否则是 std::allocator<T>
R (C++23 起) 实现了 container-compatible-range <T> 的类型
Args (C++11 起) 模板形参包
Ref C::reference
CRef C::const_reference
值 定义
v C 类型的值
cv const C 类型的值
i，j 老式输入迭代器 (LegacyInputIterator) ，[i, j) 是有效范围，并且这些迭代器所指代的元素可隐式转换到 C::value_type
rg (C++23 起) R 类型的值
il (C++11 起) std::initializer_list<value_type> 类型的值
n C::size_type 类型的值
p 到 v 中的有效常量迭代器
q 到 v 中的有效可解引用常量迭代器
q1，q2 到 v 中的两个常量迭代器，使得 [q1, q2) 是有效范围
t C::value_type 类型的值(C++11 前)左值或 const 右值(C++11 起)
rv (C++11 起) C::value_type 类型的非 const 右值
args (C++11 起) 模式为 Args&& 的函数形参包

在满足以下所有条件时，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 从 *ranges::begin(rg) 可就位构造 (EmplaceConstructible) 到 C 中。
后条件 std::distance(begin(), end()) 是 ranges::distance(rg)。
C(il)
(C++11 起) 		C 等价于 C(il.begin(), il.end())。
v = il
(C++11 起) 		C& 效果 将 il 所表示的范围赋值到 a 中。[2]
返回值 *this
前条件 T 可复制插入 (CopyInsertable) 到 C 中，并且可复制赋值 (CopyAssignable) 。
后条件 v 的既存元素要么被销毁，要么被赋值。
v.emplace(p, args)
(C++11 起) 		Iter  效果 在 p 前插入以 std::forward<Args>(args)... 构造的 T 类型对象。
返回值 指向由 args 构造到 v 中的元素的迭代器。
前条件 T 从 args 可就位构造 (EmplaceConstructible) 到 C 中。
v.insert(p, t) Iter 效果 在 p 前插入 t 的副本。
返回值 指向插入到 v 中的 t 的副本的迭代器。
前条件

T 可复制插入 (CopyInsertable) 到 C 中。

(C++11 起)
v.insert(p, rv)
(C++11 起) 		Iter 效果 在 p 前插入 rv 的副本，可能使用移动语义。
返回值 指向插入到 a 中的 rv 的副本的迭代器。
前条件 T 可移动插入 (MoveInsertable) 到 C 中。
v.insert(p, n, t) Iter 效果 在 p 前插入 n 个 t 的副本。
返回值 指向插入到 v 中的首元素的副本的迭代器（在 n 是 0 时返回 p）。
前条件

T 可复制插入 (CopyInsertable) 到 C 中，并且可复制赋值 (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 效果 以 [i, j) 的副本替换 v 中的元素。
  • 指代 v 中的元素的所有引用、指针和迭代器都会失效。
  • 范围 [i, j) 中的每个迭代器都只会恰好解引用一次。
前条件
(C++11 起)
  • i 和 j 都不在 v 中。
v.assign_range(rg)
(C++23 起) 		void 效果 以 rg 中每个元素的副本替换 v 中的元素。
  • 如果 std::assignable_from
        <T&, ranges::range_reference_t<R>>     没有得到实现，那么程序非良构。
  • 指代 v 中的元素的所有引用、指针和迭代器都会失效。
  • 范围 rg 中的每个迭代器都只会恰好解引用一次。
前条件
v.assign(il)
(C++11 起) 		void 等价于 v.assign(il.begin(), il.end())。
v.assign(n, t) void 效果 用 t 的 n 个副本替换 v 中的元素。
前条件

T 可复制插入 (CopyInsertable) 到 C 中，并且可复制赋值 (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
效果 前附一个以 std::forward<Args>(args)... 构造的 T 类型对象。
返回值 v.front()
前条件 T 从 args 可就位构造 (EmplaceConstructible) 到 C 中。
v.emplace_back(args)
(C++11 起) 		void 容器 vector, inplace_vector, deque, list
效果 后附一个以 std::forward<Args>(args)... 构造的 T 类型对象。
返回值 v.back()
前条件 T 从 args 可就位构造 (EmplaceConstructible) 到 C 中。
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() 前插入[6] rg 中的元素的副本。
  • 范围 rg 中的每个迭代器都只会恰好解引用一次。
前条件 T 从 *ranges::begin(rg) 可可就位构造 (EmplaceConstructible) 到 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.begin() 前插入[6] rg 中的元素的副本。
  • 范围 rg 中的每个迭代器都只会恰好解引用一次。
前条件 T 从 *ranges::begin(rg) 可可就位构造 (EmplaceConstructible) 到 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 >= v.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 中元素的顺序，不是逆序。
本节未完成
原因：Add bits from P2846 for (sequence) [containers]

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

  • 对于接收两个输入迭代器的构造函数模板，以及成员函数 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++ 标准。

缺陷报告 应用于 出版时的行为 正确行为
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() 会执行危险[2]的操作 --v.end() 改成自减 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 C++11 中错误地省略了 v.clear() 的复杂度要求 重申复杂度为线性
LWG 3927 C++98 operator[] 没有隐式要求 添加隐式要求
  1. ↑ 它是缺陷的原因是它会导致在空容器 v 上调用 v.erase(v.begin(), v.end()) 的行为未定义。
  2. ↑ 如果 v.end() 具有基础类型，那么 --v.end() 非良构。当 v 时模板化类型的时候这个操作就变成了危险操作，它会在 v 的类型从非基础类型变成基础类型的时候导致编译失败，并且难以排查。
  3. ↑ 它们在 C++98 中没有被记载为序列容器 (SequenceContainer) 。