C++ container

什么是容器

一个容器就是一些特定类型对象的集合。C++标准库中提供了两类容器，一类是顺序容器，一类是关联容器。
关联容器和顺序容器有着根本上的不同：关联容器的元素是按照关键字保存和访问的；而顺序容器是按照他们在容器中的位置顺序保存和访问的，这种顺序不依赖于元素的值，而跟元素加入容器时的位置相对应。关联容器中的许多行为和顺序容器相同，但是他们的不同之处反映了关键字的作用。顺序容器和关联容器共享公共的接口，不同容器可以按照不同的方式对其进行扩展，这个公共接口使得容器学习起来更容器，基于某个容器学习的内容可以扩展到其他容器上。

顺序容器为程序员提供了控制元素存储和顺序访问的能力。这种顺序不依赖于元素的值，而跟元素加入容器时的位置相对应。
关联容器支持高效的关键字查找和访问，两个主要的关联容器是map和set，map中的元素是一些关键字－值(key-value)对，关键字索引，而值表示和索引相关的数据。而set中的每个元素只有一个关键字。

顺序容器概述

关于顺序容器更详细的内容可以查看C++ sequential container。
所有C++标准库中的顺序容器包括：

vector: 可变大小数组，
list：双向链表，
forward_list：单向链表，
deque：双端队列
array：固定大小数组
string：与vector类似，但是专门用于字符操作，

时间复杂度分析

所有的顺序容器都提供了快速顺序访问元素的能力。但是，这些容器在以下方面都有不同的性能折中：

添加或者删除元素的代价
随机访问容器中元素的代价

具体如下（都是时间复杂度）：

vector：支持$O(1)$随机访问。在尾部之外的位置插入或者删除可能很慢$O(n)$。
list：只支持双向顺序访问$O(n)$，任何位置插入或者删除都是$O(1)$。
forward_list：单向链表，只支持单向顺序访问$O(n)$，任何位置插入或者删除都是$O(1)$。
deque：$O(1)$随机访问，头尾插入都是$O(1)$。
array：$O(1)$随机访问，不支持增删操作。
string：支持$O(1)$的随机访问，尾部增删是$O(1)$。

存储策略

string和vector都存储在连续的的内存空间中。由于元素是连续存储的，根据元素的下标计算元素的地址很快；但是在增删中间的元素时，需要移动增删位置之后所有的元素；此外，添加一个元素时，可能当前的存储空间不够了，还需要分配新的存储空间，这需要将所有的元素都移动到新的存储空间去。
list和forward_list的数据结构都是链表，具有链表的性质。即任何位置增删操作都是$O(1)$的，但是不支持随机存储，在寻找某一个元素时，只能遍历整个链表$O(n)$。此外，和vector,deque,array，他们还需要额外的内存开销，即指针的内存开销，指针用来记录前(后)节点的信息。
deque支持$O(1)$的随机访问，在中间位置增删都是$O(n)$的开销，但是在deque两端增删是$O(1)$的事件开销。
array和内置数组一样，大小固定，不支持增删，但是更安全。
forward_list是单向链表，它的设计目标是和手写的单向链表性能相似，因此，forward_list没有size操作，因为这会增大计算开销。对于其他容器而言，size是一个$O(1)$的操作。

顺序容器的选择

通常使用vector是最好的选择，除非有更好的理由。
程序有很多小的元素，而且空间额外开销很重要，不要用list或者forward_list。
要求支持随机访问元素，使用vector或者deque。
在容器中间插入或者删除，使用list或者forward_list。
程序需要在容器头尾增删，而不会在中间增删，使用deque。
如果即需要随机存取，又需要在容器中间增删，这个时候根据存取和增删的操作数量进行选择，哪种操作占据主导地位，就使用相对应的容器。
如果不确定到底应该使用vector还是list，那么就只使用它们都支持的操作，不使用下标运算，使用迭代器，避免随机访问。

关联容器概述

关于关联容器更详细的内容可以查看C++ associative container。
标准库共有8个关联容器，他们在三个维度上有差异

set还是map
关键字是否可以重复，是否容器名字中包含multi
元素顺序无序还是有序，容器名字是否包含unordered

