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

来自cppreference.com
< cpp‎ | named req


 
C++
 
C++ 具名要求
 

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

目录

[编辑]要求

给定以下类型和值：

类型 定义
C 序列容器类
TC 的元素类型
AC 的分配器类型：
  • 在 C::allocator_type 存在时是该类型，
  • 否则是 std::allocator<T>
R(C++23 起) 实现了 container-compatible-range <T> 的类型
Args(C++11 起) 模板形参包
RefC::reference
CRefC::const_reference
值 定义
vC 类型的值
cvconst C 类型的值
i，j老式输入迭代器(LegacyInputIterator) ，[i, j) 是有效范围，并且这些迭代器所指代的元素可隐式转换到 C::value_type
rg(C++23 起)R 类型的值
il(C++11 起)std::initializer_list<value_type> 类型的值
nC::size_type 类型的值
p 到 v 中的有效常量迭代器
q 到 v 中的有效可解引用常量迭代器
q1，q2 到 v 中的两个常量迭代器，使得 [q1, q2) 是有效范围
tC::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.06.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++ 标准。

缺陷报告 应用于 出版时的行为 正确行为
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) 。
来自“https://zh.cppreference.com/mwiki/index.php?title=cpp/named_req/SequenceContainer&oldid=100702”
close