======顺序容器======
C++ Primer 笔记 第九章\\
----
**容器**（//Container//）是 C++ 标准库提供的，用于存放**一系列指定类型对象**的数据结构。本章学习的**顺序容器**（//Sequencial Container//）指包含了以下特性的容器：
  * 元素按顺序添加进容器
  * 元素的添加顺序与其在容器里的位置一一对应

====顺序容器概述====
顺序容器主要按以下的两个方面来作出取舍：
  - 添加/删除元素的花销
  - 随机访问（非顺序访问）的花销
===顺序容器的特性===
根据不同存储的策略，不同的容器的特性也不同：
  * Vector & String 支持浮动的大小，但添加删除容器中间的元素会很慢
  * list / forward_list 支持快速添加删除元素，但舍弃了快速的随机访问。Forward_list 没有求 size 的操作。
  * Deque 支持快速随机访问。添删首尾元素快，中间元素慢
  * Array 是新标准的容器，不支持添删和改变容器大小。相较于 Build-in Aarray 更安全
{{ :cs:programming:cpp:cpp_primer:define_init_containers_1.svg?600 |}}
<WRAP center round tip 100%>
新标准下的 STL 容器比旧版本下的快上许多，在可以使用的地方尽可能的使用。
</WRAP>

===顺序容器的选择===
通常，选择顺序容器遵循以下的策略：
  - 如果没有特殊需要，**尽可能的选择** //vector//。
  - 如果有很多**小元素**，而且**空间**的 overhead 很重要，那么请**不要**使用 //list// or //forward_list//。
  - 如果容器要求大量的随机访问，使用 //vector// or //deque//。
  - 如果需要经常在容器**中部**进行添删操作，请选择 //list// ro //forward_list//。
  - 如果程序需要在容器**前后**进行添删操作，请选择 //deque//。
  - 如果程序需要在输入数据的时候向容器**中部**插入数据，而后需要**随机访问**的话：
    - 首先，看是否真的需要容器中部添加元素。如果而**只是**想队列**有序**，使用 //vector// + ''sort()'' 函数排序是个很好的选择。
    - 其次，如果必须要在容器中间添加元素，可以考虑在用 //list// 做写入的载体，完成写入以后再把 //list// 拷贝到 //vector// 中。
总的来说，牵涉到复合要求的情况下，优先**按主要操作的需求**来选择容器。
<WRAP center round tip 100%>
如果你并不确定使用哪种容器，那么使用 //iterator// 来对容器进行操作。//Iterator// 作为顺序容器的公共操作，无论是在 //vector// 或 //list// 上使用都很方便。
</WRAP>

====标准库容器概况====
STL 提供了一些泛型的操作供容器使用。总的来说：
  * 某些操作可以用到所有容器上。
  * 一些操作只能应用到顺序容器上，不能用于关联容器（//Associative Container//）和无序容器（//Unordered Container//）。
  * 还有一些操作只适用于一小部分容器。
<WRAP center round help 100%>
如果需要使用容器，只用包含名为容器名字的头文件就可以了。
</WRAP>

操作的详细分类如下表：
\\ \\ {{ :cs:programming:cpp:cpp_primer:container_operations.svg?600 |}}
{{ :cs:programming:cpp:cpp_primer:define_init_containers_2.svg?600 |}} \\ \\
总的来说，**容器都是类模板**（//Class templates//），因此需要特别指定**元素的类型**：
<code cpp>
list<Sales_data> // list that holds Sales_data objects
deque<double> // deque that holds doubles
</code>
===容器对保存类型的限制===
总的来说，基本所有的类型的对象都可以被顺序容器保存，容器的元素甚至可以是容器：
<code cpp>
vector<vector<int>> vec_vi; // vector of vectors
vector<vector<int> > vec_vi; //old compiler requires a spece bewteen two angle bracket
</code>
但某些容器的操作会受到元素类型的限制。比如依靠默认初始化的初始化方法不能用于没有默认初始化的对象：
<code cpp>
// assume noDefault is a type without a default constructor
vector<noDefault> v1(10, init); // ok: element initializer supplied
vector<noDefault> v2(10); // error: must supply an element initializer
</code>

===迭代器===
  * 当应用于容器的时候，迭代器的操作是通用的
  * 例外是 //Forward list//, 不能使用**自减操作**
  * 以下的迭代器运算只能用于 //string//,//vector//, //deque//, //array//。
    * ''iter ± n'' / ''iter ±= n'' 
    * ''iter1 - iter2'' 
    * ''>, >=, <, <='' 

==迭代器的范围==
迭代器的范围使用一对迭代器来表示的；''begin'' 指向第一个元素，''end'' 另外一个指向最后一个元素的后一位。总的说来，迭代器的范围可以用一个左闭右开的区间（//Left-inclusive Interval//）来表示：$$[begin, end)$$
两点要求：
  * 这两个迭代器必须指向同一个容器
  * ''end'' 可以等于 ''begin''，但是不能在 ''begin'' 之前。
==一些使用上述概念的假定==
  * begin = end：容器为空
  * begin != end：容器不为空，begin 指向第一个元素
  * begin 可以通过自增最后与 end 相等。
遵循上述假定而写出来的循环是安全的：
<code cpp>
while (begin != end) {
	*begin = val;
	++begin;
}
</code>
==使用容器类型成员==
前面介绍过几种容器的成员类型，其中：
  * 大多数 iterator 都有自己的 reverse iterator
  * 这些类型实际上都是 type alias