具体如下：

map，关联数组，保存关键字－值对
set，只保存关键字的容器
multimap，关键字可以重复出现的map
multiset，关键字可以重复出现的set
unordered_map，用哈希函数组织的map
unordered_set，用哈希函数组织的set
unordered_multimap，哈希组织的map，关键字可以重复出现
unordered_multiset，哈希组织的set，关键字可以重复出现

关联容器和顺序容器都支持一些公共操作，会在下一小节介绍。但是关联容器不支持顺序容器和位置相关的操作，如push_back，push_front等，因为关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。此外，关联容器也不支持接收一个元素值和一个数量值的插入操作和构造函数。
不过关联容器支持一些顺序容器不支持的操作。
关联容器的迭代器都是双向的。

定义关联容器

定义map需要指明关键字类型和值类型
定义set时只需要指明关键字类型

关键字类型的要求

`pair`类型

`map`的使用

`set`的使用

顺序容器和关联容器的公共操作

每一个容器都定义在一个头文件中，文件名和类型相同。
顺序容器几乎可以保存任意类型的元素，但是某些容器对于元素类型有特殊的要求，我们可以为不支持特定操作的类型定义容器，但是使用只用哪些没有特殊要求的容器操作了。
顺序容器构造函数的一个版本接受容器大小参数，它使用元素类型的默认构造函数，但是有些类没有默认构造函数，这时候我们可以定义这种类型的容器，但是需要传入一个元素的初始化器。例如：
1
2
vector<noDefault> v1(10, init); //正确，
vector<noDefault> v2(10); //错误，因为没有默认构造函数
对于不同类型的容器，它们有各自特有的操作，也有都支持的操作，这一节就简单介绍一下他们都支持的操作：

迭代器

所有容器都支持迭代器，迭代器也有公共接口。。所有的迭代器都允许访问容器中的元素，所有的迭代器都通过解引用来实现这个操作。

迭代器范围

一个迭代器范围由一对迭代器构成，两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置，通常一个被称为begin，一个被称为end。注意end不是指向最后一个元素而是指向最后一个元素后面的位置。
begin和end必须是同一个容器的迭代器，end不能在begin之前。如果begin和end相等，那么他们之间的范围是空；如果begin和end不等，那么范围至少包含一个元素，且begin指向该范围中的第一个元素。

关于迭代器的具体内容可以查看C++ string vector and iterator。

容器类型成员

每个容器都定义了多个类型，

iterator，容器的迭代器类型
const_iterator，无法修改元素的迭代器类型
reverse_iterator，反向迭代器
const_reverse_iterator，不能修改元素的反向迭代器
size_type，无符号整数，足够保存容器的最大大小。
difference_type，有符号整数，足够保存两个迭代器之间的距离
value_type，元素类型
reference，元素的左值类型
const_reference，元素的const左值类型。

获取迭代器

c.begin()和c.end()，返回指向c的首元素和尾后元素的迭代器
c.cbegin()和c.cend()，返回指向c的首元素和尾后元素的const_iterator
c.rbegin()和c.rend()，返回指向c的尾元素和首元素之前的反向迭代器
c.crbegin()和c.crend()，返回指向c的尾元素和首元素之前的const_reverse_iterator

当auto和begin，end结合使用时，获得的迭代器类型依赖于容器的类型。只有当容器本身是const时，才能够得到const_iterator。
而auto和cbegin和cend使用时，获得的迭代器类型和容器类型无关，一直都是const_iterator。

容器定义和初始化

C c;，默认构造
C c1(c2);或者C c1=c2;，拷贝构造，直接拷贝容器
C c(b, e);，拷贝构造，通过迭代器范围进行拷贝，将迭代器b和e指定范围的元素拷贝到c，不适用于array。这种方式不要求容器类型相同，只要能将要拷贝的对象转化为要初始化的容器的元素类型即可。
C c{a, b, c...};或者C c={a, b, c...}，列表初始化c，元素类型必须相同，同时显式的指定了容器的大小

只有顺序容器（除了array）的构造函数才能接收大小参数。

C seq(n);，进行值初始化，不适用于string
C seq(n, t);，seq是包含n个初始值为t的元素

