[C++ Primer Note8] 顺序容器

所谓的顺序容器即元素在顺序容器中的顺序与其加入容器时的位置相对应。标准库还定义了几种关联容器，关联容器中元素的位置由元素相关联的关键字值决定。所有的容器类都共享公共的接口，不同容器按不同方式对其进行扩展。

1. 标准库中的顺序容器常用的有以下这些：

• vector：可变大小数组，支持快速随机访问。非尾部插入删除很慢
• deque：双端队列，支持快速随机访问，在头尾插入/删除速度很快
• list：双向链表，只支持双向顺序访问，任何位置插入/删除都很快
• forward_list：单向链表，只支持单向顺序访问，任何位置插入/删除都很快
• array：固定大小数组，支持快速随机访问，不能添加或删除元素
• string：与vector相似的容器，但专门用于保存字符

2. 现代C++程序应该使用标准库容器，而不是更原始的数据结构，如内置数组。一般来说，使用vector是最好的选择，除非你有很好的理由选择其他容器。
3. 容器类型上的操作形成了一种层次：

• 某些操作是所有容器类型都提供的
• 另外一些操作仅针对顺序容器，关联容器或无序容器

4. 一般来说，每个容器都定义在一个头文件中，文件名与类型名相同。容器均定义为模板类，我们必须提供额外信息来生成特定的容器类型。
5. 顺序容器几乎可以保存任意类型的元素，但某些容器操作对元素类型有其自己的特殊要求。
6. 常用容器操作（通用）
   容器操作
   反向容器额外操作
7. 一个迭代器范围（iterator range）由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者尾后位置。这两个迭代器通常被称为begin和end。这种元素范围被称为左闭合区间，其标准数学描述为：

[begin, end)
begin和end必须指向相同的容器，end可以和begin指向同样的位置，但不能指向begin之前的位置。

8. 之所以规定左闭合范围是因为我们可以安全方便地处理元素，如下：

while(begin!=end){
  *begin=val;
  ++begin;
}

9. 通过容器内置的类型别名，我们可以在不了解容器中元素类型的情况下使用它（通过value_type）。如果需要元素类型的一个引用，可以使用reference或const_reference。
10. 当auto与begin或end结合使用时，获得的迭代器版本依赖于容器类型（因为实际上begin被重载过），但以c开头的版本一定会获得const_iterator。当不需要写访问时，应该使用cbegin和cend。
11. 每个容器类型都定义了一个默认构造函数。除array之外，其他容器的默认构造函数都会创建一个指定类型的空容器。
12. 为了创建一个容器为另一个容器的拷贝，两个容器的类型及元素类型必须匹配。不过如果传递迭代器参数来拷贝一个范围，就不要求容器类型是相同的了。
13. 新标准中，我们可以对一个容器进行列表初始化，这样我们显式指定了每个元素的值，还隐含了容器的大小。
14. 与内置数组一样，标准库array的大小也是类型的一部分。定义一个array时，除了指定元素类型，还要指定容器大小：

  array<int,42>;
  array<string,10>;