如果要显式的指定容器的成员类型：
<code cpp>
container type<element type>::member_name;
//e.g.
vector<int>::difference_type count;
</code>
''::'' 指我们希望使用 iterator 成员及 vector<int> 中定义的 difference_type.
===容器成员 begin & end===
容器提供了两个成员函数 begin / end ，用于建立迭代的范围。同时提供的还有他们的 const / reverse 版本：
  * c 开头的是 const 版本，比如 //cbegin()//
  * r 开头的是 reverse 版本， 比如 //rbegin()//
没有以 c 开头的版本均存在**函数重载**：
  * 一个版本接收 const 对象，返回 //const_iterator//
  * 另外一个版本接收 non-const 对象，返回 //iterator//
C++ 11 中提供了 auto 关键字，允许编译器对迭代器的类型进行推断：
<code cpp>
auto it7 = a.begin(); // const_iterator only if a is const
auto it8 = a.cbegin(); // it8 is const_iterator
</code>

===初始化 / 定义容器===
除 array 以外，基本上所有的容器都拥有两个构造函数：
  * 默认的构造函数，创建空的容器
  * 带 size / 初始值的构造函数

==容器的拷贝初始化==
容器的拷贝初始化分为两种：
  * **直接拷贝**：要求容器与元素的**类型必须一致**
  * **迭代器拷贝**：对容器的类型没有要求。允许使用存在隐式转换的元素进行初始化
<code cpp>
// each container has three elements, initialized from the given initializers
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};

list<string> list2(authors); // ok: types match
deque<string> authList(authors); // error: container types don't match
vector<string> words(articles); // error: element types must match

// ok: converts const char* elements to string
forward_list<string> words(articles.begin(), articles.end());
</code>
鉴于迭代器初始化是通过指定范围实现的，使用迭代器拷贝可以初始化源容器的子集：
<code cpp>
// copies up to but not including the element denoted by it
deque<string> authList(authors.begin(), it);
</code>
==容器的列表初始化==
C++ 11 的新标准允许列表初始化容器：
<code cpp>
list<string> authors = {"Milton", "Shakespeare", "Austen"};
</code>
该方法在显式指定元素的同时，也隐含了容器的 size 信息。
==指定大小的初始化==
**顺序容器** 可以通过指定 size 和 默认值 来进行初始化。初始化会得到与 size 相同数量的元素，每个元素的值都是初始值：
<code cpp>
list<string> svec(10, "hi!"); // ten strings; each element is "hi!"
</code>
如果不指定初始值，则初始值会进行**值初始化**：
<code cpp>
forward_list<int> ivec(10); // ten elements, each initialized to 0
deque<string> svec(10); // ten elements, each an empty string
</code>
需要注意的是，这种初始方法要求元素是 build-in tpye，或者拥有**默认构造函数**。
<WRAP center round info 100%>
该初始化方法**只**适用于**顺序容器**，不支持关系容器。
</WRAP>

==标准库 array 类型==
和 build-in array 相同，STL array 也是 //Fixed-size// 的类型。因此定义 array 需要同时指定**大小**和**类型**：
<code cpp >
array<int, 10>; // array that holds 10 ints
array<int>::size_type i; // error, array<int> is not a type.
</code>
<color #666>//**为什么 array 不能使用指定 size 的容器构造函数？**//</color> \\ \\ 
因为大小是 //array// 类型的一部分。指定 size 的容器构造函数会隐式或者显式的决定容器的大小；允许用户决定 array 的大小可能会有很多潜在的问题。\\ \\ 

 <color #666>//**array 的特性带来了什么影响？**//</color> \\ \\ 
//array// 的固定大小导致其初始化会受到一些限制：
  * //array// 的默认初始化并不会创造一个空的容器。
  * 默认初始化中，元素个数与 array 的 size 相同，所有元素都将进行**默认初始化**。
  * 如果初始化元素个数小于 array size, 那没有对应初始值的元素会进行**值初始化**。
<code cpp>
array<int, 10> ia1; // ten default-initialized ints
array<int, 10> ia2 = {0,1,2,3,4,5,6,7,8,9}; // list initialization
array<int, 10> ia3 = {42}; // ia3[0] is 42, remaining elements are 0
</code>

<color #666>//**STL array 与 built-in array 的区别？**//</color> \\ \\ 
STL //array// 可以进行**直接拷贝和赋值**，只要 //size// 和 //type// 都匹配即可：
<code cpp>
int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs; // error: no copy or assignment for built-in arrays
array<int, 10> digits = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> copy = digits; // ok: so long as array types match
</code>
===赋值与 swap===
容器的赋值分为三个类型的操作。具体操作可以参考下图：
\\ \\ {{ :cs:programming:cpp:cpp_primer:container_assginment_op.svg?600 |}} \\ \\
==使用 assign operator 赋值==
赋值操作符 ''=''：该操作会直接将右边的容器的**整个范围**和**元素**赋值给左边，是**替换**（replace）的操作。如果左右容器**大小不匹配**，最后结果以**右边容器**为准：
 <code cpp>
c1 = c2; // replace the contents of c1 with a copy of the elements in c2
c1 = {a,b,c}; // after the assignment c1 has size 3
</code>
使用 ''='' 对 STL array 赋值，需要匹配容器**类型**（再次提醒：对于 array, **大小是类型的一部分**）：
<code cpp>
array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> a2 = {0}; // elements all have value 0
a1 = a2; // replaces elements in a1
a2 = {0}; // error: cannot assign to an array from a braced list
</code>
==使用 assign 函数赋值==
该种方法是 ''='' 方式的另外一种版本，通过指定元素的个数与元素的初始值来**替换**原有的容器内容：
<code cpp>
list<string> slist1(1); // one element, which is the empty string
slist1.assign(10, "Hiya!"); // ten elements; each one is Hiya 
</code>
==使用 swap 函数赋值==
swap 函数用于**交换**（//Exchange//）两个**同类型**容器的内容：
<code cpp>
vector<string> svec1(10); // vector with ten elements
vector<string> svec2(24); // vector with 24 
//now svec1 has size 24, svc2 has size 10.
elementsswap(svec1, svec2);
</code>
 <color #666>//**使用 sawp 的要求是什么？**//</color> \\ \\ 
