%% # 纲要 > 主干纲要、Hint/线索/路标 # Q&A #### 已明确 #### 待明确 > 当下仍存有的疑惑 **❓<font color="#c0504d"> 有什么问题？</font>** # Buffer ## 闪念 > sudden idea ## 候选资料 > Read it later %% # 标准模版库 STL **标准模板库**（Standard Template Library, STL）是 **C++标准库**的核心组成部分。 STL 中提供了一系列的**通用模版类**和**函数**（用以实现基本的**通用数据结构**），以及在这些数据集合上运作的**算法**。 **STL 中的==所有组件都是模板==**，因此可以**用于任意元素类型**。 STL 包含以下四部分核心组件： - **==容器== （Container）** - **容器适配器**（Container Adapter） - **==迭代器==（Iterator）** - **迭代器适配器**（Iterator Adapter） - **==算法== （Algorithm）** - **==函数对象==（Function Object）** - **函数对象适配器**（Funtion Object Adapter） > [!NOTE] "**适配器**"（Adapter）是**基于既有的 STL 组件进行封装**，从而**提供具有不同功能的接口**的组件。 > [!NOTE] 标准库算法都是 "**==函数模版==**"，标准库容器都是 "**==类模版==**" <br><br> # 容器 ⭐ **容器**（Container）：用于**直接存储**和**管理**某一类**对象集合**的**抽象/通用数据结构**。 STL 提供的容器有： - **序列容器 Sequence container**：通常被实现为 array 或 linked list. - `std::array`（固定大小的数组） - `std::vector` - `std::list` （双向链表） - `std::forward_list`（单向链表） - `std::deque` - **关联容器 Associative container**：通常被实现为 binary tree，平衡二叉树 - `std::set` - `std::multiset` - `std::map` - `std::multimap` - **无序容器 unordered container**：通常被实现为 hash table。 - `std::unordered_set` - `std::unordered_multiset` - `std::unordered_map` - `std::unordered_multimap` <br> ## 容器提供的共通类型  <br> ## 容器的大小 STL 容器普遍提供了下列成员函数： - `.size()`：返回**容器内当前元素个数** - `.max_size()`：返回容器内所可能容纳的最大元素数量 - vector 特有： - `.capacity()`：**容器当前内存空间下**所能容纳的最大元素数量（即不重新分配内存空间的情况） 改变容器大小的操作[^3]： - `.resize(n)`：**改变容器元素个数为`n`** - `n` 大于当前元素数量时，以 "**值初始化**" 的方式默认构造元素； - `n` 小于当前元素数量时，**直接截断**。 - `.reserve(n)`：**分配能容纳 n 个元素的内存空间**（仅影响 `capacity`，严格按照 `n` 个元素需求的大小进行分配）（vector 特有） - `n` 小于当前**容量**（`.capacity()`）时，不做任何操作； <br><br> ## 容器的内存管理 STL 容器内部使用**分配器（默认为 `std::allocator`）来管理==存储"元素"==所需的内存分配和释放**。 分配器抽象了内存管理的细节，**允许容器在==堆==上分配存储空间来存储其元素**。 此外，容器的设计确保了**即使容器本身是在"栈"上或"静态存储区"创建的**，其**元素仍然存储在==堆内存==中**。 ### 容器所使用的内存空间 STL 中容器所使用的内存空间分为两部分： - **==容器对象本身==** 占有的内存空间； - **存储容器内==元素**==所用的内存空间； "容器对象本身" 所用的内存空间则取决于容器对象的**存储持续性**： - 当容器对象是**局部非静态变量**（**自动存储持续性**）时，其是在 "**==栈内存==**" 上创建的； - 当容器对象是**全局或静态变量**（**静态存储持续性**）时，其是在"**==静态存储区==**"创建的； - 当容器对象是**动态变量**（**动态存储持续性**）时，其是在 "**==堆内存==**" 上创建的。 - 使用 **`new` 关键字**或**智能指针**时 "容器内元素" 则是通常存储在 "**==堆内存==**" 上（**仅 `array` 容器除外**），**在==堆==上占有独立的内存块**。 容器在运行时根据需要**动态地申请内存空间**来存储元素。 > [!info] array 容器中的元素存储 > **array 容器相当于"数组"**，其**容器大小**在声明时以"**模版参数**"的形式提供。 > 声明示例： `array<int, 5> array_container;` > > arrary 容器中存储的元素都**作为 "容器对象本身" 的一部分**，**存储在==容器对象所占有的连续内存空间==上**，而不是作为独立的、分离的内存块。 > 说明示例： - `vector<>` 内元素存储在 "**堆内存**" 上，而 **`vector<>` 内部持有指向这一块内存空间的指针**，因此 `sizeof(vec)` 并不包含 **"元素所占内存"**； - `array<>` 内元素与容器对象本身存储在一起，因此 **`sizeof(arr)` 包含元素所占内存**。 ```cpp int main() { constexpr int size = 100000; vector<char> vec(size); array<char, size> arr; string str(10000, 'C'); cout << sizeof vec << endl; // 24 cout << sizeof arr << endl; // 100000 cout << sizeof str << endl; // 32 return 0; } ``` <br> ### 容器的动态扩容机制 #### `std::vector` 的动态扩容机制 `std::vector` 使用 **==一整块连续的堆内存空间==** 来存储元素，其容量（`capacity`）会根据需要**动态增长**。 当需要插入新元素时，**如果其容量不足以容纳新元素**，则会**申请分配一个==更大的连续内存块**==，并**将现有元素 =="移动" or "拷贝"== 到新内存块中**。 通常，编译器的实现在**扩容时**采用 "**容量翻倍策略**"，即申请**大小为当前容量 "两倍" 的新的连续内存空间**。 这一策略保证了每个元素插入的**平均/均摊时间复杂度**是常数级的，为 $O(1)$。 ` 注意，**C++标准并没有规定明确的增长因子（即新容量是旧容量的多少倍）**，因此不同的编译器和标准库实现可能会采用不同的策略。 > [!note] **容量翻倍策略**的扩容均摊复杂度：$O(1)$ > >  > >  > > <br> #### `std::deque` 的动态扩容机制 `std::deque` 内部实现通常是 **"一系列"固定大小的数组（称为块）** ，这些块 **==在内存空间上并不是连续的==**。 **当需要更多空间时则会添加新的块，这一过程通常不涉及复制或移动已有元素。 因此 ==`deque` 在前端和后端都可以快速地添加元素==， 而不是像 `vector` 那样在扩容后需要以 $O(n)$ 的复杂度将原空间位置的元素挪动到新内存空间**。 <br><br> ## 在 STL 容器中实现 Reference 语义 > [!NOTE] STL 容器不支持存储 "引用类型" 元素的原因 > > STL 容器在进行元素的安插动作时，内部实施的是**copy 或 move 动作**， > 因此 **STL 容器中存储的元素类型必须要能够被 copied 或 moved**，而 "引用类型" 不能支持这两点。 > 所有 STL 容器提供的都是 "**value 语义**" 而非 "**reference 语义**"，不支持**存储/管理"引用类型"的元素**。 如果要在 STL 容器中实现**引用语义**，可通过以下三种方式： - 以**指针 pointer** 作为容器元素； - 以**智能指针**作为容器元素； - 使用 `std::reference_wrapper<>` 包装器，让 **STL 容器持有引用**。 <br><br><br> # 容器适配器 ⭐ **容器适配器** (container adapter) 是 "**==对现有容器接口的适配或封装==**"，使其**接口和行为符合特定的数据结构**，如堆栈或队列，其**不属于真正的容器**。 STL 提供了**三种**容器适配器[^5]： - **`stack`**，位于头文件 `<stack>` - **`queue`**，位于头文件 `<queue>` - **`priority_queue`**，位于头文件 `<queue>` 这些容器适配器**建立在其它底层容器之上, 如 `deque` 或 `vector`**。 定义容器适配器时**可提供一个"底层容器类型"作为==模版参数==**。未提供时，具有如下的**默认值**： - `stack` 与 `queue` 默认**使用 `deque` 作为底层容器**； - `priority_queue ` 默认**使用 `vector` 作为底层容器**。 - 同时，其依赖于 `<algorithm>` 头文件中提供的 `std::make_heap`，`std::push_heap` 和 `std::pop_heap` 等函数**来维护"堆"的性质**。这些函数允许在普通数组或容器上执行操作。 ### 适配器共有接口 ![[_attachment/02-开发笔记/01-cpp/库使用/STL 标准模版库.assets/IMG-STL 标准模版库-C07843F8D70636BDCA506808F38159A9.png|731]] ### 栈适配器 ![[_attachment/02-开发笔记/01-cpp/库使用/STL 标准模版库.assets/IMG-STL 标准模版库-C205D8A1EFE9FF7D3A5409211AFB991C.png|753]] ### 队列适配器 ![[_attachment/02-开发笔记/01-cpp/库使用/STL 标准模版库.assets/IMG-STL 标准模版库-3EDD18400DB9E9687C47B51CF6BF9BED.png|708]] <br><br><br> # 迭代器 ⭐ > 参见 [^1] 迭代器是一种**用于访问容器中元素的==对象==**，可表示**容器内某一个元素的位置**，可用来**遍历容器内的元素**。 每一种容器都必须提供自己的迭代器，**所有 STL 容器都在其 ==class 定义内部==以==嵌套类==的方式定义了迭代器类型**。 STL 容器可能提供的迭代器类型包括： - **常规迭代器**： `Countainer<T>::iterator`，例如 `vector<int>::iterator`。 - **==常量==迭代器**： `Countainer<T>::const_iterator`， 例如 `vector<int>::const_iterator`。 此外，还有作为 "**迭代器适配器**" 的反向迭代器： - **反向迭代器**：`Container<T>::reverse_iterator`； - **==常量==反向迭代器**：`Container<T>::const_reverse_iterator` > [!NOTE] 迭代器具有与**原始指针**（ordinary pointer）相似的接口 > [!note] 两种 "常量" 迭代器相当于常量指针，**不能修改该迭代器的指向**； <br><br> ## 迭代器的类别 ![[_attachment/02-开发笔记/01-cpp/库使用/STL 标准模版库.assets/IMG-STL 标准模版库-67B5437732379D80F131FA0786ABDF32.png|662]] STL 中的**迭代器**按照 "功能" 进行划分，可分为[^7]： - **输入迭代器**（Input iterator）： - 支持向前迭代（通过 `++`），但只能 **==单趟遍历==**：不能保存迭代器状态，**迭代器移动后可能导致其他所有迭代器失效**。 - 可通过解引用 `*` 或 `->` **读取迭代器所指元素值**（只出现于赋值 `=` 右侧），用于进行 "==**赋值**=="。 - 只能 "**读取**" 元素； - **输出迭代器**（Output iterator）： - 支持向前迭代（通过 `++`），但只能 **==单趟遍历==**：不能保存迭代器状态，**迭代器移动后可能导致其他所有迭代器失效**。 - 可通过解引用 `*` 或 `->` **读取迭代器所指元素**（只出现于赋值 `=` 左侧），**允许==将值写入其所指元素==**。 - 只能向其所指元素 "**写入**"。 - **前向迭代器**（Forward iterator） ： - 具备 "**输入迭代器**" & "**输出迭代器**" 功能，且支持多次**读写**同一元素。 - 支持**向前**迭代（通过 `++`），**可保存迭代器状态**，允许 "**==多趟遍历==**"。 - **双向迭代器**（Bidirectional iterator）： - 具备 "**前向迭代器**" 所有功能； - 支持**向前向后**迭代（通过递增/递减运算符 `++/--` ），**可保存迭代器状态**，允许 "**==多趟遍历==**"。 - **随机访问迭代器**（Random-access iterator）: - 支持**双向迭代器**所有功能； - 可对迭代器进行**算术运算**，例如**增加/减少指定偏移量**，**计算两迭代器之间的距离**； - 可进行相对关系比较 ( `<` 或 `>` 等) - 支持下标访问运算符； > [!NOTE] 五种迭代器类别具有 "**层次**" 关系，**更高级的迭代器支持更弱类别迭代器的所有操作**。 > > 除 **输入迭代器与输出迭代器 "互补"** 外， > **前向迭代器**具备两者功能，**双向迭代器**则具备前向迭代器的功能，**随机访问迭代器**则具备双向迭代器的功能。 所有 STL 容器所提供的迭代器，均属于上述类型中的**后三种类别之一**： | 迭代器 | 提供该迭代器的容器 | | ------- | ---------------------------------------------------------- | | 前向迭代器 | `forward_list` | | 双向迭代器 | `list`、所有**关联类容器**、所有**无序容器**（C++标准规定至少是前向的，但标准库实际提供的是双向的） | | 随机访问迭代器 | `vector`、`array`、`deque`、`string` | | 输入迭代器 | Input stream | | 输出迭代器 | Output stream、Inserter | <br><br> ## 获取迭代器 所有容器类都提供了用以 **获取迭代器** 的成员函数，包括： - `begin()`：返回一个**指向容器起点**的迭代器，即指向**容器内首个元素（如果存在）**； - `end()` ：返回一个**指向容器终点**的迭代器，即指向**容器内==最后一个元素之后的下一位置==**，也称"**尾后迭代器（past-the-end" 或 "off-the-end"）**。 - `cbegin()` 与 `cend()`：返回 `const_iterator` **常量迭代器**，其对容器内元素**仅可读**而不可写（since C++14） - `rbegin()` 与 `rend()`：返回 "**反向迭代器**"，二者返回的迭代器方向恰好与 `begin()` 和 `end()` 相反。 - `crbegin()` 与 `crend()`：返回 "**常量反向迭代器**"； > [!note] const 容器对象的 `begin()` 与 `end()` 返回的是 "**常量迭代器**" `const_iterator` > [!info] 迭代器范围 > >  > > `begin()` 和 `end()` 获取的**迭代器**形成了一个**半开区间**：`[beg, end)`。 > 对于空区间，有 `begin() == end()`。 > > ![[_attachment/02-开发笔记/01-cpp/库使用/STL 标准模版库.assets/IMG-STL 标准模版库-20A57066FC851B94AC1EAB839BFF54CC.png|568]] > [!caution] "迭代器对" 用以表示区间范围 > > > 当使用 "**一对迭代器**" 作为参数，表示**一个范围区间**时，区间必须是合法的： > > - 前后两个迭代器，**必须指向同一个容器**； > - 从第一个迭代器出发，**必须可到达第二个迭代器所指位置**。 > <br><br> ## 迭代器的使用 迭代器使用示例： ```cpp vector<int> coll = {1, 2, 3, 4, 5}; // 声明一个迭代器对象 (可读/写容器内元素) vector<int>::iterator pos; // 通过迭代器遍历容器内元素 for (pos = coll.begin(); pos != coll.end(); ++pos) { cout << *pos << endl; // 迭代器接口类似指针, 通过解引用来访问元素. } // 声明一个const迭代器, "指向容器内的常量元素"的迭代器. (只可读容器内元素) vector<int>::const_iterator const_pos; // 通过const迭代器遍历容器内元素 for (pos = coll.cbegin(); pos != coll.cend(); ++pos) { cout << *pos << endl; } ``` > [!info] `range-based for` 循环的内部实现是**使用迭代器对象**来遍历所有元素，是基于迭代器的一个便捷接口。 > > ```cpp > for (type elem : coll) { // 这里的 elem 就是元素类型, 而不是迭代器. > ... > } > // 上述 range based for 循环被解释为: > for (auto pos=coll.begin(), end=coll.end(); pos!=end; ++pos) { > type elem = *pos; > } > ``` <br><br> ## 迭代器失效 "**==迭代器失效==**" 是指由于底层容器发生变化，导致**原先指向容器内元素的迭代器**（例如迭代器实现为指针或引用）**不再有效**。 常见导致**迭代器失效**的操作包括[^2]： - 当容器在内部进行**重新分配内存**（如 `std::vector` 在容量不足时扩展）时，**所有指向原始内存的迭代器都会失效**。 - 部分不稳定算法，例如 `std::remove()` 或`std::unique()`，导致序列重排列时； - 对任何容器，**调用 `clear()` 移除所有元素**后，**原先所有迭代器失效**。 - 当**元素被删除**时： - 对除 `vector` 和 `deque` 外的所有容器：仅 **"指向被删除元素的迭代器"** 失效，但**不影响其它迭代器**； - 对 `vector` ： **指向==被删除元素==及其==之后所有元素==的迭代器失效**，指向被删除元素之前元素的迭代器仍然有效。 - 对 `deque`：**删除==首尾位置之外==的任何元素时**，**都会使所有迭代器失效**。 - 当**元素插入**时： - 对于 `vector` 而言， - 若**发生内存重新分配**（ 在容量不足时扩展），则会导致**所有指向原始内存的迭代器都会失效**。 - 若**在尾部插入元素**，未发生内存重分配，则无影响； - 若**在中间插入元素**，则**被插入点之前的迭代器有效，原先==被插入点及之后的所有迭代器失效**==。 - 对于 `deque` 而言， - 若**重新分配内存块**（少见），**所有迭代器失效**； - 若**在==首尾==插入元素**，未发生内存重分配，无影响； - 若**在==中间==插入元素**，**则==所有迭代器失效==**（中间插入可能导致内存块的重新组织） - 对于 `list`、`forward_list`、`array` 而言，**不会导致任何迭代器失效**。 - 对于**关联容器**（如` set`）而言，**不会导致任何迭代器失效**。 - 对于**无序容器**（如`unordered_set`）而言，若插入元素后使 **==哈希表重建==**（**rehashing 重新散列**），则**所有迭代器失效**。 - （只要安插后的最终元素总数**小于 bucket 个数乘以最大负载系数，就不会发生 rehashing**） > [!NOTE] `string` 与 `vector` 一样内部采用连续内存块，因此迭代器失效情况也同 `vector`。 --- %% >  %% <br><br><br> # 迭代器适配器 ⭐ > 迭代器适配器位于 `<iterator>` 头文件中 迭代器适配器（Iterator Adapter）是 STL 提供的**特殊迭代器**，**基于既有的底层迭代器进行封装**，修改或扩展底层迭代器的功能，从而提供**特殊迭代行为**。 STL 提供的迭代器适配器包括： - **Insert iterator 插入迭代器** - `std::back_inserter` - `std::front_inserter` - `std::inserter` - **Reverse iterator 反向迭代器** - `std::reverse_iterator` - **Move iterator 移动迭代器**（since C++11） - `std::move_iterator` - **Stream iterator 流迭代器** - `std:istream_iterator` - `std::ostream_iterator` %% >  %% <br><br> ## 插入迭代器 插入迭代器是一种**迭代器适配器**，用于**向容器中插入元素**： 通过 "**插入迭代器**" 进行 "**==赋值==**" 时，**该值将被==插入到元素中迭代器的位置==**。 标准库提供了三个函数用于获取 **插入迭代器**，其均接受一个 "**==指向容器的引用==**"，**返回与该容器绑定的插入迭代器**： - `back_inserter(c)`：返回一个使用 `push_back()` 的插入迭代器，用于**在容器尾部** 插入元素。 - `front_inserter(c)`：返回一个使用 `push_front()` 的插入迭代器，用于**在容器头部**插入元素。 - `inserter(c, iter)`：返回一个使用 `insert()` 的插入迭代器，用于**在容器指定位置==之前==** 插入元素。 > [!NOTE] 仅能对支持 `push_back()` 的容器使用 `back_insert()`，仅能对支持 `push_front()` 的容器使用 `front_inserter()` 使用示例： ```cpp vector<int> vec; // 空向量 auto it = back_inserter(vec); // 获取尾部插入迭代器 *it = 42; // 将向vec中插入一个值为42的元素 vector<int> vec; // 空向量 fill_n(back_inserter(vec), 10, 5); // 将向vec中插入10个值为5的元素. list<int> lst_1 = { 1, 2, 3, 4}; list<int> lst_2; // 空链表 copy(lst_1.begin(), lst_1.end(), front_inserter(lst_2)); // 向lst_2中逆序插入lst_1的元素(头插法进行拷贝) ``` #### 插入迭代器的实现原理 ![[_attachment/02-开发笔记/01-cpp/库使用/STL 标准模版库.assets/IMG-STL 标准模版库-042862108D5A90E42C7721EEE9C24D90.png|784]] - 对插入迭代器的 "**赋值**" 操作： - 对于 `back_inserter` 和 `front_insert`，**其内部实现为调用容器的 `.push_front()`，`.push_back()` 方法**。 - 对于 `inserter` ，**其内部实现为调用容器的 `.insert(it, val)` 方法**，**且在每次执行插入后，内部 `it` 会递增，保证==插入迭代器始终指向最初元素==**。 - 对插入迭代器本身的 `*`、 `++` 操作 **实际上并未执行任何操作，都是返回其本身**。 `inserter(c, iter)` 迭代器的内部操作示例： ```cpp auto it = inserter(c, iter); it = val; // 插入迭代器始终指向最原先的元素. // `it = val`等价于下述过程: it = c.insert(it, val); ++it; // 插入迭代器递增, 仍然指向原先的元素 // 示例: vector<int> vec = { 1, 2, 3, 4}; auto insert_it = inserter(vec, vec.begin() + 2); insert_it = 99; insert_it = 98; insert_it = 97; // 得到vec: { 1, 2, 99, 98, 97, 3, 4 }, insert_it始终指向最初元素3. ``` <br><br> ## 反向迭代器 > 参见 [^6] 反向迭代器用以实现 **==逆向==遍历容器**。其调换了**基础迭代器**的**递增和递减操作**： 对反向迭代器进行**递增操作**会导致它**向容器的首部移动**，而进行**递减操作**会使它**向容器的末尾移动**。 STL 容器中提供了 `rbegin()` 和 `rend()` 两个成员函数来获取 "**反向迭代器**"，以及 `crbegin()`、`crend()` 获取 "**常量反向迭代器**"。 > [!NOTE] 除 `forward_list` 之外，其他所有容器都具有反向迭代器。 > [!caution] 反向迭代器的 `.base()` 成员函数返回**指向 "==反向迭代器所指元素的后一位置==" 的常规正向迭代器**。 > > ![[_attachment/02-开发笔记/01-cpp/库使用/STL 标准模版库.assets/IMG-STL 标准模版库-3D105FF8725DC28D65192DA6C226F309.png|517]] > > 使用示例： ```cpp title:reverse_iterator.cpp std::vector<int> vec = { 1, 2, 3, 4, 5}; for (auto it = vec.rbegin(); it != vec.rend(); ++it) { // 逆向遍历 std::cout << *it << " "; // 输出: 5 4 3 2 1 } ``` <br><br> ## 移动迭代器 移动迭代器（move iterator）的 "**==解引用运算符==**" 返回 "**右值引用类型**"（**表达式值类别为亡值**），从而支持在算法中应用 "**移动语义**"。 STL 中提供了 `std::move_iterator<>` 移动迭代器类模版，**用以将任何常规迭代器包装为 "移动迭代器"**， 使得**对移动迭代器的"==解引用=="操作都变为 "==返回'原始迭代器'的右值引用=="（相当于对元素使用了 `std::move()`）。 有两种方式创建移动迭代器： - **直接声明移动迭代器实例**：`std::move_iterator move_it(other_it);` - 使用**标准库的 `make_move_iterator()`** ：该函数接受一个迭代器参数，**返回一个移动迭代器**。 使用示例： ```cpp title:move_iterator.cpp #include <vector> #include <iostream> #include <algorithm> #include <iterator> // For std::move_iterator struct MyClass { MyClass() = default; MyClass(const MyClass&) { std::cout << "Copied" << '\n'; } MyClass(MyClass&&) noexcept{ std::cout << "Moved" << '\n'; } }; int main() { std::vector<MyClass> src(5); // 源容器 std::vector<MyClass> dest; // 目标容器 std::vector<MyClass> dest2; // 使用move_iterator包装src的begin和end迭代器 // 方式一: 直接构造`std::move_iterator`迭代器实例 std::move_iterator move_begin_it(src.begin()); std::move_iterator move_end_it(src.end()); // 将移动迭代器传递给copy, 从而实现"移动"而非拷贝. std::copy( move_begin_it, move_end_it, std::back_inserter(dest) ); // 方式二: 通过std::make_move_iterator()返回`std::move_iterator`实例. std::copy( std::make_move_iterator(dest.begin()), std::make_move_iterator(dest.end()), std::back_inserter(dest2) ); // 上述移动操作理论上将输出五次"Moved", 而不是"Copied". // 然而, 实际上由于会触发vector的重新内存分配(扩容), 因此实际输出的"Moved"是12次. } ``` <br><br> ## 流迭代器 > 参见 [^8] 流迭代器用于 **IO 类型对象**，将对应的**流**当做**一个特定类型的元素序列**进行处理，支持应用**泛型算法**从流对象**读取数据以及向其写入数据**。 - `istream_iterator`：读取**输入流**。 - `ostream_iterator`：向一个**输出流**写数据。 > [!NOTE] 可以为任何定义了 `>>` 运算符的类型创建 `istream_itertor`； 可为任何定义了 `<<` 运算符的类型创建 `ostream_iterator`。 #### 输入流迭代器 ![[_attachment/02-开发笔记/01-cpp/库使用/STL 标准模版库.assets/IMG-STL 标准模版库-A6E272F707DDE8B5399120A11397ED4B.png|817]] 使用示例： ```cpp // 示例一: 从输入流读取 istream_iterator<int> in_iter(cin); // 从cin读取int. istream_iterator<int> eof; // 尾后迭代器 while (in_iter != eof) { vec.push_back(*in_iter++); // `*in_iter++`对输入流迭代器解引用时相当于执行 `cin >>`, 返回读取的值. } // 上述循环可重写为: vector<int> vec(in_iter, eof); // 使用迭代器范围直接构造vec. // 示例二: 从文件流读取 ifstream in_file("afile"); // 文件流, 打开一个文件并绑定 istream_iterator<string> str_it(in); // 从文件流中读取字符串 istream_iterator<string> eof; // 示例三: 对输入流迭代器应用泛型算法 istream_iterator<int> in(cin), eof; int sum = accumulate(in, eof, 0); // 等待标准输入结束(读至EOF), 计算读取的值的和. ``` #### 输出流迭代器 ![[_attachment/02-开发笔记/01-cpp/库使用/STL 标准模版库.assets/IMG-STL 标准模版库-FF1D5825D0C5B1EEA2A3010985FA7407.png|836]] > [!caution] 不允许定义空的输出流迭代器，不存在表示尾后位置的 `ostream_iterator` 使用示例： ```cpp ostream_iterator<int> out_iter(cout, " "); // 每次输出一项元素后末尾加上" ". for (auto& e : vec) { out_iter = e; // 等价于向cout中使用"<<" 每次输出一项e值, 以及指定的结尾符" ". " } ``` <br><br><br> # pair 类型 > 参见 [^10] ![[_attachment/02-开发笔记/01-cpp/库使用/STL 标准模版库.assets/IMG-STL 标准模版库-B5882ACA35D637DF01AABE4BCEAE68F3.png|618]] ```cpp pair<string, int> p1 = {"Hello", 25}; auto p2 = make_pair("schar", 25); // pair<const char*, int>; cout << p1.first << " " << p1.second << endl; ``` > [!caution] `std::pair<>` 可直接用作 `std::map` 的键，但不能直接用作 `std::unordered_map<>` 的键！ > > - `std::map<>` 不是基于哈希映射，而是 **"键" 的可排序性**！只要类型支持 `operator<`，就能用作键； > - `std::unordered_map<>` 基于 "**哈希映射**"，需要将 "**键类型**" 映射为一个 **`size_t` 类型的哈希值**。 **STL 并没有为 `std::pair<>` 提供默认的哈希函数**。 > > ![[_attachment/02-开发笔记/01-cpp/库使用/STL 标准模版库.assets/IMG-STL 标准模版库-CEF14161CCE92D7B2B4CA844EF2710CD.png|563]] > <br><br><br> # tuple 类型 > 参见 [^11]，位于 `<tuple>` 头文件中。 tuple 是个**类模版**，允许将**不同类型、数目的元素**组合成一个单一对象。 tuple 的特点：**成员数目、类型固定**，是 **tuple 类型的一部分**，编译时确认。 适用场景: * （1）当函数需要返回多个值时, 使用 `std::tuple` 可以避免定义专门的结构体或类。 * tuple 中每项元素是未命名的，如果元组有特定的业务逻辑或意义，使用**具有"描述性字段名"的结构体或类**可能更合适 * （2）与 `std::tie`一起使用： - `std::tuple`和 `std::tie` 可以 **便捷地解包元组中的值**。 ## 相关操作 ![[_attachment/02-开发笔记/01-cpp/库使用/STL 标准模版库.assets/IMG-STL 标准模版库-D7CF256D4A2DB5C2CDE79B46CD65CB4E.png|723]] - 每个成员都是未命名的，**只能通过 `get<n>(t)` 模版函数获取**，返回 **`t` 中第`n`个成员的==引用==**。 - 索引值 `n` 必须是 "**==常量表达式==**"，只能在编译时确定。 - 两个辅助模版类用以查询 **tuple 的成员数量**和**类型**： - `tuple_size<tupleType>::value`： 获取指定 tuple 类型中的**成员数量** - `tuple_element<i, tupleType>::type`：获取指定 tuple 类型中**第 i 个成员的类型**。 <br> ## tie 解包/打包 > `std::tie`、`std::ignore` 同位于 `<tuple>` 中 `std::tie(var1, var2, ...varn)` 创建一个**由 "各变量 var 的==引用==" 构成的tuple**。 两个常用场景： 1. 用于 **"==解包==" 另一个 tuple**——**将 tuple 中各项值赋给 `tie` 中对应位置的变量**） 2. 用于 **"==打包==" 多个变量**——tuple 中存储变量的引用，修改 tuple 中的项将反映到原变量 > [!note] `std::tie(var1, var2, ...varn)` 等价于 `make_tuple(ref(var1), ref(var2), ... ref(varn))`，是语法糖 > [!info] C++17 中引入了 "**结构化绑定**" 功能，旨在更简洁地替代 `std::tie`。 **解包**使用示例： ```cpp int main() { tuple<string, int, char> t {"Hello", 25, 'G'}; string str; int i; char ch; // 使用tie解包, 等价于`make_tuple(ref(str), ref(i), ref(ch)) = t`; std::tie(str, i, ch) = t; cout << str << " " << i << " " << ch << endl; } ``` **打包**使用示例： ```cpp int main() { string str; int i; char ch; auto t = std::tie(str, i, ch); get<0>(t) = "Hello"; get<1>(t) = 25; get<2>(t) = 'G'; cout << str << " " << i << " " << ch << endl; } ``` #### 忽略不需要的元素项 **解包**时，可使用 **`std::ignore` 作为占位符**，**忽略 tuple 中某些位置的项**。 ```cpp int main() { tuple<string, int, char> t {"Hello", 25, 'G'}; int i; // 忽略第一项, 第二项. std::tie(std::ignore, i, std::ignore) = t; cout << i << endl; } ``` <br><br> # 其它 ## "emplace 置入函数" 与 "push 插入函数"的区别 STL 容器提供的 `emplace` 系列置入函数旨在为 **优化对象的插入和构造**而设计的， 当 "**==传入的实参类型==**" 与 "**==容器内元素类型==**" 不同时，**可省略调用 "插入函数" 时由于隐式类型转换而导致的==临时对象的构造和析构过程==**，故更有效率[^9]。 > [!info] emplace 置入函数的原理 > > `emplace` 系列方法基于 "**==完美转发==**" 实现，其将参数直接转发给**元素类型的 "==构造函数=="**， > 因此其接收的参数是 "**==元素类型构造函数所需的参数==**"，而后**直接在容器的存储空间中构造对象**。 > 使用示例： ```c++ vector<pair<int, string>> vec; vec.emplace_back(1, "example"); // 这里传入两个构造pair所需的"参数", 而不是{1, "pair"}这样的初值列 ``` <br> ### 置入函数的使用场景 > [!important] "`emplace` 置入函数" 适用于 "**==传入的实参类型==**" 与 "**==容器内元素类型==**" 不同而触发 "==**隐式类型转换**==" 的场景，在此情况下优于 **插入函数**。 > > 注：如果是将 `T` 类型对象添加到 `container<T>` 容器中，**置入函数与插入函数的==效率应该是无差异的==** 。 说明示意： ```cpp vector<string> vec; // 容器所存元素类型是string, 而传递实参是const char*类型. // 如果调用`push_back`插入, 则过程为: // 1) 调用string以`const char*`为形参的构造函数, 创建一个临时string对象. (因为push_back接收string引用, 故这里触发隐式类型转换) // 2) 调用string的"移动构造函数", 将临时对象"移动"到容器中. // 3) 调用string的析构函数, 析构临时对象. vec.push_back("example"); // 如果调用`emplace_back`, 则过程为: // - 调用string以`const char*`为形参的构造函数, 直接在容器内部构造对象. // 由此, 省略了一次对临时量的 "移动构造函数" 及 "析构函数" 的调用. vec.emplace_back("exmaple"); // ``` ### "置入函数" 与 "插入函数" 的实现示意 置入函数的实现示意： ```cpp template <typename T> template <typename... Args> void Container<T>::emplace_back(Args&&... args) { ... // 申请内存空间等其他操作 alloc_traits::construct(alloc, ptr, std::forward<Args>(args)...); // 在指定地址ptr上构造, 将args直接转发给构造函数. } ``` 插入函数的实现示意： ```cpp template <typename T> void Container<T>::push_back(const T&) { ... // 申请内存空间等其他操作 alloc_traits::construct(alloc, ptr, T); // 在指定地址ptr上构造, 调用类型T的拷贝构造函数. } template <typename T> void Container<T>::push_back(T&&) { ... // 申请内存空间等其他操作 alloc_traits::construct(alloc, ptr, std::move(T)); // 在指定地址ptr上构造, 调用类型T的移动构造函数. } ``` <br><br> # 参考资料 - 《C++ Primer》 - 第 9 章，顺序容器 - 《C++ 标准库》 # Footnotes [^1]: 《C++ Primer》(P97) [^2]: 《C++ Primer》(P315) [^3]: 《C++ Primer》（P318） [^4]: 《C++ Primer》(P320-P328) [^5]: 《C++ Primer》(P329-P330) [^6]: 《C++ Primer》P365 [^7]: 《C++ Primer》P366 [^8]: 《C++ Primer》P359 [^9]: 《Effective Modern C++》Item42 [^10]: 《C++ Primer》P380 [^11]: 《C++ Primer》P636