容器的概述

容器

一种特殊的类型，其对象可以放置其它类型的对象（元素）。
需要支持的操作：对象的添加、删除、索引、遍历，并不是有的容器都支持扇面4种操作，有的不支持添加、删除，有的不支持索引。适合添加元素的容器，可能查找就比较慢，适合查找的元素，可能添加就比较慢。

容器分类

序列容器：
其中的对象有序排列，使用整数值进行索引。

关联容器：
其中的对象顺序并不重要，使用键进行索引。
map就是一种关联容器。不同的关联容器，对键的需求不一样。

适配器：
调整原有容器的行为，使得其对外展现出新的类型、接口或返回新的元素。
将原有的容器行为进行调整。

生成器：
构造元素序列。

迭代器

用于指定容器中的一段区间，以执行遍历、删除等操作。

获取迭代器： ©begin/©end ； ©rbegin/©rend

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    std::vector<int> x{1, 2, 3, 4, 5};
    auto b = x.begin();
    auto e = x.end();
    for (auto ptr = b; ptr < e; ++ptr)
    {
        cout << *ptr << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

如果使用了cbegin和cend，表示迭代器是只读的，不能写入。
rbegin和rend

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    std::vector<int> x{1, 2, 3, 4, 5};
    auto b = x.rbegin(); // 反向迭代器，b指向最后一个位置 
    auto e = x.rend(); // e指向第一个元素前面的一个位置
    for (auto ptr = b; ptr < e; ++ptr)
    {
        cout << *ptr << endl; // 5 4 3 2 1
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

并非所有的迭代器都能完成像数组指针这样的功能。某个迭代器可能不支持某种操作，比如a+3；迭代器是泛化和模拟指针的操作，但是不是所有迭代器都有完全指针的功能。

迭代器分类：分成 5 类（ category ），不同的类别支持的操作集合不同

Input Iterator 输入迭代器
Output Iterator 输出迭代器
Forward Iterator 前向迭代器：只能一点点往前走
Bidirectional Iterator 双向迭代器：既能往前走，又能往后走
Random Access Iterator 随机访问迭代器：不知加1，还能加2，减2等。

支持迭代器的称为range。

序列容器

array ：元素个数固定的序列容器，不支持对象的添加和删除。和数组和相似。
vector ：元素连续存储的序列容器，可以添加删除，元素个数可变。在内存中是连续存储的。
forward_list / list ：forward_list 基于链表 / list 双向链表的容器，

deque ： vector 与 list 的折衷，vector是连续村粗，list是通过链表指针。deque把整个容器分成若干个段，段与段是链表的模式。

basic_string ：提供了对字符串专门的支持，是一个模版。

需要使用元素类型来实例化容器模板，从而构造可以保存具体类型的容器。

int main()
{
    std::vector<int> x; // vector这个模版可以包含什么类型的元素
    std::vector<double> y;
}
1
2
3
4
5

不同的容器所提供的接口大致相同，但根据容器性质的差异，其内部实现与复杂度不同。只要掌握了一种容器，其他容器也可以照葫芦画瓢了。同样一个操作，对某些容器快，对某些可能比较慢。

对于复杂度过高的操作，提供相对较难使用的接口或者不提供相应的接口。

Array

具有固定长度的容器，其内部维护了一个内建数组，与内建数组相比提供了复制操作。内建数组是不支持复制的，但是Array是支持的。

成员类型

#include <iostream>
#include <vector>
#include <array>
using namespace std;

int main()
{
    int a[3]; // 
    // int b[3] = a; // 内建数组不支持复制
    // error: array initializer must be an initializer list
    std::array<int, 3> x; // 提供元素类型和包含元素的个数
    std::array<int, 3> y = x;
    std::array<int, 3>::value_type; // value_type是array中类型

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

成员访问：元素访问： [] ， at ， front ， back ， data

#include <iostream>
#include <vector>
#include <array>
using namespace std;

int main()
{
    std::array<int, 3> x = {2, 4, 6}; 
    cout << x[4] << endl; // []索引，越界不报错
    // cout << x.at(3) << endl; // 越界，报错
    cout << x.front() << endl; // 2
    cout << x.back() << endl; // 6
    x.data(); // 返回一个int*，指向数组的第一个元素
    cout <<  *(x.data()) << endl; // 2 如果元素是连续保存的，那么一般提供一个data接口

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

容量相关（平凡实现）： empty ， size ， max_size

int main()
{
    std::array<int, 3> x = {2, 4, 6}; 
    cout << x.empty() << endl; // 0 非空
    cout << x.size() << endl; // 3
    cout << x.max_size() << endl; // 3 最多包含的元素个数
}
1
2
3
4
5
6
7

填充与交换： fill ， swap

int main()
{
    std::array<int, 3> x;
    x.fill(100);
    cout << x[0] << ' ' << 
            x[1] << ' ' <<
            x[2] << ' ' << endl;
}
1
2
3
4
5
6
7
8

swap复制成本是非常高的

比较操作： <=> c++20，字典序比较


迭代器

Vector

vector 容器模板：元素个数可变

可以看到，vector如果用swap方法，只改变指针就可以。所以比array快。

size元素数量，cap目前vector容量是多少。
empty、size、max_size都不是平凡实现了。

容量相关接口： capacity / reserve / shrink_to_fit

int main()
{
    std::vector<int> a;
    cout << a.capacity() << endl; // 1
    a.reserve(1024); // 刚开始就开辟了1024个buffer
    for (int i = 0; i < 1024; ++i)
    {
        a.push_back(i);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12

当vector不会再填充元素，那么用shrink_to_fit，释放原有buffer，拷贝一个大小正好的内存过来。这样没有浪费更多的内存资源。

附加元素接口： push_back / emplace_back

int main()
{
    std::vector<int> a;
    for (int i = 0; i < 1024; ++i)
    {
        a.emplace_back(i);
    }
}
1
2
3
4
5
6
7
8

两者区别：

int main()
{
    std::vector<std::string> a;
    a.push_back("hello"); //先构造一个string，再将hello添加
    a.emplace_back("hello"); // 直接生成hello string
}
1
2
3
4
5
6

元素插入接口： insert / emplace
一般是在vector的中间插入，涉及到其他元素的后移，性能要比push_back和emplace_back低


元素删除接口： pop_back / erase / clear
pop_back删除最后一个元素，erase是指定一个位置元素进行删除，后面元素要往前挪动。clear删除所有元素。

vector 不提供 push_front / pop_front ，可以使用 insert / erase 模拟，但效率不高。

Vector的swap 效率较高

写操作可能会导致迭代器失效
迭代器失效的操作

list/forward_list

vecotr:

int main()
{
    std::vector<int> a{1, 2, 3};
    for (auto ptr = a.begin(); ptr < a.end(); ++ptr)
    {
        cout << *ptr << endl;
    }
}
1
2
3
4
5
6
7
8

list

#include <iostream>
#include <vector>
#include <list>
using namespace std;

int main()
{
    std::list<int> a{1, 2, 3};
    for (auto ptr = a.begin(); ptr != a.end(); ++ptr)
    {
        cout << *ptr << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

list 容器模板：双向链表
list的插入和删除成本低，随机访问成本高。vector相反，插入和删除成本低，但是随机访问成本低。索引就是ptr+索引数，因为是连续存储的，所以可以直接知道地址为多少。

一些操作：

pop_front, push_front开头删除和插入元素。
splice：可以把list，移到另外一个list

forward_list 容器模板：单向链表
目标：一个成本较低的线性表实现。

#include <iostream>
#include <vector>
#include <list>
#include <forward_list>
using namespace std;

int main()
{
    std::forward_list<int> a{1, 2, 3};
    for (auto ptr = a.begin(); ptr != a.end(); ++ptr)
    {
        cout << *ptr << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

forward_list只支持递增操作，只能往后走，获取它的后继，不能获取它的前驱。没有rbegin和rend来反向遍历。list就可以，因为list是双向链表。
list是支持size的，但是forward_list不支持size。因为list虽然是双向链表，但是内部有一块空间用来保存第几个元素。但是forward_list因为是一个成本比较低的数据结构，所以没有开辟这样的额外空间。

不支持 pop_back / push_back。

为什么都是after操作，因为单向链表只知道后面的地址，不知道之前的。

deque/basic_string

deque双端队列



push_back / push_front 速度较快
deque是支持中括号随机访问的。知道左边每个格子包含几个灰色的格子，就可以通过中括号去找到相应的位置。但是和vector的速度是没法比的，但比list多了中括号的计算。deque也可以在序列中间添加和删除元素，但是效率很慢，比list慢很多。

basic_string： 容器模板：实现了字符串相关的接口



提供了数值与字符串转换的接口



针对短字符串的优化Short String Optimization SSO