//swap// 要求进行交换的两个容器必须**类型相同**。\\ \\ 
 <color #666>//**使用 sawp 进行交换以后，发生了什么样的变化？**//</color> \\ \\ 
swap **对容器内的内容进行了交换**。内部的迭代器、引用和指针等等均指向原来的**元素**：
\\ \\ {{ :cs:programming:cpp:cpp_primer:swap.svg?400 |}} \\ \\
 <color #666>//**哪些容器有例外？**//</color>
  - 在使用 swap 交换 //string// 的时候可能会使 迭代器、引用或者指针无效。
  - 在使用 sawp 交换 //array// 的时候，规则有些不同：
    - 与其他 contianer 不同，交换 array 同时**也交换了他们的元素**；因此交换 array 所需时间与其元素数量成正比。
    - 这些元素对应的指针、应用或迭代器**不会发生交换**。他们依然指向原来的位置，只是内容已经发生了变化。
<WRAP center round help 100%>
Swap 没有像 copy assignment 一样复制、删除或者插入任何元素。因此，swap 的执行速度非常快（可以在**常数时间**完成）。
</WRAP>
<WRAP center round tip 100%>
swap 的成员函数形式 a.swap(b) 是 C++11 的新标准。为了向前兼容，请尽量使用非成员版本的 swap。
</WRAP>

===容器大小操作===
除了一个例外，每个容器都有三个与大小相关的操作：
<code cpp linenums:1>
c.size(); // return the number of elements in container
c.empty(); // return true if there are no elements in container
c.max_size(); //return a value that greater or equal the maximum number of elements that container can hold
</code>
需要注意的是，//forward_list// 不提供 size()。
===关系运算符===
所有容器类型都支持 ''=='' 和 ''!='' 两种**相等性运算符**。除了**无序关联容器**（//unordered associative containers//）以外，其他容器还支持 ''>'', ''≥'', ''≤'', ''<'' 这四种关系运算符：
  * 比较的前提：
    * 如果使用关系运算符，容器的元素必须**定义**了相应的**关系运算符**。
    * **容器**必须是**相同类型**，**元素**也必须是相同类型。
如果满足比较的条件，则通过以下的策略进行比较：
    * **相等性**：如果容器大小相等，且对应元素一一相等，那么两个容器相等，否则不等。
    * **大小性**：
      * 如果容器 ''A'' 是容器 ''B'' 的**子序列**，那么 ''A'' < ''B''.
      * 否则，''A'' 和 ''B'' 的大小取决于他们**第一个不相等元素的比较结果**。
====顺序容器的操作====

===容器相关操作总览===
除了 array, 所有的 STL 容器都提供了 Run-time 期间的容器元素操作机制。当然，根据容器的实现方式不同，不同的操作在不同的容器上的效率也不同：
\\ \\ {{ :cs:programming:cpp:cpp_primer:seq_adding_op.svg?600 |}} \\ \\
<WRAP center round help 100%>
需要注意的是，使用对象**初始化**容器、**添加**、**插入对象**到容器这些操作，都是**拷贝操作**。实际对容器产生影响的不是原来的对象，而是它的拷贝。因此，之后对容器的任何操作**不会影响**原本的对象。
</WRAP>

===向容器首尾添加元素===
==使用 push_back()==
  *使用限制：不能应用于 ''array'', ''forward_list''。
  *使用方法：
<code cpp>
string word;
while (cin >> word)
    container.push_back(word)
</code>
==使用 push_front()==
  * 使用限制：''push_front'' 可用于 ''for_ward list''。
  * 使用方法：
<code cpp>
list<int> ilist;
// add elements to the start of ilist
for (size_t ix = 0; ix != 4; ++ix)
ilist.push_front(ix);
</code>
由于 //push_front()// 的机制类似于 stack，因此越靠后被操作的元素越处于容器的前部。比如上例中，操作的顺序是 ''0-1-2-3'' ，而最后在 List 中呈现的结构是 ''3-2-1-0''。\\ \\ 

===插入元素===
==对指定位置使用 insert()==
对容器指定位置添加元素可以使用 //insert// 成员。 //insert// 操作适合除了 //forward_list// 以外的各种容器（//forward_list// 有自己单独的一套插入操作。）
  * ''insert'' 接收一个 iterator ''p'' 作为插入的位置，该迭代器可以指代容器中任意元素的位置（包括''c.end()''）。
  * ''insert'' 的**插入位置**总是在 ''p'' 指向的**元素之前**（ 因为 //insert// 可能会插入头元素 ）
  * ''insert'' 的返回值是一个 //iterator//,  指向的新增元素序列的第一个元素。
  * ''insert'' 插入值为空的时候，返回 ''p''。
一般的使用方式：
<code cpp>
slist.insert(iter, "Hello!"); // insert "Hello!" just before iter
</code>
值得注意的是，//insert// 在对 //vector//、//string// 和 //deque// 中部进行元素插入时，**效率很低**，需要谨慎使用。
==使用 insert() 插入范围内的元素==
insert() 有两个重载版本提供了插入范围内元素的功能：\\ \\ 
 <color #666>//**指定元素个数的插入形式：**//</color> 
<code cpp>
container.insert(p, element_quantity, value);
</code>
这个版本往迭代器 ''p'' 指代元素之后插入拥有相同值的，指定数量的元素，比如：
<code cpp>
svec.insert(svec.end(), 10, "Anna"); //adding 10 element "Anna" at the end of svec
</code>
 <color #666>//**使用迭代器指定范围的插入形式：**//</color> \\ \\ 
