C++ Primer

顺序容器

这部分的内容你在写程序的时候肯定是处处都能用到的，而且会让你的程序很简洁。本章其实是第三章内容的拓展，详细地介绍了标准库顺序容器的知识。

一个容器就是一些特定类型对象的集合。顺序容器为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

顺序容器概述

所有顺序容器都提供了快速顺序访问元素的能力，但不同容器在两个方面的性能不同：

1. 向容器中添加或删除元素
2. 非顺序（随机）访问容器中的元素

你可以看到每一个容器都对性能有所侧重，都是有不同的灵活度，那我们在选择容器的时候应该选哪种呢？

• 除非你有很好的理由选择其他容器，否则一律用vector
• 程序要求随机访问，用vector或deque
• 程序需要很大的额外开销，不要用list或forward_list，因为它们再去连其他内存开销大
• 程序只在头尾插入删除元素，用deque 虽然这些原则很有用，但在实际应用的时候，你一定要自己衡量好性能，只要你掌握了表格中各个容器的特点，相信你能做出最合适的选择。

容器库概览

这部分介绍对所有容器都适用的操作
一般来说，每个容器都定义在一个头文件中，文件名和类型名相同，例如，deque定义在头文件deque中。

容器均定义为模板类，对于大多数，我们必须提供额外信息来生成特定的容器类型：

list<int> a;
vector<double> b;

对容器可以保存的元素类型的限制

顺序容器几乎可以保存任意类型的元素，包括它自己。也有一些例外，比如说，我要保存一个类类型的对象，而这个类没有默认构造函数，于是，我得自己给它提供一个元素初始化器：

//假定a是一个没有默认构造函数的类型
vector<a> v1(10, init); //正确：init是一个a对象，相当于提供了初值，v1中有10个init
vector<a> v2(10); //错误：无法初始化

所有容器都支持的操作我直接贴图片了，反正也记不住，多用用才知道。

迭代器

写一个程序看看吧，输出容器中所有元素：

vector<int> a(10, 1);
auto beg = a.begin();
while(beg != a.end())
{
    cout << *beg++ << endl;
}

迭代器可加可减，但forward_list不支持减，理由显而易见。

容器类型成员

每个容器都定义了多个类型，如前面图片中的第一部分类型别名，我们其实已经用过三种：size_type、iterator和const_iterator。 大多数容器还提供反向迭代器，反向迭代器++就是上一个元素。

通过类型别名，我们可以在不了解容器中元素类型的情况下使用它：

list<string>::iterator iter; //iter是通过list<string>定义的一个迭代器类型
vector<int>::difference_type count;
//count是通过vector<int>定义的一个difference_type类型

begin和end成员

list<string> a = {"1", "2", "3"};
auto it1 = a.begin(); //list<string>::iterator
auto it2 = a.rbegin(); //list<string>::reverse_iterator
auto it3 = a.cbegin(); //list<string>::const_iterator
auto it4 = a.crbegin(); //list<string>::const_reverse_iterator

当不需要修改时，最好用cbegin

容器定义和初始化

每个容器类型都定义了一个默认构造函数。除了array之外，其他容器的默认构造函数都会创建一个指定类型的空容器，且都可以接受指定容器大小和元素初始值的参数。
下图已经说得很清楚了，不清楚的就继续看我下面的啰嗦吧

将一个容器初始化为另一个容器的拷贝

两种方式：

1. 直接拷贝整个容器
2. 拷贝由一个迭代器对指定的元素范围（array除外） 二者在元素类型的要求严格程度上有所不同，第一种容器类型和容器内元素类型必须完全匹配，第二种容器类型无所谓，因为被迭代器隐藏了嘛，容器内元素类型能转换就行。看代码：

   list<string> a = {"1", "2", "3"}; //列表初始化
   vector<const char*> b = {"4", "5", "6"};
   list<string> a1(a); //正确
   deque<string> a2(a); //错误：容器类型不匹配
   vector<string> b1(b); //错误：容器内元素类型不匹配
   forward_list<string> b2(b.begin(), b.end()); //正确
   

与顺序容器大小相关的构造函数

这个么，也还是好用的：

vector<int> a1(10, -1); //10个-1
vector<int> a2(10); //10个0
vector<string> a3(10); //10个空string

如果元素类型是内置类型或者有默认构造函数的类类型，可以在初始化的时候只为构造函数提供一个容器大小参数；如果没有默认构造函数，必须要显式地提供初值。

标准库array具有固定大小

与内置数组一样，array的大小也是类型的一部分：

array<int, 3>; //类型是3个int的数组

array<int, 10> a1; //10个0
array<int, 3> a2 = {1, 2, 3}; //列表初始化
array<int, 3> a3 = {5}; //5, 0, 0

我们不能对内置数组进行拷贝或对象赋值，但array可以（可能这也是为什么搞出array的原因）：

array<int, 3> a = {1, 2, 3};
array<int, 3> copy = a;

赋值和swap

vector<int> a1 = {1, 2, 3, 4, 5};
vector<int> a2 =a1;
a2 = {1, 2}; //这样都行哦，大小变为2

array<int, 5> b1 = {1, 2, 3, 4, 5};
b1 = {1}; //这样不行

关于array，书上是这样说的：由于右边对象大小可能和左边对象大小不同，所以array索性不支持用花括号赋值和assgin。（我自己试了下，小于等于原来的元素数量是可以的）

使用assign（仅顺序容器）

赋值运算符要求两边运算对象类型相同，使用assign可以从一个不同但是相容的类型来赋值：

list<string> name;
vector<const char*> old;
names = old; //错误，容器类型不匹配
names.assign(old.cbegin(), old.cend()); //正确，char*能转换为string
names.assign(10, "h"); //assign重载版本，10个h

使用swap

vector<string> s1(10);
vector<string> s2(20);
swap(s1, s2); //交换后，s1有20个元素，s2有10个元素

除了array之外（它是真正交换元素了），交换两个容器的操作很快，是常数时间，因为swap只是交换了两个容器的内部数据结构，并没有真正移动元素，所以啊，原来那些指针、引用都还是指向原来的。 array就会指向交换后的了，毕竟人家来真的。

与其他容器不同，对一个string调用swap会让指针、引用、迭代器等失效。

容器大小操作

关系运算符

容器装的元素类型支持关系运算，我们才能来用它，先来看内置类型的，它们肯定被实现得很好，毕竟C++高手

vector<int> v1 = {1, 3, 5, 7, 9, 12};
vector<int> v2 = {1, 3, 9};
vector<int> v3 = {1, 3, 5, 7};
vector<int> v4 = {1, 3, 5, 7, 9, 12};
v1 < v2;
v1 > v3; 
v1 == v4;

关系运算中判等用==，大小用<，来个错误示范：

vector<Sales_data> a, b;
if(a < b) //错误，没定义<运算符