原创 【博客大赛】《C++ Primer》学习笔记（27）顺序容器

Vector是一种容器。
本章"Sequential Container"是第三章"Strings, Vectors, and Arrays"的扩展。

顺序容器的元素位置，取决于元素加入的顺序；关联容器的元素位置，取决于关联元素的key。
容器classes共享公共的接口，使得它易于学习。
A container holds a collection of objects of a specified type.

9.1 Overview of the Sequential Container
----------------------------------------------------------------
顺序容器有下面几种类型：
vector        : Flexible-size array.
deque         : Double-ended queue.
list          : Doubly linked list.
forward-list  : Singly linked list.
array         : Fixed-size array.
string        : A specialized container, similar to vector.
 
string和vector将它们的元素存储在连续的空间里，因此增加或删除元素是很复杂的操作；
list和forward_list可以在任何位置快速添加/删除元素，它不支持random访问，而必须用迭代器。
deque更加复杂，它支持random访问，在中间添加/删除元素的开销很大，但在首尾却很方便。
array不支持添加/删除操作，forward_list没有size操作。

一般来说，请使用容器，而不是旧的数据类型。
怎样选择合适的容器呢？
 • 除非你有理由选择其他的容器，否则请使用vector。
 • 如果你的程序有很多small元素，并且空间matters，不要使用list或forward_list。
 • 如果你的程序要求有random访问，那就使用vector或者deque。
 • 如果你的程序要求在中间插入或删除元素，就使用list或者forward_list。
 • 如果你的程序要求在首尾插入或删除元素，就是用deque。
 • 如果你的程序只要求在容器的中间使用reading input的方式插入元素，并且要求random访问：
    再次确认你是否真的要求在中间插入？
    如果真的要求，则使用list插入，再转换成vector。

9.2 Container Library Overview
----------------------------------------------------------------
所有的容器都提供了以下操作，比如：
iterator
C c;
c.size();
c.insert(args);
==, !=
c.begin();

顺序容器提供了以下操作：
C seq(n);
C seq(n, t);

每种容器都定义在了自己的同名头文件中，
deque定义在了deque头文件中，list定义在了list头文件中。
容器实际上是类的模板，我们必须提供额外的信息才能产生特定的容器类型。
这里的额外信息，大部分但并不是所有，是指元素的类型。

容器几乎可以是任何类型的，当然也可以是容器类型：
list<deque<int>> lst;

容器的范围是个很重要的概念，一般使用迭代器获取它：
[begin, end)

我们可以使用容器内的类型，来定义我们的变量，比如：
list<string>::iterator iter;
vector<int>::difference_type iter;

list<string> a = {"Milton", "Shakespeare", "Austen"};
auto it1 = a.begin();    //a的迭代器
auto it2 = a.rbegin();   //a的反向迭代器
auto it3 = a.cbegin();   //a的const迭代器
auto it4 = a.crbegin();  //a的const反向迭代器

虽然我们不能使用传统的数据进行复制的操作，但是容器array可以：
array<int, 10> digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
array<int, 10> copy = digits;

容器array不支持赋值操作：
copy = {0};  //非法操作

另外，swap除了可以调换容器内部的两个元素之外，还能够调换两个容器本身：
vector<string> svec1(10);
vector<string> svec2(24);
swap(svec1, svec2);

两个相同类型的顺序容器，可以进行比较操作。

9.3 Sequential Container Operations
----------------------------------------------------------------
9.4 How a vector Grows
----------------------------------------------------------------
为了保证对vector的快速访问，vector是连续存储的，因此，
如果没有空间来增加新的元素，整个vector都必须迁移到新的地点。

由于有allocation strategy的存在，vector的效率通常比list或deque要高:
c.shrink_to_fit()  // 返还被保留的空间，但不做保证
c.capacity()       // 返回剩余的空间量
c.reserve(n)       // 为容器保留n空间量，但绝不会缩减空间

9.5 Additional string Operations
----------------------------------------------------------------
9.6 Container Adaptors
----------------------------------------------------------------
Essentially, an adapter is a mechanism for making one thing act
like a different type.
容器适配器的概念有些难以理解，需要慢慢来。

如果想让一个deque表现得像栈一样，则：
stack<int> stk(deq);

如果想从vector来将长stack，则：
stack<string, vector<string>> str_stk;

所有的adaptor都需要添加或删除元素的能力，因此array不能被建立成adaptor。

结语：
本章内容是对之前学过的vector、string等顺序容器的总结和扩展。
本章内容具备自身的逻辑性，因此虽然内容很多，但是易于理解和记忆（所以笔记很少）！