第二个版本接收**一对表示范围的迭代器**，或者一个初始化列表，并将其插入到迭代器指定的位置之后：
<code cpp>
vector<string> v = {"quasi", "simba", "frollo", "scar"};
// insert the last two elements of v at the beginning of slist
slist.insert(slist.begin(), v.end() - 2, v.end());
slist.insert(slist.end(), {"these", "words", "will","go", "at", "the", "end"});
</code>
需要注意的是，传入的，表示范围的一对迭代器**不能指向正在被添加元素的容器**：
<code cpp>
// run-time error: iterators denoting the range to copy from
// must not refer to the same container as the one we are changing
slist.insert(slist.begin(), slist.begin(), slist.end());
</code>
==利用 insert() 范围版本的返回值==
C++ 11 中， //insert()// 会返回一个迭代器，该迭代器指向被插入序列的**第一个元素在容器中的位置**。利用这个返回值，我们可以写出如下的循环：
<code cpp>
list<string> 1st;
auto iter = 1st.begin();
while (cin >> word)
iter = 1st.insert(iter, word); // same as calling push_front
</code>
每次插入操作完成后，都会得到一个迭代器指向新元素所在的位置。下次循环使用该迭代器作为新的初始位置；由于 //insert()// 的插入位置是在迭代器指向位置之前，因此新的元素为以 "push" 的方式添加到之前添加的元素之前。因此，该循环实际上实现了 //push_front()// 的效果。

==使用 emplace 进行操作==
C++ 11 中提供了新的 emplace 系列成员来进行元素的插入。与之前提到的插入操作不同，emplace 使用**构造的方法**在容器中**直接**产生新的元素。由于这样的方式，emplace 的大部分 parameter 取决于**当前容器元素的构造函数**需要什么样 parameter。也就是说，emplace 实际上是在**容器内指定的位置调用构造函数**。\\ \\ 
emplace 成员有三个版本：
  * emplace(iter, arg)：在指定位置生成新的元素，//arg// 为元素的**构造函数**所需要的 arguments，可根据构造函数的重载进行变换
  * emplace_back(arg)
  * emplace_front(arg)
一些例子：
<code cpp>
c.emplace_back(); // using defualt constructor
c.emplace(iter, "999999"); // using Sales_data(string)
c.emplace_front("999999", 25, 15.99); //using Sale_data(isbn, count, price)
</code>
===访问元素===
C++ 提供了四种访问顺序容器元素的操作：
\\ \\ {{ :cs:programming:cpp:cpp_primer:accessing_op.svg?600 |}} \\ \\
使用 //back()// 、 //front()// 成员的之前应该确保容器是非空的：
<code cpp>
// check that there are elements before dereferencing an iterator or calling front or back
if (!c.empty()) {
	// val and val2 are copies of the value of the first element in c
	auto val = *c.begin(), val2 = c.front();
	// val3 and val4 are copies of the of the last element in c
	auto last = c.end();
	auto val3 = *(--last); // can't decrement forward_list iterators
	auto val4 = c.back(); // not supported by forward_list
}
</code>
==访问元素的成员返回引用==
上述的访问操作均返回绑定指定元素的**引用**。引用的 const 根据**容器**是否是 const 决定。\\ \\ 
除此之外，如果希望得到正确的返回值（引用），需要**显式的定义引用**（包括 auto）：
<code cpp>
if (!c.empty()) {
c.front() = 42; // assigns 42 to the first element in c
auto &v = c.back(); // get a reference to the last element
v = 1024; // changes the element in c
auto v2 = c.back(); // v2 is not a reference; it's a copy of c.back()
v2 = 0; // no change to the element in c
}
</code>
如果没有显式的应用，那么实际完成的是拷贝赋值，得到的是引用绑定元素的**副本**。
==下标访问与安全的随机访问==
另外两种访问方式是使用下标访问的方式。这两种方式都要求 index 必须在容器的范围内。但通常，使用下标操作符的方式不会检测 Index 是否在范围内。\\ \\ 
如果希望确保 index 是有效的，使用 //at()// 成员函数。当 index 无效时，该函数会抛出 //out_of_range// 类型的异常。
===删除元素===
C++ 也提供了几种方法用于删除容器内删除元素（不适用于 array）：
\\ \\ 
{{ :cs:programming:cpp:cpp_primer:erase_op_2.svg?600 |}}
\\ 
<WRAP center round important 100%>
这些成员不会检测其 arugments，删除前必须**确保被删除的元素存在**。
</WRAP>
==pop_front() / pop_back()==
//pop_front()// 和 //pop_back()// 用于删除容器首尾的元素：
  * 类似 //push_front()//， //vector// & //string// 没有 //pop_front()// 的成员。
  * 类似 //push_back()//, //forward_list// 没有 //pop_back()// 的成员。
  * 这两个成员返回 void。如果需要保存被删除的元素，需要在删除之前存储：
<code cpp>
while (!ilist.empty()) {
	process(ilist.front()); // do something with the current top of ilist
	ilist.pop_front(); // done; remove the first element
}
</code>
==删除容器中指定的元素==
使用 //erase(p)// 的重载版本可以删除 ''p'' 指向的元素；该成员返回一个迭代器，指向被删除元素所在位置的**下一个**元素：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/erase_p.svg"  width="250"> </div> </html> \\ \\
一个简单的应用 //erase()// 返回值的实例：
<code cpp>
list<int> lst = {0,1,2,3,4,5,6,7,8,9};
auto it = lst.begin();
while (it != lst.end())
	if (*it % 2) // if the element is odd
		it = lst.erase(it); // erase this element
	else
		++it;
