From ac11c20721b4430e2d2fa89e72e3146ab991bee0 Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Wed, 4 Sep 2019 00:19:23 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/lang/csl/container.md | 6 ++-- docs/lang/csl/sequence-container.md | 67 +++++++++++++++++++------------------ docs/lang/new.md | 4 +-- 3 files changed, 39 insertions(+), 38 deletions(-) diff --git a/docs/lang/csl/container.md b/docs/lang/csl/container.md index 7b28bd6c..9711a1ee 100644 --- a/docs/lang/csl/container.md +++ b/docs/lang/csl/container.md @@ -12,13 +12,13 @@ ### 关联式容器 -- **集合** ( `set` ) 用以存储**互异**元素并快速判断存在性的容器。其实现是由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种比较元素是否相等的谓词进行排列。 +- **集合** ( `set` ) 用以存储 **互异** 元素并快速判断存在性的容器。其实现是由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种比较元素是否相等的谓词进行排列。 - **多重集合** ( `multiset` ) 用以存储元素并快速判断存在性的容器。允许存在相等的元素。 - **映射** ( `map` ) 由 {键，值} 对组成的集合，以某种比较键是否相等的谓词进行排列。 - **多重映射** ( `multimap` ) 由 {键，值} 对组成的多重集合，亦即允许键有相等情况的映射。 -???+note 什么是谓词（ [**Predicate**](https://en.wikipedia.org/wiki/Predicate_(mathematical_logic)) ）？ - 谓词就是返回值为真或者假的函数。STL容器中经常会使用到谓词，用于模板参数。 +???+note 什么是谓词（ [ **Predicate** ](https://en.wikipedia.org/wiki/Predicate_(mathematical_logic)) ）？ + 谓词就是返回值为真或者假的函数。STL 容器中经常会使用到谓词，用于模板参数。 ### 无序（关联式）容器 diff --git a/docs/lang/csl/sequence-container.md b/docs/lang/csl/sequence-container.md index e0d05a59..5162c46a 100644 --- a/docs/lang/csl/sequence-container.md +++ b/docs/lang/csl/sequence-container.md @@ -2,31 +2,31 @@ author: MingqiHuang, Xeonacid, greyqz, i-Yirannn ## `vector` -`std::vector` 是 STL 提供的**内存连续的**、**可变长度**的数组（亦称列表）数据结构。 + `std::vector` 是 STL 提供的 **内存连续的** 、 **可变长度** 的数组（亦称列表）数据结构。 ### 为什么要用 `vector` -作为 OIer，对程序效率的追求远比对工程级别的稳定性要高得多，而 `vector` 由于其对内存的动态处理，时间效率在部分情况下低于静态数组，并且在OJ服务器不一定开全优化的情况下更加糟糕。所以在正常存储数据的时候，通常不选择 `vector`。下面给出几个 `vector` 优秀的特性，在需要用到这些特性的情况下，`vector` 能给我们带来很大的帮助。 +作为 OIer，对程序效率的追求远比对工程级别的稳定性要高得多，而 `vector` 由于其对内存的动态处理，时间效率在部分情况下低于静态数组，并且在 OJ 服务器不一定开全优化的情况下更加糟糕。所以在正常存储数据的时候，通常不选择 `vector` 。下面给出几个 `vector` 优秀的特性，在需要用到这些特性的情况下， `vector` 能给我们带来很大的帮助。 #### `vector` 可以动态分配内存 -很多时候我们不能提前开好那么大的空间（eg：预处理 1~n 中所有数的约数）。尽管我们能知道数据总量在空间允许的级别，但是单份数据还可能非常大，这种时候我们就需要 `vector` 来把内存占用量控制在合适的范围内。`vector` 还支持动态扩容，在内存非常紧张的时候这个特性就能派上用场了。 +很多时候我们不能提前开好那么大的空间（eg：预处理 1~n 中所有数的约数）。尽管我们能知道数据总量在空间允许的级别，但是单份数据还可能非常大，这种时候我们就需要 `vector` 来把内存占用量控制在合适的范围内。 `vector` 还支持动态扩容，在内存非常紧张的时候这个特性就能派上用场了。 #### `vector` 重写了比较运算符及赋值运算符 -`vector` 重载了六个比较运算符，以字典序实现，这使得我们可以方便的判断两个容器是否相等（复杂度与容器大小成线性关系）。例如可以利用 `vector` 实现字符串比较（当然，还是用 `std::string` 会更快更方便）。另外 `vector` 也重载了赋值运算符，使得数组拷贝更加方便。 + `vector` 重载了六个比较运算符，以字典序实现，这使得我们可以方便的判断两个容器是否相等（复杂度与容器大小成线性关系）。例如可以利用 `vector` 实现字符串比较（当然，还是用 `std::string` 会更快更方便）。另外 `vector` 也重载了赋值运算符，使得数组拷贝更加方便。 #### `vector` 便利的初始化 -由于 `vector` 重载了 `=` 运算符，所以我们可以方便的初始化。此外从 C++11 起 `vector` 还支持[列表初始化](https://zh.cppreference.com/w/cpp/language/list_initialization)，例如`vector data {1, 2, 3};`。 +由于 `vector` 重载了 `=` 运算符，所以我们可以方便的初始化。此外从 C++11 起 `vector` 还支持 [列表初始化](https://zh.cppreference.com/w/cpp/language/list_initialization) ，例如 `vector data {1, 2, 3};` 。 #### `vector` 支持自定义数据和空间配置器 -`vector` 是模板类型，可以通过模板参数来实现自定义类型的数组。例如如果要实现大数数组，那么可以先将大数封装为一个类，然后将其作为模板参数即可实现一个大数数组。而自定义空间配置器很少会被用到，通过自定义的空间配置器可以将自定义数据结构进行补位（ Padding ），以实现硬件加速。 + `vector` 是模板类型，可以通过模板参数来实现自定义类型的数组。例如如果要实现大数数组，那么可以先将大数封装为一个类，然后将其作为模板参数即可实现一个大数数组。而自定义空间配置器很少会被用到，通过自定义的空间配置器可以将自定义数据结构进行补位（Padding），以实现硬件加速。 ### `vector` 的使用方法 -#### 构造函数 +#### 构造函数 参见如下代码（假设你已经 `using` 了 `std` 命名空间相关类型）： @@ -47,7 +47,7 @@ vector v4(v2); // 6. 创建一个v4的拷贝vector v5，其内容是{v4[1], v4[2]}; 线性复杂度 vector v5(v4.begin() + 1, v4.begin() + 3); // 7. 移动v2到新创建的vector v6，不发生拷贝; 常数复杂度 -vector v6(std::move(v2)); // 或者 v7 = std::move(v2); +vector v6(std::move(v2)); // 或者 v7 = std::move(v2); ``` ??? note "测试代码" @@ -75,33 +75,33 @@ vector v6(std::move(v2)); // 或者 v7 = std::move(v2); 可以利用上述的方法构造一个 `vector` ，足够我们使用了。 -#### 元素访问 +#### 元素访问 -`vector` 提供了如下几种方法进行元素访问 + `vector` 提供了如下几种方法进行元素访问 1. `at()` - `v.at(pos)` 返回 vector 中下标为 `pos` 的引用。如果数组越界抛出 `std::out_of_range` 类型的异常。 + `v.at(pos)` 返回 vector 中下标为 `pos` 的引用。如果数组越界抛出 `std::out_of_range` 类型的异常。 2. `operator[]` - `v[pos]` 返回 vector 中下标为 `pos` 的引用。不执行越界检查。 + `v[pos]` 返回 vector 中下标为 `pos` 的引用。不执行越界检查。 3. `front()` - `v.front()` 返回首元素的引用。 + `v.front()` 返回首元素的引用。 4. `back()` - `v.back()` 返回末尾元素的引用。 + `v.back()` 返回末尾元素的引用。 5. `data()` - `v.data()` 返回指向数组第一个元素的指针。 + `v.data()` 返回指向数组第一个元素的指针。 -#### 迭代器 +#### 迭代器 -vector 提供了如下几种[迭代器](./iterator.md) +vector 提供了如下几种 [迭代器](./iterator.md) 1. `begin()/cbegin()` @@ -123,64 +123,65 @@ vector 提供了如下几种[迭代器](./iterator.md) #### 长度和容量 -`vector` 有以下几个与容器数量相关的函数。注意， `vector` 的长度指有效元素数量，而容量指其实际分配的内存长度，相关细节请参见后文的实现细节介绍。 + `vector` 有以下几个与容器数量相关的函数。注意， `vector` 的长度指有效元素数量，而容量指其实际分配的内存长度，相关细节请参见后文的实现细节介绍。 与长度相关： + - `empty()` 返回一个 `bool` 值，即 `v.begin() == v.end()` ， `true` 为空， `false` 为非空。 - `size()` 返回容器长度（元素数量），即 `std::distance(v.begin(), v.end())` 。 - `resize()` 改变 `vector` 的长度，多退少补。补充元素可以由参数指定。 - `max_size()` 返回容器的最大可能长度。 与容量相关： + - `reserve()` 使得 `vector` 预留一定的内存空间，避免不必要的内存拷贝。 - `capacity()` 返回容器的容量，即不发生拷贝的情况下容器的长度上限。 - `shrink_to_fit()` 使得 `vector` 的容量与长度一致，多退但不会少。 -### 元素增删 +### 元素增删 - `clear()` 清除所有元素 - `insert()` 支持在某个迭代器位置插入元素、可以插入多个 **此操作是与 `pos` 距离末尾长度成线性而非常数的** - `erase()` 删除某个迭代器或者区间的元素，返回最后被删除的迭代器。 -- `push_back()` 在末尾插入一个元素，渐进复杂度为**常数**，最坏为线性复杂度。 +- `push_back()` 在末尾插入一个元素，渐进复杂度为 **常数** ，最坏为线性复杂度。 - `pop_back()` 删除末尾元素。 - `swap()` 与另一个容器进行交换，此操作是 **常数复杂度** 而非线性的。 ### `vector` 的实现细节 -`vector`的底层其实仍然是定长数组，它能够实现动态扩容的原因是增加了避免数量溢出的操作。首先需要指明的是 `vector` 中元素的数量（长度） $n$ 与它已分配内存最多能包含元素的数量（容量） $N$ 是不一致的， `vector` 会分开存储这两个量。当向 `vector` 中添加元素时，如发现 $n>N$ ，那么容器会分配一个尺寸为 $2N$ 的数组，然后将旧数据从原本的位置拷贝到新的数组中。尽管这个操作是 $O(n)$ 的，但是可以证明其分摊复杂度（即渐进复杂度）为 $O(1)$。而在末尾删除元素和访问元素则都仍然是 $O(1)$ 的开销。 -因此，只要对 `vector` 的尺寸估计得当并善用 `reserve()` 和 `shrink_to_fit()` 函数（ C++ 11 ），就能使得 `vector` 的效率与定长数组不会有太大差距。 + `vector` 的底层其实仍然是定长数组，它能够实现动态扩容的原因是增加了避免数量溢出的操作。首先需要指明的是 `vector` 中元素的数量（长度） $n$ 与它已分配内存最多能包含元素的数量（容量） $N$ 是不一致的， `vector` 会分开存储这两个量。当向 `vector` 中添加元素时，如发现 $n>N$ ，那么容器会分配一个尺寸为 $2N$ 的数组，然后将旧数据从原本的位置拷贝到新的数组中。尽管这个操作是 $O(n)$ 的，但是可以证明其分摊复杂度（即渐进复杂度）为 $O(1)$ 。而在末尾删除元素和访问元素则都仍然是 $O(1)$ 的开销。 +因此，只要对 `vector` 的尺寸估计得当并善用 `reserve()` 和 `shrink_to_fit()` 函数（C++ 11），就能使得 `vector` 的效率与定长数组不会有太大差距。 ### `vector` -标准库特别提供了对 `bool` 的 `vector` 实例化，每个“ `bool` ”只占 1 bit，且支持动态增长。但是其 `operator[]` 的返回值的类型不是 `bool&` 而是 `vector::reference` 。因此，使用 `vector` 使需谨慎，可以考虑使用 `deque` 或 `vector` 替代。而如果你需要节省空间，请直接使用 [`bitset`](./bitset.md) 。 +标准库特别提供了对 `bool` 的 `vector` 实例化，每个“ `bool` ”只占 1 bit，且支持动态增长。但是其 `operator[]` 的返回值的类型不是 `bool&` 而是 `vector::reference` 。因此，使用 `vector` 使需谨慎，可以考虑使用 `deque` 或 `vector` 替代。而如果你需要节省空间，请直接使用 [ `bitset` ](./bitset.md) 。 ## `array` -`std::array` 是 STL 提供的**内存连续的**、**固定长度**的数组数据结构。 + `std::array` 是 STL 提供的 **内存连续的** 、 **固定长度** 的数组数据结构。 ### 为什么要用 `array` -`array` 实际上是 STL 对数组的封装。它相比 `vector` 牺牲了动态扩容的特性，但是换来了与原生数组几乎一致的性能（在开满优化的前提下）。因此如果能使用 C++ 11 特性的情况下，能够使用原生数组的地方几乎都可以直接把定长数组都换成 `array`，而动态分配的数组可以替换为 `vector`。 + `array` 实际上是 STL 对数组的封装。它相比 `vector` 牺牲了动态扩容的特性，但是换来了与原生数组几乎一致的性能（在开满优化的前提下）。因此如果能使用 C++ 11 特性的情况下，能够使用原生数组的地方几乎都可以直接把定长数组都换成 `array` ，而动态分配的数组可以替换为 `vector` 。 ### `array` 的使用方法 -`array` 的使用方法与 `vector` 高度相似，仅有声明方式与 `vector` 不同，以及没有动态扩容的功能（如 `push_back` ）。这里只给出一段例子。 + `array` 的使用方法与 `vector` 高度相似，仅有声明方式与 `vector` 不同，以及没有动态扩容的功能（如 `push_back` ）。这里只给出一段例子。 ```cpp // 1. 创建空array，长度为3; 常数复杂度 std::array v0; // 2. 用指定常数创建array; 常数复杂度 -std::array v1 {1, 2, 3}; +std::array v1{1, 2, 3}; -v0.fill(1); // 填充数组 +v0.fill(1); // 填充数组 // 访问数组 -for ( int i = 0; i != arr.size() ; ++i ) - cout << arr[i] << " "; +for (int i = 0; i != arr.size(); ++i) cout << arr[i] << " "; ``` -## `deque` +## `deque` -## `list` +## `list` -## `forward_list` +## `forward_list` diff --git a/docs/lang/new.md b/docs/lang/new.md index 74c0ad18..12581007 100644 --- a/docs/lang/new.md +++ b/docs/lang/new.md @@ -250,7 +250,7 @@ tupB.swap(tupA); | `make_tuple` | 创建一个 `tuple` 对象，其类型根据各实参类型定义 | | `std::get` | 元组式访问指定的元素 | | `operator==` 等 | 按字典顺序比较 `tuple` 中的值 | -| `std::swap` | 实例化 `std::swap` 算法 | +| `std::swap` | 实例化 `std::swap` 算法 | 例子 @@ -325,7 +325,7 @@ int main() { | --------------- | ------------------- | | `operator==` 等 | 按照字典序比较 `array` 中的值 | | `std::get` | 访问 `array` 的一个元素 | -| `std::swap` | 实例化 `std::swap` 算法 | +| `std::swap` | 实例化 `std::swap` 算法 | 例子 -- 2.11.0