15. 由于大小是array的一部分，array不支持普通的容器构造函数，这些构造函数或显式或隐式地确定了容器的大小。
16. 与其他容器不同，一个默认构造的array是非空的：它包含与其大小一样多的元素，这些元素都被默认初始化，就像一个内置数组一样。如果我们对array进行列表初始化，初始值数目必须等于或小于array的大小，如果小于，则剩余靠后的元素都会进行值初始化。这种情况下，如果元素是类类型，则必须要有一个默认构造函数。
17. 值得注意的是，虽然我们不能对内置数组进行拷贝或对象赋值操作，但array并无此限制。array要求容器类型，元素类型和大小都一样，因为大小也是array类型的一部分。
18. 赋值运算符将其左边容器中的全部元素替换成右边容器中元素的拷贝，要求左边和右边具有相同的类型
19. 顺序容器（除了array）还定义了一个名为assign的成员，允许我们从一个不同但相容的类型赋值，或者从容器的一个子序列赋值。
20. swap操作交换两个相同类型容器的内容，除了array外，swap只是交换了两个容器的内部数据结构。所以迭代器，引用和指针仍指向之前所指的元素，但是这些元素已经去到另外一个容器了。swap两个array则会真正交换它们的元素。
21. 新标准库中，容器既提供成员函数版本的swap，也提供非成员版本的swap，由于非成员版本的swap在泛型编程中很重要，所以统一使用非成员版本的swap是好习惯。
22. 每个容器类型都支持相等运算符；除了无序关联容器外所有容器都支持关系运算符，关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素。比较两个容器实际上是元素的逐对比较，与string的字典序比较类似。
23. 如果元素类型不支持所需的运算符（比如==和>），那么保存这种元素的容器就不能使用相应的关系运算。
24. 容器提供的操作与它组织元素的方式有密切关系（实际上就是内部数据结构），也与它的语义有关（比如array不支持改变大小的操作）
25. 向顺序容器添加元素：
    向顺序容器添加元素
26. 访问顺序容器的元素：
    访问元素
27. 删除顺序容器的元素：
    删除元素
28. forward_list本质上一个单向链表，删除或添加某个元素会影响前驱节点的后继，但是单向链表并没有简单的方法来获取一个元素的前驱。所以一个forward_list中添加或删除元素的操作时通过改变给定元素之后的元素来完成的。所以从forward_list添加或删除元素的时候，我们往往关注两个迭代器，如下：

forward_list<int> flst={0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin();
auto curr = flst.begin();
while(curr!=flst.end()){
  if(*curr%2)
    curr=flst.erase_after(prev);
  else{
    prev=curr++;
  }
}

在forward_list中插入或删除元素

29. 在容器中添加元素和从容器中删除元素的操作可能会使指向容器元素的指针，引用或迭代器失效，仍旧使用失效的它们是一种严重的程序设计错误。具体的失效情况可以通过分析容器的底层数据结构并将迭代器假想为指针大致得出，此处不再赘述。特别是如果在使用迭代器的循环中具有添加/删除的操作，一定要注意迭代器的更新，保证其正确性。
30. 当vector和string不得不获取新的内存空间时，通常会分配比新的空间需求更大的内存空间作为备用。但vector只有迫不得已的时候才分配新的内存空间。
31. vector和string提供了一些成员函数，允许我们与它的实现中内存分配部分互动：
    容器大小管理操作
32. 除了顺序容器共同的操作之外，string类型还提供了一些额外的操作。这些操作中大部分要么是提供了string类和C风格字符数组之间的相互转换，要么是增加了允许我们用下标代替迭代器的版本。
33. string类型提供了非常多的成员函数，总的来说，包括多种构造函数，返回子串函数，多种修改函数，多种搜索字符函数，多种比较函数，以及多种string和数值之间的转换函数，此处不一一赘述，需要时再查阅资料即可。
34. 除了顺序容器外，标准库还定义了三个顺序容器适配器：stack，queue和priority_queue。适配器（adaptor）是标准库的一个通用概念。本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型。例如，stack适配器接受一个顺序容器，使其操作看起来像一个stack一样。
    所有容器适配器都支持的操作和类型
35. 默认情况下，stack和queue是基于deque实现的，priority_queue是在vector之上实现的。我们可以在创建一个适配器时将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型。

//在vector上实现的空栈
stack<string,vector<string>> str_stk;

对于给定的适配器，可以使用哪些容器是有限制的，具体的规则可以结合适配器以及容器的接口来分析，要求适配器接口一定能通过容器的接口直接或简单间接实现，就不一一赘述了。

栈的接口
队列和优先队列接口(1)
队列和优先队列接口(2)

值得注意的是：这里关于pop的用法写错了，pop返回的是void，这是因为如果pop要弹出元素，则必须返回元素的值而不是引用。然而接收值的时候有可能发生异常（比如通过这个值来初始化一个类类型），这时丢失的元素就再也找不回来了。所以往往pop和top搭配使用。