</code>
==删除容器中多个元素==
接收双迭代器版本的 //erase(b, e)// 允许我们删除范围内的元素：
<code cpp>
// delete the range of elements between two iterators
// returns an iterator to the element just after the last removed element
elem1 = slist.erase(elem1, elem2); // after the call elem1 == elem2
</code>
指定的区间依然是左闭右开的区间，因此这里的 elem2 指向的元素不会被删除。\\ \\ 
如果需要清空所有元素，可以使用 //clear()//
<code cpp>
slist.clear(); // delete all the elements within the container
</code>
等同于：
<code cpp>
slist.erase(slist.begin(), slist.end()); 
</code>
===forward_list 的特殊操作===
 <color #666>//**为什么 forward_list 需要单独的一套成员？**//</color> \\ \\ 
之所以这样做事因为 //forward_list// 特殊的机制。简单来说，//forward_list// 一个单向的链表数据结构，每一个节点都承担着指向后方节点的任务：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/forward_list_fund_1.svg"  width="500"> </div> </html> \\ \\
由于其单向性，如果按照先断开链接，再添加或删除元素的顺序来操作是行不通的。断开链接后，被添删的元素之前的节点的指向信息无法更新，不知道新的节点在哪里：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/forward_list_fund_22.svg"  width="500"> </div> </html> \\ \\
因此，我们必须通过**先建立链接，再添加删除元素**的方式，来确保被操作元素之前的节点能够正确的指向新的节点：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/forward_list_fund_3.svg"  width="700"> </div> </html> \\ \\

基于上面的原因， forward_list 没有通用的 //insert//、//emplace// 或者 //erase// 成员。取而代之的是其自身的配套成员：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/forward_list_op_1.svg "  width="700"> </div> </html> \\ \\
可以看出来的是，如果需要添加 / 删除某一个元素，我们必须先获取其前置节点的位置。因此，上面所有的成员函数，操作的都是**迭代器 parameter ''p'' 之后的元素**。同时，为了方便操作容器的头元素，需要定义一个 // off-the-beginning// 的迭代器。这就是为什么有 //before_begin()// 成员的原因。

一些注意事项：
  * //insert_after// 函数返回一个指向被插入元素的迭代器。
  * //erase_after// 函数返回的是一个指向被删除元素后一位的迭代器。
  * //before_begin()// 不能解引用，因为该迭代器指向的是一个不存在的元素。

由于所有的 forward_list 成员函数都需要指向被操作元素之前位置的迭代器，因此在实际应用中需要同时维护两个迭代器：
<code cpp>
forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin(); // denotes element "off the start" of flst
auto curr = flst.begin(); // denotes the first element in flst
	while (curr != flst.end()) { // while there are still elements to process
		if (*curr % 2) // if the element is odd
			curr = flst.erase_after(prev); // erase it and move curr
		else {
			prev = curr; // move the iterators to denote the next
			++curr; // element and one before the next element
		}
	}
</code>
两个迭代器，前置的用于操作当前的元素，后置的用于循环和判断。
===改变容器大小===
C++中给我们提供一种改变容器大小的成员函数：''resize''。这个函数有两个版本：
<code cpp>
c.reszie(n); // change the size of c to n;
c.resize(n,t); // change the size c to n, initial all new element with value t
</code>
当 //n// 与容器大小不等时：
  - 如果 //n// < //c.size()//，那么**容器尾部的元素被删除**。
  - 如果 //n// > //c.size()//，那么会把新元素附加到容器**尾部**。此情况下要么给元素提供**初始值**，要么提供**默认构造函数**。
注意：对容器的 //resize// 操作也将导致**被删除元素**对应的迭代器、引用和指针失效。对 //vector//、//string// 和 //deque// 的 //resize// 可能会导致**所有**迭代器、引用或指针失效。
===容器与迭代器的失效===
总结一下容器操作对迭代器、指针和引用产生的影响：
  * **添加**元素后：
    * 容器是 //Vector & String//：
      * 存储空间被**重新分配**：**所有**指向容器的指针，引用，迭代器均失效。
      * 存储空间没有被重新分配：**插入位置之前**的指针，引用，迭代器不失效。
    * 容器是 //Deque//: 
      * 任何插入到**不是首尾位置**的元素都会导致所有迭代器，指针，引用失效。
      * 在首尾添加元素，则**只有迭代器**失效。
    * 容器是 //List & Forward_List//： 所有指针，引用，迭代器均有效。 
\\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/adding_op_valid_1.svg"  width="600"> </div> </html>
  * 删除元素后：
    * 指向被删除元素的所有指针，引用，迭代器都将失效。
    * 容器是 //Vector & String//：被删除元素位置**之前**的指针，引用，迭代器都有效。
    * 容器是 //Deque//：
      * 如果是除首尾之外删除任何元素，那么所有指针，引用，迭代器都会失效。
      * 如果删除尾部元素，尾部迭代器失效。
    * 容器是 //List & Forward_List// 所有指针，引用，迭代器均有效。
\\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/delete_op_valid.svg"  width="600"> </div> </html> \\ \\
 <color #666>//**如何正确的应对迭代器失效的问题？**//</color>
  * 最小化影响范围：尽量减少需要迭代器必须有效的判定。
  * 及时更新迭代器：使用某些受改变容器大小影响非常大的容器时（比如 //vector//、//deque// & //string//）尤其要注意。
===循环中迭代器的维护===
 <color #666>//**使用 erase(p) 的时候不需要手动对迭代器移位。**//</color> \\ \\
