From f17f0a4044ac01cb00e69f64811047109cdff82a Mon Sep 17 00:00:00 2001
From: Jacob Zhong <cmpute@qq.com>
Date: Wed, 4 Sep 2019 12:55:11 -0400
Subject: [PATCH] Add docs for deque

---
 docs/ds/queue.md                    |  2 +-
 docs/lang/csl/sequence-container.md | 85 +++++++++++++++++++++++++++++++------
 2 files changed, 74 insertions(+), 13 deletions(-)

diff --git a/docs/ds/queue.md b/docs/ds/queue.md
index 2537db38..92196da7 100644
--- a/docs/ds/queue.md
+++ b/docs/ds/queue.md
@@ -54,7 +54,7 @@ int q[SIZE], ql = 1, qr;
 
 有人问这个东西有什么用吗？参见下面这道题。这道题顺便可以给大家一个 **双栈模拟双端队列** 的方法。
 
-### 例题
+## 例题
 
 LOJ6515 贪玩蓝月
 
diff --git a/docs/lang/csl/sequence-container.md b/docs/lang/csl/sequence-container.md
index 230290ac..4b2b3eb1 100644
--- a/docs/lang/csl/sequence-container.md
+++ b/docs/lang/csl/sequence-container.md
@@ -2,9 +2,9 @@ author: MingqiHuang, Xeonacid, greyqz, i-Yirannn
 
 ##  `vector` 
 
- `std::vector` 是 STL 提供的 **内存连续的** 、 **可变长度** 的数组（亦称列表）数据结构。
+ `std::vector` 是 STL 提供的 **内存连续的** 、 **可变长度** 的数组（亦称列表）数据结构。能够提供线性复杂度的插入和删除，以及常数复杂度的随机访问。
 
-### 为什么要用 `vector` 
+### 为什么要使用 `vector` 
 
 作为 OIer，对程序效率的追求远比对工程级别的稳定性要高得多，而 `vector` 由于其对内存的动态处理，时间效率在部分情况下低于静态数组，并且在 OJ 服务器不一定开全优化的情况下更加糟糕。所以在正常存储数据的时候，通常不选择 `vector` 。下面给出几个 `vector` 优秀的特性，在需要用到这些特性的情况下， `vector` 能给我们带来很大的帮助。
 
@@ -22,9 +22,11 @@ author: MingqiHuang, Xeonacid, greyqz, i-Yirannn
 
 ###  `vector` 的使用方法
 
