From 1465da6224fbb75fa9518b149ffbbaa12851a405 Mon Sep 17 00:00:00 2001
From: Jacob Zhong <cmpute@qq.com>
Date: Wed, 4 Sep 2019 16:04:57 -0400
Subject: [PATCH] added docs for stl list

---
 docs/lang/csl/algorithm.md          |  1 +
 docs/lang/csl/sequence-container.md | 39 +++++++++++++++++++++++++++++--------
 2 files changed, 32 insertions(+), 8 deletions(-)

diff --git a/docs/lang/csl/algorithm.md b/docs/lang/csl/algorithm.md
index 4b4bb2ef..2aa51b7b 100644
--- a/docs/lang/csl/algorithm.md
+++ b/docs/lang/csl/algorithm.md
@@ -4,5 +4,6 @@ STL 提供了大约 100 个实现算法的模版函数，基本都包含在 `<al
 
 -    `sort` ：排序。 `sort(v.begin(), v.end(), cmp)` 或 `sort(a + begin, a + end, cmp)` ，其中 `end` 是排序的数组最后一个元素的后一位， `cmp` 为自定义的比较函数。
 -    `reverse` ：翻转数组、字符串。 `reverse(v.begin(), v.end())` 或 `reverse(a + begin, a + end)` 。
+-    `unique` : 去除容器中相邻的重复元素。`unique(v.begin(), v.end())` 或 `unique(a + begin, a + end)` 。与 `sort` 结合使用可以实现完整容器去重。
 -    `nth_element` ：按指定范围进行分类，即找出序列中第 $n$ 大的元素，使其左边均为小于它的数，右边均为大于它的数。 `nth_element(v.begin(), v.begin() + mid, v.end(), cmp)` 或 `nth_element(a + begin, a + begin + mid, a + end, cmp)` 。复杂度 $O(n)$ 。
 -    `random_shuffle` ：随机地打乱数组。 `random_shuffle(v.begin(), v.end())` 或 `random_shuffle(v + begin, v + end)` 。
diff --git a/docs/lang/csl/sequence-container.md b/docs/lang/csl/sequence-container.md
index 23bd1307..2502cc85 100644
--- a/docs/lang/csl/sequence-container.md
+++ b/docs/lang/csl/sequence-container.md
@@ -79,11 +79,11 @@ vector<int> v6(std::move(v2));  // 或者 v6 = std::move(v2);
 
 1.   `at()` 
 
-     `v.at(pos)` 返回 vector 中下标为 `pos` 的引用。如果数组越界抛出 `std::out_of_range` 类型的异常。
+     `v.at(pos)` 返回容器中下标为 `pos` 的引用。如果数组越界抛出 `std::out_of_range` 类型的异常。
 
 2.   `operator[]` 
 
-     `v[pos]` 返回 vector 中下标为 `pos` 的引用。不执行越界检查。
+     `v[pos]` 返回容器中下标为 `pos` 的引用。不执行越界检查。
 
 3.   `front()` 
 
@@ -147,7 +147,7 @@ vector 提供了如下几种 [迭代器](./iterator.md)
 
 ###  `vector` 的实现细节
 
- `vector` 的底层其实仍然是定长数组，它能够实现动态扩容的原因是增加了避免数量溢出的操作。首先需要指明的是 `vector` 中元素的数量（长度） $n$ 与它已分配内存最多能包含元素的数量（容量） $N$ 是不一致的， `vector` 会分开存储这两个量。当向 `vector` 中添加元素时，如发现 $n>N$ ，那么容器会分配一个尺寸为 $2N$ 的数组，然后将旧数据从原本的位置拷贝到新的数组中。尽管这个操作是 $O(n)$ 的，但是可以证明其分摊复杂度（即渐进复杂度）为 $O(1)$ 。而在末尾删除元素和访问元素则都仍然是 $O(1)$ 的开销。
+ `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>` 
@@ -184,7 +184,7 @@ for (int i = 0; i != arr.size(); ++i) cout << arr[i] << " ";
 
 ###  `deque` 的使用方法
 
-以下介绍常用用法，详细内容 [请参见 C++ 文档](https://zh.cppreference.com/w/cpp/container/deque) 。
+以下介绍常用用法，详细内容 [请参见 C++ 文档](https://zh.cppreference.com/w/cpp/container/deque) 。`deque` 的迭代器函数与 `vector` 相同，因此不作详细介绍。
 
 #### 构造函数
 
@@ -209,8 +209,8 @@ deque<int> v5(std::move(v2));
 
 与 `vector` 一致，但无法访问底层内存。其高效的元素访问速度可参考实现细节部分。
 
--    `at()` 返回 vector 中指定位置元素的引用，执行越界检查， **常数复杂度** 。
--    `operator[]` 返回 vector 中指定位置元素的引用。不执行越界检查， **常数复杂度** 。
+-    `at()` 返回容器中指定位置元素的引用，执行越界检查， **常数复杂度** 。
+-    `operator[]` 返回容器中指定位置元素的引用。不执行越界检查， **常数复杂度** 。
 -    `front()` 返回首元素的引用。
 -    `back()` 返回末尾元素的引用。
 
@@ -237,8 +237,31 @@ deque<int> v5(std::move(v2));
 
 ###  `deque` 的实现细节
 
- `deque` 的底层实现是多个不连续的缓冲区，而缓冲区中的内存是连续的。而每个缓冲区还会记录首指针和尾指针，用来标记有效数据的区间。当一个缓冲区填满之后便会在之前或者之后分配新的缓冲区来存储更多的数据。更详细的说明可以参考 [STL 源码剖析——deque 的实现原理和使用方法详解](https://blog.csdn.net/baidu_28312631/article/details/48000123) 
+ `deque` 通常的底层实现是多个不连续的缓冲区，而缓冲区中的内存是连续的。而每个缓冲区还会记录首指针和尾指针，用来标记有效数据的区间。当一个缓冲区填满之后便会在之前或者之后分配新的缓冲区来存储更多的数据。更详细的说明可以参考 [STL 源码剖析——deque 的实现原理和使用方法详解](https://blog.csdn.net/baidu_28312631/article/details/48000123) 。
 
 ##  `list` 
 
-##  `forward_list` 
+ `std::list` 是 STL 提供的 [双向链表](../../ds/linked-list.md) 数据结构。能够提供线性复杂度的随机访问，以及常数复杂度的插入和删除。
+
+###  `list` 的使用方法
+
+`list` 的使用方法与 `deque` 基本相同，但是增删操作和访问的复杂度不同。详细内容 [请参见 C++ 文档](https://zh.cppreference.com/w/cpp/container/list) 。`list` 的迭代器、长度、元素增删及修改相关的函数与 `deque` 相同，因此不作详细介绍。
+
+#### 元素访问
+
+由于 `list` 的实现是链表，因此它不提供随机访问的接口。若需要访问中间元素，则需要使用迭代器。
+
+-    `front()` 返回首元素的引用。
+-    `back()` 返回末尾元素的引用。
+
+#### 操作
+
+`list` 类型还提供了一些针对其特性实现的 STL 算法函数。由于这些算法需要[随机访问迭代器](./iterator.md)，因此`list`提供了特别的实现以便于使用。这些算法有`splice()`、`remove()`、`sort()`、`unique()`、`merge()`等。
+
+##  `forward_list` （C++ 11）
+
+ `std::forward_list` 是 STL 提供的 [单向链表](../../ds/linked-list.md) 数据结构，相比于 `std::list` 减小了空间开销。
+
+###  `forward_list` 的使用方法
+
+`forward_list` 的使用方法与 `list` 几乎一致，但是迭代器只有单向的，因此其具体用法不作详细介绍。详细内容 [请参见 C++ 文档](https://zh.cppreference.com/w/cpp/container/forward_list)
-- 
2.11.0