//erase(p)// 本身的效果是移除当前元素，并返回一个指向下个元素的迭代器。如果将该返回值交予控制循环的迭代器，那么达到的效果就是删除以后自动将循环迭代器移动到了下一位，因此不需要再添加任何手动的位移。
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/erase_p_effect.svg"  width="300"> </div> </html> \\ \\

 <color #666>//**使用 insert(p,N) 需要手动对迭代器向右移两位。**//</color> \\ \\
//insert(p,t)// 往 ''p'' 指代元素之前插入元素，并返回指向插入的第一个元素的迭代器。因此 ''p = insert(p,N)'' 的效果相当于将循环迭代器往左移动了一位。为了从下一个新元素开始，需要跳过插入的元素，以及之前指向的元素。因此需要右移两位：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/insert_p_effect.svg"  width="400"> </div> </html> \\ \\
 也就是：
<code cpp>
p = insert(p, N);
p += 2；
</code>
 <color #666>//**添删操作中，避免使用缓存过的 end() 迭代器**//</color> \\ \\ 
该点在对 //vector//、//string// 和 //deque// 进行添删操作的时候尤其要注意，因为对以上所有容器的添删操作都会导致 //c.end()// 返回的迭代器失效。如果将其缓存起来使用，结果会是 Undefined。比如下面的代码：
<code cpp>
// disaster: the behavior of this loop is undefined
auto begin = v.begin(),
end = v.end(); // bad idea, saving the value of the end iterator
	while (begin != end) {
		// do some processing
		// insert the new value and reassign begin, which otherwise would be invalid
		++begin; // advance begin because we want to insert after this element
		begin = v.insert(begin, 42); // insert the new value
		++begin; // advance begin past the element we just added
}
</code>
当 //insert()// 被调用以后，''end'' 变量中存储的迭代器就失效了，继续使用该迭代器将会导致 Undefined。正确的做法应该是以循环为单位重新计算 //c.end()//：
<code cpp>
// safer: recalculate end on each trip whenever the loop adds/erases elements
while (begin != v.end()) {
	// do some processing
	++begin; // advance begin because we want to insert after this element
	begin = v.insert(begin, 42); // insert the new value
	++begin; // advance begin past the element we just added
}
</code>
====Vector是如何增长的====
//Vector// 是一种大小可变的容器。当自身元素超过容器大小时，//Vector// 会进行自身的扩容。由于 //Vector// 中元素的存储是连续的，通常的策略是到别的地方申请一块更大的空间，然后将已有的 //Vector// 内容复制过去，再添加新的元素。这整个过程被称为 //Reallocate//。\\ \\ 
但这个过程有一个问题： //Reallocate// 需要拷贝整个 //Vector//，对性能的影响很大。如果严格控制 //Vector// 的大小，那么
理论上每一次插入操作都会使 //Vector// 进行 //Rellocate//。 \\ \\ 
为了尽量减少上述的开销，//Vector// 被设计成**容量远高于**其实际的需要的容器。通过这种方式，可以尽量避免 //Reallocate// 的发生，从而提高 //Vector// 的性能。
===管理容量的成员函数====
C++ 为 ''vector'' 和 ''string'' 提供了一些函数来供他们申请空间：
<code cpp>
/* only for vector、string and dqeue */
c.shrink_to_fit(); // request to reduce capacity() to equal size()        

/* only for vector and string */    
c.capacity(); // number of element that c can have before reallocation is necessary  
c.reserve(n); // allocate space for at least n elements       
</code>
有几点要注意的是：
  * ''reserve.(n)'' 代表申请的空间**至少是** ''n'' 个元素那么大；但如果请求的 ''n'' **小于现有的** //capacity//, 则什么都不做。
  * ''reserve.(n)'' 申请的空间是为 //reallocate// 准备的，并不是改变现有的 //Vector// 元素数量。
  * ''shrink_to_fit()'' 并不一定起作用，返还内存的请求很可能会被忽略。
<WRAP center round info 100%>
//c.resize()// 改变的是容器元素的数量，但并不提升容器的上限；而 //c.reserve()// 做的事正好相反。 
</WRAP>

===capacity 和 size===
 <color #666>//**Capacity 与 Size 的区别是什么？**//</color>
  * //Capacity//：代表了在不分配新的内存空间的情况下，可容纳最大元素的数量
  * //size// 则代表了容器现有元素的数量
 <color #666>//**Capacity 的增长策略是怎样的？**//</color> \\ \\ 
//Vector// 的 //Capacity// 增长策略是将当前的 //Capacity// 翻倍。但进行 //Reallocate// 的前提是当**前的 size 已经超过了 capacity**。比如容器中元素个数与 capacity 的大小均为 ''4''，如果再往容器中添加一个元素，则 capacity 就会翻倍变为 ''8''：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/vec_capacity.svg"  width="400"> </div> </html> \\ \\
通过这样的策略，使用 //push_back()// 创建 ''n'' 个元素的时间复杂度度可以控制在常数 $n$ 之内。 
====额外的 String 操作====
除了一些容器通用的函数以外，//string// 类本身还提供了一些其专属的操作。这些操作包括创建、修改、搜索、比较，以及类型转换等等。
===string 的创建===
//string// 支持三种专属的初始化方式：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/string_construct.svg"  width="650"> </div> </html> \\ \\
==使用字符串进行初始化时的注意事项==
  * 使用 //const char*// 对 //std::string// 进行初始化时，初始化的内容会复制到 ''/0'' 标记为止。有两种情况会导致该操作 Undefined:
    * //const char*// 字符串不带 ''/0'' 结束标记，且**没有指定**拷贝的长度 ''n''。
    * //const char*// 字符串不带 ''/0'' 结束标记，指定了拷贝长度 ''n''，但 ''n'' 的大小**超出了字符数组的大小**。
  * 使用 //std::string// 对 //std::string// 初始化时，如果提供的拷贝起始位置不在被拷贝的 string 之内，构造函数会抛出 //out_of_range// 异常。 其自带的 ''len'' 参数作用范围只在 ''pos'' 到 ''s.size()'' 之间。