总结一下：

将一个容器初始化为另一个容器的拷贝时，两个容器的容器类型和元素类型必须相同
使用迭代器拷贝构造容器时，不需要容器类型和元素类型相同，只需要待拷贝对象能够转换成要初始化的元素对象即可。
对于顺序容器（除了array）来说，它还有另一个构造函数，它的参数是容器大小和一个可选的元素初始值。如果不提供元素初始值，标准库会创建一个值初始化器，内置类型，如int，取0，string等类类型，由类进行默认初始化。即当如果元素是内置类型，或者具有默认构造函数的类类型，那么可以只提供一个容器大小参数。如果没有默认构造函数，就必须指定显式的元素初始值。
标准库array具有固定大小，定义array时，除了指定元素类型，还要指定元素个数。一个默认构造的array是非空的，这些元素都被默认初始化。如果进行列表初始化，初始值如果小于array大小，剩余的元素执行值初始化。对于类类型来说，不论是默认初始化还是值初始化，都需要类有一个默认构造函数。

赋值, `assign`和`swap`

c1 = c2，将c1的元素用c2的元素替换，c1和c2类型必须相同
c1 = {a, b, c, ...}，将c1中的元素替换为列表中元素，不适用于array
a.swap(b)，交换a和b的元素
swap(a,b)，和a.swap(b)相同。

还有不适用于关联容器和array的assign操作，

seq.assign(b, e);，将seq中元素替换为迭代器b和e中的元素，迭代器b和e不能指向seq中的元素
seq.addign(il);，将seq中的元素替换成初始化列表il中的元素
seq.assign(n, t);，将deq中的元素替换成n个值为t的元素

赋值号左右两边的运算对象必须具有相同的类型，而assign不需要两个容器的类型相同，只需要元素类型相容即可。array允许直接赋值array，但是不支持assign操作，也不允许用花括号包围的值列表进行赋值，因为右面运算对象的大小可能和左面运算对象的大小不同（见C++ primer第五版302页），而array的大小是不可变的。
赋值操作会让指向左边容器内部的迭代器，引用和指针失效。而swap交换容器内容不会使得指向容器的迭代器，指针和引用失效（容器类型为array和string除外）。
swap交换array时，两个array的大小必须相同，类型相同。swap交换两个array会真正交换两个array的元素。
swap交换除了string之外的容器时，指向容器的迭代器，引用和指针都不会失效，即访问的还是未交换之前的对象，但是这些对象所属的容器变了。

大小

size()，容器当前容纳的元素个数，不支持forward_list
max_size()，容器所能容纳的最大元素个数
empty()，容器是否为空

具体示例，编译器是gcc-7.4.0

int main()
{
    vector<int> vi;

    cout << vi.size() << endl;
    // 0
    cout << vi.max_size() << endl;
    // 4611686018427387903
    cout << vi.empty() << endl;
    // 1

    string s;
    
    cout << s.size() << endl;
    // 0
    cout << s.max_size() << endl;
    // 9223372036854775807
    cout << s.empty() << endl;
    // 1
    return 0;
}

关系运算符

==和!=，所有的容器都支持的运算符。
<=,<,>=, >，关系运算符（无序关联容器不支持），关系运算符两侧的容器类型必须一样，容器类的元素类型也必须一样。
容器的相等运算实际上是使用的元素的==运算实现的，而容器的关系运算实际上是使用元素的<运算实现的。对于类类型来说，必须对相应的操作符重载，才能进行相应的关系运算，否则就无法进行。
两个容器比较大小的规则：
两个容器大小相等，对应元素相等，这两个容器相等。
两个容器大小不同，但是较小元素中每个元素都等于较大容器中的对应元素，较小容器小于较大容器。
如果两个容器都不是另一个容器的前缀子序列，则他们的结果取决于第一个不相等的元素的比较结果。

增删元素（不适用于`array`）

注意，在不同的容器中，操作的接口都不同

c.insert(args)，将args中的元素拷贝进c
c.emplace(inits)，使用inits构造c中的一个元素
c.erase(args)，删除args指定的元素
c.clear()，删除c中所有元素，返回void

参考文献

1.《C++ Primer》第五版