+以下介绍常用用法，详细内容[请参见 C++ 文档](https://zh.cppreference.com/w/cpp/container/vector)。
+
 #### 构造函数
 
-参见如下代码（假设你已经 `using` 了 `std` 命名空间相关类型）：
+用例参见如下代码（假设你已经 `using` 了 `std` 命名空间相关类型）：
 
 ```cpp
 // 1. 创建空vector; 常数复杂度
@@ -42,7 +44,7 @@ vector<int> v3(3, 1, v2.get_allocator());
 vector<int> v4(v2);
 // 6. 创建一个v4的拷贝vector v5，其内容是{v4[1], v4[2]}; 线性复杂度
 vector<int> v5(v4.begin() + 1, v4.begin() + 3);
-// 7. 移动v2到新创建的vector v6，不发生拷贝; 常数复杂度
+// 7. 移动v2到新创建的vector v6，不发生拷贝; 常数复杂度; 需要 C++ 11
 vector<int> v6(std::move(v2));  // 或者 v6 = std::move(v2);
 ```
 
@@ -119,7 +121,7 @@ vector 提供了如下几种 [迭代器](./iterator.md)
 
 #### 长度和容量
 
- `vector` 有以下几个与容器长度和容量相关的函数。注意， `vector` 的长度指有效元素数量，而容量指其实际分配的内存长度，相关细节请参见后文的实现细节介绍。
+ `vector` 有以下几个与容器长度和容量相关的函数。注意， `vector` 的长度( size )指有效元素数量，而容量( capacity )指其实际分配的内存长度，相关细节请参见后文的实现细节介绍。
 
 **与长度相关**：
 
@@ -134,13 +136,13 @@ vector 提供了如下几种 [迭代器](./iterator.md)
 -    `capacity()` 返回容器的容量，即不发生拷贝的情况下容器的长度上限。
 -    `shrink_to_fit()` 使得 `vector` 的容量与长度一致，多退但不会少。
 
-### 元素增删
+### 元素增删及修改
 
 -    `clear()` 清除所有元素
--    `insert()` 支持在某个迭代器位置插入元素、可以插入多个 **此操作是与 `pos` 距离末尾长度成线性而非常数的** 
--    `erase()` 删除某个迭代器或者区间的元素，返回最后被删除的迭代器。
+-    `insert()` 支持在某个迭代器位置插入元素、可以插入多个。**复杂度与 `pos` 距离末尾长度成线性而非常数的** 
+-    `erase()` 删除某个迭代器或者区间的元素，返回最后被删除的迭代器。复杂度与 `insert` 一致。
 -    `push_back()` 在末尾插入一个元素，均摊复杂度为 **常数** ，最坏为线性复杂度。
--    `pop_back()` 删除末尾元素。
+-    `pop_back()` 删除末尾元素，常数复杂度。
 -    `swap()` 与另一个容器进行交换，此操作是 **常数复杂度** 而非线性的。
 
 ###  `vector` 的实现细节
@@ -152,9 +154,9 @@ vector 提供了如下几种 [迭代器](./iterator.md)
 
 标准库特别提供了对 `bool` 的 `vector` 特化，每个“ `bool` ”只占 1 bit，且支持动态增长。但是其 `operator[]` 的返回值的类型不是 `bool&` 而是 `vector<bool>::reference` 。因此，使用 `vector<bool>` 使需谨慎，可以考虑使用 `deque<bool>` 或 `vector<char>` 替代。而如果你需要节省空间，请直接使用 [ `bitset` ](./bitset.md) 。
 
-##  `array` 
+##  `array` ( C++ 11 )
 
- `std::array` 是 STL 提供的 **内存连续的** 、 **固定长度** 的数组数据结构。
+ `std::array` 是 STL 提供的 **内存连续的** 、 **固定长度** 的数组数据结构。其本质是对原生数组的直接封装。
 
 ### 为什么要用 `array` 
 
@@ -162,7 +164,7 @@ vector 提供了如下几种 [迭代器](./iterator.md)
 
 ###  `array` 的使用方法
 
- `array` 的使用方法与 `vector` 高度相似，仅有声明方式与 `vector` 不同，以及没有动态扩容的功能（如 `push_back` ）。这里只给出一段例子。
+ `array` 的使用方法与 `vector` 高度相似，仅有声明方式与 `vector` 不同，以及没有元素增删的能力（如 `push_back` ）。这里只给出一段例子，详细内容[请参见 C++ 文档](https://zh.cppreference.com/w/cpp/container/array)。
 
 ```cpp
 // 1. 创建空array，长度为3; 常数复杂度
@@ -178,6 +180,65 @@ for (int i = 0; i != arr.size(); ++i) cout << arr[i] << " ";
 
 ##  `deque` 
 
+ `std::deque` 是 STL 提供的[双端队列](../../ds/queue.md)数据结构。能够提供线性复杂度的插入和删除，以及常数复杂度的随机访问。
+
+### `deque` 的使用方法
+
+以下介绍常用用法，详细内容[请参见 C++ 文档](https://zh.cppreference.com/w/cpp/container/deque)。
+
+#### 构造函数
+
+参见如下代码（假设你已经 `using` 了 `std` 命名空间相关类型）：
+
+```cpp
+// 1. 定义一个int类型的空双端队列 v0
+deque<int> v0;
+// 2. 定义一个int类型的双端队列 v1，并设置初始大小为10; 线性复杂度
+deque<int> v1(10);
+// 3. 定义一个int类型的双端队列 v2，并初始化为10个1; 线性复杂度
+deque<int> v2(10, 1);
+// 4. 复制已有的双端队列 v1; 线性复杂度
+deque<int> v3(v1);
+// 5. 创建一个v2的拷贝deque v4，其内容是v4[0]至v4[2]; 线性复杂度
+deque<int> v4(v2.begin(), v2.begin()+3);
+// 6. 移动v2到新创建的deque v5，不发生拷贝; 常数复杂度; 需要 C++ 11
+deque<int> v5(std::move(v2));
+```
+
+#### 元素访问
+
+与 `vector` 一致，但无法访问底层内存。其高效的元素访问速度可参考实现细节部分。
+
+-   `at()` 返回 vector 中指定位置元素的引用，执行越界检查，**常数复杂度**。
+-   `operator[]` 返回 vector 中指定位置元素的引用。不执行越界检查，**常数复杂度**。
+-   `front()` 返回首元素的引用。
+-   `back()` 返回末尾元素的引用。
+
+#### 迭代器
+
+与 `vector` 一致。
+
+#### 长度
+
+与 `vector` 一致，但是没有 `reserve()` 和 `capacity()` 函数。（仍然有 `shrink_to_fit()` 函数）
+
+#### 元素增删及修改
+
+与 `vector` 一致，并额外有向队列头部增加元素的函数。
+
+-    `clear()` 清除所有元素
+-    `insert()` 支持在某个迭代器位置插入元素、可以插入多个。**复杂度与 `pos` 与两端距离较小者成线性**。
+-    `erase()` 删除某个迭代器或者区间的元素，返回最后被删除的迭代器。复杂度与 `insert` 一致。
+-    `push_front()` 在头部插入一个元素， **常数复杂度**。
+-    `pop_front()` 删除头部元素，**常数复杂度**。
+-    `push_back()` 在末尾插入一个元素， **常数复杂度**。
+-    `pop_back()` 删除末尾元素，**常数复杂度**。
+-    `swap()` 与另一个容器进行交换，此操作是 **常数复杂度** 而非线性的。
+
+###  `deque` 的实现细节
+
+ `deque` 的底层实现是多个不连续的缓冲区，而缓冲区中的内存是连续的。而每个缓冲区还会记录首指针和尾指针，用来标记有效数据的区间。当一个缓冲区填满之后便会在之前或者之后分配新的缓冲区来存储更多的数据。更详细的说明可以参考[STL源码剖析——deque的实现原理和使用方法详解](https://blog.csdn.net/baidu_28312631/article/details/48000123)
+
 ##  `list` 
 
 ##  `forward_list` 
-- 
2.11.0