<code cpp>
const char *cp = "Hello World!!!"; // null-terminated array
char noNull[] = {'H', 'i'};        // not null terminated
string s1(cp);  // copy up to the null in cp; s1 == "Hello World!!!"
string s2(noNull,2); // copy two characters from no_null; s2 == "Hi"
string s3(noNull);   // undefined: noNull not null terminated
string s4(cp + 6, 5);// copy 5 characters starting at cp[6]; s4 == "World"
string s5(s1, 6, 5); // copy 5 characters starting at s1[6]; s5 == "World"
string s6(s1, 6);    // copy from s1 [6] to end of s1; s6 == "World!!!"
string s7(s1,6,20);  // ok, copies only to end of s1; s7 == "World!!!"
string s8(s1, 16);   // throws an out_of_range exception
</code>
==使用 sutstr() 构造子字符串==
通过 //sutstr()// 成员可以以某个 string 的一部分构造一个新的 string：
<code cpp>
//Return a string contains n characters from a staring at pos.
//pos default to 0
//n defaults to a value that cause the library to copy all the characters in a starting from pos.
s.substr(pos, n); 
</code>
如果 ''pos'' 超出被拷贝 string 的范围，该成员同样会抛出 //out_of_range// 的异常。如果 ''n'' 超出了 string 的 size 范围，拷贝的内容同样只拷贝到 string 的结束位置。
===string 的修改=== 
//string// 类同时也支持一些额外的修改操作。某些操作还支持不同的重载版本：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/modifiy_strings_1.svg"  width="700"> </div> </html> \\ \\
几个比较重要的概念：
  * 牵涉到插入和替换的操作，range 分为 [index + length] 和 [iter.begin, iter.end] 两种表现形式。
  * 某些成员支持对 c-style string 进行操作。这些操作通过指向对应C 字符串的 ''cp'' 指针实现。
  * argument 形式中可能会出现两个字符串：被修改的 s 和 用于 str：
    * str 与 s 不能是同一个 string
    * 如果是迭代器 (b,e) 形式的 args，b,e 不能指向 s
==append() & replace()==
string 额外拥有两个成员：//append()// 与 //replace()//。//append()// 将对应内容添加到目标 string 的末尾，而 //replace()// 类似于 //insert// + //erase// 的组合，用于将目标 string 中的某段内容替换为指定内容：
<code cpp>
string s("C++ Primer"), s2 = s; 
s.insert(s.size(), " 4th Ed."); //s == "C++ Primer 4th Ed."
s2.append(" 4th Ed."); // s2 == "C++ Primer 4th Ed."

s.erase(11, 3); //s == "C++ Primer Ed."
s.insert(11, "5th"); // s == "C++ Primer 5th Ed."
s2.replace(11, 3, "5th"); // s2 == "C++ Primer 5th Ed."
</code>
==用于修改 string 的多种重载形式==
尽管 //append//、//assign//、//insert// 和 //replace// 的重载形式很多，但这些成员共享一个接口：
  * assgin & append **不需要指定** 目标 string 需要被修改的 range，因为 assign 是对 string 做整体替换，而 append 总是将内容全加到 string 的末尾。
  * replace 与 insert 都通过**两种** range 形式来指定替换区域和插入位置。 insert 的插入位置总是在 range **之前**。
  * 往目标 string 中添加字符的来源有多种：另一个 string, c-string（的指针），初始化列表，或者指定个数的同一个字符。来源是 string / c-string 的时候，会提供额外的控制参数。
  * 不是所有的 args 都是通用的。
===string 的搜索===
//String// 类提供了六种函数用于搜索 string 或者 字符。当这些函数找不到匹配结果的时候，会返回一个 //static// 的成员 ''string::npos''。这个成员的类型是 ''const string::size_type'', 初始值是 ''-1''。因为 ''npos'' 是 //unsigned//  类型，所以 ''npos'' 等于任何 //string// 最大可能的大小。\\
\\
<html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/string_searching_op.svg"  width="700"> </div> </html> \\ \\
所有上述函数返回的都是位置(index，''std::string::size_type'' 类型)，或者是 ''npos''，所有的搜索函数均**区分大小写**。
\\
\\
==搜寻不是数字的字符==
通过创建字符白名单，再利用 //find_first_not_of// 的特性可达到此效果：
<code cpp>
string numbers("0123456789")；
string dept("03714p3");
// returns 5, which is the index to the character 'p'
auto pos = dept.find_first_not_of(numbers);
</code>
==利用 find 返回的位置指定搜索点==
//find// 系列函数会返回对应的 index. 一个应用是利用该 index 与 ''npos'' 配合使用实现循环查找：
<code cpp>
string::size_type pos = 0;
//refresh and matching number at current position, if match then move to the next loop
while ((pos = name.find_first_of(number, pos) !=  string::npos) {
    cout <<  name[pos] << endl;
    ++pos; //move to the next character
}
</code>
这里利用了
<code cpp>
pos = name.find_first_of(number, pos)
</code>
这个表达式来刷新当前的 index. 该 index 是基于之前的位置刷新的，即找到匹配的字符以后，就把该字符位置作为当前的起始点，接着向下查找。需要注意 ''++pos''，如果是按段落查找，可以考虑改变移动的大小到 //args.size()//；这样会更加效率。
==从右向左查找==
//find// 系列函数同时提供了从右向左查找的选项：
<code cpp>
string river("Mississippi");
auto first_pos = river.find("is"); // returns 1
auto last_pos = river.rfind("is"); // returns 4
</code>
这里 //rfind// 找到的是右边第一个匹配的 ''is'' ，因此返回 ''4''。同时，//find_last// 系列函数也能达到相似的效果： 
  * //find_last_of//：寻找最后一个匹配的字符
  * //find_last_not_of//: 寻找最后一个不匹配字符
===string 的比较===
//compare// 函数和 C 语言的 //strcmp// 很像，用于比较 string 的大小：如果相等返回 ''0''，如果**前者大于后者**返回**正数**，**反之**返回**负数**。\\ \\ 
一些常用的参数组合：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/compare_arg.svg"  width="650"> </div> </html> \\ \\
===String 的数字转换===
String 的中往往会出现数字，但这些数字存储的方式是以 //Latin-1// 编码的字符来存储的，比如字符串 ''15''，实际上是以两个字符的形式存储的，每个字符分别占 8 个字节的空间：
<code cpp>
00110001 00110101 // string "15"
</code>
而对应的数值 ''15'' 则是以 int 的形式存储的：
<code cpp>
00000000 00001111 //int 15
</code>
C++11中，string 类提供了对应的成员函数，使得这两者可以相互转换：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/str_conversion.svg"  width="700"> </div> </html> \\ \\
这些成员函数分为三类：
  * 从数值转换为 //string//
  * //string// 转换为整型
  * //string// 转换为浮点型
<code cpp>
string s2 = "pi = 3.14";
// convert the first substring in s that starts with a digit,  d = 3.14
d = stod(s2.substr(s2.find_first_of("+-.0123456789")));
</code>
上面的例子中，''s2.find_first_of()'' 将返回第一个是数字的迭代器，并依据此创建出一个 string。而 ''stod()'' 将读取该 string，并转换为 double，并将在遇到 string 中下一个不是 Number 的位置停止。 \\ \\ 
可以转换成数字的 string 需要满足以下要求：
  * string 首个 non-whitespece 的字符必须是正负符号（''+'' 或 ''-''），或者是数字。
  * 如果 ''b'' 设置为了 16 进制，可以以 0x 开头。
  * 如果是浮点数，可以以 ''.'' (decimal point, 小数点） 开头，同时也支持 ''e'' 或 ''E'' （科学计数法中的指数）
如果 string **不能转换为一个数值**， 则会抛出 //invalid_argument// 异常。如果**转换得到的数值不能用任何类型表示**，则抛出 //out_of_range// 异常。
====容器适配器====
**适配器**（//Adaptor）// 是 C++ STL 中的一个概念。适配器是一种机制，它基于某种容器、迭代器或者函数类型，然后像另外一种类型一样使用这些类型。\\ \\ 
**容器适配器**（//Container Adapter//）则是基于某种容器，然后使该容器可以像另外一种类型的容器一样使用。一些适配器通用的类型与操作如下：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/adptor.svg"  width="650"> </div> </html> \\ \\

==容器适配器的定义==
容器适配器拥有两个构造函数：
  * 默认构造函数，创造空的对象
  * 初始化是适配器的构造函数，接收一个容器，将其以复制的形式初始化适配器：
比如定义一个基于 ''deque<int>'' 的 //stack//：
<code cpp>
stack<int> stk(deq); //copy init from deq
</code>
不仅如此，在定义适配器的时候可以指定其使用的容器：
<code cpp>
// empty stack implemented on top of vector
stack<string, vector<string>> str_stk;
// str_stk2 is implemented on top of vector and initially holds a copy of svec
stack<string, vector<string>> str_stk2(svec);
</code>

当然，每种适配器必须选择合适的容器来进行初始化。一些限制：
  * 适配器要求可以添删 & 尾部元素修改，因此**不能使用** //array// 和 //forward_list//。
  * //stack// 要求 ''push_back'', ''pop_back'', 和 ''back'' 操作，所以可以用除前两种以外的所有容器。
  * //queue// 要求 ''back'', ''push_back'' / ''push_front'', ''front'', 所以可以用 //list//, //deque//, 但是**不能使用** //vector//。
  * //priority_queue// 相比 //queue// 不需要 ''push_front''，但需要 //random access//，所以**不能使用** //list//。

===stack 适配器===
//stack// 适配器定义在 ''<stack>'' header 中, 包含如下几种额外的操作：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/stack_op.svg"  width="600"> </div> </html> \\ \\
一个实例：
<code cpp>
stack<int> intStack; //empty stack
//fill up the stack
for (size_t ix = 0; ix != 10; ++ix) {
    intStack.push(ix); //insStack holds [0...9]
}
whlie(!intStack.empty()) {
    int value = intStack.top(); //show the top elmenet
    intStack.pop(); //remove the top element
}
</code>
注意这里，即便 //stack// 是基于 //deque// 实现的，我们也不能使用 //push_back()// 来操作 //stack//。
<WRAP center round help 100%>
**适配器应该使用适配器定义的操作，不能使用底层容器的操作来操作适配器**。
</WRAP>

===queue 适配器===
标准库中：
  * //queue// 是一种访问策略为**先进先出**（//FIFO//）的类型；这意味着**进入** //queue// 的元素都会在**队尾添加**，而**离开** //queue// 的元素都会从**队首删除**。默认使用 //deque// 实现，但也可以用 //list// & //vector//。
  * //priority_queue// 按照优先级来排序。先加入的元素会排在所有比它优先级低的元素之前（使用 ''<'' 运算符进行排位）。比如饭店按预约的时间来分配座位，而不是按先来后到分配。默认使用 //vector// 实现，但也可以用 //deque//。
相关的操作：
\\ \\ <html><div align="center"> <img src="/_media/programming/cpp/cpp_primer/queue_pqueue_op.svg"  width="600"> </div> </html> \\ \\